LL (1) не может быть двусмысленным

Как можно показать, что никакая грамматика LL (1) не может быть двусмысленной?

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

Ответы

Ответ 1

Я думаю, что это почти прямой результат определения LL (1). Попробуйте доказать противоречие; предположим, что у вас есть грамматика LL (1), которая неоднозначна и ищет то, что вы можете показать как истинное, а не истинное. В качестве отправной точки "что вы всегда знаете при обработке ввода?"

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

Ответ 2

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

(Боковое замечание: жаль, что SO не поддерживает математику, например, в LaTeX.)

Proof

Пусть T и N - множества терминальных и нетерминальных символов.

Пусть выполнено

MaybeEmpty(s) = true <=> s ->* empty
First(s) = X containing all x for which there exists Y such that s ->* xY
Follow(A) = X containing all x for which there exists Y,Z such that S ->* YAxZ

Заметим, что грамматика LL (1), если для каждой пары произведений A → B и A → C:

1. (not MaybeEmpty(B)) or (not MaybeEmpty(C))
2. (First(B) intersect First(C)) = empty
3. MaybeEmpty(C) => (First(B) intersect Follow(A)) = empty

Рассмотрим язык с LL (1), с A -> B и A -> C. То есть есть некоторая строка терминалов TZ, которая допускает множественные деривации различными деревьями синтаксического анализа.

Предположим, что левый вывод достигает S ->* TAY ->* TZ. Следующим шагом может быть либо TAY -> TBY, либо TAY -> TCY. Таким образом, язык неоднозначен, если оба BY ->* Z и CY ->* Z. (Заметим, что поскольку A является произвольным нетерминальным, если такой случай не существует, язык не является двусмысленным.)

Случай 1: Z = пустой

По правилу 1 грамматик LL (1) не более одного из B и C может выводить пустой (не двусмысленный случай).

Случай 2: Z непусто, и ни B, ни C не выводят пустой

По правилу 2 грамматик LL (1) не более одного из B и C может допускать дальнейший вывод, поскольку главный вывод Z не может быть как в First(B), так и в First(C) (не двусмысленный случай).

Случай 3: Z непустое и либо MaybeEmpty(B), либо MaybeEmpty(C)

Обратите внимание, что по правилу 1 грамматик LL (1), B и C не могут оба быть пустыми. Предположим поэтому, что MaybeEmpty(C) истинно.

Это дает два поддиапазона.

Случай 3a: CY -> Y; и Случай 3b: CY ->* DY, где D не пусто.

В 3a мы должны выбрать между BY ->* Z и CY -> Y ->* Z, но обратите внимание, что First(Y) subset-of Follow(A). Так как Follow(A) не пересекается с First(B), то может произойти только одно деривация (не двусмысленная).

В 3b мы должны выбрать между BY ->* Z и CY ->* DY ->* Z, но обратите внимание, что First(D) subset-of First(C). Так как First(C) не пересекается с First(B), может выполняться только один вывод (не двусмысленный).

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