Формальные грамматики и языки (1119467), страница 3

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

Текст из файла (страница 3)

L порождается регулярной грамматикой2. L допускается ДКА3. L допускается НКА79Преобразование НКА в ДКА• Алгоритм преобразования НКА в ДКАВход:Конечный автомат НКА = (K, V, δ, H, S)Выход: Конечный автомат ДКА = (K’, V’, δ’, H’, S’)L (ДКА) = L (НКА)1. Множество состояний К’ нового автомата M’ строитсяиз комбинаций всех состояний К старого автомата M(как множество подмножеств множества К)Каждое состояние из К’ обозначается как [A1A2...An],где Ai ∈ K, 1 ≤ i ≤ nВсего имеется не более 2n – 1 состояний новогоавтомата M’80Преобразование НКА в ДКА• Алгоритм преобразования НКА в ДКАВход:Конечный автомат НКА = (K, V, δ, H, S)Выход: Конечный автомат ДКА = (K’, V’, δ’, H’, S’)L (ДКА) = L (НКА)2. Пусть H есть множество начальных состояний старогоавтомата: {H1, H2, ..., Hp}, в качестве исходногосостояния ДКА M’ при построении отображения δ’(функции переходов) берётся состояние [A1A2...Ap], гдеAi ∈ H, 1 ≤ i ≤ p или [H1H2...Hp], то есть объединениевсех начальных состояний НКА МЭто состояние включается в множество состояний К’нового автомата (сначала оно единственное)81Преобразование НКА в ДКА3.

