Оставшись устранение рекурсии в грамматике LL1

Question

Я пытаюсь устранить леворекурсивный из следующего отрывка грамматики -

expression := fragment ((+ | - | * | /) fragment)* 

fragment := identifier | number | (+ | -) fragment | expression 

Вопрос заключается в том, что выражение может перейти к фрагменту, можно перейти к выражению. Я пробовал кучу способов его устранения, некоторые выглядят так, как будто они работают (в JavaCC), но я a) не уверены в их правильности, и б) довольно уверен, что я нарушил ассоциативность, изменив структуру грамматики.

Я уверен, что мне нужно выражение», и имеют

fragment := identifier | number | (+ | -) fragment | expression 

изменен

fragment := identifier | number | (+ | -) fragment | expressionPrime 

Но я не уверен в пути формирования expressionPrime. Оба

expressionPrime := identifier | number | (+ | -) fragment | {} 

И

expressionPrime := ((+ | - | * | /) fragment)* 

Казаться работать, но я знаю, что это не может быть и другое.

Любые идеи будут высоко оценены, даже точка в правильном направлении.

Answer 1

Старт с

expression ::= fragment ((+ | - | * | /) fragment)* 
fragment ::= identifier | number | (+ | -) fragment | expression 

Определение

frag1 ::= identifier | number | (+ | -) fragment 

Обратите внимание, что фрагмент эквивалентно frag1 | expression. Заменить бывший последним везде, чтобы получить

expression ::= (frag1 | expression) ((+ | - | * | /) (frag1 | expression))* 
frag1 ::= identifier | number | (+ | -) (frag1 | expression) 

fragment больше не нужен.

Распределить получить

expression ::= frag1 more | expression more , 

где

more ::= ((+ | - | * | /) (frag1 | expression))* 

Теперь вы можете видеть, что выражение является frag1 следует один или более more

Так

expression ::= frag1 (more)+ 

Ваша грамматика по-прежнему неоднозначна - для «1 * - 2 * 3» есть 2 синтаксического анализа. Но, по крайней мере, он больше не остается рекурсивным.

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

Я все еще думаю, что ваш инструктор сделал ошибку, так как, если вы измените

fragment ::= identifier | number | (+ | -) fragment | expression 

в

fragment ::= identifier | number | (+ | -) fragment | "(" expression ")" , 

у вас есть разумная грамматика для выражений.