Дерево вывода и неоднозначность грамматик

Определение. Деревом вывода цепочки w ϵ Т в грамматике G = (V, T, P, S) называется упорядоченное дерево, узлы которого помечены символами из множеств V, T так, что корень дерева помечен аксиомой (стартовым символом), внутренние узлы – нетерминалами, а листья – терминалами.

Пример.

Построим дерево вывода цепочки (a + b) * (a + b + a0 + a1) из грамматики выражений.

Корень дерева Е, внутренние узлы E и I, листья – заданная цепочка.

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

Если обойти все листья дерева слева направо, то получим в точности выводимую цепочку.

Основная роль дерева вывода состоит в том, что оно связывает синтаксис и семантику (смысл) выводимой цепочки. Например, семантика естественного языка – смысл фразы, а для компьютерной программы – это алгоритм решения задачи. Чтобы сохранить семантику языковой цепочки, грамматика и дерево вывода должны быть однозначны.

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

Неоднозначность – отрицательное свойство грамматики.

Если программа кодирует 2 различные последовательности машинных инструкций, то одна из них наверняка реализует не тот алгоритм.

Пример. Грамматика G = {E→E+E | E*E | 0 | 1 | … | 9} является неоднозначной, т. к. цепочка 4+2*3 имеет 2 дерева вывода:

Дерево «а» показывает, что сложение должно применяться к результату умножения 4+(2*3)=10, а дерево «б» - в умножении участвует результат сложения (4+2)*3=18.

Неоднозначность данной грамматики приводит к невозможности однозначно определить значение выражения, и следовательно, к непригодности данной грамматики для порождения арифметических выражений.

Аналогичная грамматика GA₁ = {E→E+E | E*E | (E) | x} также является неоднозначной, т. к. отсутствует порядок (приоритет) выполнения операций. Эта грамматика порождает и правильную и неправильную цепочки арифметических выражений:

Е → E*E → (Е)*х → (E+E)*х → (х+х)*х

Е → E+E → х+(Е) → х+(Е*Е) → х+(х*х)

Для устранения неоднозначности уточним грамматику согласно определению арифметического выражения:

арифметическое выражение – это сумма одного или более слагаемых, каждое из которых – произведение одного или более множителей, каждый из которых есть буква «х» или арифметическое выражение в скобках.

Введем дополнительно нетерминал «Т» для слагаемых и нетерминал «F» для множителей.

GA₂ = { E→ E+T | T, T→ T*F | F, F→ (E) | x }

Попробуем вывести правильную и неправильную цепочки

Е → Т → T*F → F*x → (E)*x → (E+T)*x → (T+F)*x → (F+x)*x → (x+x)*x

Е → E+Т → Т+Т*F → F+F*x → х+х*х

Неправильную цепочку породить не удалось, вместо нее породили правильную, без скобок.

Второй пример уточнения грамматики.

Язык двоичных чисел порождается грамматикой

GN₁ = { S→ L |.L | L.L, L→ LB | B, B→ 0 | 1 }

Породим число 6,75 (10) или 0110.1100 (2)

S → L.L → LB.LB → LB0.LB0 → LB10.LB00 → B110.B100 → 0110.1100

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

Если целая часть всегда начинается единицей, а дробная единицей заканчивается, то вводим нетерминал «R», обозначающий правую часть числа и уточняем правила вывода левой и правой части:

GN₂ = { S→ L |.R | L.R, L→ L0 | L1 | 1, R→ 0R | 1R | 1 }

S → L.R → L0.1R → L10.11 → 110.11

Закрепление материала:

1. Составить деревья вывода правильной и неправильной цепочек из грамматики

GA₁ = {E→E+E | E*E | (E) | x}.

2. Составить деревья вывода правильной и неправильной цепочек из грамматики

GA₂ = { E→ E+T | T, T→ T*F | F, F→ (E) | x }

Выведем неправильную цепочку x+(x*x):

E → E+T → T+F → F+(E) → x+(T) → x+(T*F) → x+(F*x) → x+(x*x)

Грамматика все же порождает неправильную цепочку. Необходимо еще уточнить. В скобках может быть только сумма.

GA₂ = { E→ E+T | T, T→ T*F | F, F→ (E+T) | x }

Проверим: