Розробка нових алгоритмів реалізації з метою розробки інтелектуальної системи синтаксичного аналізу

Формально, основа правой сентенциальной формы z - это правило вывода A     и позиция в z, в которой может быть найдена цепочка   такие, что в результате замены   на A получается предыдущая сентенциальная форма в правостороннем выводе z. Таким образом, если S  _r^* A   _r , то A    в позиции, следующей за  , это основа цепочки  . Подцепочка   справа от основы содержит только терминальные символы.

Вообще говоря, грамматика может  быть неоднозначной, поэтому не единственным может быть правосторонний вывод   и не единственной может быть основа. Если грамматика однозначна, то каждая правая сентенциальная форма грамматики имеет в точности одну основу. Замена основы в сентенциальной форме на нетерминал левой части называется отсечением основы. Обращение правостороннего вывода может быть получено с помощью повторного применения отсечения основы, начиная с исходной цепочки w. Если w - слово в рассматриваемой грамматике, то w =  _n, где  _n - n-я правая сентенциальная форма еще неизвестного правого вывода S =  _{0  r 1  r}...  _{r n-1  r n} = w.

Чтобы восстановить этот вывод в  обратном порядке, выделяем основу  _n в  _n и заменяем  _n на левую часть некоторого правила вывода A_{n    n}, получая (n - 1)-ю правую сентенциальную форму  _n-1. Затем повторяем этот процесс, т.е. выделяем основу  _n-1 в  _n-1 и сворачиваем эту основу, получая правую сентенциальную форму  _n-2. Если, повторяя этот процесс, мы получаем правую сентенциальную форму, состоящую только из начального символа S, то останавливаемся и сообщаем об успешном завершении разбора. Обращение последовательности правил, использованных в свертках, есть правый вывод входной строки.

Таким образом, главная задача анализатора  типа сдвиг-свертка - это выделение  и отсечение основы.

4.4.2 LR(1)-анализаторы

В названии LR(1) символ L указывает на то, что входная цепочка читается слева-направо, R - на то, что строится правый вывод, наконец, 1 указывает на то, что анализатор видит один символ непрочитанной части входной  цепочки.

LR(1)-анализ  привлекателен по нескольким  причинам:

• LR(1)-анализ - наиболее мощный метод анализа без возвратов типа сдвиг-свертка;
• LR(1)-анализ может быть реализован довольно эффективно;
• LR(1)-анализаторы могут быть построены для практически всех конструкций языков программирования;
• класс грамматик, которые могут быть проанализированы LR(1)-методом, строго включает класс грамматик, которые могут быть проанализированы предсказывающими анализаторами (сверху-вниз типа LL(1)).

Схематически структура LR(1)-анализатора  изображена на рис. 4.8. Анализатор состоит из входной ленты, выходной ленты, магазина, управляющей программы и таблицы анализа (LR(1)-таблицы), которая имеет две части - функцию действий (Action) и функцию переходов (Goto). Управляющая программа одна и та же для всех LR(1)-анализаторов, разные анализаторы отличаются только таблицами анализа.

Программа анализатора читает символы  на входной ленте по одному за шаг. В процессе анализа используется магазин, в котором хранятся строки вида S₀X₁S₁X₂S₂...X_mS_m (S_m - верхушка магазина). Каждый X_i - символ грамматики (терминальный или нетерминальный), а S_i - символ состояния.

Заметим, что символы грамматики (либо символы состояний) не обязательно  должны размещаться в магазине. Однако, их использование облегчает понимание  поведения LR-анализатора.

Рис. 4.8:

Элемент функции действий Action[S_m, a_i] для символа состояния S_m и входа a_i   T  {$}, может иметь одно из четырех значений:

• shift S (сдвиг), где S - символ состояния,
• reduce A     (свертка по правилу грамматики A    ),
• accept (допуск),
• error (ошибка).

Элемент функции переходов Goto[S_m, A] для символа состояния S_m и входа A   N, может иметь одно из двух значений:

