CONSCOMP (Материалы к контрольным работам), страница 8

целая константа, понимаемая синтаксическим анализатором как

лексема 'if'. Аналогично обрабатываются ключевые слова 'then'

и 'else' в двух следущих правилах.

В действии, связанном с правилом для id, два оператора.

Переменной yylval присваивается значение, возвращаемое

процедурой install_id. Определение этой процедуры приведено в

разделе 3.1. Переменная yylval определена в программе

lex.yy.c, выходе lex, и она доступна синтаксическому

анализатору. yylval хранит возвращаемое лексическое значение,

поскольку второй оператор в действии, return(id), может только

возвратить код класса лексем.

Функция install_id заносит идентификаторы в таблицу

символов. Текущая лексема доступна благодаря двум указателям:

yytext и yyleng. Переменная yytext - это указатель на первый

символ лексемы, yyleng - это целое, дающее длину лексемы.

Например, при занесении идентификатора в таблицу могут быть

скопированы yyleng символов, начиная с yytext.

Аналогично обрабатываются числа в следующем правиле. В

последних шести правилах yylval используется для возврата кода

операции отношения, возвращаемое же функцией значение - это

код лексемы relop.

Если, например, в текущий момент лексический анализатор

обрабатывает лексему 'if', то этой лексеме соответствуют два

образца: 'if' и {id} и более длинной строки, соответствующей

образцу, нет. Поскольку образец 'if' предшествует образцу для

идентификатора, конфликт разрешается в пользу ключевого слова.

Такая стратегия разрешения конфликтов позволяет легко

резервировать ключевые слова.

Если на входе встречается '<=', то первому символу

соответствует образец '<', но это не самый длинный образец,

который соответствует префиксу входа. Стратегия выбора самого

длинного префикса легко разрешает такого рода конфликты.

Глава 3. Синтаксический анализ

3.1. Основные понятия и определения

Пусть g=<n,t,p,s> - контекстно-свободная грамматика, где n -

множество нетерминальных символов, t - множество терминальных

символов, p - множество правил вывода и s - аксиома. Будем

говорить, что uxv выводится за один шаг из uav (и записывать

это как uav=>uxv), если a->x - правило вывода и u и v -

произвольные строки из (n u t)*. Если u1=>u2=>...=>un, будем

говорить, что из u1 выводится un, и записывать это как

u1=>*un. Т.е.:

1) u=>*u для любой строки u,

2) если u=>*v и v=>*w, то u=>*w.

Аналогично, "=>+" означает выводится за один или более шагов.

Если дана грамматика g с начальным символом s, отношение =>+

можно использовать для определения l(g) - языка, порожденного

g. Строки l(g) могут содержать только терминальные символы g.

Строка терминалов w принадлежит l(g) тогда и только тогда,

когда s=>+w. Строка w называется предложением в g.

Если s=>*u, где u может содержать нетерминалы, то u

называется сентенциальной формой в g. Предложение - это

сентенциальная форма, не содержащая нетерминалов.

Рассмотрим выводы, в которых в любой сентенциальной форме на

каждом шаге делается подстановка самого левого нетерминала.

Такой вывод называется левосторонним. Если s=>*u в процессе

левостороннего вывода, то u - левая сентенциальная форма.

Аналогично определяется правосторонний вывод.

Упорядоченным графом называется пара (v,e), где v обозначает

множество вершин, а e - множество линейно упорядоченных

списков дуг, каждый элемент которого имеет вид

((v,e1),(v,e2),...,(v,en)). Этот элемент указывает, что из

вершины a выходят n дуг, причем первой из них считается дуга,

входящая в вершину e1, второй - дуга, входящая в вершину e2, и

т.д.

Дерево вывода в грамматике g=(n,t,p,s) - это помеченное

упорядоченное дерево, каждая вершина которого помечена

символом из множества n u t u {e}. Если внутренняя вершина

помечена символом a, а ее прямые потомки - символами x1,...,

xn, то a->x1x2...xn - правило этой грамматики.

Упорядоченное помеченное дерево d называется деревом вывода

(или деревом разбора) в КС-грамматике g(s)=(n,t,p,s), если

выполнены следующие условия:

(1) корень дерева d помечен s;

(2) каждый лист помечен либо a<-t, либо e;

(3) каждая внутренняя вершина помечена нетерминалом;

(4) если n - нетерминал, которым помечена внутренняя вершина

и x1,...,xn - метки ее прямых потомков в указанном

порядке, то n->x1...xk - правило из множества p.

Автомат с магазинной памятью (сокращенно МП-автомат) - это

семерка p=(q,t,Г,d,q0,z0,f), где

(1) q - конечное множество символов состояний,

представляющих всевозможные состояния управляющего

устройства;

(2) t - конечный входной алфавит;

(3) Г - конечный алфавит магазинных символов;

(4) d - функция переходов - отображение множества qx(t u

{e})xГ в множество конечных подмножеств qxГ*, т.е. d:qx(t

u {e})xГ -> {qxГ*};

(5) q0<-q - начальное состояние управляющего устройства;

(6) z0<-Г - символ, находящийся в магазине в начальный

момент (начальный символ);

(7) f<=q - множество заключительных состояний

Конфигурацией МП-автомата называется тройка (q,w,u)<-qxt*xГ*,

где

(1) q - текущее состояние управляющего устройства;

(2) w - неиспользованная часть входной цепочки; первый

символ цепочки w находится под входной головкой; если w

e, то считается, что вся входная лента прочитана;

(3) u - содержимое магазина; самый левый символ цепочки u

считается верхним символом магазина; если u=e, то магазин

считается пустым.

Такт работы МП-автомата p будем представлять в виде бинарного

отношения |-, определенного на конфигурациях. Будем писать

(q,aw,zu)|-(q',w,vu)

если множество d(q,a,z) содержит (q',v), где q, q'<-q, a<-t u

{e}, w<-t*, z<-Г, u,v<-Г*.

Начальной конфигурацией МП-автомата p называется

конфигурация вида (q0,w,z0), где w<-t*, т.е. управляющее

устройство находится в начальном состоянии, входная лента

содержит цепочку, которую нужно распознать, а в магазине есть

только начальный символ z0. Заключительная конфигурация - это

конфигурация вида (q,e,u), где q<-f, u<-Г*.

Говорят, что цепочка w допускается МП-автоматом p, если

(q0,w,z0)|-*(q,e,u) для некоторых q<-f и u<-Г*. Языком,

определяемым (или допускаемым) автоматом p (обозначается

l(p)), называют множество цепочек, допускаемых автоматом p.

Иногда допустимость определяют несколько иначе: цепочка w

допускается МП-автоматом p, если (q0,w,z0)|-*(q,e,e). Эти

определения эквивалентны.

3.2. Таблично-управляемый предсказывающий разбор

3.2.1. Алгоритм разбора сверху-вниз

Основная проблема предсказывающего разбора - определение

правила вывода, которое нужно применить к нетерминалу. Процесс

предсказывающего разбора (сверху-вниз) с точки зрения

построения дерева разбора можно проиллюстрировать рис. 3.1.

Фрагменты недостроенного дерева соответствуют сентенциальным

формам вывода. Вначале дерево состоит только из одной вершины,

соответствующей аксиоме s. В этот момент по первому символу

входного потока предсказывающий анализатор должен определить

правило s->x1 x2 ..., которое должно быть применено к s. Затем

необходимо определить правило, которое должно быть применено к

x1, и т.д., до тех пор, пока в процессе такого построения

сентенциальной формы, соответствующей левому выводу, не будет

применено правило y->a .... Этот процесс затем применяется для

следующего самого левого нетерминального символа