Косвенная рекурсия в LL(1)-разборе

Напомни, что такое LL(1) грамматика? И что такое косвенная рекурсия? (<P>::=x|y|(<E>) это место, что ли?) Овежишь память у лоровцев - может вместе что-нибудь придумаем.

Ну и стандатный вопрос. Книгу дракона прочитал?

Тебе надо избавиться только от левой рекурсии. У тебя она в левую сторону наращивается, сделай так, чтобы в правую.

Сказал бы сначала, что за грамматика, было бы проще сделать её изначально нормальной.

Ага, и чтобы ещё правое ветвление не появилось при этом.

Вообще, это очень похоже на грамматику арифметических выражений. Для неё есть канонiчная беспроблемная грамматика:

E->T|E+T
E->F|T*F
F->n|(E)

Без левой рекурсии она выглядит так:

E->TE'
E'->+TE'|ε
T->FT'
T'->*FT'|ε
F->n|(E)

У тебя там, вижу, вместо n какие-то x и y, но это неважно.

Косвенная рекурсия - в первых трёх правилах.

А где у меня там левая рекурсия? Не видать.

Почти она и есть, но надо именно привести к LL(1) и объяснить, как привёл.

Есть готовый ответ (пардон, что сразу не выложил):

Преобразование 1:
1) <G>::=<E>
2) <E>::=<E>+<T>
3) <E>::=<T>
4) <T>::=<T>*<P>
5) <T>::=<P>
6) <P>::=(<E>)
7) <P>::=x
8) <P>::=y
<G> - аксиома

Преобразование 2:
1) <G>::=<E>
2) <E>::=<T><D>
3) <D>::=+<T><D>
4) <D>::=λ
5) <T>::=<P><V>
6) <V>::=*<P><V>
7) <V>::=λ
8) <P>::=(<E>)
9) <P>::=x
10) <P>::=y
<G> - аксиома

Связи с автором этого решения, увы, нет, так что спросить его я не могу. Как и не могу быть уверен, что решение правильное.

<E>::=<A><T>
<A>::=<E>+|<B>

E → A → E → A → ...

Ну именно это я и назвал косвенной рекурсией. Левая, это же когда:
<A>::=<A>a
(просто пример)
Или я неправ?

Это явная левая рекурсия, бывает ещё неявная, которая у тебя в задании.

Это косвенная левая рекурсия.

Верный алгоритм устранения произвольной левой рекурсии такой:

устранить ε-правила
устранить явную левую рекурсию

Собственно, насколько я понимаю, приведённое решение именно так и делает. Как устранять ε-правила и явную левую рекурсию, гуглится.

Спасибо большое, хоть теперь примерно знаю куда копать. А как в гугле называть ε-правила?

http://www.csd.uwo.ca/~moreno//CS447/Lectures/Syntax.html/node8.html

Эпсилон-правила? eps-правила?

Всё же непонятно, что это за зверь. Гугл говорит, что это правила вида:
S::=eps, но что есть eps? Один товарищ предположил, что это пустая строка. У меня она обозначена как λ. Он неправ?

Он прав. Это стандартное обозначение пустой строки. Не знаю, с какого перепугу у тебя вместо него λ.

Препод - наркоман, сир!
А вообще, большое спасибо.

Все несколько сложнее

http://neerc.ifmo.ru/wiki/index.php?title=Устранение_левой_рекурсии

А, да, затупил что-то.