Как yacc генерирует синтаксический парсер из правил грамматики? - PullRequest
Новая
       3

Как yacc генерирует синтаксический парсер из правил грамматики?

0 голосов
/ 21 января 2011

Я понял, как работает лексический анализ,

но не знаю, как проводится синтаксический анализ,

хотя в принципе они двое должны быть похожи (единственное отличие заключается в тип их входных символов, символов или токенов.),

но сгенерированный код парсера сильно отличается.

Особенно yy_action,yy_lookahead, в лексическом анализе такого нет ...

1 Ответ

1 голос
/ 05 ноября 2011

Грамматики, используемые для генерации лексических анализаторов, обычно представляют собой обычные грамматики , в то время как грамматики, используемые для генерирования синтетических анализаторов, обычно представляют собой контекстно-свободные грамматики . Хотя они могут выглядеть одинаково на поверхности, они имеют очень разные характеристики и возможности. Регулярные грамматики могут быть распознаны с помощью детерминированных конечных автоматов , которые относительно просты в создании и создании быстро. Для контекстно-зависимых грамматик сложнее создать распознаватель, и обычно инструмент генератора синтаксических анализаторов создает синтаксический анализатор только для подмножества контекстно-свободных грамматик. Например, yacc создает синтаксические анализаторы для неконтекстных грамматик, которые также являются грамматиками LALR (1), используя push-down автоматы .

Для получения дополнительной информации о синтаксическом анализе я настоятельно рекомендую Методы синтаксического анализа , в которых рассматриваются все нюансы синтаксического анализа в мучительных (но хорошо описанных!) Деталях.

...