Лекции по конструированию компиляторов. В.А. Серебряков (1134687), страница 7

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

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

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 из магазина.

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

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

3.3.1. Основа

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

S S S
/ | \
X1 X2...
/ |
............
/ |
Y Y |
/|\ /|\ Z
/ ... / ... /|\
a.........$ a...........$ a.......b.......$

а) б) в)

Рис. 3.13

Пример 3.5. Рассмотрим грамматику арифметических выражений, приведенную на рис. 3.14 а). Строка а+b*c может быть сведена к S, как показано на рис. 3.14.б). Дерево этой строки приведено на рис. 3.14 в).

В строке a+b*c ищется подстрока, которую можно сопоставить с правой частью некоторого правила вывода. Этому удовлетворяют подстроки a, b и c. Если выбрать самое левое a и заменить его на F - левую часть правила F->id, то получим строку F+b*c. Теперь правой части того же правила можно сопоставить подстроки b и c. Эти свертки представляют собой в обратном порядке правосторонний вывод:

E->E+T->E+T*F->E+T*c->E+F*c->E+b*c->T+b*c->F+b*c->a+b*c

E -> E + T а+b*c E
E -> T F+b*c /+\
T -> T*F T+b*c E T
T -> F E+b*c | |\
F -> id E+F*c T T *
E+T*c | | \
E+T*F F F F
E+T | | \
E id id id
| | |
a b c

а) б) в)
Рис. 3.14

Подстрока сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода, называется основой строки. В приведенном выше выводе основы выделены. Самая левая подстрока, которая сопоставляется правой части некоторого правила вывода A->v, не обязательно является основой, поскольку свертка по правилу A->v может дать строку, которая не может быть сведена к аксиоме. Если, скажем, в примере 3.5 заменить a на F и b на F, то получим строку F+F*c, которая не может быть сведена к S.

Формально, основа правой сентенциальной формы z - это правило вывода A->v и позиция в z, в которой может быть найдена строка v такие, что в результате замены v на A получается предыдущая сентенциальная форма в правостороннем выводе z. Таким образом, если S=>*uAw=>uvw, то A->v в позиции, следующей за u, это основа строки uvw. Строка w справа от основы содержит только терминальные символы. Вообще говоря, грамматика может быть неоднозначной, поэтому не единственным может быть правосторонний вывод uvw и не единственной может быть основа. Если грамматика однозначна, то каждая правая сентенциальная форма грамматики имеет в точности одну основу. Замена основы в сентенциальной форме на нетерминал левой части называется отсечением основы. Обращение правостороннего вывода может быть получено с помощью повторного применения отсечения основы, начиная с разбираемой строки w. Если w - слово в рассматриваемой грамматике, то w=Z_n, n-я правая сентенциальная форма еще неизвестного правого вывода

S = Z₀ => Z₁ => Z₂ => ... => Z_n-1 => Z_n =w.

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

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

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

Список файлов лекций