Парсер против лексера и XML - PullRequest
Новая
       46

Парсер против лексера и XML

9 голосов
/ 02 сентября 2010

Я сейчас читаю об архитектуре компиляторов и синтаксических анализаторов, и мне интересно одно: если у вас есть XML, XHTML, HTML или любой другой язык на основе SGML, какова будет роль лексер здесь и что бы были токены?

Я читал, что токены похожи на слова , подготовленные для синтаксического анализа лексером .Хотя у меня нет проблем с поиском токенов для языков C, C ++, Pascal и т. Д., Где есть ключевые слова, имена, литералы и другие словоподобные строки, разделенные пробелами, с XML у меня есть проблема, потому что нет 'т любые слова!Это только обычный текст, чередующийся с разметкой (тегами).

Я подумал, что эти теги и фрагменты простого текста могут быть токенами, что-то вроде этого: [TXT][TAG][TAG][TXT][TAG][TXT][TAG][TAG][TXT]....Это было бы вполне разумно, поскольку SGML не волнует, что находится внутри разделителей разметки < и > (ну, он распознает специальные инструкции и определения обработки, когда находит ? или ! в качестве следующего символа; комментариипринадлежат также к этой группе), и токенайзер SGML может стать основой для синтаксического анализатора XML / HTML / XHTML.

Но затем я понял, что в разметке могут быть вставлены < символов как частьдругой синтаксис: значения атрибутов: - / Даже если не очень хорошая идея помещать < символы внутри значений атрибутов (для этого лучше использовать &lt;), многие браузеры и редакторы имеют дело с этим и рассматривают эти < какчасть значения атрибута, а не разделитель тегов.

Это немного усложняет ситуацию, потому что я не вижу способа распознать такую ​​разметку с помощью простого детерминированного конечного автомата (DFA) в лексере.Похоже, что он требует отдельного контекста для автомата, когда он находится внутри тега, и другого контекста, когда он встречает значение атрибута.Я думаю, что для этого потребуется стек состояний / контекстов, поэтому DFA может с этим не справиться.Я прав?

Что ты думаешь?Хорошо ли делать токены из тегов (разметки) и простого текста?

Здесь: http://www.antlr.org/wiki/display/ANTLR3/Parsing+XML
используется какая-то другая техника: они обрабатывают < и > (а также * 1034).* и />) как отдельные токены, а внутри тегов они используют GENERIC_ID в качестве токена и т. д. Они обычно переносят большую часть работы на анализатор.Но они также должны изменить контексты для токенизатора: они используют другой контекст в простом тексте и различаются в разметке (но я думаю, что они забыли о контексте значений атрибутов, потому что первое появление > завершит тег в своем лексере).

Итак, каков наилучший подход для анализа SGML-подобных языков?Лексер действительно используется там?Если да, какие строки составляют токены?

1 Ответ

12 голосов
/ 02 сентября 2010

Создав парсеры XML и HTML, у меня есть мнения.

Лексемы вообще должны быть узнаваемыми элементами языка.

Для XML и HTML они в основном соответствуют

  • TAGBEGIN, вещи в форме
  • TAGCLOSE, в форме
  • TAGENDANDCLOSE в форме /> (только XML)
  • ATTRIBUTENAME, в виде NAME
  • EQUALSIGN, точно равный =
  • ATTRIBUTEVALUE, являющийся значением точной символьной строки, представленнойатрибут, независимо от кавычек (или даже отсутствия кавычек, для унаследованного HTML).Если в атрибуте есть экранированные коды символов, этот код следует преобразовать в их действительный код символа.
  • CONTENT, который представляет собой текст между тегами TAGEND и TAGBEGIN.Как и ATTRIBUTEVALUES, любые экранированные символы должны быть преобразованы, поэтому CONTENT между foo преобразуется в текст foo(если у меня есть это право), это просто смешная цитата, которая исчезает при создании лексемы CONTENT.Чтобы справиться со всем этим, вам понадобится довольно сложный лексерный движок.И да, на практике вам нужны разные лексические состояния («режимы») для обработки разных частей текста.У меня в значительной степени есть один основной режим для обработки вещей внутри <</em> ... > и один основной режим для обработки CONTENT.
...