Синтаксические деревья и неоднозначность

Рассмотрим грамматику c правилами вывода

(1.1.1)

B ® B+B½B*B½V½C

V ® a½b½c½... x½y½z

C ® 0½1½2½...8½9

и вывод цепочки b+a*9

(1.1.2) BÞB+BÞB+B*BÞV+B*BÞV+V*BÞV+V*CÞb+V*CÞb+a*CÞb+a*9

Такая запись не очень удобна, так как по ней трудно определить в какой части сентенциальной формы проводилась замена и какой нетерминал породил тот или иной символ. Более наглядна запись в виде дерева вывода или синтаксического дерева, представленного на рис 1.2 (a).

Для того чтобы понять что выведено, применяем левый обход дерева. Идем от корня по крайней левой ветви, дойдя до терминала (конца ветви), выписываем его, возвращаемся до ближайшего разветвления и идем по самой левой из тех, которые еще не пройдены. Если все ветви данного узла уже исчерпаны, возвращаемся к предыдущему разветвлению, если оно есть. Продолжая, таким образом, получим в результате b+a*9. Кроме вывода (1.1.2) по данному дереву можно получить целую серию выводов, например,

(1.1.3) BÞB+BÞB+B*BÞB+B*CÞV+V*9ÞB+V*9ÞB+a*CÞV+a*CÞb+a*9

Заметим, что эти выводы отличаются лишь порядком применения правил и что синтаксическое дерево и грамматика не определяют точный порядок вывода. На каждом шаге вывода имеется некоторый произвол в выборе заменяемого нетерминала. На данном этапе эти различия порядка для нас несущественны и мы считаем выводы эквивалентными, если им соответствует одно и то же дерево. Более важным здесь является то, что цепочка b+a*9 в данной грамматике имеет два дерева вывода (рисунки 1.2 (а) и (б)). Сентенциальная форма B+B*B имеет два синтаксических дерева и две основы: B+B и B*B. Грамматика неоднозначна и при разборе сентенциальной формы можно выбрать любую из основ. Нельзя сказать, что выполняется раньше: умножение или сложение. Из рис. 1.2 (б) следует, что b+a*9 имеет два подвыражения b+a и 9, хотя по смыслу необходимо иметь подвыражения b и a*9.

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

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

(1.1.4) <врж> ® <терм> ç+ <терм> ç- <терм> ç<врж> + <терм> ç<врж> - <терм>

<терм> ® <множ> ç<терм> * <множ> ç<терм> / <множ>

<множ> ® (<врж>) ç i ç k

В этой грамматике i - любой идентификатор (имя переменной), а k - любая константа. Единственное дерево вывода для выражения i+i*k представлено на рис. 1.3. (a). В соответствии с предложенной грамматикой, эта, да и все остальные цепочки, порождаемые грамматикой (1.1.4) однозначны.

Определим теперь, что в выражении i+i*k должно выполняться раньше: сложение или умножение. Операндами для +, согласно дереву, является <врж>, из которого выводится i, и <терм>, порождающий i*k. Это означает, что умножение должно выполняться первым и образовать <терм> для сложения; следовательно, умножение предшествует сложению. Сделать наоборот можно используя только скобки, как показано на рис. 1.3 (б). Грамматику арифметических выражений (1.1.4) следует предпочесть грамматике (1.1.1) ввиду ее однозначности и учета приоритета операций.