LR Parser уменьшить / уменьшить (YACC и т. Д.) - PullRequest
0 голосов
/ 21 марта 2012

Предполагается, что у меня есть следующая контекстно-свободная грамматика в указанном порядке (для YACC):

  • z → x
  • z → z x

Если у меня есть ввод:

(z (z x

)

Будет ли синтаксический анализатор уменьшен:

  1. от 'x' до 'z'
  2. от 'z x' до 'z'

Я думаю, что это № 2, но я не совсем уверен, почему. Большое спасибо

редактировать: изменен ввод для уточнения

1 Ответ

1 голос
/ 21 марта 2012

Ваша грамматика левоассоциативна, потому что она леворекурсивна. Левый ассоциативный означает, что производство будет выполняться жадно, так как вход сканируется слева направо. У вас всегда есть z, который увеличивается до более длинного z путем сканирования другого x и уменьшения.

Что касается вашего вопроса, у вас не может быть ввода z z x, потому что ввод состоит из символов терминала. Предположительно x является терминальным символом (в противном случае грамматика является неполной). z явно нетерминальный.

Вы можете подумать о частичной форме предложения z z x. Однако такая форма не может быть сгенерирована этой грамматикой.

Начиная с z, ваши следующие шаги - сгенерировать x (и, следовательно, завершить) или сгенерировать z x. Следующие возможные шаги после этого - заменить z одним из двух способов: сгенерировать x x (и закончить) или сгенерировать z x x.

Как видите, строка z z x недоступна по этим правилам.

...