В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 8
Текст из файла (страница 8)
Такая стратегия разрешения конфликтов позволяет легко резервировать ключевые слова.Если на входе встречается “<=”, то первому символу соответствует образец“<”, но это не самый длинный образец, который соответствует префиксу входа.Стратегия выбора самого длинного префикса легко разрешает такого рода конфликты.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. Построим грамматику G, порождающую язык L.Пусть G = ({ [qZr] | q, r ∈ Q, Z ∈ Γ} ∪ {S}, T, P, S), где P состоит изправил следующего вида:1. Если (r, X1 ... Xk ) ∈ D(q, a, Z), k > 1, то[qZsk ] → a[rX1 s1 ][s1 X2 s2 ] ... [sk−1 Xk sk ]для любого набора s1 , s2 , ... , sk состояний из Q;2. Если (r, e) ∈ D(q, a, Z), то [qZr] → a ∈ P , a ∈ T ∪ {e};3. S → [q0 Z0 q] ∈ P для всех q ∈ Q.Нетерминалы и правила вывода грамматики определены так, что работе автомата M при обработке цепочки w соответствует левостороннийвывод w в грамматике G.Индукцией по числу шагов вывода в G или числу тактов M нетруднопоказать, что (q, w, A) `+ (p, e, e) тогда и только тогда, когда [qAp] ⇒+ w.Тогда, если w ∈ L(G), то S ⇒ [q0 Z0 q] ⇒+ w для некоторого q ∈ Q.Следовательно, (q0 , w, Z0 ) `+ (q, e, e) и поэтому w ∈ L.
Аналогично, еслиw ∈ L, то (q0 , w, Z0 ) `+ (q, e, e). Значит, S ⇒ [q0 Z0 q] ⇒+ w, и поэтомуw ∈ L(G).МП-автомат M = (Q, T, Γ, D, q0 , Z0 , F ) называется детерминированным (ДМП-автоматом), если выполнены следующие два условия:(1) Множество D(q, a, Z) содержит не более одного элемента для любых q ∈ Q, a ∈ T ∪ {e}, Z ∈ Γ;(2) Если D(q, e, Z) 6= ∅, то D(q, a, Z) = ∅ для всех a ∈ T .Язык, допускаемый ДМП-автоматом, называется детерминированным КС-языком.Так как функция переходов ДМП-автомата содержит не более одного элемента для любой тройки аргументов, мы будем пользоваться записью D(q, a, Z) = (p, u) для обозначения D(q, a, Z) = {(p, u)}.Пример 4.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
