Как создать / написать простой парсер XML с нуля?

Question

Как создать / написать простой парсер XML с нуля?

Вместо примеров кода я хочу знать, каковы упрощенные, основные шаги на английском языке.

Как спроектирован хороший парсер? Я понимаю, что регулярное выражение не следует использовать в синтаксическом анализаторе, но какова роль регулярного выражения в анализе XML?

Какую структуру данных рекомендуется использовать? Должен ли я использовать связанные списки для хранения и извлечения узлов, атрибутов и значений?

Я хочу узнать, как создать синтаксический анализатор XML, чтобы я мог написать его на языке программирования D.

Answer 1

Если вы не знаете, как написать синтаксический анализатор, вам нужно немного почитать. Возьмите любую книгу по написанию компиляторов (многие из лучших были написаны 30 или 40 лет назад, например Aho и Ullmann) и изучите главы по лексическому анализу и синтаксическому анализу. XML по сути ничем не отличается, за исключением того, что лексическая и грамматическая фазы не так четко изолированы друг от друга, как в некоторых языках.

Одно предупреждение: если вы хотите написать полностью совместимый синтаксический анализатор XML, то 90% ваших усилий будут потрачены на то, чтобы получить правильные крайние варианты в неясных углах спецификации, связанных с такими вещами, как объекты параметров, к которым относится большинство пользователей XML. даже не в курсе.

Answer 2

Существует разница между синтаксическим анализатором и нодлистом.Синтаксический анализатор - это фрагмент, который берет кучу простого текстового XML и пытается определить, какие узлы там находятся.Затем есть внутренняя структура, в которой вы сохраняете узлы. В слое над этой структурой вы найдете DOM, объектную модель документа.Это структура вложенных узлов, которые составляют ваш XML-документ.Синтаксическому анализатору нужно только знать универсальный интерфейс DOM для создания узлов.

Я бы не использовал regex в качестве анализатора для этого.Я думаю, что лучше всего просто обойти строковый символ за символом и проверить, совпадает ли полученное с тем, что вы должны получить.

Но почему бы не использовать какой-либо из существующих анализаторов XML?Есть много возможностей в кодировании данных.Много исключений.И если ваши парсеры не управляют ими, вряд ли стоит заголовок XML-парсера.

Answer 3

для парсера на основе событий пользователь должен передать ему некоторые функции (startNode(name,attrs), endNode(name) и someText(txt), вероятно, через интерфейс) и вызывать их при необходимости при передаче файла

синтаксический анализатор будет иметь цикл while, который будет чередоваться между чтением до < и до > и выполнять соответствующие преобразования для типов параметров

void parse(EventParser p, File file){
    string str;
    while((str = file.readln('<')).length !=0){
        //not using a rewritable buffer to take advantage of slicing 
        //but it's a quick conversion to a implementation with a rewritable buffer though
        if(str.length>1)p.someText(str.chomp('<'));


        str = file.readln('>');
        str = str.chomp('>');

        //split str in name and attrs
        auto parts = str.split();
        string name = parts[0];
        string[string] attrs;
        foreach(attribute;parts[1..$]){
            auto splitAtrr = attribute.split("=");
            attrs[splitAtrr[0]] = splitAtrr[1];
        }

        if(str[0] == '/')p.endNode(name);
        else {
            p.startNode(name,attrs);
            if(str[str.length-1]=='/')p.endNode(name);//self closing tag
        }
    }
}

---

вы можете построить DOM-парсер поверх анализатора на основе событий, и для каждого узла вам понадобятся основные функции getChildren и getParent getName и getAttributes (с установщиками при сборке;))

объект для парсера dom с описанными выше методами:

class DOMEventParser : EventParser{
    DOMNode current = new RootNode();
    overrides void startNode(string name,string[string] attrs){
        DOMNode tmp = new ElementNode(current,name,attrs);
        current.appendChild(tmp);
        current = tmp;
    }
    overrides void endNode(string name){
        asser(name == current.name);
        current = current.parent;
    }
    overrides void someText(string txt){
        current.appendChild(new TextNode(txt));
    }
}

