Материалы (5) (Материалы к лекциям)

58Мы рассмотрели основные понятия теорииформальных языков, что дает математическую базудля изучения основ трансляции.ТФЯ является одной из старейших и наиболеефундаментальных областей информатики, еерезультаты используются не только в теориитрансляции, но и в других областях математики,лингвистики, биологии.59Основы трансляции• задача разбора• лексический анализ• синтаксический анализ• семантические действия• формальный перевод• генерация кода (на языке ПОЛИЗ)• интерпретация ПОЛИЗ60Задача разбора:Даны КС-грамматика G и цепочка x.x∈L(G) ?Если да, то построить дерево вывода для x(или левый вывод для x, или правый вывод для x ).Задача распознавания: x∈L(G) ? Дерево или вывод нетребуются в качестве ответа, только ответ - «да»или «нет».61Задача распознавания алгоритмически неразрешима вклассе языков типа 0;разрешима в классе языков типа 1.Для КС-языков и регулярных языков существуютэффективные алгоритмы разбора.Регулярные и КС-языки используются при описаниисинтаксиса языков программирования62Построение дерева выводаG: S → a S | bСверху вниз:SaaЦепочка:⇒bSaSa⇒baabSaSa⇒SSbaSaSbЛевыйвывод:S→aS→ aaS → a a b →63Построение дерева выводаG: S → a S | bЦепочка:aabСвертка – это применение правила вывода «в обратную сторону», заменаправой части на нетерминал из левой части:aab ← aaS — свертка по правилу S → b.

Обозначаем свертку с помощьюобратной стрелки ← .С помощью сверток можно построить вывод «задом наперед» (обращениевывода): от цепочки к цели грамматики S. Например, сентенциальную формуaaS можно свернуть к aS, а затем к S :aab ← aaS ← aS ← S64Построение дерева выводаG: S → a S | bЦепочка:aabСнизу вверх:S⇒S⇒SSa a bОбратныйправыйвывод:aab ←aaaaSb←aS⇒SSSaba S←aaS←Sb65РЕГУЛЯРНЫЕ ЯЗЫКИспособы описания:-- регулярные грамматики(леволинейныелибоправолинейные)-- конечные автоматы(недетерминированные или детерминированные)-- регулярные выражения(см.

материал “О регулярных языках” на cmcmsu.no-ip.info)66Недетерминированный конечный автомат (НКА) — этопятерка A = (K, Σ, δ, I, F), где:К — конечное множество состояний, или вершин;Σ — входной алфавит (также конечный);δ ⊆ K × Σ × K — множество команд, или дуг;I ⊆ K — множество начальных состояний;F ⊆ K — множество заключительных состояний.Множество δ можно также интерпретироватьотображение K × Σ в множество подмножеств K.как67A = (K, Σ, δ, I, F) — НКА.Каждая дуга НКА A имеет пометку из Σ.Путь в ориентированном графе может быть представленпоследовательностью дуг. Пустой путь можно представитьодной вершиной, которая считается одновременно началом иконцом пути.Пометка пути — это сцепление (конкатенация) пометокего дуг. Пустой путь имеет пустую пометку.

Путь из начальнойвершины в заключительную называется успешным.Язык, допускаемый автоматом A (обозначается L(A)), — этомножество пометок всех успешных путей автомата.68Пример 1. A1 = ({A, B, C, D, E}, {a, b}, δ, {A, D}, {C, E}),где δ = {(A, a, B), (D, a, E), (B, b, C), (E, b, C), (C, b, C)}.Автомат удобно представлять в виде ориентированногоразмеченного графа:A a B b CbbD aEВходящими непомеченными стрелками отмечены начальныевершины A и D, исходящими — заключительные вершины E иC.L(A1) = {abn | n ≥ 0}69Алгоритм построения НКА по леволинейной грамматике (без пустыхправых частей)1.

Множество вершин НКА состоит из нетерминаловграмматики и еще одной новой вершины Н, котораяобъявляется начальной.2. Каждому правилу вида А → Ва в автомате соответствуетдуга из вершины В в вершину А, помеченная символом а:aB⎯→⎯ A. Каждому правилу вида А → а соответствует дугаaH⎯⎯→A. Других дуг нет.3. Заключительной вершиной автомата является вершина,соответствующаяначальномусимволуграмматики.Начальной является вершина H, построенная на шаге 1.70G = ({a, b, ⊥}, {S, A, B, C}, P, S), гдеP: S → C⊥С → Ab | BaДиаграмма состояний дляA → a | Caграмматики G – это граф,представляющий конечный автомат, B → b | Cbпостроенный нашим алгоритмом пограмматике G.CABSab⊥AC-BC-S-Представление в виде таблицыHaПредставление в виде набора командили функции переходов :AbabbCBa(С,a)→ A(С,b)→ B(С, ⊥)→ S(A,b)→ C…⊥Sилиилиилиилиδ(С,a) = {A}δ(С,b) = {B}δ(С, ⊥) = {S}δ(A,B) = {C}…71Алгоритм построения леволинейной грамматикипо НКА с единственным заключительным состоянием1.

