LL (1) не может быть неоднозначным - PullRequest
Новая
       10

LL (1) не может быть неоднозначным

11 голосов
/ 17 апреля 2010

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

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

Ответы [ 3 ]

7 голосов
/ 17 апреля 2010

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

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

5 голосов
/ 24 сентября 2013

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

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

Доказательство

Пусть 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), может продолжаться только одна деривация (не однозначная).

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

1 голос
/ 23 сентября 2013

Докажите, что никакая неоднозначная грамматика не может быть грамматикой LL (1). Подсказки см. http://www.cse.ohio -state.edu / ~ rountev / 756 / pdf / SyntaxAnalysis.pdf , слайды 18-20. Также см. http://seclab.cs.sunysb.edu/sekar/cse304/Parse.pdf, стр. 11 и предшествующий.

...