Материалы (5) (1115032)
Текст из файла
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 заполняются заранее, т.к.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
