В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 17
Текст из файла (страница 17)
Пусть z = ak bk ck . Тогда z = uvwxy . Так как |vwx| 6 k ,то в цепочке vwx не могут быть вхождения каждого из символов a, b и c. Такимобразом, цепочка uwy , которая по лемме о разрастании принадлежит L, содержитлибо k символов a, либо k символов c. Но она не может иметь k вхожденийкаждого из символов a, b и c, потому, что |uwy| < 3k . Значит, вхождений какого-то/ L. Полученноеиз этих символов в uwy больше, чем другого, и, следовательно, uwy ∈противоречие позволяет заключить, что L — не КС-язык.4.2. Преобразования КС-грамматикРассмотрим ряд преобразований, позволяющих «улучшить» свойстваконтекстно-свободной грамматики без изменения порождаемого ею языка.Назовем символ X ∈ (N ∪ T ) недостижимым в КС-грамматике G == (N , T , P , S), если X не появляется ни в одной выводимой цепочке этойграмматики. Иными словами, символ X недостижим, если в G не существуетвывода S ⇒∗ αXβ , α, β ∈ (N ∪ T )∗ .Назовем символ X ∈ (N ∪ T ) несводимым (бесплодным), если в грамматике не существует вывода вида X ⇒∗ w, где w ∈ T ∗ .Назовем символ бесполезным, если он является недостижимым илинесводимым.4.2.
Преобразования КС-грамматик79Бесполезные символы не могут участвовать в порождении терминальныхстрок языка, поэтому рассмотрим алгоритм построения грамматики, эквивалентной данной, но не содержащей бесполезных символов.Алгоритм 4.1. Устранение несводимых символов.Вход.
КС-грамматика G = (N , T , P , S).Выход. КС-грамматика G′ = (N ′ , T ′ , P ′ , S) без несводимых символов,такая, что L(G′ ) = L(G).Метод. Выполнить шаги 1–4:1. Положить N0 = T и i = 1;2. Положить Ni = {A|A → α ∈ P и α ∈ (Ni−1 )∗ } ∪ Ni−1 ;3. Если Ni 6= Ni−1 , то положить i = i + 1 и перейти к шагу 2, в противномслучае положить Ne = Ni и перейти к шагу 4;4.
Положить G1 = ((N ∩ Ne ) ∪ {S}, T , P1 , S), где P1 состоит из правилмножества P , содержащих только символы из Ne ∪ T ;Алгоритм 4.2. Устранение недостижимых символов.Вход. КС-грамматика G = (N , T , P , S).Выход. КС-грамматика G′ = (N ′ , T ′ , P ′ , S) без недостижимых символов,такая, что L(G′ ) = L(G).Метод. Выполнить шаги 1–4:1.
Положить V0 = {S} и i = 1;2. Положить Vi = {X | в P есть A → αXβ и A ∈ Vi−1 } ∪ Vi−1 ;3. Если Vi 6= Vi−1 , положить i = i + 1 и перейти к шагу 2, в противномслучае перейти к шагу 4;4. Положить N ′ = Vi ∩ N , T ′ = Vi ∩ T . Включить в P ′ все правила из P ,содержащие только символы из Vi .Чтобы устранить все бесполезные символы, необходимо применить к исходной грамматике сначала алгоритм 4.1, а затем алгоритм 4.2.Пример 4.5.
Все символы следующей грамматикиS → AS | b;A → AB ;B → a.Поскольку все символы грамматики достижимы, применение сначала алгоритма4.2 не меняет грамматику. Применение алгоритма 4.1 приводит к появлению недостижимых символов.КС-грамматика без бесполезных символов называется приведенной. Легковидеть, что для любой КС-грамматики существует эквивалентная приведенная. В дальнейшем будем предполагать, что все рассматривамые грамматики— приведенные.80Глава 4. Синтаксический анализ4.3. Алгоритм Кока–Янгера–КасамиПриведем алгоритм синтаксического анализа, применимый для любойграмматики в нормальной форме Хомского.Алгоритм 4.3 (Кока–Янгера–Касами).Вход.
КС-грамматика G = (N , T , P , S) в нормальной форме Хомскогои входная цепочка w = a1 a2 . . . an ∈ T + .Выход. Таблица разбора T ab для w, такая, что A ∈ tij тогда и толькотогда, когда A ⇒ + ai ai+1 . . . ai+j−1 .Метод. Выполнить шаги 1–3:1. Положить ti1 = {A | A → ai ∈ P } для каждого i. Таким образом, еслиA ∈ ti1 , то A ⇒ + ai .2. Пусть tij ′ вычислено для 1 6 i 6 n и 1 6 j ′ < j . Положим tij = {A | длянекоторого 1 6 k < j правило A → BC ∈ P , B ∈ tik , C ∈ ti+k,j−k }.
Таккак 1 6 k < j , то k < j и j − k < j . Поэтому tik и ti+k,j−k вычисляютсяраньше, чем tij . Если A ∈ tij , тоA ⇒BC ⇒ + ai . . . ai+k−1 C ⇒ + aI . . . ai+k−1 ai+k . . . ai+j−1 .3. Повторять шаг 2 до тех пор, пока не станут известны tij для всех1 6 i 6 n и 1 6 j 6 n − i + 1.Алгоритм 4.4 (нахождения левого разбора по таблице разбора Tab).Вход. КС-грамматика G = (N , T , P , S) в нормальной форме Хомскогос правилами, занумерованными от 1 до p, входная цепочка w = a1 a2 .
. . an ∈∈ T + и таблица разбора T ab.Выход. Левый разбор цепочки w или сигнал «ошибка».Метод. Процедура gen(i, j , A).1. Если j = 1 и A → ai = pm , то выдать m.2. Пусть j > 1 и k — наименьшее из чисел от 1 до j − 1, для которых существуют B ∈ tik , C ∈ ti+k,j−k и правило pm = A → BC .
Выдать m и выполнить gen(i, k , B), затем gen(i + k , j − k , C). Выполнить gen(1, n, S ),если S ∈ t1,n ; иначе «ошибка».4.4. Разбор сверху-вниз (предсказывающий разбор)4.4.1. Алгоритм разбора сверху-вниз. Пусть дана КС-грамматика G == (N , T , P , S). Рассмотрим разбор сверху-вниз (предсказывающий разбор)для грамматики G.Главная задача предсказывающего разбора — определение правила вывода, которое нужно применить к нетерминалу. Процесс предсказывающего разбора с точки зрения построения дерева разбора проиллюстрирован на рис.
4.1.4.4. Предсказывающий разбор сверху-вниз81Рис. 4.1Фрагменты недостроенного дерева соответствуют сентенциальным формам. Вначале дерево состоит только из одной вершины, соответствующейаксиоме S . В этот момент по первому символу входной цепочки предсказывающий анализатор должен определить правило S →X1 X2 . . ., которое должнобыть применено к S . Затем необходимо определить правило, которое должнобыть применено к X1 , и т. д. до тех пор, пока в процессе такого построениясентенциальной формы, соответствующей левому выводу, не будет примененоправило Y → a .
. .. Этот процесс затем применяется для следующего самоголевого нетерминального символа сентенциальной формы.На рис. 4.2 условно показана структура предсказывающего анализатора,который определяет очередное правило с помощью таблицы. Такую таблицуможно построить и непосредственно по грамматике. Таблично-управляемыйпредсказывающий анализатор имеет входную ленту, управляющее устройство(программу), таблицу анализа, магазин и выходную ленту. Входная лентасодержит анализируемую строку, заканчивающуюся символом $ — маркеромконца строки. Выходная лента содержит последовательность примененныхправил вывода.Рис. 4.2Таблица анализатора — это двумерный массив M [A, a], где A — нетерминал, a — терминал или символ $.
Значением M [A, a] может быть некотороеправило грамматики или элемент «ошибка».82Глава 4. Синтаксический анализМагазин может содержать последовательность символов грамматики с $на дне. В начальный момент магазин содержит только начальный символграмматики на верхушке и $ на дне.Анализатор работает следующим образом. Вначале он находится в конфигурации, в которой магазин содержит S $, на входной ленте w$ (w —анализируемая цепочка), выходная лента пуста. На каждом такте анализаторрассматривает X — символ на верхушке магазина и a — текущий входнойсимвол. Эти два символа определяют действия анализатора. Имеются следующие возможности.1.
Если X= a = $, то анализатор останавливается, сообщает об успешномокончании разбора и выдает содержимое выходной ленты.2. Если X= a 6= $, то анализатор удаляет X из магазина и продвигаетуказатель входа на следующий входной символ.3. Если X — терминал, причем X 6= a, то анализатор останавливаетсяи сообщает о том, что входная цепочка не принадлежит языку.4. Если X — нетерминал, то анализатор обращается к таблице M [X , a].Возможны два случая.а) Значением M [X , a] является правило для X . В этом случае анализатор заменяет X на верхушке магазина на правую часть данногоправила, а само правило помещает на выходную ленту.
Указательвхода не передвигается.б) Значением M [X , a] является «ошибка». В этом случае анализаторостанавливается и сообщает о том, что входная цепочка не принадлежит языку.Работа анализатора может быть задана следующей программой:Поместить $,затем S в магазин;do {X = верхний символ магазина;if (X - терминал){ if (X ==InSym){удалить X из магазина;InSym = очередной символ;}else {error(); break;}else if (X - нетерминал)if (M [X , InSym]=="X->Y1Y2...Yk{удалить X из магазина;поместить Yk,Yk-1,...Y1 в магазин (Y1 на верхушку);вывести правило X->Y1Y2...Yk;}else {error(); break;} /*вход таблицы M пуст*/834.4. Предсказывающий разбор сверху-вниз}while (X != $); /*магазин пуст*/if (InSym != $) error(); /*Не вся строка прочитана*/Пример 4.6. Рассмотрим грамматику арифметических=({E , E ′ , T , T ′ , F }, {id, +, ∗, (, )}, P , E) с правилами:E → T E′;E ′ → +T E ′ ;E ′ → e;T → F T ′;выраженийG=T ′ → ∗F T ′ ;T ′ → e;F → (E);F → id.Ниже приведена таблица предсказывающего анализатора для этой грамматики(табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