Нетерминалами грамматики будут вершины автомата,терминалами — пометки дуг.a⎯→ B в грамматику добавляется2. Для каждой дуги A ⎯правило В → Аа. Для каждой начальной вершины В вграмматику добавляется правило В → ε.3. Начальным символом будет нетерминал, соответствующийзаключительной вершине.4. К построенной по пунктам 1—3 грамматике применитьалгоритм устранения ε-правил.72Конечный автомат называется детерминированнымконечным автоматом (ДКА), если он имеет единственноеначальное состояние, и любые две дуги, исходящие изодной и той же вершины имеют различные пометки.Множество δ в ДКА можно интерпретировать какотображение K × Σ в множество K.Тогда конечный автомат допускает цепочку a1a2...an,если δ (H,a1) = A1; δ (A1,a2) = A2; ... ; δ (An-2,an-1) = An-1;δ(An-1,an) = S, где ai ∈ Σ, Aj ∈ K, j = 1, 2,..., n-1; i = 1,2,...,n; H – начальное состояние, S – одно из заключительныхсостояний.Язык, допускаемый ДКА — это множество всехдопускаемых им цепочек.73Алгоритм построения ДКА по НКАВход: A′ = (K′, Σ, δ′, I, F) — НКА.Выход: A = (K, Σ, δ, InitState, FinalStates) — ДКА.Метод: Вершинами (состояниями) автомата A будут подмножества множества К′автомата A′.

CurState и NewState — вспомогательные переменные для хранения такихподмножеств. Сам алгоритм запишем в паскалеподобном стиле. Фигурные скобкиозначают конструкторы множеств.begin InitState := {s | s ∈ I}; K := {InitState}; δ := ∅;while (в К есть нерассмотренный элемент)beginCurState := нерассмотренный элемент из К;for (каждого а ∈ Σ)beginNewState := {q | ( p ⎯⎯a → q ) ∈ δ, p ∈ CurState};K := K ∪ {NewState};δ := δ ∪ {(CurState ⎯⎯a → NewState)};endend;FinalStates := {P ∈ K | существует q ∈ P: q ∈ F }end.Пример.A′:1aa2ba,b743bbПроцесс построения ДКА удобно изобразить в виде таблицы,начав с состояния {1, 2}. Затем заполняем строки для вновьпоявляющихся состояний.символab{1, 2}{2, 3}{1, 2, 3}{2, 3}{2, 3}{1, 2, 3}{1, 2, 3}{2, 3}{1, 2, 3}состояние75Обозначим состояние {1, 2} через A, {2, 3} — B, {1, 2,3} — C.символabABCBBCCBCсостояниеС учетом переобозначений построим по таблице ДКА A :aaABL(A)={a, b}+bbaCb76Можно заметить, что язык L = {a, b}+, допускаемый автоматом A,допускается также ДКА A′′, имеющим только два состояния.A′′:1a,b2a,bСуществует алгоритм, позволяющий по любому ДКА построитьэквивалентный ДКА с минимальным числом состояний.77Для более удобной работы с диаграммами состоянийвведем несколько соглашений:a) если из одного состояния в другое выходитнесколько дуг, помеченных разными символами, тобудем изображать одну дугу, помеченную всеми этимисимволами;b) непомеченная дуга будет соответствовать переходупри любом символе, кроме тех, которыми помеченыдругие дуги, выходящие из этого состояния.c) введем состояние ошибки (ERR); переход в этосостояние будет означать, что исходная цепочка языкуне принадлежит.78Алгоритм моделирования работы ДКАВход: ДКА A = (K, Σ, δ, I, F) и цепочка x⊥, где x ∈ Σ*, ⊥ ∉ Σ — маркер концацепочки.Выход: «Да», если x ∈ L(A), иначе — «Нет».Метод: Введем переменные St для хранения текущего состояния автомата и c дляхранения очередного считанного символа входной цепочки x.beginc := первый символ цепочки x;St := I; {начальное состояние}while ( St ≠ ERR and c ≠ '⊥' )beginSt := δ (St, c);c := очередной символend;if St ∈ F thenwrite ('Да')elsewrite ('Нет')end;79Пример анализатора{S, A, B, C}, P, S 〉, гдеP: S → C⊥С → Ab | BaA → a | CaB → b | CbдляграмматикиHaAabbG = 〈{a, b, ⊥},bCBПрограмма-анализатор на С++ :⊥a#include <iostream.h>char c; //текущий символvoid gc () {cin >> c;} // считать очередной символ со входаbool scan_G(){enum state {H, A, B, C, S, ERR};state CS;// CS —— текущее состояниеCS=H;gc(); // считать первый символ//множество состоянийS80do {switch (CS) {case H: if (c == 'a') { gc(); CS = A;}else if (c == 'b') { gc(); CS = B;}else CS = ERR;break;case A: if (c == 'b') { gc(); CS = C;}else CS = ERR;break;case B: if (c == 'a') { gc(); CS = C;}else CS = ERR;break;case C: i (c =='a') { gc(); CS = A;}else if (c == 'b') { gc(); CS = B;}else if (c == '⊥') CS = S;else CS = ERR;abreak;AH}} while (CS != S && CS != ERR);if (CS == ERR)bbreturn false;belseCreturn true;B}aa⊥SaH81AПример разбора цепочки abba⊥HaAbCbBaCb⊥SCBaabba⊥ ← Abba⊥ ← Cba⊥ ← Ba⊥ ← C⊥ ← SSS⇒ab⇒ACabba⇒bSBb⊥Aa⇒a⊥AaCbbBbaC⊥AaSCb⇒bS⇒aabb⊥AaCbBbaCa⊥S⊥⊥S82Недетерминированный разборЕсликонечныйавтомат,построенныйпограмматике,недетерминированный, тонужно перебирать все возможные вариантыпереходов.

