Учитывая грамматику неоднозначно или нет?

Рассмотрим грамматику ниже...

bexp -> bterm | bterm ‘||’ bexp
bterm -> bfact | bfact ‘&&’ bterm
bfact -> true | false | id | ‘(‘ bexp ‘)’

Предположим, мы расширяем BEXP с помощью '!' оператор для отрицания, изменив правило bfact следующим образом:

bfact -> true | false | id | '(' bexp ')' | '!' bexp

Назовем эту расширенную грамматику BEXP2. Как я могу доказать, что это неоднозначно?


grammar programming-languages context-free-grammar language-theory
person sparta93    schedule 12.02.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вы можете доказать, что это неоднозначно, найдя строку с двумя разборами :)

В этом случае попробуйте !id&&id. Это (!id)&&id или !(id&&id)

person rici    schedule 12.02.2015
comment
Я все еще не уверен, как я могу получить 2 разбора из !id&&id. - person sparta93; 13.02.2015
comment
@ sparta93: Просто сделайте самые правильные выводы. (Или самый левый, если хотите.) Помните, что при самом правом выводе вы всегда получаете самый правый нетерминал на каждом шаге. Если это домашнее задание (или даже если нет), вы лучше научитесь, выполняя его. Но в любом случае: bexp->bterm->bfact&&bterm->bfact&&bfact->bfact&&id->!bexp&&id->!bterm&&i->!bfact&&id->!id&&id. bexp->bterm->bfact->!bexp->!bterm->!bfact->!bfact&&bterm->!bfact&&bfact->!bfact&&id->!id&&id. Теперь вы должны нарисовать соответствующие деревья синтаксического анализа. - person rici; 13.02.2015