Рекурсивный спуск против Lex / Parse? - PullRequest
Новая
       41

Рекурсивный спуск против Lex / Parse?

2 голосов
/ 27 февраля 2012

Мне кажется, я понимаю (примерно), как работают парсеры рекурсивного спуска (например, Scala's Parbin Combinators): Вы анализируете входную строку одним парсером, и этот парсер вызывает другие, меньшие парсеры для каждой "части" всего ввода, ии так далее, пока вы не достигнете синтаксических анализаторов низкого уровня, которые непосредственно генерируют AST из фрагментов входной строки

. Я также думаю, что понимаю, как работает Lexing / Parsing: сначала вы запускаете лексер, чтобы разбить весь ввод наплоский список токенов, и затем вы запускаете парсер, чтобы взять список токенов и сгенерировать AST.

Однако я не понимаю, как стратегия Lex / Parse работает со случаями, когда именно от того, как вы токенизируете что-то, зависитна токены, которые были токенизированы ранее.Например, если я возьму кусок XML: 

"<tag attr='moo' omg='wtf'>attr='moo' omg='wtf'</tag>"

Парсер рекурсивного спуска может взять это и разбить его (каждый последующий отступ представляет декомпозицию родительской строки) 

"<tag attr='moo' omg='wtf'>attr='moo' omg='wtf'</tag>" 
  -> "<tag attr='moo' omg='wtf'>"
       -> "<tag"
       -> "attr='moo'"
            -> "attr"
            -> "="
            -> "moo"
       -> "omg='wtf'"
            -> "omg"
            -> "="
            -> "wtf" 
       -> ">"
  -> "attr='moo' omg='wtf'"
  -> "</tag>"

И небольшие парсеры, которые по отдельности разбирают <tag, attr="moo" и т. Д., Будут затем создавать представление XML-тега и добавлять к нему атрибуты.

Однако, как работает одношаговый Lex /Разбирать работу?Откуда Lexer знает, что строка после <tag и до > должна быть разбита на отдельные атрибуты, в то время как строка между > и </tag> не должна быть?Не нужно ли парсеру сказать, что первая строка находится внутри тела тега, а вторая - вне тела тега?

РЕДАКТИРОВАТЬ: Изменен пример, чтобы сделать его более понятным

Ответы [ 2 ]

3 голосов
/ 27 февраля 2012

Обычно лексер имеет настройку «режим» или «состояние», которая изменяется в зависимости от входа.Например, при просмотре символа < режим изменится на режим «тега», и лексер будет соответствующим образом токенизироваться, пока не увидит >.Затем он войдет в режим «содержимого», и лексер вернет все значения attr='moo' omg='wtf' в виде одной строки.Например, лексеры языка программирования обрабатывают строковые литералы следующим образом: 

string s1 = "y = x+5";

y = x+5 никогда не будет обрабатываться как математическое выражение, а затем превращаться обратно в строку.Он распознается как строковый литерал, потому что " меняет режим лексера.

Для языков, таких как XML и HTML, вероятно, проще создать собственный анализатор, чем использовать один из генераторов синтаксического анализатора, таких как yacc, bisonили ANTLR.Они имеют структуру, отличную от языков программирования, которые лучше подходят для автоматических инструментов.

Если вашему синтаксическому анализатору необходимо преобразовать список токенов обратно в строку, из которой он получен, это признак того, что что-то не такв дизайне.Вам нужно разобрать это по-другому.

2 голосов
/ 27 февраля 2012

Откуда Lexer знает, что строка после должна быть разбитым на отдельные атрибуты, а строка между> и не нужно быть?

Это не так.

Не нужно ли парсеру сказать, что первая строка находится внутри тело тега, а второй случай находится вне тела тега?

Да.

Обычно лексер превращает входной поток в последовательность токенов . Токен не имеет контекста, то есть токен имеет одинаковое значение независимо от того, где он находится во входном потоке. Как только процесс лексизма завершен, каждый токен рассматривается как единое целое.

Для XML сгенерированный лексер обычно идентифицирует целые числа, идентификаторы, строковый литерал и т. Д., А также управляющие символы, такие как «<» и «>», но не целый тег. Понимание того, что такое открытый тег, закрытый тег, атрибут, элемент и т. Д., Оставлено на усмотрение синтаксического анализатора.

...