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

Деревом вывода грамматики G(N,T,P,S) называется дерево, которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям: 1) каждая вершина дерева обозначается символом грамматики A; 2) корнем дерева является вершина, обозначенная целевым символом грамматики - S; 3) листьями дерева (конечные вершины) являются вершины, обозначенные терминальными символами грамматики или символом пустой цепочки; 4) если некоторый узел дерева обозначен нетерминальным символом A, а связанные с ним узлы - символами b1, b2,...bn; n>0 то в грамматике G существует правило A->b1|b2|...|bn из P.

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

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

Для цепочки a+b+a в грамматике G=({a,b}, {S,T}, {S->T|T+S;T->a|b}, S)

можно построить левосторонний вывод:

S->T+S->T+T+S->T+T+T->a+T+T->a+b+T->a+b+a

можно построить правосторонний вывод:

S->T+S->a+S->a+T+S->a+b+S->a+b+T->a+b+a

смешанный вывод(не левый и не правый):

S->T+S->T+T+S->T+T+T->T+T+a->T+b+a->a+b+a

Канонические выводы

Каноническая форма а) Каждая КС-грамматика эквивалентна (т.е. генерирует тот же язык) грамматике в нормальной форме Хомского, т.е. со всеми порождающими правилами вида A → BC | a при обычных условиях, касающихся терминалов и нетерминалов. б) Каждая КС-грамматика эквивалентна грамматике в нормальной форме Грейбаха, т.е. со всеми порождающими правилами вида A → bα где α – строка нетерминалов (возможно, пустая).

Неоднозначность(двусмысленность) грамматик

КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка, для которой может быть построено два или более различных деревьев вывода.

Пример: G({+,-,*,/,(,),a,b},{S},P,S):

Р: S-> S+S | S-S | S*S | S/S | (S) | а | b

Для цепочки а*b+а возможны два левых вывода:

(1) S -> S+S -> S*S+S -> a*S+S -> a*b+S -> a*b+a

(2) S -> S*S -> a*S -> a*S+S -> a*b+S -> a*b+a

Проблема разбора.

Задача разбора в общем виде: на основе имеющейся грамматики некоторого языка построить распознаватель для этого языка

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

Процесс построения такого вывода (а, следовательно, и определения принадлежности цепочки языку) называется разбором.

Проблему разбора можно свести к 1) нахождению левостороннего разбора; 2) нахождению правостороннего разбора; 3) построению синтаксического дерева.

Вывод цепочки b (VT)^* из S VN в КС-грамматике G = (VT, VN, P, S), называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого нетерминала.

Вывод цепочки b (VT)^* из S VN в КС-грамматике G = (VT, VN, P, S), называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого правого нетерминала.

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

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

Исследуем грамматику с порождающими правилами (E - начальный символ). 1. Е → Е + Т 2. Е → T 3. T → T * F 4. T → F

5. F → (Е) 6. F → x 7. F → y

Ясно, что строка (x + y) * x принадлежит данному языку. В частности, это можно вывести следующим образом (для каждого шага вывода указан номер применяемого правила) (левосторонний вывод): 2) E ⇒ T 3) ⇒ T * F 4) ⇒ F * F 5) ⇒ (E)* F 1) ⇒ (E + T) * F 2) ⇒ (T + T) * F 4) ⇒ (F + T) * F 6) ⇒ (x + T)*F 4) ⇒ (x + F) * F 7) ⇒ (x + y) * F 6) ⇒ (x + y) * x

Или же это можно вывести так (правосторонний вывод): 2) E ⇒ T 3) ⇒ T * F 6) ⇒ T * x 4) ⇒ F * x 5) ⇒ (E) * x 1) ⇒ (E + T) * x 4) ⇒ (E + F) * x

7) ⇒ (E + y) * x 2) ⇒ (T + y) * x ) ⇒ (F + y) * x 6) ⇒ (x + y) * x

Лексический анализ.

Лексический анализ (сканер ) На входе сканера — цепочка символов некоторого алфавита (именно так выглядит для сканера наша исходная программа). При этом некоторые комбинации символов рассматриваются сканером как единые объекты. Лексический анализатор (ЛА) группирует определенные терминальные символы (т. е. входные символы) в единые синтаксические объекты — лексемы. В простейшем случае лексема — это пара вида <тип_лексемы, значение>.

Первой фазой процесса компиляции является лексический анализ, то есть группирование строк литер, обозначающих идентификаторы, константы или слова языка и т.д., в единые символы (лексемы). Этот процесс может идти параллельно с другими фазами компиляции (например, в однопроходных компиляторах). Однако, в любом случае, при описании конструкции компилятора и его построения удобно представлять лексический анализ как самостоятельную фазу. Блок сканирования (сканер) должен выдавать каждую лексему, устанавливая ее принадлежность тому или иному классу. Выбор классов зависит от особенностей транслируемого языка. Часто выделяют классы имен переменных, констант, ключевых слов, арифметических и логических операций ("+", "-", "*", "/" и т.д.), специальных символов ("=", ";" и т. д.). Характер распознаваемых строк может намного упростить процесс лексического анализа. Все эти строки можно генерировать с помощью регулярных выражений. Например, вещественные числа можно генерировать посредством регулярного выражения (+ | -) d d*.d* , где d обозначает любую цифру. Из выражения видно, что вещественное число состоит из следующих компонентов, расположенных именно в таком порядке: 1. возможного знака; 2. последовательности из одной или более цифр; 3. десятичной точки; 4. последовательности из нуля или более цифр.

Регулярные выражения эквивалентны грамматикам типа 3. Например, грамматика типа 3, соответствующая регулярному выражению для вещественного числа, имеет порождающие правила: R → +S | -S | dQ S → dQ Q → dQ | .F | . F → d | dF где R - начальный символ, d – цифра.

Существует полное соответствие между регулярными выражениями (а потому и грамматиками типа 3) и конечными автоматами, более подробно рассмотренными в следующей главе. Некоторые лексемы (например, *) могут быть распознаны по одному считанному символу, другие (такие, как :=) – по двум символам, а для идентификации третьих необходимо прочитать неизвестное заранее число символов (например, код константы). В последнем случае, чтобы найти конец лексемы, приходится считывать один лишний символ, не входящий в состав данной лексемы. Этот символ необходимо запоминать, чтобы при разборе следующей лексемы он не был утерян. Лексический анализатор, наряду с разбиением исходного потока символов на лексемы, может включать в исходный текст дополнительную информацию или исключать из него строки символов. Примером дополнительно включаемой информации являются номера строк. Если их не включить, то информация о том, в какой строке исходного текста находилась та или иная лексема, будет, в случае выполняющего сканирование в отдельном проходе компилятора, утеряна после лексического анализа. Однако для диагностики на фазе синтаксического анализа необходимо иметь возможность ссылаться на ошибки в программе с указанием номеров строк оригинального исходного текста. С другой стороны, комментарии включаются в текст программы или описания объекта проектирования только для предоставления человеку дополнительных пояснений. Они никак не влияют на генерируемый в дальнейшем код, и лексический анализатор обычно их просто исключает.