Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 3
Текст из файла (страница 3)
Иобратно: для каждого регулярного выражения можно построитьрегулярное множество, обозначаемое этим выражением. Для каждогорегулярного множества существует бесконечно много обозначающих егорегулярных выражений. Будем говорить, что два регулярных выраженияравны, если они обозначают одно и то же множество.2.2. Конечные автоматыНедетерминированный конечный автомат (НКА) - это пятеркаM=<Q,T,D,q0,F>, где(1) Q - конечное множество состояний;(2) T - конечное множество допустимых входных символов;(3) D - функция переходов, отображающая множество QxTU{e} вомножество подмножеств множества Q и определяющая поведениеуправляющего устройства;(4) q0<-Q - начальное состояние управляющего устройства;(5) F<=Q - множество заключительных состояний.Детерминированный конечный автомат (ДКА) - это пятеркаM=<Q,T,D,q0,F>, где(1) Q - конечное множество состояний;(2) T - конечное множество допустимых входных символов;(3) D - функция переходов, отображающая множества QxT в множествоQ и определяющая поведение управляющего устройства;(4) q0<-Q - начальное состояние управляющего устройства;(5) F<=Q - множество заключительных состояний.Работаконечногоавтоматапредставляет22собойнекоторуюпоследовательность шагов, или тактов.
Такт определяется текущимсостояниемуправляющегоустройстваивходнымсимволом,обозреваемым в данный момент входной головкой. Сам шаг состоит изизменения состояния и сдвига входной головки на одну ячейку вправо(рис. 2.3).СостояниеaПрочитанная частьвходной цепочки................Текущий Непрочитанная частьвходной цепочкивходнойсимволРис. 2.3Текущее состояние управляющего устройства, символ под головкой ицепочка символов вправо от головки называются конфигурацией автомата.Конфигурация (q0,w) называется начальной, а пара (q,e), где q<-F,называется заключительной (или допускающей).Такт автомата M представляется бинарным отношением |-, определеннымна конфигурациях: отношение имеет место, если есть переход изконфигурации (q1,w1) в конфигурацию (q2,w2). Для детерминированногоконечного автомата всегда w1=aw2.
Для нетерминированного автоматаможет быть w1=w2, если q2<-D(q1,e). Отношения |-+ и |-* - это,соответственно, транзитивное и рефлексивно-транзитивное замыканиеотношения |-. Говорят, что автомат M допускает цепочку w, если (q0,w)|*(q,e) для некоторого q<-F. Языком, допускаемым (распознаваемым,определяемым) автоматом M, (обозначается L(M)), называется множествовходных цепочек, допускаемых автоматом M. Т.е.L(M)={w | w<-T* и (q0,w)|-*(q,e) для некоторого q<-F}Конечный автомат может быть изображен графически в виде графа,в котором каждому состоянию соответствует вершина, а дуга, помеченнаясимволом a, соединяет две вершины p и q, если функция переходовсодержит (q,a)->p.
На диаграмме выделяются конечные состояния (впримерах выше двойным контуром).23Пример 2.2. Диаграмма для чисел языка Паскаль приведена на рис. 2.4.E1 Цифра 2.3 ЦифраЦифра4ЦифраE 5+,-Цифра6 Цифра 7ЦифраРис. 2.42.3. Построение детерминированного конечного автомата понедерминированномуАлгоритм строит функцию переходов Dtran для детерминированногоконечного автомата DFA. Каждое состояние DFA - это некотороемножество состояний недерминированного автомата NFA. DFAмоделирует “в параллель” все возможные шаги NFA, которые он можетсделать на входной строке. В алгоритме будут использоваться следующиеоперации:e-closure(S) - множество состояний NFA, достижимых из некоторогосостояния q<-S на e-переходах.move(S,a) - множество состояний NFA, в которые есть переход на входе aдля некоторого состояния q<-S.Прежде, чем увидеть первый входной символ, NFA может находиться влюбом состоянии из множества e-closure({q0}).
Пусть S - множествосостояний, достижимых NFA на некоторой последовательности входныхсимволов и пусть a - очередной входной символ. Читая a, NFA можетперейти в любое из состояний из move(S,a). Если учесть e-переходы, NFAможет оказаться в любом из состояний из e-closure(move(S,a)).Алгоритм 2.1. Построение детерминированного конечного автомата понедетермнированномуВначале единственное состояние в Dstates - e-closure({q0}) и оно непомечено.24while (в Dstates есть непомеченное состояние S){пометить S;for (каждого входного символа a<-T){R= e-closure(move(S,a));if (R !<- Dstates)добавить R в Dstates как непомеченноесостояние;определить Dtran[S,a]=R;}}Начальное состояние так построенного автомата DFA - это e-closure({q0}),заключительное - любое такое, которое содержит заключительноесостояние NFA.2e0e3ae1e67aeeeeb45aaAbaBbaDbaCEbbРис. 2.5e-closure(S) можно вычислить следующим образом:R=e-closure(S)=S;while (R!={})258b9b10{Пусть r<-R;for (каждого q такого, что q <- D(r,e))if (q !<- e-closure(S)){добавить q к e-closure(S);добавить q к R;}убрать r из R;}Пример применения алгортима приведен на рис.
2.5.2.4. Построение детерминированного конечного автомата порегулярному выражению.Приведем теперь алгоритм построения детерминированногоконечного автомата по регулярному выражению [1]. К регулярномувыражению (сокращенно РВ) r добавим маркер конца: (r)#. Послепостроения ДКА для расширенного РВ легко построить ДКА дляисходного РВ: все состояния ДКА из которых есть переход в конечное счтением символа "#", можно считать конечными, а символ "#" исоответствующие переходы удалить.Представим РВ в виде дерева, листья которого - терминальныесимволы, а внутренние вершины - операции "." (конкатенации), "U"(объединение), "*" (итерация).Каждому листу дерева (кроме e-листьев) припишем уникальныйномер и ссылаться на него будем, с одной стороны, как на позицию вдереве и, с другой стороны, как на позицию символа, соответствующеголисту.Теперь, обходя дерево T снизу-вверх слева-направо, вычислимчетыре функции: nullable, firstpos, lastpos и followpos.
Функции nullable,firstpos и lastpos определены на узлах дерева, а followpos - на множествепозиций. Значением всех функций, кроме nullable, является множествопозиций. Функция followpos вычисляется через три остальные функции.Функция firstpos(n) для каждого узла n синтаксического дереварегулярного выражения дает множество позиций, которые соответствуютпервым символам в подцепочках, генерируемых подвыражением свершиной в n. Аналогично, lastpos(n) дает множество позиций, которымсоответствуют последние символы в подцепочках, генерируемыхподвыражениями с вершиной n. Для узлов n, поддеревья которых (т.е.дерево, у которого узел n является корнем) могут породить пустое слово,определим nullable(n)=true, а для остальных узлов false.26узел nлист eлист iU/\u v./\u vnullable(n)truefalsenullable(u)ornullable(v)nullable(u)andnullable(v)*|vtruefurstpos(n){}{i}firstpos(u)Ufirstpos(v)if nullable(u)firstpos(u) Ufirstpos(v)else firstpos(u)firstpos(v)lastpos(n){}{i}lastpos(u)Ulastpos(v)if nullable(v)lastpos(u) Ulastpos(v)else lastpos(v)lastpos(v)Рис.
2.6Таблица для вычисления функций nullable, firstpos и followposприведена на рис. 2.6.{1,2,3}.{6}/\{1,2,3}.{5} {6}#{6}/\{1,2,3}.{4} {5}b{5}/\{1,2,3}.{3} {4}b{4}/\{1,2}*{1,2} {3}a{3}|{1,2}U{1,2}/\ {1}a{1} {2}b{2}Рис. 2.7позиция123456followpos{1,2,3}{1,2,3}{4}{5}{6}Рис. 2.8Функции firstpos и lastpos для выражения (a+b)*abb#приведены на рис. 2.7. Слева от каждой вершины значение firstpos, справа- lastpos.
Заметим, что эти функции могут быть вычислены за один обходдерева.Пример 2.3.Если i - позиция, то followpos(i) есть множество позиций j таких, чтосуществует некоторая строка ...cd..., входящая в язык, описываемый РВ,такая, что i - соответствует этому вхождению c, а j - вхождению d.Функция followpos может быть вычислена также за один обходдерева снизу-вверх по следующим двум правилам1. Пусть n - внутренний узел с операцией "." (конкатенация), a,b - егопотомки. Тогда для каждой позиции i, входящей в lastpos(a), добавляем к27множеству значений followpos(i) множество firstpos(b).2.
Пусть n - внутренний узел с операцией "*" (итерация), a - егопотомок. Тогда для каждой позиции i, входящей в lastpos(a), добавляем кмножеству значений followpos(i) множество firstpos(а).Для примера 2.3 значения функции followpos приведены на рис. 2.8.Функцияfollowposпозволиттеперьсразупостроитьдетерминированный конечный автомат с помощью следующегоалгоритма.Алгоритм 2.2. Прямое построение ДКА по регулярному выражению.Будем строить множество состояний автомата Dstates и помечать их.Состояния ДКА соответствуют множествам позиций.
Начальнымсостоянием будет состояние firstpos(root), где root - вершинасинтаксического дерева регулярного выражения, конечными - всесостояния, содержащие позиции, связанные с символом "#".Сначала в Dstates имеется только одно непомеченное состояниеfirstpos(root).while (в Dstates есть непомеченное состояние R){пометить R;for (каждого входного символа a, такого, что в Rимеется позиция, которой соответствует a){пусть символ a в R соответствует позициямp1,...,pi, и пусть S=U followpos(pi);iif (S не пусто и S не принадлежит Dstates)добавить непомеченное состояние S в Dstates(рис. 2.9);Функцию перехода Dtran для R и a определить какDtran(R,a)=S;}}Для примера 2.3 вначале R={1(a),2(b),3(a)}. Последовательность шагов{p b }Sb{p a }SaSРис.
2.928алгоритма приведена на рис. 2.10. В результате будет построендетерминированный конечный автомат, изображенный на рис. 2.11.Состояния автомата обозначаются как множества позиций, например{1,2,3}, конечное состояние заключено в квадратные скобки [1,2,3,6].U followpos(p(a)) U followpos(p(b)){1,2,3}{1,2,3,4,}{1,2,3}{1,2,3,4} {1,2,3,4}{1,2,3,5}{1,2,3,5} {1,2,3,4}{1,2,3,6}{1,2,3,6} {1,2,3,4}{1,2,3}Рис. 2.10bbb{1,2,3}aa{1,2,3,4 b}{1,2,3,5}ab [{1,2,3,6}]Рис. 2.112.5 Построение детерминированного конечного автомата сминимальным числом состоянийРассмотрим теперь алгоритм построения ДКА с минимальным числомсостояний, эквивалентного данному ДКА [2].Алгоритм 2.3. Построение ДКА с минимальным числом состояний.Шаг 1.
Строим начальное разбиение П множества состояний из двухгрупп: заключительные состояния Q и остальные Q-F.Шаг 2. Применяем к П следующую процедуру и получаем новое разбиениеПnew (рис. 2.12):for (каждой группы G в П){разбиваем G на подгруппы так, чтобысостояния s и t из G оказались в однойгруппе тогда и только тогда, когда для каждоговходного символа a состояния s и t имеютпереходы по a в состояния из одной и той жегруппы в П;заменяем G в Пnew на множество всех29полученных подгрупп;}GG3aaG1s1t1abG4G5G2s2at2bbG6bРис.
2.12Шаг 3. Если Пnew=П, полагаем Пres=П и переходим к шагу 4, иначеповторяем шаг 2 с П:=Пnew.bba1b2bb3aa4abbab{2,3,4,5}{1}b5bbaababba{2,3} a{1}{4}{5}baabРис. 2.13Шаг 4. Выберем по одному состоянию из каждой группы в разбиении П resв качестве представителя для этой группы. Представители будутсостояниями приведенного ДКА М'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
