В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 16
Текст из файла (страница 16)
Синтаксический анализ[q1 , X , q1 ] → 1Или в другой записи:S→AA → 0BCB → 0BDC→eB→1D→eD→1МП-автомат 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.3.
Рассмотрим ДМП-автоматM = ({q0 , q1 , q2 }, {a, b, c}, {Z , a, b}, D, q0 , Z , {q2 }),функция переходов которого определяется следующим образом:D(q0 , X , Y ) = (q0 , XY ), X ∈ {a, b}, Y ∈ {Z , a, b},D(q0 , c, Y ) = (q1 , Y ), Y ∈ {a, b},D(q1 , X , X) = (q1 , e), X ∈ {a, b},D(q1 , e, Z) = (q2 , e).Нетрудно показать, что этот детерминированный МП-автомат допускает языкL = {wcwR |w ∈ {a, b}+ }.К сожалению, ДМП-автоматы имеют меньшую распознавательную способность, чем МП-автоматы.
Доказано, в частности, что существуют КСязыки, не являющиеся детерминированными КС-языками (таковым, например, является язык из примера 4.1).Рассмотрим еще один важный вид МП-автомата.Расширенным автоматом с магазинной памятью назовем семерку M == (Q, T , Γ, D, q0 , Z0 , F ), где смысл всех символов тот же, что и для обычного МП-автомата, кроме D, представляющего собой отображение конечногоподмножества множества Q × (T ∪ {e}) × Γ∗ во множество конечных подмножеств множества Q × Γ∗ .
Все остальные определения (конфигурации, такта,допустимости) для расширенного МП-автомата остаются такими же, как дляобычного.4.1. Контекстно-свободные грамматики и автоматы с магазинной памятью77Теорема 4.4. Пусть M = (Q, T , Γ, D, q0 , Z0 , F ) — расширенный МПавтомат. Тогда существует МП-автомат M ′ , такой, что L(M ′ ) = L(M ).Расширенный МП-автомат M = (Q, T , Γ, D, q0 , Z0 , F ) называется детерминированным, если выполняются следующие условия:1) множество D(q , a, u) содержит не более одного элемента для любых q ∈∈ Q, a ∈ T ∪ {e}, u ∈ Γ∗ ;2) если D(q , a, u) 6= ∅, D(q , a, v) 6= ∅ и u 6= v , то не существует цепочки x,такой, что u = vx или v = ux;3) если D(q , a, u) 6= ∅, D(q , e, v) 6= ∅, то не существует цепочки x, такой,что u = vx или v = ux.Теорема 4.5.
Пусть M = (Q, T , Γ, D, q0 , Z0 , F ) — расширенный ДМПавтомат. Тогда существует ДМП-автомат M ′ , такой, что L(M ′ ) == L(M ).ДМП-автомат и расширенный ДМП-автомат лежат в основе рассматриваемых далее в этой главе LL- и LR-анализаторов.Определение 4.1. Говорят, что КС-грамматика находится в нормальнойформе Хомского, если каждое правило имеет один из следующих видов:1) A → BC , A, B , C — нетерминалы;2) A → a, a — терминал;3) S → e, и в этом случае S не встречается в правых частях правил.Утверждение 4.1. Любую КС-грамматику можно преобразовать в эквивалентную ей в нормальной форме Хомского.Определение 4.2.
Назовем высотой дерева максимальную длину пути(число внутренних вершин) от корня до листа.Утверждение 4.2. Если КС-грамматика находится в нормальной форме Хомского, то для любой цепочки α, если α ∈ L(G) и h — высота деревавывода с кроной α, |α| 6 2h−1 .Обратно, если |α| > 2h−1 , то высота дерева больше или равна h.Теорема 4.6. (Лемма о разрастании для контекстно-свободных языков.)Для любого КС-языка L существуют такая константа k , что любаяцепочка α ∈ L, |α| > k , представима в виде α = uvwxy , где:1) |vwx| 6 k ;2) vx 6= e;3) uv i wxi y ∈ L для любого i > 0.Д о к а з а т е л ь с т в о .
Пусть L = L(G), где G = (N , Σ, P , S) —контекстно-свободная грамматика в нормальной форме Хомского. Обозначимчерез n число нетерминалов, т. е. n = |N |, и рассмотрим k = 2n .78Глава 4. Синтаксический анализПусть |α| > k = 2n . Тогда высота дерева с кроной α больше или равна n + 1 и есть путь по дереву (от корня до некоторого листа), которыйвключает не менее, чем n + 1 внутренних вершин (нетерминалов). Такимобразом, существует хотя бы один нетерминал, который помечает не менеедвух вершин этого пути. Среди всех таких нетерминалов на этом путипусть A — такой, что его второе вхождение, считая от листа, не содержитдругих нетерминалов, обладающих этим свойством (если бы это было не так,то выбрали бы этот другой). Пусть q — вхождение A, ближайшее к листу,p — ближайшее, расположенное выше.
Представим крону α в виде uvwxy , гдеw — крона поддерева D1 с корнем q и vwx — крона поддерева D2 с корнем p.Тогда высота поддерева D2 не более (n − 1) + 2 = n + 1 (не более n − 1нетерминалов, отличных от A, плюс два вхождения A), так что |vwx| 6 2n .Также очевидно, что vx 6= e, поскольку в силу определения нормальнойформы Хомского p имеет двух сыновей, помеченных нетерминалами, из которых не выводится пустая цепочка.Кроме того, S ⇒∗ uAy ⇒ ∗ uvAxy ⇒ ∗ uvwxy , а также A ⇒ ∗ vAx ⇒ ∗ vwx.Отсюда получаем A ⇒ ∗ v i wxi для всех i > 0 и S ⇒ ∗ uv i wxi y для всех i > 0.Пример 4.4.
Покажем, что язык L = {an bn cn | n > 1} не является контекстно–свободным языком.Если бы он был КС–языком, то мы взяли бы константу k , которая определяетсяв лемме о разрастании. Пусть 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 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
