1.4.2. Сентенциальная форма грамматики

Вывод называется законченным, если на основе цепочки , полученной в результате вывода, нельзя больше сделать ни одного шага вывода. Иначе говоря, цепочка  при законченном выводе или пустая, или содержит только терминальные символы грамматики G, т. е.   T^*. При этом  называется конечной цепочкой вывода.

В рассмотренном примере все цепочки законченные. Если же взять вывод S ^* – 4FF (первая строка), то этот вывод будет незаконченным.

Цепочка символов   V^* называется сентенциальной формой грамматики G<T, N, P, S>, если она выводима из целевого символа грамматики: S ^* .

Если   T^* (т. е. получена в результате законченного вывода), то она называется конечной сентенциальной формой.

Из рассмотренного примера цепочки – 479 и 18 являются конечными сентенциальными формами грамматики целых десятичных чисел со знаком.

Цепочка F8 из строки 2 тоже является сентенциальной, но не конечной. В то же время в выводах 3, 4 и 5 примера явно не присутствуют сентенциальные формы. Но на самом деле они (350, 1004, 5) сентенциальные конечные, только надо построить другие цепочки вывода, начиная от целевого символа. Для строчки 3 и 5 это сделать просто. Но в примере 4 цепочка TFT не может быть получена из целевого символа и потому сентенциальной формой не является.

Язык L, заданный грамматикой G<T, N, P, S> – это множество всех конечных сентенциальных форм грамматики G – L(G). Алфавит такого языка – множество T грамматики G.

Две грамматики эквивалентны, если эквивалентны заданные ими языки.

1.4.3. Левосторонний и правосторонний выводы

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

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

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

Если рассмотреть выводы для нашего примера, содержащих пять цепочек, то 1 и 5 цепочки являются левосторонними, 2, 3 и 5 – правосторонними, 4 – не является ни левосторонней, ни правосторонней.

Для грамматик типа 2 и 3 для любой сентенциальной формы всегда можно построить левосторонний или правосторонний выводы. Для грамматик других типов это не всегда возможно, т. к. по структуре их правил не всегда можно выполнить замену крайне левого или крайне правого нетерминала в цепочке.

1.4.4. Дерево вывода и методы его построения

Деревом вывода грамматики G<T, N, P, S> называется дерево (граф), которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям:

– каждая вершина дерева обозначается символом грамматики, принадлежащим общему алфавиту A  T  N;

– корнем дерева является вершина, обозначенная целевым символом грамматики S;

– листьями дерева (концевыми вершинами) являются вершины, обозначенные терминальными символами или символом ;

– если некоторый узел дерева обозначен нетерминальным символом A  N, а связанные с ними узлы – символами b₁, b₂, … b_n; n > 0 (b_i  V^*), то в грамматике G существует правило A  b₁b₂…b_n  P. Из определения видно, что по структуре правил дерево вывода в указанном виде всегда можно построить только для контекстно-свободных и регулярных грамматик, т. е. грамматик типа 2 и 3.

Для грамматик других типов дерево вывода в таком виде можно построить не всегда, либо оно будет иметь несколько иной вид.

На основе рассмотренного примера с пятью выводами построим деревья для цепочек вывода 1 и 2 (рис 1.2).

Рис.1.2. Варианты деревьев для цепочек вывода: а) цепочка 1; б) цепочка 2

По порядку следования букв, обозначающих связи, можно определить левосторонность (1) и правосторонность (2). Для того, чтобы построить дерево вывода, достаточно иметь только цепочку вывода. Дерево можно построить двумя способами: сверху вниз и снизу вверх. Для строго формализованного построения дерева вывода всегда надо строго определяться – левосторонний или правосторонний вывод.

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

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

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