Начиная с исходного состояния [H1H2...Hp], длякаждого нового состояния [A1A2...An] из К’ и каждоговходного символа t ∈ T строятся переходыδ’ ([A1A2...An], t) = [B1B2...Bm], где для ∀ k: 1 ≤ k ≤ m∃ i: 1 ≤ i ≤ n такое, что δ (Ai, t) = Bk{B1, B2, ..., Bm} – это все состояния НКА, в которые естьпереходы из состояний {A1, A2, ..., An} по символу tВ ДКА М’ формируется детерминированный переходпо символу t из состояния [A1A2...An] в состояние[B1B2...Bm] (если m = 0, δ’ ([A1A2...An], t) = ∅)Все новые состояния [B1B2...Bm] (m≠ 0) включаются 82в К’Преобразование НКА в ДКА4. Пусть конечное состояние старого автомата S естьмножество состояний {S1, S2, ..., Sq}, тогда S’ – всесостояния из K’ вида [...

Sr ...], где Sr ∈ S для 1 ≤ r ≤ q• Если S’ состоит более, чем из одного элемента,изменяют входной язык, добавляя маркер ‘⊥’ в конецкаждой цепочкиВводится новое состояние S, и для каждого состоянияQ из множества S’ добавляется переход δ’ (Q, ⊥) = SS объявляется единственным заключительнымсостоянием83ДC и праволинейные грамматики• Если все правила праволинейной грамматики содносимвольной правой частью имеют видV → ⊥:• Состояниями ДС будут нетерминалыграмматики и одно специальноезаключительное состояние S, в которое длякаждого правила вида V → ⊥ проводится дугаиз V, помеченная признаком конца ⊥• Для каждого правила вида V → tW проводитсядуга из V в W, помеченная символом t• Начальным состоянием будет начальныйсимвол H84Разбор цепочки• При анализе цепочки abba⊥ имеем ту жепоследовательность переходов:⊥H→A→C→B→C→SabbaГрамматика:H → aA | bBA → bCB → aCС → aA | bB | ⊥• Каждая смена состояния теперь означает“свёртку” сентенциальной формы путёмзамены в ней нетерминала L на пару“нетерминал-терминал” tN, где L → tN –правило грамматики• Возникает такая последовательность замен нетерминальныхсимволов, соответствующая сменам состояний припостроении дерева сверху вниз:H→ aA → abC → abbB → abbaC → abba⊥85Диаграммы состояний,функции переходов,правила регулярных грамматикправила леволинейных грамматикHAAtA ≡ δ (H, t) = A ≡ A → t ≡ H → tAtB ≡ δ (A, t) = B ≡ B → At ≡ A → tBtS ≡ δ (A, t) = S ≡ S → At ≡ A → tправила праволинейных грамматик86Выявлениенедетерминированности разбора• Леволинейная грамматика: в разных правилахимеются одинаковые правые части• Праволинейная грамматика: в правилах для одногосимвола имеются альтернативы, начинающиеся содинаковых терминальных символов• Диаграмма состояний: из одной вершины выходятнесколько дуг с одинаковыми надписями• Функция переходов: разные значения для одного итого же набора параметров (переход из некоторогосостояния в разные состояния по одному символу) 87Диаграмма с действиями• В конечном автомате лексического анализатора действияотображаются с помощью диаграммы состояний: скаждым переходом из одного состояния в другое надиаграмме состояний связывается выполнение функциидействия D (k, t), где k – текущее состояние, а t – текущийвходной символ автомата• Функция D (k, t) может выполнять действия:• размещение новой лексемы в таблице лексем• проверка наличия лексемы-имени в таблице имён• внесение новой записи в таблицу имён• выдача сообщений об ошибках, обнаруженных впроцессе лексического анализа• остановка процесса компиляции88Диаграмма с действиями• Функция действия D (k, t) записывается на диаграммесостояний с помощью дополнительных пометок поддугами, соединяющими состояния автомата• Каждая дуга может выглядеть так:At1, t2, …, tnBD1, D2, …, Dm• ti – символы анализируемого языка: если в состоянииA очередной анализируемый символ языка совпадаетс ti для какого-либо i = 1, 2,..., n, осуществляетсяпереход в состояние B, при этом выполняютсядействия D1, D2, ..., Dm89Диаграмма с действиямиДано: грамматика G = ({a, b, ⊥}, {S, A, B}, P, S)bHbПравила грамматики:⊥AbaP : S → A⊥A → Ab | Bb | bB → AaBSЗадача: подсчитатьмаксимальное числосимволов ‘b’,следующих ванализируемойцепочке подряд90Диаграмма с действиямиРешение: диаграмма состояний с действиямиbk ++bдля полнойопределённостиавтоматаHAmax = k = 1a⊥bif (k > max) max = kprint (max)Sak=1E⊥if (k > max) max = ka⊥B91Метод рекурсивного спуска• Для каждого нетерминального символа A ∈ Nграмматики G (N, T, P, S) строится процедура, котораяполучает на вход цепочку символов α и текущеесостояние указателя ввода символов из этой цепочки• Если для символа A больше одного правила, то ищетсяправило вида A → aγ, где γ ∈ (T ∪ N)* и a ∈ T совпадаетс текущим символом входной цепочки• Если такое правило (A → aγ) найдено (либо правилоA → γ – единственное для A), то для каждогонетерминального символа из цепочки γ рекурсивновызывается процедура разбора этого символа92Метод рекурсивного спуска• Грамматика G=({a, b, c, ⊥},{S, A, B}, P, S) и цепочка caba⊥P: S → AB⊥SA → a | cAB → bAABAAA→acaba⊥• S → AB⊥ → cAB⊥ → caB⊥ → cabA⊥ → caba⊥93Метод рекурсивного спуска• Процедура каждого нетерминального символаграмматики, начиная с указанного места исходнойцепочки, ищет подцепочку, которая начинается стекущего символа и выводится из этогонетерминального символа• Пример распознавания рекурсивным спуском:••Процедура GetL () вводит очередной символ языкаПроцедура S () начинает работу, когда первый символ уже прочитанS → AB⊥A → a | cAB → bAvoid S () { A (); B ();void A () {elseelsevoid B () {elseif (c != ‘⊥’) ERROR ();}if (c == ‘a’) GetL ();if (c == ‘c’) { GetL (); A (); }ERROR ();}if (c == ‘b’) { GetL (); A (); }ERROR ();}94Метод рекурсивного спуска• Метод рекурсивного спуска работоспособен, если накаждом шаге вывода выбор правила для заменылевого нетерминала безошибочно принимается попервому символу из непрочитанной входной цепочкиДостаточные условия применимости методарекурсивного спускаМетод применим, если каждое правило грамматики имеет вид:• либо для символа A имеется единственное правило выводаA → α, где α ∈ (T ∪ N)*• либо (если для символа А правил вывода несколько) всеправила начинаются с различных терминальных символов:A → a1α1 | a2α2 | ...

