Синтаксический анализ (стр. 1 )

Синтаксический анализ

Формальные языки

Алфавит – непустое конечное множество произвольных элементов (символов), задаваемое перечислением.

S1 = {a, b, c, …, y, z}, S2 = {0, 1}, S3 = {§, ¨, ©, ª}

Цепочки, операции над цепочками

a – цепочка (над алфавитом S) – упорядоченная последовательность символов из алфавита S :
a = a1a2…an (ai ΠS)

|a | – длина цепочки a :
|a1…an| = n

e – пустая цепочка: |e | = 0.

ab – конкатенация (сцепление) цепочек a и b :
a = a1…an, b = b1…bm ® ab = a1…anb1…bm

|ab | = |a| + |b |, ae = ea = a

Если w = ab, то a – префикс w, b – суффикс w .

a k – k-степень цепочки a :
a 0 = e, a k+1 = aa k

Множества цепочек и операции над ними

AÈB, AÇB, A\ B – теоретико-множественные операции над множествами.

AB – конкатенация множеств:
AB = {ab | a Î A, b Î B}

Ak – k-степень множества:
A0 = {e }, Ak+1 = AAk

A* – замыкание Клини множества (множество всех цепочек над A произвольной длины):
A* = È{i³0}Ai

A+ = A*\ A0

Языки и операции над ними

L – (формальный) язык над алфавитом S – произвольное множество цепочек над S :
L Í S*

Операции L1L2, Lk, L*, L+ для языков определяются как для множеств цепочек.

Проблема описания языка: задание языка перечислением либо невозможно (бесконечные языки), либо непрактично (большие языки). Требуется компактный набор правил, позволяющих проверять a Î L.

Для описания языков применяются формализмы трех типов:

–  порождающие грамматики (метод исчисления составляющих);

–  автоматы-распознаватели (метод эффективного вычисления характеристической функции языка);

–  алгебры множеств (аналитический метод).

Формальные грамматики

(Формальная) грамматика (порождающая грамматика, грамматика составляющих Н. Хомски):
G = < T, N, S, P>, где:
T – множество терминальных символов (терминалов);
N – множество нетерминальных символов (нетерминалов);
S Î N – стартовый нетерминал;
P – множество продукций (правил вывода) вида a ® b.

Классификация грамматик по Хомски – по виду продукций из P:

Грамматики типа 0 (с фразовой структурой общего вида):
a ® b, где a, b Î (TÈN)*.

Грамматики типа 1 (контекстно-зависимые, КЗ-грамматики, КЗГ):
a ® b, где a Î (TÈN)*N(TÈN)*, b Î (TÈN)*.

Грамматики типа 2 (контекстно-свободные, КС-грамматики, КСГ):
A ® a , где AÎ N, a Î (TÈN)*.

Грамматики типа 3 (регулярные, РГ):
A ® aB или A ® a, где A, B Î N, a Î T.

В практике автоматического синтаксического анализа применяются только классы КСГ и РГ.

Основа продукции A ® a – её правая часть a.

Сокращенная форма записи продукций КСГ:

A ® a1, A ® a2 , ... , A ® an Û A ® a1 | a2 | ... | an .

Соглашения об обозначениях

Следующие обозначения используются в дальнейшем для сокращения уточнений о множествах символов или цепочек:

Строчные буквы начала латинского алфавита:
a, b, c, ... Î T – одиночные терминалы;

Строчные буквы конца латинского алфавита:
... u, v, x, y, z Î T* – цепочки терминалов;

Заглавные буквы начала латинского алфавита:
A, B, C, ... Î N – одиночные нетерминалы;

Заглавные буквы конца латинского алфавита:
... X, Y, Z Î TÈN – одиночные терминалы или нетерминалы;

Строчные греческие буквы (кроме e – пустой цепочки):
a, b, g… Î (TÈN)* – смешанные цепочки терминалов и нетерминалов.

Вывод по грамматике

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

Вывод (разверткой) (за 1 шаг, непосредственный) по грамматике G:
a ÞG b Û a = a1ja2, b = a1ya2, j ®y Î P.
(индекс G опускается, когда ясно, о какой грамматике идет речь)

Вывод за k шагов:
a Þk b Û a Þ j , j Þk-1b . (a Þ0 a )

Вывод за произвольное число шагов:
a Þ*b Û $k ³ 0: a Þkb

