А-грамматик в виде графа состояний. Неодназначность грамматик

Синтаксические деревья вывода в КС-грамматиках. Представление

Рассмотрим КС-грамматику 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) ввиду ее однозначности и учета приоритета операций.

Наглядным способом представления А-грамматики является граф состояний (переходов). Вершины этого графа соответствуют нетерминалам и из вершины A в вершину B проводится дуга, помеченная терминалом a, если в грамматике существует правило

A ® aB.

Добавим еще одну дополнительную заключительную вершину F и проведем дуги (рис. 1.4), если в грамматике присутствует заключительное правило A ® b, а само это правило будем записывать A ® bF, получив тем самым модифицированную А-грамма­ти­ку.

Заметим, что каждому выводу в А-грамматике будет соответствовать путь по графу состояний из начальной вершины S в вершину F. Граф А-грамматики действительного числа из примера 1.9 представлен на рис. 1.5 (a).

А-грамматика числа, рассмотренная в примере 1.9, является недетерминированной, то есть в ней существует такой нетерминал A и терминал a, для которых существует несколько нетерминалов B, таких что выполняются правила A ® aB. Например, модифицированная А-грамматика числа, что отчетливо видно на рис. 5.1 (а), содержит правила < чбз >®. < дчп > и < чбз >®. F или < дчп > ® 0< дчп > и < дчп > ® 0F. Это нежелательно с точки зрения построения программ синтаксического анализа.

А-грамматика называется детерминированной, если для любого нетерминала A (A ¹ F )и любого терминала a существует не более одного нетерминала B, для которого выполняется правило A ® aB.

А-грамматика называется вполне детерминированной, если для любого нетерминала A (A ¹ F )и любого терминала a существует единственный нетерминал B, для которого выполняется правило A ® aB.

В следующей главе будет показано, что любую недетерминированную А-грамматику можно привести к детерминированной. Пока же, для того чтобы перейти к реализации программ синтаксического анализа А-языков, что является основной частью лабораторных работ на ЭВМ в данной части курса, отметим, что на практике всегда используется специальный символ - ограничитель цепочки. Это либо нулевой байт, либо символ конца файла и т.п.

Если, например, считать, что число из примера 1.9 завершается символом “; ”, то детерминированная А-грамматика числа строится элементарно. Граф состояний для этого случая представлен на рис. 1.5 (б). Нетерминалы < чбз1 >, < дчп1 >, < пбз1 > добавлены здесь для того, чтобы исключить возможность формирования числа без целой и дробной частей и без числа порядка после символа ” E ”.

Вполне детерминированная форма должна включать, кроме того, “ошибочный” нетерминал < Ош > и правила типа < чбз > ® + < Ош > или < дчп > ®. < Ош > и т.п. То есть для тех AÎ V_N (A ¹ F)и a Î V_T, для которых в модифицированной детерминированной А-грамматике нет правил A ® aB, необходимо для формирования вполне детерминированной формы добавить правила A ® aE, где E º <Ош> - “ошибочная” вершина.

Дата добавления: 2014-01-11