Лекции (18) (Презентации лекций (PDF))

Элементы теории трансляцииЛексический анализВ основе лексических анализаторов лежат регулярныеграмматики.Соглашения:- для описания лексем будем использоватьлеволинейную автоматную грамматику без пустыхправых частей.Грамматика G = (T, N, P, S) автоматная леволинейная,если каждое правило из Р имеет видA → Bt либоA → t,где A  N, B  N, t  T.- анализируемая цепочка заканчивается специальнымсимволом  - признаком конца цепочки.Алгоритм разбора по леволинейной грамматике.(1) первый символ исходной цепочкиa1a2...anзаменяемнетерминалом A, для которого в грамматике есть правило выводаA → a1(производим "свертку" терминала a1 к нетерминалу A )(2) многократно (до тех пор, пока не считаем признак конца цепочки)выполняем следующее: полученный на предыдущем шагенетерминал A и расположенный непосредственно справа от негоочередной терминал ai исходной цепочки заменяем нетерминаломB, для которого в грамматике есть правило выводаB → Aai (i = 2, 3,.., n)Если в результате работы алгоритма прочитана вся цепочка, на каждомшаге находилась единственная нужная «свертка», а на последнемшаге произошла свертка к символу S, значит цепочка a1a2...anпринадлежит языку.Если на каком-то шаге не нашлось нужной свертки или на последнемшаге произошла свертка к символу, отличному от S, значит цепочкаa1a2...an не принадлежит языку.Если на каком-то шаге нашлось более одной подходящей свертки, значитразбор по заданной грамматике недетерминированный.Диаграммы состояний (ДС)Диаграмма состояний (ДС) - неупорядоченный ориентированный помеченныйграф, который строится следующим образом:(1) строим вершины графа, помеченные нетерминалами грамматики(для каждого нетерминала - одну вершину), и еще одну вершину,помеченную символом, отличным от нетерминальных (например, H).Эти вершины называются состояниями.

H - начальное состояние.(2) соединяем эти состояния дугами по следующим правилам:a) для каждого правила вида W  t соединяем дугой состояния H и W(от H к W) и помечаем дугу символом t;б) для каждого правила вида W  Vt соединяем дугой состояния V и W(от V к W) и помечаем дугу символом t.Диаграмма состояний для грамматики G_ex = ( { a, b,  }, { S, A, B, C }, P, S ), гдеP:S  CC  Ab | BaA  a | CaB  b | Cbбудет выглядеть так:HaAbbBL(G) = { ([ab | ba])n  | n >= 1 }abCaSАлгоритм разбора по диаграмме состояний(1) объявляем текущим состояние H;(2) многократно (до тех пор, пока не считаем признак конца цепочки)выполняем следующее: считываем очередной символ исходнойцепочки и переходим из текущего состояния в другое состояние подуге, помеченной этим символом.

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

