LL17 (1131464), страница 3

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

Текст из файла (страница 3)

A -> u A'
A' -> v₁ | v₂

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

Для каждого нетерминала A ищем самый длинный префикс u, общий для двух или более его альтернатив. Если u#e, т.е. существует нетривиальный общий префикс, заменяем все A-правила A->uv₁ | uv₂ | ... | uv_n | z, где z - все альтернативы, не начинающиеся с u, на

A -> uA' | z
A' -> v₁ | v₂ | ... | v_n

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

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

St -> if Ex then St
| if Ex then St else St
| Cont
Ex -> ...

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

St -> if Ex then St St'
| Cont
St' -> else St | e
Ex -> ...

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

St

St
St St'

St St'
St’

if E then if E then S else S if E then if E then S S' else S

а) б)

Рис. 3.8

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

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

void N()/*N -> u₁ | u₂ | ... |u_k*/
{if (InSym<-FIRST(u_i))//только одному!
if (parse(u_i))
result(“N->u_i”);
else error();
else
//Вариант 1:
if (имеется правило N->u_i =>* e)
//Вариант 1.1
if (InSym<-FOLLOW(N))
result(“N->u_i“);
else error();
/_{/Конец варианта 1.1}

//Вариант 1.2:
result(“N->u_i“)_{;
//Конец варианта 1.2
//Конец варианта 1}
Вариант 2:
if (нет правила N->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);
}
Рис. 3.9

3.2.8. Диаграммы переходов для рекурсивного спуска

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

Пусть имеется LL(1)-грамматика. Тогда для каждого нетерминала построение диаграммы включает следующие шаги.

Шаг 1. Вводим начальное и заключительное состояния.

Шаг 2. Для каждого правила вывода A->X₁X₂...X_n строим путь из начального в конечное состояние с дугами, помеченными X₁,...,X_n. Если анализатор, построенный по диаграмме переходов, оказывается в состоянии s и дуга, помеченная терминалом a, ведет в состояние t, то если очередной входной символ равен a, анализатор продвигает вход на одну позицию вправо и переходит в состояние t. Если же дуга помечена нетерминалом A, анализатор входит в начальное состояние для A без продвижения входа. После того как он достигает заключительного состояния для A, он переходит в состояние t, что означает "чтение" A из входа при переходе из состояния s в состояние t. Наконец, если есть дуга из s в t, помеченная e, то анализатор переходит из s в t, не читая входа.

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

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

T E` + T E`
E: 0 1 2 E`: 3 4 5 6

e

F T` * F T`
T: 7 8 9 T`: 10 11 12 13

e

( E )

F: 14 15 16 17

id

Рис. 3.10

e T

+ T +

E` 3 4 5 E` 3 4

e e

6 6

e +

+ T T e

E: 0 3 4 E: 3 4 6

e

6 6

Рис. 3.11

+ *

T e F e

E: 0 3 6 T: 7 8 13

( E )

F: 14 15 16 17

id

Рис. 3.12

На рис 3.11 приведена эквивалентная диаграмма переходов для E'. Можно подставить диаграмму для E' рис.3.11 в диаграмму для E рис. 3.10. Получится диаграмма рис. 3.11 для E. Наконец, видно, что в этой диаграмме нулевая и четвертая вершины эквивалентны и их можно слить. Так же можно поступить с диаграммами для T и T'. В результате получится набор диаграмм рис. 3.12.

Такое преобразование эквивалентно описанию грамматики расширенными формулами Бэкуса-Наура, в которых помимо собственно рекурсивных определений допускаются описания повторений. При программировании рекурсивного спуска такая диаграмма для E записывается очевидным образом:

procedure E; repeat T; until InSym<>PLUS;

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

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

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

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

51

Характеристики

Список файлов ответов (шпаргалок)