• S, где S - символ состояния,
• error (ошибка).

Конфигурацией LR(1)-анализатора называется пара, первая компонента которой - содержимое магазина, а вторая - непросмотренный  вход:

Эта конфигурация соответствует правой сентенциальной форме

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

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

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

Пусть LR(1)-анализатор находится в  конфигурации

Анализатор может проделать  один из следующих шагов:

• Если Action[S_m, a_i] = shift S, то анализатор выполняет сдвиг, переходя в конфигурацию

Таким образом, в магазин помещаются входной символ a_i и символ состояния S, определяемый Action[S_m, a_i]. Текущим входным символом становится a_i+1.

• Если Action[S_m, a_i] = reduce A    , то анализатор выполняет свертку, переходя в конфигурацию

где S = Goto[S_m-r, A] и r - длина  , правой части правила вывода.

Анализатор сначала удаляет  из магазина 2r символов (r символов состояния  и r символов грамматики), так что  на верхушке оказывается состояние S_m-r. Затем анализатор помещает в магазин A - левую часть правила вывода, и S - символ состояния, определяемый Goto[S_m-r, A]. На шаге свертки текущий входной символ не меняется. Для LR(1)-анализаторов X_m-r+1...X_m - последовательность символов грамматики, удаляемых из магазина, всегда соответствует   - правой части правила вывода, по которому делается свертка.

После осуществления шага свертки  генерируется выход LR(1)-анализатора, т.е. исполняются семантические действия, связанные с правилом, по которому делается свертка, например, печатаются номера правил, по которым делается свертка.

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

• Если Action[S_m, a_i] = accept, то разбор успешно завершен.
• Если Action[S_m, a_i] = error, то анализатор обнаружил ошибку, и выполняются действия по диагностике и восстановлению.

Пример 4.8. Рассмотрим грамматику арифметических выражений G = ({E, T, F}, {id, +, *}, P, E) с правилами:

	(1) E   E + T
	(2) E   T
	(3) T   T * F
	(4) T   F
	(5) F   id

 

  На рис. 4.9 изображены функции Action и Goto, образующие LR(1)-таблицу для этой грамматики. Для Элемент Si функции Action означает сдвиг и помещение в магазин состояния с номером i, Rj - свертку по правилу номер j, acc - допуск, пустая клетка - ошибку. Для функции Goto символ i означает помещение в магазин состояния с номером i, пустая клетка - ошибку.

На входе id + id * id последовательность состояний магазина и входной  ленты показаны на рис. 4.10. Например, в первой строке LR-анализатор находится в нулевом состоянии и «видит» первый входной символ id. Действие S6 в нулевой строке и столбце id в поле Action (рис. 4.9) означает сдвиг и помещение символа состояния 6 на верхушку магазина. Это и изображено во второй строке: первый символ id и символ состояния 6 помещаются в магазин, а id удаляется со входной ленты.

Рисунок 4.9

Рис. 4.10:

Текущим входным символом становится +, и действием в состоянии 6 на вход + является свертка по F  id. Из магазина удаляются два символа (один символ состояния и один символ грамматики). Затем анализируется нулевое состояние. Поскольку Goto в нулевом состоянии по символу F - это 3, F и 3 помещаются в магазин. Теперь имеем конфигурацию, соответствующую третьей строке. Остальные шаги определяются аналогично.

4.4.3 Конструирование LR(1)-таблицы

Рассмотрим теперь алгоритм конструирования  таблицы, управляющей LR(1)-анализатором.

Пусть G = (N, T, P, S) - КС-грамматика. Пополненной  грамматикой для данной грамматики G называется КС-грамматика

т.е. эквивалентная грамматика, в которой введен новый начальный  символ S' и новое правило вывода S'  S.

Это дополнительное правило вводится для того, чтобы определить, когда  анализатор должен остановить разбор и зафиксировать допуск входа. Таким  образом, допуск имеет место тогда  и только тогда, когда анализатор готов осуществить свертку по правилу S'  S.

