В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов, страница 5

Несколько примеров регулярных выражений и обозначаемыхими регулярных множеств:а) a(e|a)|b – обозначает множество {a, b, aa};б) a(a|b)∗ – обозначает множество всевозможных цепочек, состоящих из a иb, начинающихся с a;в) (a|b)∗ (a|b)(a|b)∗ – обозначает множество всех непустых цепочек, состоящих из a и b, т.е. множество {a, b}+ ;г) ((0|1)(0|1)(0|1))∗ – обозначает множество всех цепочек, состоящих из нулей и единиц, длины которых делятся на 3.Ясно, что для каждого регулярного множества можно найти регулярное выражение, обозначающее это множество, и наоборот. Более того, для каждого регулярного множества существует бесконечно многообозначающих его регулярных выражений.Будем говорить, что регулярные выражения равны или эквивалентны (=), если они обозначают одно и то же регулярное множество.Существует ряд алгебраических законов, позволяющих осуществлятьэквивалентное преобразование регулярных выражений.Лемма. Пусть p, q и r – регулярные выражения.

Тогда справедливыследующие соотношения:(1) p|q = q|p;(7)pe = ep = p;(2) ∅∗ = e;(8)∅p = p∅ = ∅;(3) p|(q|r) = (p|q)|r;(9)p∗ = p|p∗ ;(4) p(qr) = (pq)r;(10) (p∗ )∗ = p∗ ;(5) p(q|r) = pq|pr;(11) p|p = p;(6) (p|q)r = pr|qr;(12) p|∅ = p.Следствие. Для любого регулярного выражения существует эквивалентное регулярное выражение, которое либо есть ∅, либо не содержит в своей записи ∅.3.2.

КОНЕЧНЫЕ АВТОМАТЫ25В дальнейшем будем рассматривать только регулярные выражения,не содержащие в своей записи ∅.При практическом описании лексических структур бывает полезносопоставлять регулярным выражениям некоторые имена, и ссылатьсяна них по этим именам. Для определения таких имен мы будем использовать запись видаd1 = r1d2 = r2...dn = rnгде di – различные имена, а каждое ri – регулярное выражение над символами T ∪ {d1 , d2 , ... , di−1 }, т.е. символами основного алфавита и ранее определенными символами (именами). Таким образом, для любого ri можно построить регулярное выражение над T , повторно заменяяимена регулярных выражений на обозначаемые ими регулярные выражения.Пример 3.2.

Использование имен для регулярных выражений.а) Регулярное выражение для множества идентификаторов.Letter = a|b|c| ... |x|y|zDigit = 0|1| ... |9Identif ier = Letter(Letter|Digit)∗б) Регулярное выражение для множества чисел в десятичной записи.Digit = 0|1| ... |9Integer = Digit+F raction = .Integer|eExponent = (E(+| − |e)Integer)|eN umber = Integer F raction Exponent3.2Конечные автоматыРегулярные выражения, введенные ранее, служат для описания регулярных множеств. Для распознавания регулярных множеств служатконечные автоматы.Недетерминированный конечный автомат (НКА) – это пятерка M =(Q, T, D, q0 , F ), где(1) Q – конечное множество состояний;(2) T – конечное множество допустимых входных символов (входнойалфавит);(3) D – функция переходов (отображающая множество Q × (T ∪ {e}) вомножество подмножеств множества Q), определяющая поведениеуправляющего устройства;(4) q0 ∈ Q – начальное состояние управляющего устройства;ГЛАВА 3.

ЛЕКСИЧЕСКИЙ АНАЛИЗ26(5) F ⊆ Q – множество заключительных состояний.Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт определяется текущим состояниемуправляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и, возможно, сдвига входной головки на одну ячейку вправо (рис. 3.2).Khklhygb_IjhqblZggZyqZklv\oh^ghcp_ihqdbDL_dmsbc\oh^ghckbf\heG_ijhqblZggZyqZklv\oh^ghcp_ihqdbРис. 3.2:Недетерминизм автомата заключается в том, что, во-первых, находясь в некотором состоянии и обозревая текущий символ, автомат может перейти в одно из, вообще говоря, нескольких возможных состояний, и во-вторых, автомат может делать переходы по e.Пусть M = (Q, T, D, q0 , F ) – НКА.

Конфигурацией автомата M называется пара (q, w) ∈ Q × T ∗ , где q – текущее состояние управляющегоустройства, а w – цепочка символов на входной ленте, состоящая из символа под головкой и всех символов справа от него. Конфигурация (q0 , w)называется начальной, а конфигурация (q, e), где q ∈ F – заключительной (или допускающей).Пусть M = (Q, T, D, q0 , F ) – НКА. Тактом автомата M называетсябинарное отношение `, определенное на конфигурациях M следующимобразом: если p ∈ D(q, a), где a ∈ T ∪ {e}, то (q, aw) ` (p, w) для всехw ∈ T ∗.Будем обозначать символом `+ (`∗ ) транзитивное (рефлексивнотранзитивное) замыкание отношения `.Говорят, что автомат M допускает цепочку w, если (q0 , w) `∗ (q, e)для некоторого q ∈ F .

Языком, допускаемым (распознаваемым, определяемым) автоматом M , (обозначается L(M )), называется множествовходных цепочек, допускаемых автоматом M . Т.е.L(M ) = {w|w ∈ T ∗ и (q0 , w) `∗ (q, e) для некоторого q ∈ F }.3.2. КОНЕЧНЫЕ АВТОМАТЫ27Важным частным случаем недетерминированного конечного автомата является детерминированный конечный автомат, который на каждом такте работы имеет возможность перейти не более чем в одно состояние и не может делать переходы по e.Пусть M = (Q, T, D, q0 , F ) – НКА. Будем называть M детерминированным конечным автоматом (ДКА), если выполнены следующие дваусловия:(1) D(q, e) = ∅ для любого q ∈ Q, и(2) D(q, a) содержит не более одного элемента для любых q ∈ Q и a ∈ T .Так как функция переходов ДКА содержит не более одного элементадля любой пары аргументов, для ДКА мы будем пользоваться записьюD(q, a) = p вместо D(q, a) = {p}.Конечный автомат может быть изображен графически в виде диаграммы, представляющей собой ориентированный граф, в котором каждому состоянию соответствует вершина, а дуга, помеченная символомa ∈ T ∪ {e}, соединяет две вершины p и q, если p ∈ D(q, a).

На диаграммевыделяются начальное и заключительные состояния (в примерах ниже,соответственно, входящей стрелкой и двойным контуром).Пример 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Рис.