Можно также преобразовать его в эквивалентный ДКА и проводитьдетерминированный разбор.Пример использования автоматов в решениитеоретических задачУтверждение. Контекстно-свободный языкL ={anbn | n ≥1}нерегулярен(доказательство см. http://cmcmsu.no-ip.info/download/regular.languages.pdf)83Конечные автоматы (диаграммы состояний) с действиямиидентификатор (I):I → a | b| ...| z | Ia | Ib |...| Iz | I0 | I1 |...| I9целое без знака (N):N→ 0 | 1 |...| 9 | N0 | N1 |...| N9ДС с действиями может выглядеть так:At 1,t 2,...,t nD 1;D 2;...;D mBСмысл ti прежний — если в состоянии A очередной анализируемыйсимвол совпадает с ti для какого-либо i = 1, 2 ,...

n, то осуществляется переходв состояние B; при этом необходимо выполнить действия D1, D2, ... ,Dm.84Лексический анализ (ЛА) — это первый этаппроцесса компиляции. На этом этапе литеры,составляющие исходную программу, группируются вотдельные элементы, называемые лексемами.задачи лексического анализатора:- выделить в исходном тексте цепочку символов,представляющую лексему, и проверить правильность еезаписи;- зафиксировать в специальных таблицах для храненияразных типов лексем факт появления соответствующих лексемв анализируемом тексте;- преобразоватьлексему, в пару:цепочкусимволов,представляющих(тип_лексемы, указатель_на_информацию_о_ней);- удалить пробельные литеры и комментарии.85Лексический анализатор для М-языкаОписание модельного языкаP → program D1; B⊥D1 → var D {,D}D → I {,I}: [ int | bool ]B → begin S {;S} endS → I := E | if E then S else S | while E do S | B | read (I) | write (E)E → E1 [ = | < | > | <= | >= | != ] E1 | E1E1 → T {[ + | - | or ] T}T → F {[ * | / | and ] F}F → I | N | L | not F | (E)L → true | falseI→ a | b| ...| z | Ia | Ib |...| Iz | I0 | I1 |...| I9N → 0 | 1 |...| 9 | N0 | N1 |...| N986Контекстные условия:1.

Любое имя, используемое в программе, должно быть описано и толькоодин раз.2. В операторе присваивания типы переменной и выражения должнысовпадать.3. В условном операторе и в операторе цикла в качестве условия возможнотолько логическое выражение.4. Операнды операции отношения должны быть целочисленными.5.

Тип выражения и совместимость типов операндов в выраженииопределяются по обычным (паскалевским) правилам; старшинство операцийзадано синтаксисом.87Проектирование структурыанализатора М-языкаклассовлексическогоПредставление лексем: выделим следующие типы лексем:enumtype_of_lex {LEX_NULL, /*0*/LEX_AND, LEX_BEGIN, … LEX_WRITE, /*18*/LEX_FIN, /*19*/LEX_SEMICOLON, LEX_COMMA, … LEX_GEQ, /*35*/LEX_NUM, /*36*/LEX_ID, /*37*/POLIZ_LABEL, /*38*/POLIZ_ADDRESS, /*39*/POLIZ_GO, /*40*/POLIZ_FGO}; /*41*/88Соглашение об используемых таблицах лексем:TW – таблица служебных слов М-языка;TD – таблица ограничителей М-языка;TID – таблица идентификаторов анализируемойпрограммы.Таблицы TW и TD заполняются заранее, т.к.