| anαnai ∈ T для всех i = 1, 2, ..., nαi ∈ (T ∪ N)*ai ≠ aj для i ≠ j95Метод рекурсивного спуска• Рекурсивный спуск применим для грамматикиG = ({a, b, c, ⊥}, {S, A, B}, P, S), гдеA → a | cAB → bAP: S → AB⊥• Неоднозначная грамматика (метод не применим):Pн: S → aA | B | сA → aA | сB → aA | a• Однозначная грамматика с неоднозначными прогнозами:Pо: S → A | BA → aA | сB → aB | b• Наличие в грамматике правил вида X → α и X → β, изправых частей которых выводятся цепочки, начинающиесяодним и тем же терминалом a, то есть α ⇒ aα′ и β ⇒ aβ ′,делает неоднозначным прогноз по символу a, в такихслучаях метод рекурсивного спуска неприменим96Применение рекурсивного спуска• Множество first (A) – это множество терминальныхсимволов, которыми начинаются цепочки, выводимыеиз А в грамматике G = (T, N, P, S):• first (A) = {a ∈ T | A ⇒ aα, A ∈ (T ∪ N)+, α ∈ (T ∪ N)*}• first (ε) = ∅• Для альтернатив правила S → A | B в грамматике Gо:first (A) = { a, c }, first (B) = { a, b }S→A|Bпересечение first (A) ∩ first (B) = { a } ≠ ∅A → aA | сметод рекурсивного спуска к Gо неприменим B → aB | b• Наличие в грамматике двух разных правил X → α | β,таких что first (α) ∩ first (β) ≠ ∅, делает методрекурсивного спуска неприменимым97Применение рекурсивного спуска• Если в грамматике для правил X → α | β выполняютсясоотношения α ⇒ ε и β ⇒ ε, то метод рекурсивногоспуска заведомо неприменим• Для грамматики Gрс наличие ε-правила не приводит кневозможности использования метода рекурсивногоспуска, для второй грамматики Gнрс препятствие есть:Gрс: S → cAd | dGнрс: S → BdA → aA | εA → aA | εB → cAa | a• В грамматике Gнрс любой вывод, содержащий A, имеетвид: S → Bd → cAad → … → ca…aAad, и сделать выборпо текущему символу невозможно98Рекурсивный спуск для списков• Общий вид правил для описания синтаксисапоследовательностей однотипных конструкций:L → a | a,L (в сокращённой форме: L → a {,a})• Условия применимости метода рекурсивного спускадля грамматик с правилами для списков невыполнены: в цепочке a,a,a,a,a из L могут выводиться• a• a,a• a,a,a,a,a• Разбор детерминирован, если всегда выбираетсясамая длинная подцепочка99Рекурсивный спуск для списков• При анализе цепочек грамматикиG = ({a,}, {L}, P, L), где P = {L → a | a,L}методом рекурсивного спуска процедура L ()будет содержать оператор цикла:void L () { if (c != ‘a’)ERROR ();while ((GetL (), c) == ‘,’)if ((GetL (), c) != ‘a’) ERROR ();}100Преобразование грамматик• Для произвольной контекстно-свободной грамматикинельзя сказать, анализируется заданный ею языкметодом рекурсивного спуска или нет• Проблема поиска эквивалентной контекстносвободной грамматики, для которой методрекурсивного спуска применим, есть алгоритмическинеразрешимая проблема• Для некоторых частных видов грамматик, неудовлетворяющих требованиям применимости методарекурсивного спуска, удаются преобразования,позволяющие получить эквивалентные грамматики,пригодные для анализа этим методом101Применение рекурсивного спуска1.

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

Список файлов лекций