Ликвидация левой рекурсии

Question

Итак, у меня есть грамматика, которая не работает для анализатора сверху вниз из-за того, что он оставил рекурсию:

L::= A a | B b
A::= L b | a a
B::= b B b | b a

Поэтому, чтобы это исправить, я должен удалить левую рекурсию. Для этого я делаю небольшую замену:

L::= A a | B b
A::= A a b | B b b | a a (I plugged in the possible values of "L")

А затем поворачивается к (я считаю):

A::= a a A' | B b b
A'::= a b A' | ε

Я совершенно уверен, что я прав там (не удивлюсь, если я не так). Сейчас я борюсь за то, чтобы убрать левую рекурсию из "B b b". Я пытался обойти это так много способов, и я не думаю, что какой-либо из них работает. Вот тот, который кажется наиболее логичным, но также и некрасивым (таким образом, говоря, что это, вероятно, неправильно). Начиная с манипулирования B::= b B b | ба

B::= b B b | b a
B::= b B' (they both start with b, so maybe i can pull it out?)
B'::= B b | a
B'::= b B' b | a (substituted B's value in)
B'::= b B" | a
B"::= b B" |a B" | ε

Итак, я думаю, чтобы показать, какими будут окончательные B:

B::= b B'
B'::= b B" | a
B"::= b B" | a B" | ε

Это кажется слишком уродливым, чтобы быть правильным. Тем более, что мне пришлось бы подключить это к новым "А" терминалам, которые я создал.

Кто-нибудь может мне помочь? Не знаю, правильно ли я поступлю. Я должен быть в состоянии создать таблицу анализа LL(1) впоследствии (должен быть в состоянии выполнить эту часть самостоятельно).

Благодарю.

Answer 1

В синтаксическом анализаторе, который пытается расширить нетерминалы слева, если какой-то нетерминал может развернуться до строки с самим собой слева, синтаксический анализатор может расширить этот нетерминал навсегда, фактически ничего не анализируя. Это левая рекурсия. С другой стороны, совершенно нормально, если нетерминал расширяется до строки с каким-то другим нетерминалом слева, если цепочка расширений не создает строку с исходным нетерминалом слева. Точно так же хорошо, если нетерминалы расположены не полностью направо в расширении, если они не полностью налево.

tl; dr Нет ничего плохого B b b или же b B b, Вы удалили всю оставленную рекурсию. Вам не нужно продолжать идти.