Грамматика однозначна.
Во-первых, мы можем показать, что язык грамматики - 0*(0 + 1*1); то есть язык любого числа 0 s, за которым следует либо одиночный 0, либо любая непустая строка 1 s. Обратите внимание, что любую такую строку можно получить следующим образом:
- если строка равна
0^k с k> 0: S -> 0S (k-1) раз, затем S -> 0 один раз. - , если строка
0^i 1^k с i >= 0 и k > 0, то: S -> 0S i раз, затем S -> A один раз, затем A -> 1A (k-1) раз и A -> 1 один раз.
Также обратите внимание, что грамматика не может генерировать ничего, кроме таких строк:
- все
0 идут перед любыми 1 s - любая строка без
1 s должен иметь хотя бы один 0.
Теперь вопрос в том, существуют ли разные деревья синтаксического анализа для любой сгенерированной строки. Мы можем показать, что существуют не очень простые случаи использования:
, если строка 0^k с k> 0: только две продукции вводят 0 s: S -> S0 и S -> 0. Чтобы получить k экземпляров 0, мы вынуждены сначала использовать производственный S -> S0 (k-1) раз, а затем использовать S -> 0, поскольку в противном случае мы завершили бы промежуточную форму, прежде чем перейти к строке длиной k.
если строка 0^i 1^k с i> = 0 и k> 0: мы вынуждены использовать производство S -> 0 i раз, чтобы получить 0^i, поскольку никакая другая последовательность производств не даст нам незавершенная промежуточная форма, начинающаяся с i 0 s. Затем мы вынуждены использовать S -> A, поскольку любой другой выбор добавит дополнительные 0 s. Затем мы вынуждены использовать A -> 1A количество раз, равное (k - 1), поскольку в противном случае мы завершили бы строку, прежде чем перейти к требуемым k экземплярам 1, поскольку единственное оставшееся производство - это A -> 1, что исключает последний нетерминал. Наконец, мы вынуждены использовать A -> 1 для завершения строки.
Итак, в обоих случаях наш выбор продукции был продиктован числами 0 s и 1 с; у нас никогда не было произвольного выбора того, какую продукцию использовать. Фактически, поскольку все промежуточные формы когда-либо содержали только один нетерминал, у нас никогда не было выбора, в каком порядке использовать продукцию: существует не только одно дерево синтаксического анализа для каждой строки, но только один порядок, в котором грамматика может выводить строки. Существуют однозначные грамматики, в которых даже это строгое условие не выполняется; рассмотрите
S -> AB
A -> a
B -> b
Это однозначно, хотя есть два производных строки ab:
S -> AB -> aB -> ab
S -> AB -> Ab -> ab
В обоих случаях дерево одно и то же:
A - a
/
S
\
B - b