Удаление левой рекурсии в грамматике при сохранении левой ассоциации оператора

У меня проблема с этим упражнением:

Пусть G будет следующей неоднозначной грамматикой для λ-исчисления:

E → v | λv.E | EE | (E)

где E - единственный нетерминальный символ, λv.E представляет абстракцию относительно переменной v в E, а EE представляет приложение.

1. Определите LL (1) грамматику G ′ так, что L (G ′) = L (G) и неоднозначность G разрешается путем наложения следующих обычных соглашений:
   1. абстракция правильная ассоциативная;
   2. приложение остается ассоциативным;
   3. Приложение имеет более высокий приоритет, чем абстракция.
2. Покажите таблицу разбора LL (1) для G ′ и дерево разбора, полученное при разборе строки λv1. λv2. v1v2v1.

Я устранил двусмысленность, установив приоритет и связь, получив следующую грамматику:

E -> EF | F
F -> λv.G | G
G -> (E) | v

который не является LL (1), так как производство E -> EFостается рекурсивным. Однако, устраняя левую рекурсию из этого производства, я получаю:

E -> FE¹
E¹-> FE¹ | ɛ
F -> λv.G | G
G -> (E) | v

это не соответствует требованию 1.2.

Я искал решение в Интернете, но кажется, что невозможно устранить левую рекурсию, сохраняя левую ассоциативность.

Однако это упражнение появилось на экзамене компиляторов несколько лет назад, поэтому должен быть правильный ответ.

Спасибо за помощь.

Совместимость левой ассоциативности и парсинга LL (1)

Вы просто столкнулись с одним из основных несоответствий в использовании контекстно-свободного (CF) синтаксиса. Люди хотят выбирать грамматики так, чтобы дерево разбора отражало предполагаемую структуру предложения, близкую к его семантике, особенно в случае неассоциативных операторов, таких как приложение . Это было в значительной степени оригинальным намерением грамматик CF в лингвистике. Но в то же время они ограничиваются технологией синтаксического анализа, которая допускает только некоторые типы грамматик.

Действительно, если дерево разбора должно отражать левую ассоциативность оператора, то грамматика обязательно будет рекурсивной влево, поскольку верхний узел приложения в дереве разбора обязательно добавляет самый правый член непаретизированных последовательных приложений. Таким образом, разбор LL исключен. Вы правы.

Есть два выхода из этого. Нельзя полагаться на синтаксический анализатор, который дает правильное «дерево синтаксического анализа», которое будет использоваться на более поздних этапах обработки (например, сокращение лямбда-выражения здесь). Это приводит к концепции абстрактных синтаксических деревьев (AST), которые могут быть построены из дерева разбора, но с другой структурой.

Другое решение состоит в том, чтобы использовать более общие методы синтаксического анализа, которые будут принимать любую грамматику CF, и анализировать в соответствии с ней. Парсеры General CF - это хорошо разработанная технология (и я не перестаю удивляться, почему LL остается таким популярным).

Я понятия не имею, что можно считать правильным ответом на эти противоречивые требования.

То, что я хотел бы сделать, это показать, что они противоречат требованиям. Задайте первую грамматику, которая соответствует ограничениям ассоциативности и приоритетов, затем преобразуйте грамматику в грамматику LL (1) для анализа.

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

Об этом конкретном примере

При этом первая предложенная вами грамматика не совсем верна. У него нет способа получения λu.λv.v.

Один прием, который нужно знать, - начать с операторов (здесь абстракция или приложение) с самым низким приоритетом (абстракция). То же самое для арифметических выражений.

Моя попытка:

E  -> A | λv.E
A  -> FA'
A' -> A | ɛ
F  -> (E) | v

Эта грамматика LL (1) и должна соответствовать требуемым свойствам.