Неоднозначность грамматик. Устранение неоднозначности

Пример 12

Обратимся вновь к грамматике арифметических выражений (5.3). Предложение
id+id*id имеет два разных левых порождения

E=>E+E E=>E*E

=>id+ E E=>E+E*E

=>id + E*E => id + E * E

=> id + id * E => id + id * E

=> id + id*id => id + id*id

с двумя соответствующими им деревьями разбора, показанными на рис. 24.

a) 6)

Рис. 24. Два дерева разбора для id+id*id

Дерево разбора на рис. 24(а) отражает обычные приоритеты операций + и *, в отличие от дерева на рис. 24(6). Обычно приоритет умножения выше, и выражение типа а+b*с трактуется как а+(b*с), а не как (а+b)*с.

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

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

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

stmt —> if expr then stmt

(5.7)

| if expr then stmt else stmt other

| other

Здесь "other" означает все прочие инструкции. Грамматика (5.7) неоднозначна, поскольку cтрока

if E₁ then if E₂ then S₁ else S₂ (5.8)

имеет два дерева разбора, показанных на рис. 25.

Рис. 25 Два дерева разбора для неоднозначного предложения

Во всех языках программирования с условными инструкциями такого вида предпочтительно первое дерево разбора. Общее правило гласит "сопоставить каждое else, ближайшему незанятому then". Это правило устранения неоднозначности может быть встроено непосредственно в грамматику. Например, можно переписать грамматику рассмотренную ранее как однозначную. Основная идея заключается в том, что инструкция, появляющаяся между then и else, должна быть "сбалансированная", т.е. не должна оканчиваться на then не соответствующее некоторому else. Такая "сбалансированная" инструкция может представлять собой либо полную инструкцию if-then-else, содержащую только "соответствующие" инструкции, либо любые инструкции, отличающиеся от условной, т.е. получаем грамматику.

Stmt àS1 | S2

S1à if expr then S1 else S1 | other (5.9)

S2à if expr then stmt | if expr then S1 else S2

Эта грамматика генерирует то же множество строк, что и грамматика (5.7), но для строки (5.8) дает только одно дерево разбора, а именно то, которое связывает каждое else с ближайшим незанятым then.

Дата добавления: 2014-12-27