И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1119400), страница 6

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

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

Состояния и дуги ДС — это графическое изображение функции переходов конечного автомата из состояния в состояние при условии, что очередной анализируемый символ совпадает с символом-меткой дуги. Среди всех состояний выделяется начальное (считается, что в начальный момент своей работы автомат находится в этом состоянии) и заключительное (если автомат завершает работу переходом в это состояние, то анализируемая цепочка им допускается).

На ДС эти состояния отмечаются короткими входящей и соответственно исходящей стрелками, не соединенными с другими вершинами.Определение: детерминированный конечный автомат (ДКА) — это пятерка  K, T, ,H, S , гдеK — конечное множество состояний;T — конечное множество допустимых входных символов; — отображение множества K  T в K, определяющее поведение автомата;H  K — начальное состояние;S  K — заключительное состояние (либо множество заключительных состоянийS  K).Замечания к определению ДКА:(1) Заключительных состояний в ДКА может быть более одного, однако для любогорегулярного языка, все цепочки которого заканчиваются маркером конца (), су-24Элементы теории трансляции / Разбор по регулярным грамматикамществует ДКА с единственным заключительным состоянием. Заметим также, чтоДКА, построенный по регулярной грамматике рассмотренным выше способом,всегда будет иметь единственное заключительное состояние S.

13)(2) Отображение : K  T → K называют функцией переходов ДКА. (A, t)  B означает, что из состояния A по входному символу t происходит переход в состояние B.Иногда  определяют лишь на подмножестве K  T (частичная функция). Еслизначение (A, t) не определено, то автомат не может дальше продолжать работу иостанавливается в состоянии «ошибка».Определение: ДКА допускает цепочку a1a2...an, если  (H, a1)  A1;  (A1, a2)  A2 ; …;  (An − 2, an − 1)  An − 1;  (An − 1, an)  S, где ai  T, Aj  K, j  1, 2, ..., n  1; i  1, 2, ..., n; H —начальное состояние, S — заключительное состояние.Определение: множество цепочек, допускаемых ДКА, составляет определяемый имязык.Для более удобной работы с диаграммами состояний введем несколько соглашений: если из одного состояния в другое выходит несколько дуг, помеченных разнымисимволами, то будем изображать одну дугу, помечая ее списком из всех таких символов; непомеченная дуга будет соответствовать переходу при любом символе, кроме тех,которыми помечены другие дуги, выходящие из этого состояния; введем состояние ошибки (ER); переход в это состояние будет означать, что исходная цепочка языку не принадлежит.По диаграмме состояний легко написать анализатор для регулярной грамматики.Например, для грамматики Gleft   {a, b, }, {S, A, B, C}, P, S  с правиламиP:S → CC → Ab | BaA → a | CaB → b | Cbанализатор будет таким:#include <iostream>using namespace std;char c;// текущий символvoid gc () { cin >> c; }// считать очередной символ из входной цепочкиbool scan_G (){enum state { H, A, B, C, S, ER }; // множество состояний13)Нетрудно указать и обратный способ — построения грамматики по диаграмме состояний автомата, — причем получившаяся грамматика будет автоматной.

Каждой дуге из начального состояния Н в состояние W,помеченной символом t, будет соответствовать правило W → t; каждой дуге из состояния V в состояние W,помеченной символом t, будет соответствовать правило W → Vt. Заключительное состояние S объявляетсяначальным символом грамматики.Если в вершину Н входит некоторая дуга (это возможно в произвольно построенном автомате), то алгоритм модифицируется так: каждой дуге из начального состояния Н в состояние W, помеченной символомt, будет соответствовать правило W →Ht, и в грамматику добавляется правило Н→ε; затем к построеннойграмматике применяется алгоритм удаления правил с пустыми правыми частями.25Элементы теории трансляции / Разбор по регулярным грамматикамstate CS;CS = H;// CS —— текущее состояниеdo{ gc ();switch (CS){case H: if ( c == 'a' ){CS = A;}else if ( c == 'b' ){CS = B;}elseCS = ER;break;case A: if ( c == 'b' ){CS = C;}elseCS = ER;break;case B: if ( c == 'a' ){CS = C;}elseCS = ER;break;case C: if ( c =='a' ){CS = A;}else if ( c == 'b' ){CS = B;}else if ( c == '' )CS = S;elseCS = ER;break;}}while ( CS != S && CS != ER);return CS == S; // true, если CS != ER,}26иначе falseЭлементы теории трансляции / Разбор по регулярным грамматикамПример разбора цепочкиРассмотрим работу анализатора для грамматики G на примере цепочки abba.

