В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1134643), страница 9
Текст из файла (страница 9)
Согласно первому правилу, если обнаружено ws, т.е. максимальная последовательность пробелов, табуляций и новых строк, никаких действий не производится. В частности, не осуществляется возврат в синтаксический анализатор.Согласно второму правилу, если обнаружена последовательность букв “if”,нужно вернуть значение IF, которое определено как целая константа, понимаемая синтаксическим анализатором как лексема “if”. Аналогично обрабатываются ключевые слова “then” и “else” в двух следущих правилах.В действии, связанном с правилом для id, два оператора. Переменной yylvalприсваивается значение, возвращаемое процедурой install_id.
Переменная yylvalопределена в программе lex.yy.c, выходе LEX, и она доступна синтаксическомуанализатору. yylval хранит возвращаемое лексическое значение, поскольку второй оператор в действии, return(ID), может только возвратить код класса лексем.Функция install_id заносит идентификаторы в таблицу символов.Аналогично обрабатываются числа в следующем правиле. В последних шести правилах yylval используется для возврата кода операции отношения, возвращаемое же функцией значение – это код лексемы relop.Если, например, в текущий момент лексический анализатор обрабатываетлексему “if”, то этой лексеме соответствуют два образца: “if” и {id} и более длинной строки, соответствующей образцу, нет. Поскольку образец “if” предшествует образцу для идентификатора, конфликт разрешается в пользу ключевого слова.
Такая стратегия разрешения конфликтов позволяет легко резервировать ключевые слова.Если на входе встречается “<=”, то первому символу соответствует образец“<”, но это не самый длинный образец, который соответствует префиксу входа.Стратегия выбора самого длинного префикса легко разрешает такого рода конфликты.48ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗГлава 4Синтаксический анализ4.1КС-грамматики и МП-автоматыПусть G = (N, T, P, S) – контекстно-свободная грамматика.
Введем несколько важных понятий и определений.Вывод, в котором в любой сентенциальной форме на каждом шагеделается подстановка самого левого нетерминала, называется левосторонним. Если S ⇒∗ u в процессе левостороннего вывода, то u – леваясентенциальная форма. Аналогично определяется правосторонний вывод.
Будем обозначать шаги левого (правого) вывода посредством ⇒l (⇒r ).Упорядоченным графом называется пара (V, E), где V есть множествовершин, а E – множество линейно упорядоченных списков дуг, каждыйэлемент которого имеет вид ((v, v1 ), (v, v2 ), ...
, (v, vn )). Этот элемент указывает, что из вершины v выходят n дуг, причем первой из них считается дуга, входящая в вершину v1 , второй – дуга, входящая в вершину v2 ,и т.д.Упорядоченным помеченным деревом называется упорядоченный граф(V, E), основой которого является дерево и для которого определена функция f : V → F (функция разметки) для некоторого множества F .Упорядоченное помеченное дерево D называется деревом вывода (илидеревом разбора) цепочки w в КС-грамматике G = (N, T, P, S), если выполнены следующие условия:(1) корень дерева D помечен S;(2) каждый лист помечен либо a ∈ T , либо e;(3) каждая внутренняя вершина помечена нетерминалом A ∈ N ;(4) если X – нетерминал, которым помечена внутренняя вершина иX1 , ...
, Xn – метки ее прямых потомков в указанном порядке, тоX → X1 ... Xk – правило из множества P ;4950ГЛАВА 4. СИНТАКСИЧЕСКИЙ АНАЛИЗ(5) Цепочка, составленная из выписанных слева направо меток листьев, равна w.Грамматика G называется неоднозначной, если существует цепочкаw, для которой имеется два или более различных деревьев вывода в G.Грамматика G называется леворекурсивной, если в ней имеется нетерминал A такой, что существует вывод A ⇒+ Aα для некоторой цепочкиα.Автомат с магазинной памятью (МП-автомат) – это семеркаM = (Q, T, Γ, D, q0 , Z0 , F ), где(1) Q – конечное множество состояний, представляющих всевозможные состояния управляющего устройства;(2) T – конечный входной алфавит;(3) Γ – конечный алфавит магазинных символов;(4) D – отображение множества Q × (T ∪ {e}) × Γ в множество всехконечных подмножеств Q × Γ∗ , называемое функцией переходов;(5) q0 ∈ Q – начальное состояние управляющего устройства;(6) Z0 ∈ Γ – символ, находящийся в магазине в начальный момент (начальный символ магазина);(7) F ⊆ Q – множество заключительных состояний.Конфигурацией МП-автомата называется тройка (q, w, u), где(1) q ∈ Q – текущее состояние управляющего устройства;(2) w ∈ T ∗ – непрочитанная часть входной цепочки; первый символцепочки w находится под входной головкой; если w = e, то считается, что вся входная лента прочитана;(3) u ∈ Γ∗ – содержимое магазина; самый левый символ цепочки u считается верхним символом магазина; если u = e, то магазин считается пустым.Такт работы МП-автомата M будем представлять в виде бинарногоотношения `, определенного на конфигурациях.
Будем писать(q, aw, Zu) ` (p, w, vu),если множество D(q, a, Z) содержит (p, v), где q, p ∈ Q, a ∈ T ∪{e}, w ∈ T ∗ ,Z ∈ Γ и u, v ∈ Γ∗ .Начальной конфигурацией МП-автомата M называется конфигурация вида (q0 , w, Z0 ), где w ∈ T ∗ , т.е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую4.1.
КС-ГРАММАТИКИ И МП-АВТОМАТЫ51нужно проанализировать, а в магазине находится только начальный символ Z0 .Заключительная конфигурация – это конфигурация вида (q, e, u), гдеq ∈ F , u ∈ Γ∗ , т.е. управляющее устройство находится в одном из заключительных состояний, а входная цепочка целиком прочитана.Введем транзитивное и рефлексивно-транзитивное замыкание отношения `, а также его степень k > 0 (обозначаемые `+ , `∗ и `k соответственно).Говорят, что цепочка w допускается МП-автоматом M , если(q0 , w, Z0 ) `∗ (q, e, u) для некоторых q ∈ F и u ∈ Γ∗ .Язык, допускаемый (распознаваемый, определяемый) автоматом M(обозначается L(M )) – это множество всех цепочек, допускаемых автоматом M .Пример 4.1. Рассмотрим МП-автоматM = ({q0 , q1 , q2 }, {a, b}, {Z, a, b}, D, q0 , Z, {q2 }),у которого функция переходов D содержит следующие элементы:D(q0 , a, Z) = {(q0 , aZ)},D(q0 , b, Z) = {(q0 , bZ)},D(q0 , a, a) = {(q0 , aa), {q1 , e)},D(q0 , a, b) = {(q0 , ab)},D(q0 , b, a) = {(q0 , ba)},D(q0 , b, b) = {(q0 , bb), (q1 , e)},D(q1 , a, a) = {(q1 , e)},D(q1 , b, b) = {(q1 , e)},D(q1 , e, Z) = {(q2 , e)}.Нетрудно показать, что L(M ) = {wwR |w ∈ {a, b}+ }, где wR обозначает обращение (“переворачивание”) цепочки w.Иногда допустимость определяют несколько иначе: цепочка w допускается МП-автоматом M , если (q0 , w, Z0 ) `∗ (q, e, e) для некоторого q ∈Q.
В таком случае говорят, что автомат допускает цепочку опустошением магазина. Эти определения эквивалентны, ибо справедливаТеорема 4.1. Язык допускается магазинным автоматом тогда и только тогда, когда он допускается (некоторым другим автоматом)опустошением магазина.Доказательство. Пусть L = L(M ) для некоторого МП-автомата M =(Q, T, Γ, D, q0 , Z0 , F ). Построим новый МП-автомат M 0 , допускающий тотже язык опустошением магазина.Пусть M 0 = (Q ∪ {q00 , qe }, T, Γ ∪ {Z00 }, D0 , q00 , Z00 , ∅), где функция переходов D0 определена следующим образом:1. Если (r, u) ∈ D(q, a, Z), то (r, u) ∈ D0 (q, a, Z) для всех q ∈ Q, a ∈T ∪ {e} и Z ∈ Γ;52ГЛАВА 4. СИНТАКСИЧЕСКИЙ АНАЛИЗ2. D0 (q00 , e, Z00 ) = {(q0 , Z0 Z00 )};3.
Для всех q ∈ F и Z ∈ Γ ∪ {Z00 } множество D0 (q, e, Z) содержит (qe , e);4. D0 (qe , e, Z) = {(qe , e)} для всех Z ∈ Γ ∪ {Z00 }.Автомат сначала переходит в конфигурацию (q0 , w, Z0 Z00 ) в соответствии с определением D0 в п.2, затем в (q, e, Y1 ... Yk Z00 ), q ∈ F в соответствии с п.1, затем в (qe , e, Y1 ... Yk Z00 ), q ∈ F в соответствии с п.3, затем в (qe , e, e) в соответствии с п.4. Нетрудно показать по индукции, что(q0 , w, Z0 ) `+ (q, e, u) (где q ∈ F ) выполняется для автомата M тогда итолько тогда, когда (q00 , w, Z00 ) `+ (qe , e, e) выполняется для автомата M 0 .Поэтому L(M ) = L0 , где L0 – язык, допускаемый автоматом M 0 опустошением магазина.Обратно, пусть M = (Q, T, Γ, D, q0 , Z0 , ∅) – МП-автомат, допускающий опустошением магазина язык L. Построим автомат M 0 , допускающий тот же язык по заключительному состоянию.Пусть M 0 = (Q ∪ {q00 , qf }, T, Γ ∪ {X}, D0 , q00 , Z00 , {qf }), где D0 определяется следующим образом:1.
D0 (q00 , e, Z00 ) = {(q0 , Z0 Z00 )} – переход в “режим M ”;2. Для каждого q ∈ Q, a ∈ T ∪ {e}, и Z ∈ Γ определим D0 (q, a, Z) =D(q, a, Z) – работа в “режиме M ”;3. Для всех q ∈ Q, (qf , e) ∈ D0 (q, e, Z00 ) – переход в заключительноесостояние.Нетрудно показать по индукции, что L = L(M 0 ).Одним из важнейших результатов теории контекстно-свободных языков является доказательство эквивалентности МП-автоматов и КС-грамматик.Теорема 4.2. Язык является контекстно-свободным тогда и толькотогда, когда он допускается магазинным автоматом.Доказательство. Пусть G = (N, T, P, S) – КС-грамматика.
ПостроимМП-автомат M , допускающий язык L(G) опустошением магазина.Пусть M = ({q}, T, N ∪ T, D, q, S, ∅), где D определяется следующимобразом:1. Если A → u ∈ P , то (q, u) ∈ D(q, e, A);2. D(q, a, a) = {(q, e)} для всех a ∈ T .Фактически, этот МП-автомат в точности моделирует все возможныевыводы в грамматике G. Нетрудно показать по индукции, что для любой цепочки w ∈ T ∗ вывод S ⇒+ w в грамматике G существует тогда и4.1. КС-ГРАММАТИКИ И МП-АВТОМАТЫ53только тогда, когда существует последовательность тактов (q, w, S) `+(q, e, e) автомата M .Обратно, пусть M = (Q, T, Γ, D, q0 , Z0 , ∅) – МП-автомат, допускающий опустошением магазина язык L.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