LR(1)-ситуацией называется пара [A    . , a], где A     - правило грамматики, a - терминал или правый концевой маркер $. Вторая компонента ситуации называется аванцепочкой.

Будем говорить, что LR(1)-ситуация [A    . , a] допустима для активного префикса  , если существует вывод S  _r^* Aw  _r w, где   =   и либо a - первый символ w, либо w = e и a = $.

Будем говорить, что ситуация допустима, если она допустима для какого-либо активного префикса.

Пример 4.9. Рассмотрим грамматику G = ({S, B}, {a, b}, P, S) с правилами

	S   BB
	B   aB | b

Существует правосторонний вывод S  _r^*aaBab   _raaaBab. Легко видеть, что ситуация [B   a.B, a] допустима для активного префикса   = aaa, если в определении выше положить   = aa, A = B, w = ab,   = a,   = B. Существует также правосторонний вывод S  _r^*BaB   _rBaaB. Поэтому для активного префикса Baa допустима ситуация [B   a.B, $].

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

Анализатор, работающий слева-направо  по типу сдвиг-свертка, должен уметь  распознавать основы на верхушке магазина. Состояние автомата после прочтения  содержимого магазина и текущий  входной символ определяют очередное  действие автомата. Функцией переходов  этого конечного автомата является функция переходов LR-анализатора. Чтобы не просматривать магазин на каждом шаге анализа, на верхушке магазина всегда хранится то состояние, в котором должен оказаться этот конечный автомат после того, как он прочитал символы грамматики в магазине от дна к верхушке.

Рассмотрим ситуацию вида [A    .B , a] из множества ситуаций, допустимых для некоторого активного префикса z. Тогда существует правосторонний вывод S  _r^*yAax  _ry B ax, где z = y . Предположим, что из  ax выводится терминальная строка bw. Тогда для некоторого правила вывода вида B   q имеется вывод S  _r^*zBbw  _rzqbw. Таким образом [B   .q, b] также допустима для z и ситуация [A    B. , a] допустима для активного префикса zB. Здесь либо b может быть первым терминалом, выводимым из  , либо из   выводится e в выводе  ax  _r^*bw и тогда b равно a. Т.е. b принадлежит FIRST( ax). Построение всех таких ситуаций для данного множества ситуаций, т.е. его замыкание, делает приведенная ниже функция closure.

Система множеств допустимых LR(1)-ситуаций для всевозможных активных префиксов  пополненной грамматики называется канонической системой множеств допустимых LR(1)-ситуаций. Алгоритм построения канонической системы множеств приведен ниже.

Алгоритм 4.9. Конструирование канонической системы  множеств допустимых LR(1)-ситуаций.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Каноническая система C множеств допустимых LR(1)-ситуаций для грамматики G.

Метод. Заключается в выполнении для  пополненной грамматики G' процедуры items, которая использует функции closure и goto.

function closure(I){ /* I - множество ситуаций */

do{

for (каждой ситуации [A    .B , a] из I,

каждого правила вывода B     из G',

каждого терминала b из FIRST( a),

такого, что [B   . , b] нет в I)

добавить [B   . , b] к I;

}

while (к I можно добавить новую ситуацию);

return I;

} 

 

function goto(I,X){ /* I - множество ситуаций;

X - символ грамматики */

Пусть J = {[A    X. , a] | [A    .X , a]   I};

return closure(J);

} 

 

procedure items(G'){ /* G' - пополненная грамматика */

I₀ = closure({[S'  .S, $]});

C = {I₀};

do{

for (каждого множества ситуаций I из  системы C,

каждого символа грамматики X такого,

что goto(I, X) не пусто и не принадлежит C)

добавить goto(I, X) к системе C;

}

while (к C можно добавить новое множество  ситуаций);

Если I - множество ситуаций, допустимых для некоторого активного префикса  , то goto(I, X) - множество ситуаций, допустимых для активного префикса  X.