LL17 (1131464)

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

Текст из файла

Глава 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, будем говорить, что из u₁ выводится u_n, и записывать это как u₁=>*u_n. Т.е.:

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,e₁),(v,e₂),...,(v,e_n)). Этот элемент указывает, что из вершины a выходят n дуг, причем первой из них считается дуга, входящая в вершину e₁, второй - дуга, входящая в вершину e₂, и т.д.

Дерево вывода в грамматике G=<N,T,P,S> - это помеченное упорядоченное дерево, каждая вершина которого помечена символом из множества N U T U {e}. Если внутренняя вершина помечена символом A, а ее прямые потомки - символами X₁,..., X_n, то A->X₁X₂...X_n - правило этой грамматики.

Упорядоченное помеченное дерево D называется деревом вывода (или деревом разбора) в КС-грамматике G(S)=(N,T,P,S), если выполнены следующие условия:

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

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

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

(4) если N - нетерминал, которым помечена внутренняя вершина и X₁,...,X_n - метки ее прямых потомков в указанном порядке, то N->X₁...X_k - правило из множества P.

Автомат с магазинной памятью (сокращенно МП-автомат) - это семерка P=<Q,T,Г,D,q₀,Z₀,F>, где

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

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

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

(4) D - функция переходов - отображение множества Qx(T U {e})xГ в множество конечных подмножеств QxГ*, т.е. d:Qx(T U {e})xГ -> {QxГ*};

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

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

(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 называется конфигурация вида <q₀,w,Z_0>, где w<-T*, т.е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно распознать, а в магазине есть только начальный символ Z₀. Заключительная конфигурация - это конфигурация вида <q,e,u>, где q<-F, u<-Г*.

Говорят, что цепочка w допускается МП-автоматом P, если <q₀,w,Z_0>|-*<q,e,u> для некоторых q<-F и u<-Г*. Языком, определяемым (или допускаемым) автоматом P (обозначается L(P)), называют множество цепочек, допускаемых автоматом P.

Иногда допустимость определяют несколько иначе: цепочка w допускается МП-автоматом P, если <q₀,w,Z_0>|-*<q,e,e>. Эти определения эквивалентны.

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

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

Основная проблема предсказывающего разбора - определение правила вывода, которое нужно применить к нетерминалу. Процесс предсказывающего разбора (сверху-вниз) с точки зрения построения дерева разбора можно проиллюстрировать рис. 3.1. Фрагменты недостроенного дерева соответствуют сентенциальным формам вывода. Вначале дерево состоит только из одной вершины, соответствующей аксиоме S. В этот момент по первому символу входного потока предсказывающий анализатор должен определить правило S->X₁ X₂ ..., которое должно быть применено к S. Затем необходимо определить правило, которое должно быть применено к X₁, и т.д., до тех пор, пока в процессе такого построения сентенциальной формы, соответствующей левому выводу, не будет применено правило Y->a .... Этот процесс затем применяется для следующего самого левого нетерминального символа сентенциальной формы

S S S
/ | \ / | \
X1 X2... X1 X2...
/ / |
........... .............
/ / |
Y Y |
/|\ /|\ Z
/ ... / ... /|\
a..........$ a...........$ a.....................b.......$
а) б) в)
Рис. 3.1

На рис. 3.2 приведена структура предсказывающего анализатора, который определяет очередное правило из таблицы. Такую таблицу множно построить непосредственно из грамматики.

Вход a + b $


X Программа предсказы- Выход
Магазин вающего анализатора
Y
Z

$ Таблица анализатора

Рис. 3.2

Таблично-управляемый предсказывающий анализатор имеет входной буфер, таблицу анализа и выход. Входной буфер содержит распознаваемую строку, за которой следует $ - правый концевой маркер, признак конца строки. Магазин содержит последовательность символов грамматики с $ на дне. Вначале магазин содержит начальный символ грамматики на верхушке и $ на дне. Таблица анализа - это двумерный массив M[A,a], где A - нетерминал, и a - терминал или символ $.

Анализатор управляется программой, которая работает следующим образом. Она рассматривает X - символ на верхушке магазина и a - текущий входной символ. Эти два символа определяют действие анализатора. Имеются три возможности.

1. Если X=a=$, анализатор останавливается и сообщает об успешном окончании разбора.

2. Если X=a#$, анализатор удаляет X из магазина и продвигает указатель входа на следующий входной символ.

3. Если X - нетерминал, программа заглядывает в таблицу M[X,a]. По этому входу хранится либо правило для X, либо ошибка. Если, например, M[X,a]={X->UVW}, анализатор заменяет X на верхушке магазина на WVU {на верхушке U}. Будем считать, что анализатор в качестве выхода просто печатает использованные правила вывода. Если M[X,a]=error, анализатор обращается к подпрограмме анализа ошибок.

Поведение анализатора может быть описано в терминах конфигураций автомата разбора.

Алгоритм 3.1. Нерекурсивный предсказывающий анализ.

do
{X=верхний символ магазина;
if (X <- T|| X==`$`)
if (X==InSym)
{удалить X из магазина;
InSym=очередной символ;
}
else error();
else /*X - нетерминал*/
if (M[X,InSym]==“X->Y₁Y₂...Y_k“)
{удалить X из магазина;
поместить Y_k,Y_k-1,...Y₁ в магазин
(Y₁ на верхушку);
вывести правило X->Y₁Y₂...Y_k;
_}
else error(); /*вход таблицы M пуст*/
}
while (X!=$) /*магазин пуст*/

Рис. 3.3

Вначале анализатор находится в конфигурации, в которой магазин содержит S$, (S - начальный символ грамматики), во входном буфере w$ (w - входная цепочка), переменная InSym содержит первый символ входной строки. Программа, использующая таблицу анализатора M для осуществления разбора, изображена на рис. 3.3.

Пример 3.1. Рассмотрим грамматику арифметических выражений:

E -> T E'
E' -> + T E' | e
T -> F T'
T' -> * F T' | e
F -> ( E ) | id

Таблица предсказывающего анализатора для нее изображена на рис. 3.4. Здесь пустые клетки - входы ошибок. Непустые дают правила, по которым делается развертка нетерминала.

Нетер- Входной символ

минал id + * ( ) $

E E->TE' E->TE'
E' E'->+TE' E'->e E'->e
T T->FT' T->FT'
T' T'->e T'->*FT' T'->e T'->e
F F->id F->(E)

Рис. 3.4

М агазин Вход Выход

$E d+id*id$
$E'T d+id*id$ E->TE'
$E'T'F d+id*id$ T->FT'
$E'T'id id+id*id$ F->id
$E'T' +id*id$ E
$E' +id*id$ T'->e
$E'T+ +id*id$ E'->+TE`
$E'T id*id$ T E'
$E'T'F id*id$ T->FT'
$E'T'id id*id$ F->id F T' + T E'
$E'T' *id$
$E'T'F* *id$ T'->*FT' id
$E'T'F id$ F T'
$E'T'id id$ F->id
$E'T' $ id * F T'
$E' $ T'->e
$ $ E'->e id

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

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