Прианализе данной цепочки получим следующую последовательность переходов в ДС:abbaHACBCSВспомним, что каждый переход в ДС означает свертку сентенциальной формы путем заменыв ней пары «нетерминал-терминал» Nt на нетерминал L, где L → Nt правило вывода в грамматике. Такое применение правила в обратную сторону будем записывать с помощью обратной стрелки Nt ← L (обращение правила вывода). Тогда получим следующую последовательность сверток, соответствующую переходам в ДС:abba  Abba  Cba  Ba  C  SЭта последовательность не что иное, как обращение (правого) вывода цепочки abba в грамматике G. Она соответствует построению дерева снизу вверх (см. рис. 5).SSSAabbaaCAbbaSabbSSCBAaCBCBCAbbaaaCAbbaabbaРис.

5. Построение дерева вывода снизу вверх.Разбор по праволинейной грамматикеПо диаграмме состояний (см. рис. 4) построим праволинейную автоматную грамматику Gright следующим способом: нетерминалами будут состояния из ДС (кроме S ); каждой дуге из состояния V в заключительное состояние S (помеченной признакомконца ) будет соответствовать правило V → ; каждой дуге из состояния V в состояние W, помеченной символом t, будет соответствовать правило V → tW;14) начальное состояние H объявляется начальным символом грамматики .14)Нетрудно описать и обратный алгоритм для праволинейной автоматной грамматики, если все ее правила содносимвольной правой частью имеют вид V → .

Состояниями ДС будут нетерминалы грамматики и ещеодно специальное заключительное состояние S, в которое для каждого правила вида V →  проводится дуга27Элементы теории трансляции / Разбор по регулярным грамматикамGright   {a, b, }, {H, A, B, C}, P, H P:H → aA | bBA → bCC → bB | aA | B → aCЗаметим, что L(Gright)  L(Gleft), так как грамматики Gright и Gleft соответствуют одной и тойже ДС (см. рис. 4).Рассмотрим разбор цепочки abba по праволинейной грамматике Gright. Последовательность переходов в ДС для этой цепочки такова:abbaHACBCSКаждый переход, за исключением последнего, означает теперь замену в сентенциальнойформе нетерминала на пару «терминал-нетерминал» с помощью некоторого правила выводаграмматики Gright. В результате получаем следующий (левый) вывод, который соответствуетпоследовательности переходов в ДС:H  aA  abC  abbB  abbaC  abbaТакой вывод отражает построение дерева вывода сверху вниз (см.

рис. 6).HHHAACabbaaHbbaaHACCBBCabbaaaACBbHAbbbaCabbaРис. 6. Построение дерева вывода сверху вниз.О недетерминированном разбореПри анализе по леволинейной грамматике может оказаться, что несколько нетерминалов имеют одинаковые правые части, и поэтому неясно, к какому из них делать свертку (см.ситуацию 4 в описании алгоритма). При анализе по праволинейной грамматике может ока-из V, помеченная признаком конца .

Для каждого правила вида V → t W проводится дуга из V в W, помеченная символом t. Начальным состоянием в ДС будет начальный символ H.28Элементы теории трансляции / Разбор по регулярным грамматикамзаться, что нетерминал имеет две правые части с одинаковыми терминальными символами ипоэтому неясно, на какую альтернативу заменить нетерминал. В терминах диаграммы состояний эти ситуации означают, что из одного состояния выходит несколько дуг, ведущих вразные состояния, но помеченных одним и тем же символом.Например, для грамматики G  {a, b, }, {S, A, B}, P, S , гдеP:S → AA → a | BbB → b | Bbразбор будет недетерминированным (т.к. у нетерминалов A и B есть одинаковые правые части — Bb).Такой грамматике будет соответствовать недетерминированный конечный автомат.Определение: недетерминированный конечный автомат (НКА) — это пятерка  K, T,, H, S , гдеK — конечное множество состояний;T — конечное множество допустимых входных символов; — отображение множества K  T в множество подмножеств K;H  K — конечное множество начальных состояний;S  K — конечное множество заключительных состояний.(A, t)  {B1, B2,..., Bn} означает, что из состояния A по входному символу t можно осуществить переход в любое из состояний Bi, i  1, 2, ..., n.

Также как и ДКА, любой НКА можнопредставить в виде таблицы (в одной ячейке такой таблицы можно указывать сразу несколько состояний, в которые возможен переход из заданного состояния по текущему символу)или в виде диаграммы состояний (ДС). В ДС каждому состоянию из множества K соответствует вершина; из вершины A в вершину B ведет дуга, помеченная символом t, еслиB   (A, t). (В НКА из одной вершины могут исходить несколько дуг с одинаковой пометкой). Успешный путь — это путь из начальной вершины в заключительную; пометка пути— это последовательность пометок его дуг.

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

Список файлов книги