Вывод за ненулевое число шагов:
a Þ+b Û $k > 0: a Þkb

Для КСГ на каждом шаге вывода заменяется один нетерминал.

Левосторонний вывод для КСГ:
a Þl b Û заменяется самый левый нетерминал в a .

Правосторонний вывод для КСГ:
a Þr b Û заменяется самый правый нетерминал в a .

Þlk, Þl*, Þl+, Þrk, Þr*, Þr+ определяются аналогично.

Язык, порождаемый грамматикой

Сентенциальная форма грамматики – цепочка, выводимая из S:
a : S Þ* a

Предложение – терминальная сентециальная форма:
w : S Þ* w

Фраза – терминальная цепочка, выводимая из нетерминала:
v : A Þ* v

Язык, порождаемый грамматикой, – множество выводимых в ней предложений:
L(G) = {w | S ÞG* w}

Деревья синтаксического разбора

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

Дерево (синтаксического) разбора для грамматики G – это корневое ориентированное упорядоченное помеченное дерево (в смысле теории графов), в котором:
– корень помечен S;
– узлы помечены нетерминалами из N;
– листья помечены e или терминалами из T;
– сыновья каждого нетерминального узла A образуют упорядоченное множество X1, … , Xn, если A ® X1 … Xn Î P .

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

Крона дерева – cечение, содержащее только пометки листьев.

Цепочка w выводима деревом в G, если существует дерево разбора с корнем S и кроной w.

Теорема о корректной выводимости

Выводимость деревом равносильна выводимости разверткой:

1.  Для любого вывода S Þ a1 Þ … Þ an Þ w можно построить дерево разбора, в котором a1…an – сечения, а w – крона.

2.  Для любого дерева разбора с кроной w существует вывод S Þ* w.

Следствия:

1.  Каждое сечение дерева разбора – сентенциальная форма.

2.  Каждая сентенциальная форма – cечение некоторого дерева разбора.

Неоднозначность разбора

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

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

Нисходящий и восходящий способы разбора

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

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

Эти два способа лежат в основе практических методов синтаксического анализа.

Примеры

КС-грамматика, описывающая язык арифметических выражений над переменными a:

G = < T = { a, +, -, *, /, (, ) },

N = { E, T, F },

S = E,

P = { E ® E+E | E–E | E*E | E/E | (E) | a } >

Выводы разверткой для цепочки a+a*a:

– произвольный: E Þ E*E Þ E*a Þ E+E*a Þ a+E*a Þ a+a*a

– левосторонний: E Þl E+E Þl a+E Þl a+E*E Þl a+a*E Þl a+a*a

– правосторонний: E Þr E+E Þr E+E*E Þr E+E*a Þr E+a*a Þr a+a*a

Два различных дерева вывода, иллюстрирующие неоднозначность G:

1: E 2: E семантически соответствуют:

/|\ /|\ 1: a+(a*a)

E + E E * E 2: (a+a)*a

| /|\ /|\ |

a E * E E + E a выделено сечение: a+E*E

| | | |

a a a a

Нисходящий вывод деревом для цепочки a+a*a:

E E E E E E

/|\ /|\ /|\ /|\ /|\

E + E E + E E + E E + E E + E

| | /|\ | /|\ | /|\

a a E * E a E * E a E * E

| | |

a a a

Восходящий вывод деревом для цепочки a+a*a:

E

/|\

E / / E

/|\ | | /|\

E E E E E E E E|E E | E|E

| | | | | | | ||| | | |||

a + a*a a + a*a a + a*a a + a*a a + a*a a + a*a

Недетерминированный синтаксический анализ для КСГ

Недетерминированный нисходящий разбор

Нисходящий анализатор с левосторонним выводом разверткой для КСГ

Пусть G = < T, N, S, P > – КС-грамматика.

Нисходящий анализатор с левосторонним выводом для G – следующий МА:
ML = < S = T, Q = {q0, qF}, Г = NÈT, s0 = S, F = {qF}, d >
Функция переходов d строится исходя из следующих правил:
1. Начальная конфигурация:
(q0, S, w)
2. Правила развертки:
"A®a Î P: (q0, As, w) ð (q0, as, w)
3. Правила сравнения:
"a Î T: (q0, as, aw) ð (q0, s, w)
4. Правило допуска:
(q0, e, e ) ð (qF, e, e )

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

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

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