когда синтаксический анализ заканчивается, корневой узел будет иметь корень дерева DOM

note : я не добавил туда проверочный код, чтобы убедиться в правильности xml

edit : в синтаксическом анализе атрибутов есть ошибка, вместо разделения на пробел лучше использовать регулярное выражение

Answer 4

Парсер должен соответствовать потребностям вашего языка ввода. В вашем случае простой XML. Первое, что нужно знать о XML, это то, что он не зависит от контекста и абсолютно не двусмысленен, все обернуто между двумя токенами, и это то, что делает XML известным: его легко анализировать. Наконец, XML всегда просто представлен древовидной структурой. Как уже говорилось, вы можете просто проанализировать ваш XML и выполнить код в это время, или проанализировать XML, генерируя дерево, а затем выполнить код в соответствии с этим деревом.

D предоставляет очень интересный способ очень легко написать анализатор XML, например:

doc.onStartTag["pointlight"] = (ElementParser xml)
{
  debug writefln("Parsing pointlight element");

  auto l = new DistantLight(to!int(xml.tag.attr["x"]),
                            to!int(xml.tag.attr["y"]),
                            to!int(xml.tag.attr["z"]),
                            to!ubyte(xml.tag.attr["red"]),
                            to!ubyte(xml.tag.attr["green"]),
                            to!ubyte(xml.tag.attr["blue"]));
  lights ~= l;

  xml.parse();
};

Answer 5

Первым элементом в документе должен быть пролог.Здесь указывается версия xml, кодировка, является ли файл автономным, и, возможно, некоторые другие вещи.Пролог открывается с <?.

После пролога есть метки с метаданными.Специальные теги, такие как комментарии, типы документов и определения элементов, должны начинаться с <!.Обработка инструкций начинается с <?.Здесь можно иметь вложенные теги, так как тег <!DOCTYPE может содержать теги <!ELEMENT и <!ATTLIST в XML-документе в стиле dtd - подробный пример см. Википедия .

Должен быть ровно один элемент верхнего уровня.Это единственный без <! или <? предшествующий ему.После элемента верхнего уровня может быть больше тегов метаданных;сначала обработайте их.

Для явного анализа: сначала идентифицируйте теги - все они начинаются с < - затем определите, какой это тег и как выглядит его закрытие.<!-- является тегом комментария, и не может иметь -- где-либо, кроме его конца.<? оканчивается на ?>.<! заканчивается >.Повторим: <!DOCTYPE может иметь теги, вложенные до его закрытия, и могут быть другие вложенные теги, о которых я не знаю.

Как только вы найдете тег, вы захотите найти его закрывающий тег.Проверьте, является ли тег самозакрывающимся первым;в противном случае найдите его замыкание.

Для структур данных: я бы порекомендовал древовидную структуру, где каждый элемент является узлом, а каждый узел имеет индексированный / отображенный список подэлементов.

Очевидно,полный парсер потребует гораздо больше исследований;Надеюсь, этого достаточно, чтобы вы начали.

Answer 6

Поскольку D довольно тесно связан с Java, возможно, генерирует синтаксический анализатор XML с ANTLR (поскольку, скорее всего, уже существуют грамматики XML EBNF для ANTLR, вы можете использовать их) , а затем преобразование сгенерированного кода Java-анализатора в D, может быть вариант? По крайней мере, это даст вам отправную точку, и вы сможете приложить некоторые усилия, пытаясь оптимизировать код специально для D ...

По крайней мере, ANTLR вовсе не так сложен, как многие думают. Я начал, ничего не зная об этом, просмотрев 3-4 из этого замечательного набора скринкастов на ANTLR .

Кстати, я нашел ANTLRWorks , с которым очень легко работать (в отличие от плагина Eclipse, используемого в скринкасте ... но содержание скринкаста применимо в любом случае).

Просто мой 0,02с.