Как разобрать эту простую грамматику?Это двусмысленно? - PullRequest
Новая
       104

Как разобрать эту простую грамматику?Это двусмысленно?

0 голосов
/ 13 декабря 2018

Я углубляюсь в анализ и столкнулся с проблемой, которую я не совсем понимаю.Я составил следующую грамматику: 

S = R | aSc
R = b | RbR

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

S => aSc
aSc => aRc

, в этот момент я бы подумал, что рекурсивное спуск выберет первый вариантво втором производстве, потому что следующий токен b ведет к: 

 aRc => abc

, и мы закончили, поскольку нет больше нетерминалов, что, конечно, не abbbc.Единственный способ показать, что abbbc действителен, - это выбрать второй вариант, но, с одной стороны, я предполагаю, что он всегда выберет b.Я не думаю, что грамматика неоднозначна, если я что-то пропустил.Так что я делаю не так?

Обновление: Я наткнулся на это замечательное приложение для деривации на https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/. Я использовал для проверки работоспособности, что abbbc является допустимым предложением, и оноявляется.

Размышляя больше об этой проблеме, правда ли сказать, что я не могу использовать LL (1) для разбора этой грамматики, но на самом деле нужен LL (2)?С двумя взглядами я мог правильно выбрать второй вариант во втором производстве, потому что теперь я также знаю, что есть больше токенов, которые нужно прочитать, и поэтому выбор b преждевременно прервет деривацию.

1 Ответ

0 голосов
/ 13 декабря 2018

Для начала, я рад, что вы нашли наш инструмент CFG полезным!Несколько моих TA сделали это некоторое время назад, и мы получили много пробега.

Ваша грамматика действительно неоднозначна.Это связано с вашим нетерминалом R:

R → b |RbR

Вообще говоря, если у вас есть рекурсивные производственные правила с двумя копиями одного и того же нетерминала, это приведет к неоднозначности, так как будет несколько вариантов того, как применять правило дважды.Например, в этом случае вы можете получить bbbbb, сначала расширив R до RbR, затем либо

  1. , расширив левый R до RbR и преобразовав каждый R в ab, либо
  2. , расширивправо R на RbR и преобразование каждого R в b.

Поскольку эта грамматика неоднозначна, она не будет LL (k) для любого выбора k, потому что все LL (k)грамматика должна быть однозначной.Это означает, что увеличение мощности вашего парсера здесь не поможет.Вам нужно будет переписать грамматику, чтобы она не была неоднозначной.

Нетерминал R, который вы описали здесь, генерирует строки с нечетным числом b в них, поэтому мы могли бы попробовать перепроектировать R, чтобы достичь этого более непосредственно.Первоначальная попытка может выглядеть примерно так:

R → b |bbR

Это, к сожалению, не LL (1), поскольку после просмотра одного b неясно, должны ли вы применять первое правило производства или второе.Однако это LL (2).

Если вам нужна грамматика LL (1), вы можете сделать что-то вроде этого:

R → bX

X → bbX |ε

Это работает, кладя один b, а затем кладя столько необязательных пар b, сколько вы хотите.

...