Недетерминизм (конфликты) при нисходящем разборе

Если грамматика содержит более одной продукции для некоторого нетерминала, то правила развертки разрешают недетерминированный выбор между ними при обнаружении этого нетерминала на вершине стека. Этот выбор назовем конфликтом «развертка-развертка».

Если грамматика содержит только по одной продукции для каждого нетерминала, то она порождает язык, состоящий из единственной цепочки, который едва ли представляет практический интерес. Поэтому недетерминированность нисходящего разбора неизбежна для любого содержательного языка и является следствием существенного и неустранимого свойства любой его грамматики. Отсюда, предложенный недетерминированный нисходящий анализатор не может работать детерминированно ни для какого содержательного языка. Требуется введение дополнительных механизмов решения конфликтов.

Недетерминированный восходящий разбор

Пополненные грамматики

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

Пополненная (расширенная) грамматика, полученная из G = < T, N, S, P >:
G’ = < T, NÈ{S’ }, S’, P È {S’® S} >

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

Восходящий анализатор с правосторонним выводом сверткой для КСГ

Пусть G = < T, N, S, P > – КС-грамматика.

Восходящий анализатор с правосторонним выводом для G’ – следующий расширенный МА:
MR = < S = T, Q = {q0, qF}, Г = NÈT, s0 = e, F = {qF}, d >
Функция переходов d строится исходя из правил:
1. Начальная конфигурация:
(q0, e, w)
2. Правила переноса:
"a Î T: (q0, s, aw) ð (q0, s a, w)
3. Правила cвертки:
"A®a Î P: (q0, sa, w) ð (q0, sA, w)
4. Правило допуска:
(q0, S’, e ) ð (qF, e, e )

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

Так как грамматика пополненная, продукции вида S’ ® a применимы только на последнем шаге вывода, поэтому появление S’ в стеке анализатора равносильно допуску входной цепочки.

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

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

Недетерминизм (конфликты) при восходящем разборе

Пусть в грамматике есть продукции вида A ® b1, B ® b1b2, C ® b2 и пусть b2 Þr* w.

Конфликт «перенос-свертка» (shift-reduce conflict, SR-конфликт) – это состояние анализатора, в котором стековая цепочка оканчивается основой некоторой продукции и следующим шагом могут быть как свертка по этой продукции, так и продолжение переноса:

(q0, b1, w…) {	ð (q0, A, w…) ð* (q0, Ab2, …) ð (q0, AC, …)	свертка A ® b1
ð* (q0, b1b2, …) ð (q0, B, …)	перенос

Конфликт «cвертка-свертка» (reduce-reduce conflict, RR-конфликт) – это состояние анализатора, в котором возможна свертка по двум продукциям:

(q0, …b1b2, …) {	ð (q0, …B, …)	свертка B ® b1b2
ð (q0, …b1C, …)	свертка C ® b2

RR-конфликты не неизбежны: они не возникают, если в грамматике нет двух таких продукций, что одна основа является суффисом другой. SR-конфликты кажутся неизбежными, поскольку перенос возможен в любом состоянии, в том числе и при допустимой свертке. Однако если в грамматике нет пары продукций, где одна основа является частью другой, то SR-конфликт можно решить приоритетом свертки. Итак, оба типа конфликтов теоретически возможно решить модификацией грамматики, а значит, недетерминированный анализатор вполне может работать детерминированно на некоторых грамматиках.

Сравнение схем восходящего и нисходящего разборов

Следующий пример иллюстрирует последовательность шагов левостороннего и правостороннего выводов и состояния стека при нисходящем и восходящем разборах.

Нисходящий разбор с левосторонним выводом:

Грамматика:

шаг:

вывод ®

стек

ввод

1) S ® SaSb

развертка 1

S

a

a

b

b

¾¾ левосторонний вывод ¾®

2) S ® e

развертка 2

S

a

S

b

a

a

b

b

сравнение

a

e

a

S

b

a

a

b

b

развертка 1

a

S

b

a

b

b

развертка 2

a

S

a

S

b

b

a

b

b

cравнение

a

e

a

S

b

b

a

b

b

развертка 1

a

a

S

b

b

b

b

cравнение

a

a

e

b

b

b

b

cравнение

a

a

b

b

b

допуск

a

a

b

b

¾ сентенциал. форма ¾®

остат. ввод

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