S - начальное состояние.F – заключительное состояние.(2) соединяем эти состояния дугами по следующим правилам:a) для каждого правила вида W  t соединяем дугой состояния F и W(от W к F) и помечаем дугу символом t;б) для каждого правила вида W  t V соединяем дугой состояния V и W(от W к V) и помечаем дугу символом t;Диаграмма состояний для грамматики G_ex2 = ( { 0, 1,  }, { S, B, C }, P, S ), гдеP:S  0BB  1B | 1C | CL(G) = { 01n | n >= 0 }будет выглядеть так:S0B1C1FИмея ДС, построенную по любой регулярной грамматике, можно по нейвосстановить как леволинейную, так и эквивалентную ей праволинейнуюрегулярную грамматику.Алгоритм построения праволинейной грамматикиGright по ДС, построенной по леволинейнойграмматике Gleft.• Нетерминалами Gright будут все состояния из ДС, кроме S.• Если в ДС есть исходящие дуги из S, то вводим в ДС новоезаключительное состояние S’, в которое из S ведет дуга,помеченная признаком конца .• Каждой дуге из состояния V в заключительное состояние S(или S’), помеченной символом t (  ) ставится всоответствие правило V → t ( V → ).• Каждой дуге из состояния V в состояние W, помеченнойсимволом t, ставится в соответствие правило V → tW.• Начальное состояние H объявляется начальным символомграмматики.Алгоритм построения леволинейной грамматикиGrleft по ДС, построенной по праволинейнойграмматике Gright.• Нетерминалами Gleft будут все состояния из ДС дляGright, кроме S.• Каждой дуге из состояния S в состояние W, помеченнойсимволом t, ставится в соответствие правило W → t.Если в ДС есть входящие дуги в S, то в Gleft добавляетсятакже и правило W → St.• Каждой дуге из состояния V в состояние W, помеченнойсимволом t, ставится в соответствие правило W → Vt.• Заключительное состояние F объявляется начальнымсимволом грамматики.Соглашения для работы с диаграммамисостоянийa) Если из одного состояния в другое выходитнесколько дуг, помеченных разнымисимволами, то изображается одна дуга,помеченная всеми этими символами.b) Непомеченная никакими символами дугасоответствует переходу при любом символе,кроме тех, которыми помечены другие дуги,выходящие из этого состояния.c) Вводится дополнительное состояние ошибки(ER); переход в это состояние означает, чтоисходная цепочка языку не принадлежит.Конечный автомат (КА)Конечный автомат (КА) - это пятерка (K, T, δ , H, S), гдеK - конечное множество состояний;T - конечное множество допустимых входных символов;δ - отображение (функция переходов) множества K  T → K,определяющее поведение автомата;H  K - начальное состояние;S  K - заключительное состояние (либо конечное множествозаключительных состояний, но для грамматик – одно!).δ (A, t) = B означает, что из состояния A по входному символу tпроисходит переход в состояние B.Конечный автомат допускает цепочку 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 - одно из заключительных состояний.Множество цепочек, допускаемых конечным автоматом,составляет определяемый им язык.Анализатор для регулярной грамматики G_ex.char c;void gc ( ) { cin >> c; }bool scan_G ( ) {enum state { H, A, B, C, S, ER };state CS; // CS - текущее состояниеCS = H;do { gc ();switch (CS) {case H: if (c == 'a') { CS = A;}else if (c == 'b') { CS = B;}else CS = ER;break;case A: if (c == 'b') { CS = C;}else CS = ER;break;case B: if (c == 'a') { CS = C;}else CS = ER;break;case C: if (c == 'a') { CS = A;}else if (c == 'b') { CS = B;}else if (c == '') CS = S;else CS = ER;break;}} while (CS != S && CS != ER);if (CS == ER) return false;elsereturn true;}О недетерминированном разбореПри анализе по ДС для регулярной грамматики может оказаться, что из одногосостояния выходит несколько дуг, ведущих в разные состояния, но помеченныходним и тем же символом.Для леволинейных грамматик эта ситуация возникает, когда в правилах выводаесть совпадающие правые части.Для праволинейных грамматик аналогичная ситуация возникает, когдаальтернативы вывода из одного нетерминала грамматики начинаютсяодинаковыми терминальными символами.Недетерминированный конечный автомат (НКА) – это пятерка( 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.Алгоритм построения детерминированного КА по НКАВход: M = (K, T, δ , H, S) - НКА.Выход: M1 = (K1, T, δ1, H1, S1) - детерминированный КА, допускающий тот жеязык, что и автомат М.Метод:1. Строим отображение δ1 (K1  T → K1) по δ, начиная с состояния H.2. δ1 для Н  К1 строим т.о.:- если в НКА переход из Н по какому-то символу былдетерминированным, переносим соответствующие отображение врезультирующий КА. Состояния, появляющиеся в правой частиотображений δ1 принадлежат К1;- если же в НКА переход из Н по какому-то символу t былнедетерминированным, то в КА включаем отображения δ1 по правилу:δ1 (H, t) = A1A2...An,где Ai  К, и в НКА есть F (H, t) = Aiдля всех 1 <= i <= n.Состояние A1A2...An  К1.3.

Для всех состояний, появившихся в правой части отображений δ1результирующего КА, определяем отображения δ1 т.о.:δ1 (A1A2...An, t) = B1B2...Bm, где для каждого 1 <= j <= m в НКАсуществует δ (Ai, t) = Bj для каких-либо 1 <= i <= n.4. Заключительными состояниями построенного детерминированного КАявляются все состояния, содержащие S  К в своем имени. Длянаписания грамматики по КА все эти состояния необходимо свести кодному заключительному состоянию S1  К1 с помощью символа .Пример работы алгоритма преобразования НКА в КАЗадан НКА M = ( { H, A, B, S }, { 0, 1 }, δ , { H }, { S } ),δ (H, 1) = Bδ (A, 1) = Bδ (A, 1) = Sδ (B, 0) = A ,гдеL = { 1(01)n | n >=1 }Функции переходов КА, построенные по НКА в соответствии спредложенным алгоритмом.δ1(Н, 1) = Bδ1(B, 0) = Aδ1(A, 1) = BSδ1(BS, 0) = AЗаключительным состоянием построенного детерминированного КАявляется состояние BS.Таким образом, M1 = ({H, B, A, BS}, {0, 1}, δ1, H, BS).Задачи лексического анализа1.выделить в исходном тексте цепочку символов, представляющуюлексему, и проверить правильность ее записи;2.удалить пробельные литеры и комментарии;3.преобразовать цепочку символов, представляющих лексему, впару:( тип_лексемы,4.указатель_на_информацию_о_ней );зафиксировать в специальных таблицах для хранения разныхтипов лексем факт появления соответствующих лексем ванализируемом тексте.Чтобы решить эту задачу, опираясь на способ анализа с помощьюДС, на дугах вводится дополнительные пометки-действия.Теперь каждая дуга в ДС может выглядеть так:At 1,t 2,...,t nD 1;D 2;...;D mBЛексический анализ языков программированияПринято выделять следующие типы лексем: идентификаторы,служебные слова, константы и ограничители.Каждой лексеме сопоставляется пара:( тип_лексемы,указатель_на_информацию_о_ней ).Таким образом, лексический анализатор - это транслятор, входомкоторого служит цепочка символов, представляющих исходнуюпрограмму, а выходом - последовательность лексем.Лексемы перечисленных выше типов можно описать с помощьюрегулярных грамматик.