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

Рассмотрим  алгоритм вычисления функции FOLLOW.

Алгоритм 4.5. Вычисление FOLLOW для нетерминалов грамматики.

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

Выход. Множество FOLLOW(X) для каждого символа X   N.

Метод. Выполнить шаги 1-4:

• Положить FOLLOW(X) =   для каждого символа X   N.
• Добавить $ к FOLLOW(S).
• Если в P eсть правило вывода A    B , где  ,     (N T)^* то все элементы из FIRST( ), за исключением e, добавить к FOLLOW(B).
• Пока ничего нельзя будет добавить ни к какому множеству FOLLOW(X), выполнять:

если в P есть правило A    B или A    B ,  ,     (N T)^*, где FIRST( ) содержит e (т.е.    ^*e), то все элементы из FOLLOW(A) добавить к FOLLOW(B).

Пример 4.4. Рассмотрим грамматику из примера 4.3. Для нее

	FIRST(E) = FIRST(T) = FIRST(F) = {(, id}
	FIRST(E') = {+, e}
	FIRST(T') = {*, e}
	FOLLOW(E) = FOLLOW(E') = { ), $}
	FOLLOW(T) = FOLLOW(T') = {+, ), $}
	FOLLOW(F) = {+, *, ), $}

Например, id и левая скобка добавляются  к FIRST(F) на шаге 3 при i = 1, поскольку FIRST(id) = {id} и FIRST(”(”) = {”(”} в соответствии с шагом 1. На шаге 3 при i = 1, в соответствии с правилом вывода T  FT' к FIRST(T) добавляются также id и левая скобка. На шаге 2 в FIRST(E') включается e.

При вычислении множеств FOLLOW на шаге 2 в FOLLOW(E) включается $. На шаге 3, на основании  правила F   (E), к FOLLOW(E) добавляется также правая скобка. На шаге 4, примененном к правилу E  TE', в FOLLOW(E') включаются $ и правая скобка. Поскольку E' ^*e, они также попадают и во множество FOLLOW(T). В соответствии с правилом вывода E   TE', на шаге 3 в FOLLOW(T) включаются и все элементы из FIRST(E'), отличные от e.

4.3.3 Конструирование таблицы предсказывающего  анализатора

Для конструирования таблицы предсказывающего анализатора по грамматике G может  быть использован алгоритм, основанный на следующей идее. Предположим, что A     - правило вывода грамматики и a  FIRST( ). Тогда анализатор делает развертку A по  , если входным символом является a. Трудность возникает, когда   = e или     ^*e. В этом случае нужно развернуть A в  , если текущий входной символ принадлежит FOLLOW(A) или если достигнут $ и $   FOLLOW(A).

Алгоритм 4.6. Построение таблицы предсказывающего анализатора.

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

Выход. Таблица M[A, a] предсказывающего анализатора, A   N, a   T  {$}.

Метод. Для каждого правила вывода A     грамматики выполнить шаги 1 и 2. После этого выполнить шаг 3.

• Для каждого терминала a из FIRST( ) добавить A     к M[A, a].
• Если e   FIRST( ), добавить A     к M[A, b] для каждого терминала b из FOLLOW(A). Кроме того, если e   FIRST( ) и $   FOLLOW(A), добавить A     к M[A, $].
• Положить все неопределенные входы равными «ошибка».

Пример 4.5. Применим алгоритм 4.6 к грамматике из примера 4.3. Поскольку FIRST(TE') = FIRST(T) = {(, id }, в соответствии с правилом вывода E   TE' входы M[E, ( ] и M[E, id ] становятся равными E   TE'.

В соответствии с правилом вывода E'  +TE' значение M[E', +] равно E'  +TE'. В соответствии с правилом вывода E'   e значения M[E', )] и M[E', $] равны E'  e, поскольку FOLLOW(E') = { ), $}.

Таблица анализа, построенная алгоритмом 4.6 для этой грамматики, приведена  на рис. 4.3.

4.3.4 LL(1)-грамматики

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

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

Доказано, что алгоритм 4.6 для каждой LL(1)-грамматики G строит таблицу предсказывающего анализатора, распознающего все  цепочки из L(G) и только эти цепочки. Нетрудно доказать также, что если G - LL(1)-грамматика, то L(G) - детерминированный  КС-язык.

Справедлив также следующий  критерий LL(1)-грамматики. Грамматика G = (N, T, P, S) является LL(1)-грамматикой тогда  и только тогда, когда для каждой пары правил A    , A     из P (т.е. правил с одинаковой левой частью) выполняются следующие 2 условия:

• FIRST( )   FIRST( ) =  ;
• Если e   FIRST( ), то FIRST( )   FOLLOW(A) =  .

Язык, для которого существует порождающая  его LL(1)-грамматика, называют LL(1)-языком. Доказано, что проблема определения  того, порождает ли грамматика LL-язык, является алгоритмически неразрешимой.

Пример 4.6. Неоднозначная грамматика не является LL(1). Примером может служить следующая грамматика G = ({S, E}, {if, then, else, a, b}, P, S) с правилами:

	S   if E then S | if E then S else S | a
	E   b

Эта грамматика является неоднозначной, что иллюстрируется на рисунке 4.6.

Рисунок 4.6:

4.3.5 Удаление левой рекурсии

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

Непосредственную левую рекурсию, т.е. рекурсию вида A   A , можно удалить следующим способом. Сначала группируем A-правила:

где никакая из строк  _i не начинается с A. Затем заменяем этот набор правил на

где A' - новый нетерминал. Из нетерминала A можно вывести те же цепочки, что и раньше, но теперь нет левой рекурсии. С помощью  этой процедуры удаляются все  непосредственные левые рекурсии, но не удаляется левая рекурсия, включающая два или более шага. Приведенный  ниже алгоритм 4.7 позволяет удалить  все левые рекурсии из грамматики.

Алгоритм 4.7. Удаление левой рекурсии.

Вход. КС-грамматика G без e-правил (правил вида A   e).

Выход. КС-грамматика G' без левой рекурсии, эквивалентная G.

Метод. Выполнить шаги 1 и 2.

• Упорядочить нетерминалы грамматики G в произвольном порядке.
• Выполнить следующую процедуру:

for (i=1;i<=n;i++){

for (j=1;j<=i-1;j++){

пусть A_{j    1} |  ₂ | ... |  _k - все текущие правила для A_j;

заменить все правила вида A_i   A_j

на правила A_{i    1}  |  ₂  | ... |  _k ;

}

удалить правила вида A_i   A_i;

удалить непосредственную левую рекурсию в правилах для A_i;

}

После (i - 1)-й итерации внешнего цикла  на шаге 2 для любого правила вида A_k   A_s , где k < i, выполняется s > k. В результате на следующей итерации (по i) внутренний цикл (по j) последовательно увеличивает нижнюю границу по m в любом правиле A_i   A_m , пока не будет m   i. Затем, после удаления непосредственной левой рекурсии для A_i-правил, m становится больше i.

Алгоритм 4.7 применим, если грамматика не имеет e-правил (правил вида A   e). Имеющиеся в грамматике e-правила могут быть удалены предварительно. Получающаяся грамматика без левой рекурсии может иметь e-правила.

4.3.6 Левая факторизация

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

Если A    ₁ |  ₂ - два A-правила и входная цепочка начинается с непустой строки, выводимой из  , мы не знаем, разворачивать ли по первому правилу или по второму. Можно отложить решение, развернув A    A'. Тогда после анализа того, что выводимо из  , можно развернуть по A'   ₁ или по A'   ₂. Левофакторизованные правила принимают вид

Алгоритм 4.8. Левая факторизация грамматики.

Вход. КС-грамматика G.

Выход. Левофакторизованная КС-грамматика G', эквивалентная G.

Метод. Для каждого нетерминала A ищем самый  длинный префикс  , общий для двух или более его альтернатив. Если  e, т.е. существует нетривиальный общий префикс, заменяем все A-правила

где z обозначает все альтернативы, не начинающиеся с  , на

где A' - новый нетерминал. Повторно применяем это преобразование, пока никакие две альтернативы не будут иметь общего префикса.

Пример 4.7. Рассмотрим вновь грамматику условных операторов из примера 4.6:

	S   if E then S | if E then S else S | a
	E   b

После левой факторизации грамматика принимает  вид

	S   if E then SS'| a
	S'  else S | e
	E   b

К сожалению, грамматика остается неоднозначной, а  значит, и не LL(1).

4.3.7 Рекурсивный спуск

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

В процедуре A для случая, когда  имеется правило A   u_i, такое, что u_i  ^*e (напомним, что не может быть больше одного правила, из которого выводится e), приведены два варианта 1.1 и 1.2. В варианте 1.1 делается проверка, принадлежит ли следующий входной символ FOLLOW(A). Если нет - выдается ошибка. Во втором варианте этого не делается, так что анализ ошибки откладывается на процедуру, вызвавшую A.

void A(){ // A   u₁ | u₂ | ...| u_k

if (InSym   FIRST(u_i)) // только одному!

if (parse(u_i))

result("A   u_i");

else error();

else

//Вариант  1:

if (имеется  правило A   u_i такое, что u_i  ^*e)

//Вариант 1.1

if (InSym   FOLLOW(A))

result("A   u_i");

else error();

//Конец  варианта 1.1

//Вариант  1.2:

result("A   u_i");

//Конец  варианта 1.2

//Конец  варианта 1

//Вариант  2:

if (нет  правила A   u_i такого, что u_i  ^*e)

error();

//Конец  варианта 2

} 

 

boolean parse(u){ // из u не выводится e!

v = u;

while (v e){ // v = Xz

if (X - терминал a)

if (InSym a)

return(false);

else InSym = getInsym();

else // X - нетерминал B

B();

v = z;

}

return(true);

}

4.3.8 Восстановление после синтаксических  ошибок

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

Если в момент обнаружения ошибки на верхушке магазина оказался нетерминальный символ A и для него нет правила, соответствующего входному символу, то сканируем вход до тех пор, пока не встретим символ либо из FIRST(A), либо из FOLLOW(A). В первом случае разворачиваем A по соответствующему правилу, во втором - удаляем A из магазина.

Если на верхушке магазина терминальный символ, то можно удалить все терминальные символы с верхушки магазина вплоть до первого (сверху) нетерминального  символа и продолжать так, как  это было описано выше.

 

 

4.4 Разбор снизу-вверх типа сдвиг-свертка

4.4.1 Основа

В процессе разбора снизу-вверх  типа сдвиг-свертка строится дерево разбора входной цепочки, начиная  с листьев (снизу) к корню (вверх). Этот процесс можно рассматривать  как «свертку» цепочки w к начальному символу грамматики. На каждом шаге свертки подцепочка, которую можно  сопоставить правой части некоторого правила вывода, заменяется символом левой части этого правила  вывода, и если на каждом шаге выбирается правильная подцепочка, то в обратном порядке прослеживается правосторонний вывод (рис. 4.7). Здесь ко входной цепочке, так же как и при анализе LL(1)-грамматик, приписан концевой маркер $.

Рисунок 4.7

Подцепочка сентенциальной формы, которая может быть сопоставлена правой части некоторого правила  вывода, свертка по которому к левой  части правила соответствует  одному шагу в обращении правостороннего  вывода, называется основой цепочки. Самая левая подцепочка, которая  сопоставляется правой части некоторого правила вывода A    , не обязательно является основой, поскольку свертка по правилу A     может дать цепочку, которая не может быть сведена к аксиоме.