formal_languages_translation_theory (Формальные грамматики), страница 6

Это означает, что исходнаяцепочка a1a2...an   L(G).(2) прочитана вся цепочка; на каждом шаге находилась единственная нужная свертка;на последнем шаге свертка произошла к символу, отличному от S. Это означает,что исходная цепочка a1a2...an   L(G).(3) на некотором шаге не нашлось нужной свертки, т. е. для полученного на предыдущем шаге нетерминала A и расположенного непосредственно справа от негоочередного терминала ai исходной цепочки не нашлось нетерминала B, для которого в грамматике было бы правило вывода B → Aai. Это означает, что исходнаяцепочка a1a2...an   L(G).(4) на некотором шаге работы алгоритма оказалось, что есть более одной подходящейсвертки, т.

е. в грамматике разные нетерминалы имеют правила вывода с одинаковыми правыми частями, и поэтому непонятно, к какому из них производитьсвертку. Это говорит о недетерминированности разбора. Анализ этой ситуациибудет дан ниже.Допустим, что разбор на каждом шаге детерминированный.12)22Полное отсутствие -правил в грамматике не позволяет описывать языки, содержащие пустую цепочку.

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

Сделаем это в виде таблицы, столбцы которой помечены терминальными символами. Первая строка помечена символом Н (НN), а значение каждого элементаэтой строки — это нетерминал, к которому можно свернуть помечающий столбец терминальный символ. Остальные строки помечены нетерминальными символами грамматики.Значение каждого элемента таблицы, начиная со второй строки — это нетерминальный символ, к которому можно свернуть пару «нетерминал-терминал», которыми помечены соответствующие строка и столбец.Например, для леволинейной грамматики Gleft  {a, b, }, {S, A, B, C}, P, S , гдеP:S → CC → Ab | BaA → a | CaB → b | Cb ,такая таблица будет выглядеть следующим образом:abHAB—CABSA—C—BC——S———Знак «—» ставится в том случае, если соответствующей свертки нет.Но чаще информацию о возможных свертках представляют в виде диаграммы состояний (ДС) — неупорядоченного ориентированного помеченного графа, который строитсяследующим образом:(1) строим вершины графа, помеченные нетерминалами грамматики (для каждого нетерминала — одну вершину), и еще одну вершину, помеченную символом, отличным от нетерминальных, например, H.

Эти вершины будем называть состояниями. H — начальное состояние.(2) соединяем эти состояния дугами по следующим правилам:а) для каждого правила грамматики вида W → t соединяем дугой состояния Hи W (от H к W ) и помечаем дугу символом t;б) для каждого правила W → Vt соединяем дугой состояния V и W (от V к W) ипомечаем дугу символом t;Диаграмма состояний для грамматики Gleft (см. пример выше) изображена на рис.4:HabAbabBCSaРис. 4.

Диаграмма состояний для грамматики Gleft.23Элементы теории трансляции / Разбор по регулярным грамматикамАлгоритм разбора по диаграмме состояний(1) объявляем текущим начальное состояние H;(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: считываем очередной символ исходной цепочки и переходим из текущего состояния в другое состояние по дуге, помеченной этим символом.

Состояние, в которое мы при этом попадаем, становится текущим.При работе этого алгоритма возможны следующие ситуации (аналогичные ситуациям,которые возникают при разборе непосредственно по регулярной грамматике):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 = 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.