И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 6
Текст из файла (страница 6)
Состояние, в которое мы при этом попадаем, становится текущим.При работе этого алгоритма возможны следующие ситуации (аналогичные ситуациям,которые возникают при разборе непосредственно по регулярной грамматике):1) Прочитана вся цепочка; на каждом шаге находилась единственная дуга, помеченная очередным символом анализируемой цепочки; в результате последнего перехода оказались в состоянии S.
Это означает, что исходная цепочка принадлежитL(G).2) Прочитана вся цепочка; на каждом шаге находилась единственная «нужная» дуга;в результате последнего шага оказались в состоянии, отличном от S. Это означает,что исходная цепочка не принадлежит L(G).3) На некотором шаге не нашлось дуги, выходящей из текущего состояния и помеченной очередным анализируемым символом. Это означает, что исходная цепочкане принадлежит L(G).4) На некотором шаге работы алгоритма оказалось, что есть несколько дуг, выходящих из текущего состояния, помеченных очередным анализируемым символом,но ведущих в разные состояния. Это говорит о недетерминированности разбора.Анализ этой ситуации будет приведен ниже.Диаграмма состояний определяет конечный автомат, построенный по регулярнойграмматике, который допускает множество цепочек, составляющих язык, определяемый этойграмматикой. Состояния и дуги ДС — это графическое изображение функции переходов конечного автомата из состояния в состояние при условии, что очередной анализируемый символ совпадает с символом-меткой дуги.
Среди всех состояний выделяется начальное (считается, что в начальный момент своей работы автомат находится в этом состоянии) и заключительное (если автомат завершает работу переходом в это состояние, то анализируемая цепочка им допускается). На ДС эти состояния отмечаются короткими входящей и соответственно исходящей стрелками, не соединенными с другими вершинами.Определение: детерминированный конечный автомат (ДКА) — это пятерка 〈 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 —— текущее состояниеCS = H;gc ();do{switch (CS){case H: if ( c == 'a' ){gc ();CS = A;}else if ( c == 'b' ){gc ();CS = B;}elseCS = ER;break;case A: if ( c == 'b' ){gc();CS = C;}elseCS = ER;break;case B: if ( c == 'a' ){gc();CS = C;}elseCS = ER;break;case C: if ( c =='a' ){gc();CS = A;}else if ( c == 'b' ){gc();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).Sa⇒bb⇒⇒⇒⇒⇒aРис. 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).⇒⇒⇒⇒⇒⇒Рис. 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разбор будет недетерминированным (т.к.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
