может ли контекстно-свободная грамматика быть лево- и праворекурсивной?

ex.

S-> S + T | T

T-> U - T | U

U -> ID | N

ассоциативность явно не сохраняется. Но я в любом случае не вижу, чтобы это было двусмысленно. Так это недвусмысленный cfg?


person DJPlayer    schedule 03.02.2011    source источник
comment
Учитывая, что два из этих правил никогда не прекращаются...   -  person Anon.    schedule 03.02.2011


Ответы (1)


Грамматика может иметь как левую, так и правую рекурсию, как вы показываете, но это мало что значит. Любую грамматику можно переписать так, чтобы все рекурсии были либо левыми, либо правыми (но не всегда одинаковыми, если только грамматика не является регулярной):

A -> B A C

становится:

A -> B X
X -> A C

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

person Jeremiah Willcock    schedule 07.03.2011