В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 5
Текст из файла (страница 5)
На диаграммевыделяются начальное и заключительные состояния (в примерах ниже,соответственно, входящей стрелкой и двойным контуром).Пример 3.3. Пусть L = L(r), где r = (a|b)∗ a(a|b)(a|b).а) Недетерминированный конечный автомат M , допускающий язык L:M = {{1, 2, 3, 4}, {a, b}, D, 1, {4}},где функция переходов D определяется так:D(1, a) = {1, 2}, D(3, a) = {4},D(2, a) = {3},D(3, b) = {4},D(2, b) = {3}.Диаграмма автомата приведена на рис. 3.3, а.б) Детерминированный конечный автомат M , допускающий язык L:M = {{1, 2, 3, 4, 5, 6, 7, 8}, {a, b}, D, 1, {3, 5, 6, 8}},где функция переходов D определяется так:D(1, a) = 2, D(5, a) = 8,D(1, b) = 1, D(5, b) = 6,D(2, a) = 4, D(6, a) = 2,D(2, b) = 7, D(6, b) = 1,D(3, a) = 3, D(7, a) = 8,D(3, b) = 5, D(7, b) = 6,D(4, a) = 3, D(8, a) = 4,D(4, b) = 5, D(8, b) = 7.Диаграмма автомата приведена на рис.
3.3, б.Пример 3.4. Диаграмма ДКА, допускающего множество чисел в десятичнойзаписи, приведена на рис. 3.4.ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ28EDDDEDEDDDEEDEEZEDDEDEDE[Рис. 3.3:Пример 3.5. Анализ цепочек.а) При анализе цепочки w = ababa автомат из примера 3.3, а, может сделатьследующую последовательность тактов:(1, ababa) ` (1, baba) ` (1, aba) ` (2, ba) ` (3, a) ` (4, e).Состояние 4 является заключительным, следовательно, цепочка w допускается этим автоматом.б) При анализе цепочки w = ababab автомат из примера 3.3, б, должен сделать следующую последовательность тактов:(1, ababab) ` (2, babab) ` (7, abab) ` (8, bab) ` (7, ab) ` (8, b) ` (7, e).Так как состояние 7 не является заключительным, цепочка w не допускается этим автоматом.('LJLW'LJLW'LJLW'LJLW'LJLWРис. 3.4:('LJLW'LJLW3.3.
АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ293.3Алгоритмы построения конечных автоматов3.3.1Построение недетерминированного конечного автомата по регулярному выражениюРассмотрим алгоритм построения по регулярному выражению недетерминированного конечного автомата, допускающего тот же язык.Алгоритм 3.1. Построение недетерминированного конечного автомата по регулярному выражению.Вход. Регулярное выражение r в алфавите T .Выход. НКА M , такой что L(M ) = L(r).Метод. Автомат для выражения строится композицией из автоматов, соответствующих подвыражениям.
На каждом шаге построения строящийся автомат имеет в точности одно заключительное состояние, в начальное состояние нет переходов из других состояний и нет переходовиз заключительного состояния в другие.1. Для выражения e строится автоматLHIРис. 3.5:2. Для выражения a (a ∈ T ) строится автоматLDIРис. 3.6:3.
Пусть M (s) и M (t) – НКА для регулярных выражений s и t соответственно.а) Для выражения s|t автомат M (s|t) строится как показано нарис. 3.7. Здесь i – новое начальное состояние и f – новое заключительное состояние. Заметим, что имеет место переходпо e из i в начальные состояния M (s) и M (t) и переход по e иззаключительных состояний M (s) и M (t) в f . Начальное и заключительное состояния автоматов M (s) и M (t) не являютсятаковыми для автомата M (s|t).ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ30LHH0VHH0WIРис.
3.7:б) Для выражения st автомат M (st) строится следующим образом:L0W0VIРис. 3.8:Начальное состояние M (s) становится начальным для нового автомата, а заключительное состояние M (t) становится заключительным для нового автомата. Начальное состояние M (t)и заключительное состояние M (s) сливаются, т.е. все переходы из начального состояния M (t) становятся переходами иззаключительного состояния M (s). В новом автомате это объединенное состояние не является ни начальным, ни заключительным.в) Для выражения s∗ автомат M (s∗ ) строится следующим образом:LHH0VHРис. 3.9:HI3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ31Здесь i – новое начальное состояние, а f – новое заключительное состояние.3.3.2Построение детерминированного конечногоавтомата по недетерминированномуРассмотрим алгоритм построения по недетерминированному конечному автомату детерминированного конечного автомата, допускающего тотже язык.Алгоритм 3.2.
Построение детерминированного конечного автоматапо недетерминированному.Вход. НКА M = (Q, T, D, q0 , F ).Выход. ДКА M 0 = (Q0 , T, D0 , q00 , F 0 ), такой что L(M ) = L(M 0 ).Метод. Каждое состояние результирующего ДКА – это некотороемножество состояний исходного НКА.В алгоритме будут использоваться следующие функции:e-closure(R) (R ⊆ Q) – множество состояний НКА, достижимых изсостояний, входящих в R, посредством только переходов по e, т.е. множество[S={p|(q, e) `∗ (p, e)}q∈Rmove(R, a) (R ⊆ Q) – множество состояний НКА, в которые есть переход на входе a для состояний из R, т.е. множество[S={p|p ∈ D(q, a)}q∈RВначале Q0 и D0 пусты.
Выполнить шаги 1-4:(1) Определить q00 = e-closure({q0 }).(2) Добавить q00 в Q0 как непомеченное состояние.(3) Выполнить следующую процедуру:while (в Q0 есть непомеченное состояние R){пометить R;for (каждого входного символа a ∈ T ){S = e-closure(move(R, a));if (S 6= ∅){if (S ∈/ Q0 )добавить S в Q0 как непомеченное состояние;определить D0 (R, a) = S;ГЛАВА 3.
ЛЕКСИЧЕСКИЙ АНАЛИЗ32}}}(4) Определить F 0 = {S|S ∈ Q0 , S ∩ F 6= ∅}.Пример 3.6. Результат применения алгоритма 3.2 приведен на рис. 3.10.HHDHHEHHHDD$E%D&HDEDEDEE'E(EРис. 3.10:3.3.3Построение детерминированного конечногоавтомата по регулярному выражениюПриведем теперь алгоритм построения по регулярному выражению детерминированного конечного автомата, допускающего тот же язык [10].Пусть дано регулярное выражение r в алфавите T . К регулярномувыражению r добавим маркер конца: (r)#. Такое регулярное выражение будем называть пополненным.
В процессе своей работы алгоритмбудет использовать пополненное регулярное выражение.3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ33Алгоритм будет оперировать с синтаксическим деревом для пополненного регулярного выражения (r)# , каждый лист которого помеченсимволом a ∈ T ∪{e, #}, а каждая внутренняя вершина помечена знакомодной из операций: · (конкатенация), | (объединение), ∗ (итерация).Каждому листу дерева (кроме e-листьев) припишем уникальный номер, называемый позицией, и будем использовать его, с одной стороны,для ссылки на лист в дереве, и, с другой стороны, для ссылки на символ,соответствующий этому листу. Заметим, что если некоторый символ используется в регулярном выражении несколько раз, он имеет несколькопозиций.Теперь, обходя дерево T снизу-вверх слева-направо, вычислим четыре функции: nullable, f irstpos, lastpos и f ollowpos.
Функции nullable,f irstpos и lastpos определены на узлах дерева, а f ollowpos – на множестве позиций. Значением всех функций, кроме nullable, является множество позиций. Функция f ollowpos вычисляется через три остальныефункции.Функция f irstpos(n) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуютпервым символам в подцепочках, генерируемых подвыражением с вершиной в n.
Аналогично, lastpos(n) дает множество позиций, которымсоответствуют последние символы в подцепочках, генерируемых подвыражениями с вершиной n. Для узла n, поддеревья которого (т.е. деревья, у которых узел n является корнем) могут породить пустое слово,определим nullable(n) = true, а для остальных узлов nullable(n) = f alse.Таблица для вычисления функций nullable, f irstpos и lastpos приведена на рис. 3.11.узел nлист eлист i(не e)|/\uv·/\uv∗|vnullable(n)truef alsef irstpos(n)∅{i}lastpos(n)∅{i}nullable(u)orf irstpos(u) ∪ f irstpos(v) lastpos(u) ∪ lastpos(v)nullable(v)nullable(u)if nullable(u) thenif nullable(v) thenandf irstpos(u) ∪ f irstpos(v) lastpos(u) ∪ lastpos(v)nullable(v)else f irstpos(u)else lastpos(v)truef irstpos(v)lastpos(v)Рис. 3.11:Пример 3.7.
Синтаксическое дерево для пополненного регулярного выражения (a|b)∗ abb# с результатом вычисления функций f irstpos и lastpos приведеноГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ34^ ` ^ `^ ` ^ `^ ` ^ `^ ` ^ ` ^ ` E ^ `^ ` ^ ` ^ ` E ^ `^ ` ^ ` ^ `D ^ `^ ` _ ^ `^ ` D ^ `^ ` E ^ `Рис. 3.12:позиция123456f ollowpos{1, 2, 3}{1, 2, 3}{4}{5}{6}∅Рис. 3.13:на рис. 3.12. Слева от каждого узла расположено значение f irstpos, справа от узла – значение lastpos.
Заметим, что эти функции могут быть вычислены за одинобход дерева.Если i – позиция, то f ollowpos(i) есть множество позиций j таких,что существует некоторая строка ... cd ..., входящая в язык, описываемый регулярным выражением, такая, что позиция i соответствует этому вхождению c, а позиция j – вхождению d.Функция f ollowpos может быть вычислена также за один обход дерева снизу-вверх по следующим двум правилам.1. Пусть n – внутренний узел с операцией · (конкатенация), u и v – егопотомки.
Тогда для каждой позиции i, входящей в lastpos(u), добавляемк множеству значений f ollowpos(i) множество f irstpos(v).2. Пусть n – внутренний узел с операцией ∗ (итерация), u – его потомок. Тогда для каждой позиции i, входящей в lastpos(u), добавляем кмножеству значений f ollowpos(i) множество f irstpos(u).3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ35Пример 3.8. Результат вычисления функции f ollowpos для регулярного выражения из предыдущего примера приведен на рис. 3.13.Алгоритм 3.3. Прямое построение ДКА по регулярному выражению.Вход.
Регулярное выражение r в алфавите T .Выход. ДКА M = (Q, T, D, q0 , F ), такой что L(M ) = L(r).Метод. Состояния ДКА соответствуют множествам позиций.Вначале Q и D пусты. Выполнить шаги 1-6:(1) Построить синтаксическое дерево для пополненного регулярноговыражения (r)#.(2) Обходя синтаксическое дерево, вычислить значения функцийnullable, f irstpos, lastpos и f ollowpos.(3) Определить q0 = f irstpos(root), где root – корень синтаксическогодерева.(4) Добавить q0 в Q как непомеченное состояние.(5) Выполнить следующую процедуру:while (в Q есть непомеченное состояние R){пометить R;for (каждого входного символа a ∈ T , такого, чтов R имеется позиция, которой соответствует a){пусть символ a в R соответствует позициямSp1 , ... , pn , и пусть S =f ollowpos(pi );1≤i≤nif (S 6= ∅){if (S ∈/ Q)добавить S в Q как непомеченное состояние;определить D(R, a) = S;}}}(6) Определить F как множество всех состояний из Q, содержащих позиции, связанные с символом #.Пример 3.9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
