Рассмотрим алгоритм построения по регулярному выражению недетерминированного конечного автомата, допускающего тот же язык.

Алгоритм 3.1 . Построение недетерминированного конечного автомата по регулярному выражению.

Вход . Регулярное выражение r в алфавите T .

Выход . НКА M , такой что L(M) = L(r) .

Метод .Автомат для выражения строится композицией из автоматов, соответствующих подвыражениям. На каждом шаге построения строящийся автомат имеет в точности одно заключительное состояние, в начальное состояние нет переходов из других состояний и нет переходов из заключительного состояния в другие.

Построение детерминированного конечного автомата по недетерминированному

Рассмотрим алгоритм построения по недетерминированному конечному автомату детерминированного конечного автомата, допускающего тот же язык.

Алгоритм 3.2 . Построение детерминированного конечного автомата по недетерминированному.

Вход . НКА M = (Q, T, D, q 0 , F) .

Выход . ДКА .

Метод . Каждое состояние результирующего ДКА - это некоторое множество состояний исходного НКА.

В алгоритме будут использоваться следующие функции: - множество состояний НКА, достижимых из состояний, входящих в R , посредством только переходов по e , то есть множество

Множество состояний НКА, в которые есть переход на входе a для состояний из R , то есть множество

Вначале Q" и D" пусты. Выполнить шаги 1-4:

(1) Определить .

(2) Добавить в Q" как непомеченное состояние

(3) Выполнить следующую процедуру:

(4) Определить .

Пример 3.6 . Результат применения алгоритма 3.2 приведен на рис. 3.10 .

Рис. 3.10.

Построение детерминированного конечного автомата по регулярному выражению

Приведем теперь алгоритм построения по регулярному выражению детерминированного конечного автомата, допускающего тот же язык [?] .

Пусть дано регулярное выражение r в алфавите T . К регулярному выражению r добавим маркер конца: (r)# . Такое регулярное выражение будем называть пополненным. В процессе своей работы алгоритм будет использовать пополненное регулярное выражение.

Алгоритм будет оперировать с синтаксическим деревом для пополненного регулярного выражения (r)#, каждый лист которого помечен символом , а каждая внутренняя вершина помечена знаком одной из операций: (конкатенация), | (объединение), * (итерация).

Каждому листу дерева (кроме e -листьев) присвоим уникальный номер, называемый позицией, и будем использовать его, с одной стороны, для ссылки на лист в дереве, и, с другой стороны, для ссылки на символ, соответствующий этому листу. Заметим, что если некоторый символ используется в регулярном выражении несколько раз, он имеет несколько позиций.

Обойдем дерево T снизу-вверх слева-направо и вычислим четыре функции: nullable,firstpos, lastpos и followpos . Три первые функции - nullable, firstpos и lastpos - определены на узлах дерева, а followpos - на множестве позиций. Значением всех функций, кроме nullable , является множество позиций. Функция followpos вычисляется через три остальные функции.

Функция firstpos(n) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуют первым символам в подцепочках , генерируемых подвыражением с вершиной в n . Аналогично, lastpos(n) дает множество позиций, которым соответствуют последние символы в

ДКА является частным случаем НКА. В нем:

нет состояния с ε-переходами;

для каждого состояния S и входного символа а существует не более одной дуги, исходящей из S и помеченной а.

ДКА имеет лишь максимум один переход для любого входного символа из каждого состояния. Если для представления функции переходов ДКА использовать таблицу, то в каждой записи будет содержаться лишь одно состояние. Таким образом, легко проверить, допускает ли данный ДКА некоторую строчку, так как есть лишь один путь из стартового состояния, который помечен этой строкой.

На рисунке 3 показан граф переходов ДКА, допускающий тот же язык (a|b) * a(a|b)(a|b), что и НКА на рисунке 1.

Рисунок 3. ДКА, допускающий строку (a|b) * a(a|b)(a|b).

Детерминированный конечный автомат M, допускающий данный язык:

M = {{1, 2, 3, 4, 5, 6, 7, 8}, {a, b}, D, 1, {3, 5, 6, 8}}

Функция переходов D определяется так:

Построение нка по регулярному выражению

1. Для ε НКА имеет следующий вид (0 – начальное состояние, 1 – конечное):

2. Для а, входящего в данный язык НКА:

3. Пусть N(s) и N(t) – НКА для регулярных выражений s и t.

Для регулярного выражения s|t составной НКА имеет следующий вид:

b. Для регулярного выражения st НКА:

с. Для выражения s* НКА имеет вид:

d. Для выражения в скобках (s) используется НКА N(s) как в пункте а.

Каждое новое состояние получает индивидуальное имя. Построение НКА N(r) имеет следующие свойства:

N(r) имеет количество состояний, которое не превышает количества символов более чем в 2 раза.

N(r) имеет ровно одно начальное и одно конечное состояние. Конечное состояние не имеет исходящих переходов.

Каждое состояние N(r) имеет либо 1 переход для символа из алфавита (), либо не более 2-й исходящих ε-переходов.

Преобразование нка в дка.

НКА на рисунке 1 имеет 2 перехода из состояния 0 для символа а: состояния 0 и 1. Такой переход неоднозначен, как и переход по ε. Моделирование таких НКА с помощью компьютерной программы значительно затрудняется. Определение допустимости утверждает, что должен существовать некоторый путь из начального состояния к конечному, но когда есть несколько путей для одной и той же входной строки, их надо рассматривать все, чтобы найти путь к заключительному состоянию или выяснить, что такого пути нет.

В таблице переходов НКА каждой записи соответствует множество состояний, а в таблице переходов ДКА – лишь одно. Суть преобразования состоит в том, что каждое состояние ДКА соответствует множеству состояний НКА. ДКА использует свои состояния для отслеживания всех возможных состояний, в которых НКА может находиться после чтения очередного входного символа. То есть после чтения входного потока ДКА находится в состоянии, которое представляет некоторое множество состояний НКА, достижимых из начального по пути, соответствующему входной строке. Количество таких состояний ДКА может значительно превышать количество состояний НКА (экспоненциальная зависимость), но на практике это встречается крайне редко, а порой в ДКА даже меньше состояний, чем в НКА.

Рассмотрим подобное преобразование на конкретном примере. На рисунке 4 изображен еще один НКА, который допускает язык (a|b) * a(a|b)(a|b) (как и на рисунках 1 и 3).

Рисунок 4. НКА, допускающий язык (a|b) * a(a|b)(a|b)

Изображенный на рисунке переход из состояния 13 в состояние 14 может быть представлен аналогично переходу из 8-го в 13-е состояние.

Построим ДКА для данного языка. Стартовое состояние эквивалентного ДКА представляет собой состояние A ={0, 1, 2, 4, 7}, то есть те состояния, в которые можно попасть из 0 по ε.

Алфавит входных символов представляет собой {a, b}. Из начального состояния А можно вычислить состояние, достижимое по а. Назовем это состояние В = {1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14}.

Среди состояний в А только состояние 4 имеет переход по b в состояние 5, так что ДКА имеет переход по b из А в состояние С = {1, 2, 4, 5, 6, 7}.

Если продолжить этот процесс с состояниями В и С, все множества состояний НКА будут помечены. Таким образом будем иметь множества состояний:

A = {0, 1, 2, 4, 7}

В = {1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14}

С = {1, 2, 4, 5, 6, 7}

D = {10, 12, 13, 14}

Состояние А – начальное, а состояния B, D, E – заключительные.

Полностью таблица переходов приведена ниже.

Ниже на рисунке 5 приведен сам ДКА для этого языка.

Рисунок 5. ДКА, допускающий язык (a|b) * a(a|b)(a|b)

Список использованной литературы:

Пентус А. Е., Пентус М. Р. – Теория формальных языков

А. Ахо, Р. Сети, Д, Ульман – Компиляторы: принципы, технологии, инструменты.

Для дальнейшего изучения свойств конечных автоматов и, в частности, для решения задачи синтеза важное значение имеет следующая теорема.

Теорема 7.7 (теорема о детерминизации). Для любого конечного автомата может быть построен эквивалентный ему детерминированный конечный автомат.

Для того чтобы доказать теорему, нужно, во-первых, описать алгоритм построения детерминированного конечного автомата по исходному; во-вторых, обосновать этот алгоритм, строго доказав, что он действительно дает конечный автомат, который является детерминированным и эквивалентным исходному. Здесь мы приведем только сам алгоритм построения детерминированного автомата.

Преобразование произвольного конечного автомата к эквивалентному детерминированному осуществляется в два этапа: сначала удаляются дуги с меткой \lambda , затем проводится собственно детерминизация.

1. Удаление λ-переходов (дуг с меткой \lambda ).

Чтобы перейти от исходного конечного автомата M=(V,Q,q_0,F,\delta) к эквивалентному конечному автомату M"=(V,Q",q_0,F",\delta") без λ-переходов, достаточно в исходном графе M проделать следующие преобразования.

а. Все состояния, кроме начального, в которые заходят только дуги с меткой \lambda , удаляются; тем самым определяется множество Q" конечного автомата M" . Понятно, что Q"\subseteq Q . При этом полагаем, что начальное состояние остается прежним.

б. Множество дуг конечного автомата M" и их меток (тем самым и функция переходов M" ) определяется так: для любых двух состояний p,r\in Q",~ p\to_{a}r имеет место тогда и только тогда, когда a\in V , а в графе M имеет место одно из двух: либо существует дуга из p в r , метка которой содержит символ a , либо существует такое состояние q , что p\Rightarrow_{\lambda}^{+}q и q\to_{a}r . При этом вершина q , вообще говоря, может и не принадлежать множеству Q" , т.е. она может и исчезнуть при переходе к автомату M" (рис. 7.11). Если же q\in Q" , то, естественно, в M" сохранится дуга (q,r) и символ a будет одним из символов, принадлежащих метке этой дуги (рис. 7.12).

Таким образом, в M" сохраняются все дуги M , метки которых отличны от \lambda и которые соединяют пару (вершин) состояний из множества Q" (не удаляемых согласно п. а). Кроме этого, для любой тройки состояний p,q,r (не обязательно различных!), такой, что p,r\in Q" и существует путь ненулевой длины из p в q , метка которого равна \lambda (т.е. путь по λ-переходам), а из q в r ведет дуга, метка которой содержит символ a входного алфавита, в M" строится дуга из p в r , метка которой содержит символ a (см. рис. 7.11).

в. Множество заключительных состояний F" конечного автомата M" содержит все состояния q\in Q" , т.е. состояния конечного автомата M , не удаляемые согласно п. а, для которых имеет место q\Rightarrow_{\lambda}^{\ast}q_f для некоторого q_f\in F (т.е. либо состояние q само является заключительным состоянием конечного автомата M , либо из него ведет путь ненулевой длины по дугам с меткой \lambda в одно из заключительных состояний конечного автомата M ) (рис. 7.13).

2. Собственно детерминизация.

Пусть M=(Q,V,q_0,F,\delta) - конечный автомат без λ-переходов. Построим эквивалентный M детерминированный конечный автомат M_1 .

Этот конечный автомат определяется таким образом, что его множество состояний есть множество всех подмножеств множества состояний конечного автомата M . Это значит, что каждое отдельное состояние конечного автомата M_1 определено как некоторое подмножество множества состояний конечного автомата M . При этом начальным состоянием нового конечного автомата (т.е. M_1 ) является одноэлементное подмножество, содержащее начальное состояние старого конечного автомата (т.е. M ), а заключительными состояниями нового конечного автомата являются все такие подмножества Q , которые содержат хотя бы одну заключительную вершину исходного конечного автомата M .

Впредь, допуская некоторую вольность речи, мы будем иногда называть состояния конечного автомата M_1 состояниями-множествами. Важно, однако, четко усвоить, что каждое такое состояние-множество есть отдельное состояние нового конечного автомата, но никак не множество его состояний. В то же время для исходного ("старого") конечного автомата M это именно множество его состояний. Образно говоря, каждое подмножество состояний старого конечного автомата "свертывается" в одно состояние нового конечного автомата*.

*Формально следовало бы определить множество Q_1 как множество, находящееся во взаимно однозначном соответствии с множеством 2^Q , но нам все-таки удобнее считать, что Q_1 совпадает с 2^Q , - ведь множеством состояний конечного автомата может быть любое непустое конечное множество.

Функция переходов нового конечного автомата определена так, что из состояния-множества S по входному символу а конечный автомат M_1 переходит в состояние-множество, представляющее собой объединение всех множеств состояний старого конечного автомата, в которые этот старый конечный автомат переходит по символу а из каждого состояния множества S . Таким образом, конечный автомат M_1 является детерминированным по построению.

Приведенное выше словесное описание можно перевести в формулы следующим образом: строим конечный автомат M_1 так, что

M_1=(Q_1,V,\{q_0\},F_1,\delta_1) , где

\begin{cases}Q_1=2^Q,\quad F_1=\{T\colon\, T\cap F\ne\varnothing,~T\in2^Q\},\\ (\forall S\subseteq Q)(\forall a\in V)\Bigl(\delta_1(S,a)= \bigcup\limits_{q\in S}\delta(q,a)\Bigr). \end{cases}

Обратим внимание на то, что среди состояний нового конечного автомата есть состояние \varnothing , причем, согласно (7.8), \delta_1(\varnothing,a)=\varnothing для любого входного символа a . Это значит, что, попав в такое состояние, конечный автомат M_1 уже его не покинет. Вообще же любое состояние q конечного автомата, такое, что для любого входного символа a имеем \delta(q,a)=q , называют поглощающим состоянием конечного автомата. Таким образом, состояние \varnothing детерминированного конечного автомата M_1 является поглощающим. Полезно заметить также, что \delta_1(S,a)=\varnothing тогда и только тогда, когда для каждого q\in S (состояния старого конечного автомата из множества состояний S ) \delta(q,a)=\varnothing , т.е. в графе M из каждого такого состояния q не выходит ни одна дуга, помеченная символом a .

Можно доказать, что полученный по такому алгоритму конечный автомат эквивалентен исходному.

Пример 7.9. Детерминизируем конечный автомат, изображенный на рис. 7.14.

Эквивалентный конечный автомат без λ-переходов изображен на рис. 7.15. Заметим, что вершина q_2 исчезает, так как в нее заходят только "пустые" дуги.

Чтобы детерминизировать полученный автомат, совершенно не обязательно выписывать все его 2^3=8 состояний, среди которых многие могут оказаться не достижимыми из начального состояния \{q_0\} . Чтобы получить достижимые из \{q_0\} состояния, и только их, воспользуемся так называемым методом вытягивания.

Этот метод в общем случае можно описать так.

В исходном конечном автомате (без пустых дуг) определяем все множества состояний, достижимых из начального, т.е. для каждого входного символа a находим множество \delta(q_0,a) . Каждое такое множество в новом автомате является состоянием, непосредственно достижимым из начального.

Для каждого из определенных состояний-множеств S и каждого входного символа a находим множество \textstyle{\mathop{\bigcup\limits_{q\in S} \delta(q,a)}\limits^{\phantom{A}^{.}}} . Все полученные на этом шаге состояния будут состояниями нового (детерминированного) автомата, достижимыми из начальной вершины по пути длины 2. Описанную процедуру повторяем до тех пор, пока не перестанут появляться новые состояния-множества (включая пустое!). Можно показать, что при этом получаются все такие состояния конечного автомата M_1 , которые достижимы из начального состояния \{q_0\} .

Для конечного автомата на рис. 7.15 имеем:

\begin{aligned}& \delta_1(\{q_0\},a)=\{q_1\};\qquad \delta_1(\{q_0\},b)=\{q_1,q_3\};\\ & \delta_1(\{q_1\},a)=\{q_1\};\qquad \delta_1(\{q_1\},b)=\{q_1\};\\ & \delta_1(\{q_1,q_3\},a)= \delta(q_1,a)\cup \delta(q_3,a)= \{q_1\}\cup\{q_1\}=\{q_1\};\\ & \delta_1(\{q_1,q_3\},b)= \delta(q_1,b)\cup \delta(q_3,b)= \{q_1\}\cup\{q_1\}=\{q_1\}. \end{aligned}

Так как новых состояний-множеств больше не появилось, процедура "вытягивания" на этом заканчивается, и мы получаем граф, изображенный на рис. 7.16.

Дополнение регулярного языка

Одним из важных теоретических следствий теоремы о детерминизации является следующая теорема.

Теорема 7.8. Дополнение регулярного языка есть регулярный язык.

Пусть L - регулярный язык в алфавите V . Тогда дополнение языка L (как множества слов) есть язык \overline{L}=V^{\ast}\setminus L .

Согласно теореме 7.7, для регулярного языка L может быть построен детерминированный конечный автомат M , допускающий L . Поскольку в детерминированном автомате из каждой вершины по каждому входному символу определен переход в точности в одну вершину, то, какова бы ни была цепочка x в алфавите V , для нее найдется единственный путь в M , начинающийся в начальном состоянии, на котором читается цепочка x . Ясно, что цепочка x допускается автоматом M , то есть x\in L(M) , тогда и только тогда, когда последнее состояние указанного пути является заключительным. Отсюда следует, что цепочка x\notin L(M) тогда и только тогда, когда последнее состояние указанного пути не заключительное. Но нам как раз и нужен конечный автомат M" , который допускает цепочку x тогда и только тогда, когда ее не допускает исходный конечный автомат M . Следовательно, превращая каждое заключительное состояние M в не заключительное и наоборот, получим детерминированный автомат, допускающий дополнение языка L .

Доказанная теорема позволяет строить конечный автомат, не допускающий определенное множество цепочек, следующим методом: строим сначала автомат, допускающий данное множество цепочек, затем детерминизируем его и переходим к автомату для дополнения так, как это указано в доказательстве теоремы 7.8.

Пример 7.10. а. Построим конечный автомат, допускающий все цепочки в алфавите \{0;1\} , кроме цепочки 101.

Сначала построим конечный автомат, допускающий единственную цепочку 101. Этот автомат приведен на рис. 7.17.

Этот автомат квазидетерминированный, но не детерминированный, так как он не полностью определен. Проведем его детерминизацию и получим детерминированный эквивалентный конечный автомат, изображенный на рис. 7.18.

И наконец, переходя к дополнению (и переименовывая состояния), получим автомат, изображенный на рис. 7.19.

Обратим внимание, что в полученном автомате все вершины, кроме вершины s_3 , являются заключительными.

Заметим также, что переход к дополнению, о котором идет речь в доказательстве теоремы 7.8, может быть проведен только в детерминированном автомате. Если бы мы поменяли ролями заключительные и незаключительные вершины в автомате, изображенном на рис. 7.17, то получили бы автомат, допускающий язык \{\lambda,1,10\} , который не является - как нетрудно сообразить - множеством всех цепочек, отличных от цепочки 101.

Отметим также, что конечный автомат на рис. 7.19 допускает все цепочки, содержащие вхождение цепочки 101, но не совпадающие с самой этой цепочкой. Вот, например, путь, несущий цепочку 1011: s_0,s_1,s_2,s_3,t .

б. Построим конечный автомат, допускающий все цепочки в алфавите \{0;1\} , кроме тех, которые содержат вхождение цепочки 101. Рассмотрим язык L , каждая цепочка которого содержит вхождение цепочки 101. Его можно задать так:

L=(0+1)^{\ast}101(0+1)^{\ast}.

Нам нужно построить автомат для дополнения языка L .

Непосредственно по регулярному выражению в этом случае легко построить конечный автомат, допускающий язык L (рис. 7.20).

Затем методом "вытягивания" проведем детерминизацию. Результат детерминизации представлен на рис. 7.21.

Для полного решения задачи осталось только на рис. 7.21 поменять ролями заключительные и не заключительные вершины (рис. 7.22).

в. Обсудим идею построения конечного автомата, допускающего те и только те цепочки в алфавите \{0;1\} , которые не начинаются цепочкой 01 и не заканчиваются цепочкой 11 (т.е. не разрешаются цепочки вида 01x и цепочки вида y11 , каковы бы ни были цепочки x,y\in\{0;1\} ).

В этом случае дополнением языка, для которого нужно построить конечный автомат, является множество всех таких цепочек нулей и единиц, которые начинаются цепочкой 01 или заканчиваются цепочкой 11. Допускающий это множество цепочек автомат строится как автомат для объединения 01(0+1)^{\ast}+(0+1)^{\ast}11 тем способом, который изложен при доказательстве теоремы Клини (см. теорему 7.6).

Из свойства замкнутости класса регулярных языков относительно дополнения (см. теорему 7.8) немедленно вытекает замкнутость этого класса относительно пересечения, теоретико-множественной и симметрической разности.

Следствие 7.3. Для любых двух регулярных языков L_1 и L_2 справедливы следующие утверждения:

1) пересечение L_1\cap L_2 регулярно;
2) разность L_1\setminus L_2 регулярна;
3) симметрическая разность L_1\vartriangle L_2 регулярна.

Справедливость утверждений вытекает из тождеств:

\begin{aligned} &{\scriptstyle{\mathsf{1)}}}\quad L_1\cap L_2= \overline{\overline{L_1} \cup\overline{L_2}}\,;\\ &{\scriptstyle{\mathsf{2)}}}\quad L_1\setminus L_2= L_1\cap \overline{L_2}\,;\\ &{\scriptstyle{\mathsf{3)}}}\quad L_1\,\triangle\,L_2 = (L_1\cup L_2)\setminus (L_1\cap L_2).\end{aligned}

Во-первых, полученные результаты позволяют утверждать, что класс регулярных языков относительно операций объединения, пересечения и дополнения является булевой алгеброй, в которой единицей служит универсальный язык, а нулем - пустой язык. Во-вторых, эти алгебраические свойства семейства регулярных языков позволяют решить важную проблему распознавания эквивалентности двух произвольных конечных автоматов.

Согласно определению 7.10, конечные автоматы эквивалентны, если допускаемые ими языки совпадают. Поэтому, чтобы убедиться в эквивалентности автоматов M_1 и M_2 , достаточно доказать, что симметрическая разность языков L(M_1) и L(M_2) пуста. Для этого, в свою очередь, достаточно построить автомат, допускающий эту разность, и убедиться в том, что допускаемый им язык пуст. В общем случае проблему распознавания того, что язык конечного автомата пуст, называют проблемой пустоты для конечного автомата. Чтобы решить эту проблему, достаточно найти множество заключительных состояний автомата, достижимых из начального состояния. Так как конечный автомат - это ориентированный граф, то решить такую проблему можно, например, с помощью, поиска в ширину. Язык, допускаемый конечным автоматом, пуст тогда и только тогда, когда множество заключительных состояний, достижимых из начального состояния, пусто. Практически эквивалентность конечных автоматов предпочтительнее распознавать, используя алгоритм минимизации, но сейчас нам важно подчеркнуть, что принципиальная возможность решить проблему эквивалентности вытекает из теоремы 7.7 и ее алгебраических следствий.

В этом разделе мы сформируем важные вопросы, связанные с регулярными языками. Сначала нужно разобраться, что значит задать вопрос о некотором языке. Типичный язык бесконечен, поэтому бессмысленно предъявлять кому-нибудь цепочки этого языка и задавать вопрос, требующий проверки бесконечного множества цепочек. Гораздо разумнее использовать одно из конечных представлений языка, а именно: ДКА, НКА, ε- НКА или регулярное выражение.

Очевидно, что представленные таким образом языки будут регулярными. В действительности не существует способа представления абсолютно произвольных языков. В следующих главах предлагаются конечные методы описания более широких классов, чем класс регулярных языков, и можно будет рассматривать вопросы о языках из них. Однако алгоритмы разрешения многих вопросов о языках существуют только для класса регулярных языков. Эти же вопросы становятся “неразрешимыми” (не существует алгоритмов ответов на эти вопросы), если они поставлены с помощью более “выразительных” обозначений (используемых для выражения более широкого множества языков), чем представления, разработанные для регулярных языков.

Начнем изучение алгоритмов для вопросов о регулярных языках, рассмотрев способы, которыми одно представление языка преобразуется в другое. В частности, рассмотрим временную сложность алгоритмов, выполняющих преобразования. Затем рассмотрим три основных вопроса о языках.

1. Является ли описываемый язык пустым множеством?

2. Принадлежит ли некоторая цепочка w представленному языку?

3. Действительно ли два разных описания представляют один и тот же язык? (Этот вопрос часто называют “эквивалентностью” языков.)

2.1 Преобразования различных представлений языков

Каждое из четырех представлений регулярных языков можно преобразовать в любое из остальных трех. На рис. 3.1 представлены переходы от одного представления к другому. Хотя существуют алгоритмы для любого из этих преобразований, иногда нас интересует не только осуществимость некоторого преобразования, но и время, необходимое для его выполнения. В частности, важно отличать алгоритмы, которые занимают экспоненциальное время (время как функция от размера входных данных) и, следовательно, могут быть выполнены только для входных данных сравнительно небольших размеров, от тех алгоритмов, время выполнения которых является линейной, квадратичной или полиномиальной с малой степенью функцией от размера входных данных. Последние алгоритмы “реалистичны”, так как их можно выполнить для гораздо более широкого класса экземпляров задачи. Рассмотрим временную сложность каждого из обсуждавшихся преобразований.

Преобразование НКА в ДКА

Время выполнения преобразования НКА или ε-НКА в ДКА может быть экспоненциальной функцией от количества состояний НКА. Начнем с того, что вычисление ε-замыкания n состояний занимает время O(n3). Необходимо найти все дуги с меткой ε, ведущие от каждого из n состояний. Если есть n состояний, то может быть не более n2 дуг. Разумное использование системных ресурсов и хорошо спроектированные структуры данных гарантируют, что время исследования каждого состояния не превысит O(n2). В действительности для однократного вычисления всего ε-замыкания можно использовать такой алгоритм транзитивного замыкания, как алгоритм Уоршалла (Warshall)5.

После вычисления ε-замыкания можно перейти к синтезу ДКА с помощью конструкции подмножеств. Основное влияние на расход времени оказывает количество состояний ДКА, которое может равняться 2n. Для каждого состояния можно вычислить переходы за время O(n3), используя ε-замыкание и таблицу переходов НКА для каждого входного символа. Предположим, нужно вычислить δ({q1, q2, …, qk}, a) для ДКА. Из каждого состояния qi можно достичь не более n состояний вдоль путей с меткой ε, и каждое из этих состояний может иметь не более, чем n дуг с меткой a. Создав массив, проиндексированный состояниями, можно вычислить объединение не более n множеств, состоящих из не более, чем n состояний, за время, пропорциональное n2.

Таким способом для каждого состояния qi можно вычислить множество состояний, достижимых из qi вдоль пути с меткой a (возможно, включая дуги, отмеченные ε). Поскольку k ≤ n, то существует не более n таких состояний qi, и для каждого из них вычис-ление достижимых состояний занимает время O(n2). Таким образом, общее время вычисления достижимых состояний равно O(n3). Для объединения множеств достижимых состояний потребуется только O(n2) дополнительного времени, следовательно, вычисление одного перехода ДКА занимает время O(n3).

Заметим, что количество входных символов считается постоянным и не зависит от n. Таким образом, как в этой, так и в других оценках времени работы количество входных символов не рассматривается. Размер входного алфавита влияет только на постоянный коэффициент, скрытый в обозначении “О большого”.

Итак, время преобразования НКА в ДКА, включая ситуацию, когда НКА содержит ε-переходы, равно O(n32n). Конечно, на практике обычно число состояний, которые строятся, намного меньше 2n. Иногда их всего лишь n. Поэтому можно установить оценку времени работы равной O(n3s), где s - это число состояний, которые в действительности есть у ДКА.

Преобразование ДКА в НКА

Это простое преобразование, занимающее время O(n) для ДКА с n состояниями. Все, что необходимо сделать, - изменить таблицу переходов для ДКА, заключив в скобки {} состояния, а также добавить столбец для ε, если нужно получить ε-НКА. Поскольку число входных символов (т.е. ширина таблицы переходов) считается постоянным, копирование и обработка таблицы занимает время O(n).

Преобразование автомата в регулярное выражение

Каждом из n этапов (где n - число состояний ДКА) размер конструируемого регулярного выражения может увеличиться в четыре раза, так как каждое выражение строится из четырех выражений предыдущего цикла. Таким образом, простая запись n3 выражений может занять время O(n34n). Улучшенная конструкция из раздела 3.2.2 уменьшает постоянный коэффициент, но не влияет на экспоненциальность этой задачи (в наихудшем случае).

Аналогичная конструкция требует такого же времени работы, если преобразуется НКА, или даже ε-НКА, но это здесь не доказывается. Однако использование конструкции для НКА имеет большое значение. Если сначала преобразовать НКА в ДКА, а затем ДКА - в регулярное выражение, то на это потребуется время O(n34n32n), которое является дважды экспоненциальным.

Преобразование регулярного выражения в автомат

Для преобразования регулярного выражения в ε-НКА потребуется линейное время. Необходимо эффективно проанализировать регулярное выражение, используя метод, занимающий время O(n) для регулярного выражения длины n6. В результате получим дерево с одним узлом для каждого символа регулярного выражения (хотя скобки в этом дереве не встречаются, поскольку они только управляют разбором выражения).

Полученное дерево заданного регулярного выражения можно обработать, конструируя ε-НКА для каждого узла. Правила преобразования регулярного выражения, представленные в разделе 3.2.3, никогда не добавляют более двух состояний и четырех дуг для каждого узла дерева выражения. Следовательно, как число состояний, так и число дуг результирующего ε-НКА равны O(n). Кроме того, работа по созданию этих элементов в каждом узле дерева анализа является постоянной при условии, что функция, обрабатывающая каждое поддерево, возвращает указатели в начальное и допускающие состояния этого автомата.

Приходим к выводу, что построение ε-НКА по регулярному выражению занимает время, линейно зависящее от размера выражения. Можно исключить ε-переходы из ε- НКА с n состояниями, преобразовав его в обычный НКА за время O(n3) и не увеличив числа состояний. Однако преобразование в ДКА может занять экспоненциальное время.

Необходимо по недетерминированному конечному автомату M = (Q , T , D , q 0 , F ) построить детерминированный конечный автомат M = (Q" , T , D" , q" 0 , F" ). Начальным состоянием для строящегося автомата является ε-замыкание начального состояния автомата исходного. ε-замыкание - множество состояний, которые достижимы из данного путём переходов по ε. Далее, пока есть состояния, для которых не построены переходы (переходы делаются по символам, переходы по которым есть в исходном автомате), для каждого символа вычисляется ε-замыкание множества состояний, которые достижимы из рассматриваемого состояния путём перехода по рассматриваемому символу. Если состояние, которое соответствует найденному множеству, уже есть, то добавляется переход туда. Если нет, то добавляется новое полученное состояние.

Пример

Инициализация

Помечаются состояния, соответствующие ε-замыканию начального. Эти состояния будут соответствовать состоянию A будущего ДКА.

Первая итерация

Из ε-замыкания есть переходы в состояния НКА 3 и 10 (по a и c , соответственно). Для состояния 3 ε-замыканием является множество состояний {3, 4, 6}, для состояния 10 - {10}. Обозначим соответствующие данным множествам новые состояния ДКА как B и C .

Состояние ДКА	Множество состояний НКА
		a	b	c
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	-	-
C	{10}	-	-	-

Вторая итерация

Из множества состояний НКА {3, 4, 6}, соответствующего состоянию ДКА B есть два перехода - в состояние 5 (по b ) и 7 (по c ). Их ε-замыкания пересекаются, но сами множества различны, поэтому им ставятся в соответствие два новых состояния ДКА - D и E . Из состояний НКА, соответствующих состоянию ДКА C , никаких переходов нет.

Состояние ДКА	Множество состояний НКА	Символы, по которым осуществляется переход
		a	b	c
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	D	E
C	{10}	-	-	-
D	{2, 5, 8, 9}	-	-	-
E	{2, 7, 8, 9}	-	-	-

Третья итерация

Из множеств состояний НКА, соответствующих состояниям ДКА D и E переходы делаются в множества состояний, соответствующие уже имеющимся состояниям (из множества {2, 5, 8, 9}, соответствующего состоянию D , по a переход в состояние 3, принадлежащее множеству {3, 4, 6}, соответствующему состоянию ДКА B , по c - переход в состояние 10, соответствующее состоянию C ; аналогично для множества, соответствующего состоянию ДКА E ). Процесс построения таблицы состояний и переходов ДКА завершён.

Состояние ДКА	Множество состояний НКА	Символы, по которым осуществляется переход
		a	b	c
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	D	E
C	{10}	-	-	-
D	{2, 5, 8, 9}	B	-	C
E	{2, 7, 8, 9}	B	-	C

Результат:

Построение праволинейной грамматики по конечному автомату

Каждому состоянию ставим в соответствие нетерминал. Если есть переход из состояния X в состояние Y по а , добавляем правило X → aY . Для конечных состояний добавляем правила X → ε. Для ε-переходов - X → Y .

Пример 1 (детерминированный конечный автомат)

• A → a B | c C
• B → b D | c E
• C → ε
• D → a B | c C
• E → a B | c C

Пример 2 (недетерминированный конечный автомат)

• 1 → 2 | 9
• 2 → a 3
• 3 → 4 | 6
• 4 → b 5
• 5 → 8
• 6 → c 7
• 7 → 8
• 8 → 2 | 9
• 9 → c 10
• 10 → ε

Построение ДКА по РВ

Пусть есть регулярное выражение r . По данному регулярному выражению необходимо построить детерминированный конечный автомат D такой, что L (D ) = L (r ).

Модификация регулярного выражения

Добавим к нему символ, означающий конец РВ - «#». В результате получим регулярное выражение (r )#.

Построение дерева

Представим регулярное выражение в виде дерева, листья которого - терминальные символы, а внутренние вершины - операции конкатенации «.», объединения «∪» и итерации «*». Каждому листу дерева (кроме ε-листьев) припишем уникальный номер и ссылаться на него будем, с одной стороны, как на позицию в дереве и, с другой стороны, как на позицию символа, соответствующего листу.

Вычисление функций nullable, firstpos, lastpos

Теперь, обходя дерево T снизу вверх слева-направо, вычислим три функции: nullable , firstpos , и lastpos . Функции nullable , firstpos и lastpos определены на узлах дерева. Значением всех функций, кроме nullable , является множество позиций. Функция firstpos (n ) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуют первым символам в подцепочках, генерируемых подвыражением с вершиной в n . Аналогично, lastpos (n ) дает множество позиций, которым соответствуют последние символы в подцепочках, генерируемых подвыражениями с вершиной n . Для узлов n , поддеревья которых (т. е. дерево, у которого узел n является корнем) могут породить пустое слово, определим nullable (n ) = true , а для остальных узлов false . Таблица для вычисления nullable , firstpos , lastpos :

узел n	nullable (n )	firstpos (n )	lastpos (n )
ε	true	∅	∅
i ≠ ε	false	{i }	{i }
u ∪ v	nullable (u ) or nullable (v )	firstpos (u ) ∪ firstpos (v )	lastpos (u ) ∪ lastpos (v )
u . v	nullable (u ) and nullable (v )	if nullable (u ) then firstpos (u ) ∪ firstpos (v ) else firstpos (u )	if nullable (v ) then lastpos (u ) ∪ lastpos (v ) else lastpos (v )
v*	true	firstpos (v )	lastpos (v )

Построение followpos

Функция followpos вычисляется через nullable , firstpos и lastpos . Функция followpos определена на множестве позиций. Значением followpos является множество позиций. Если i - позиция, то followpos (i ) есть множество позиций j таких, что существует некоторая строка...cd ..., входящая в язык, описываемый РВ, такая, что i соответствует этому вхождению c , а j - вхождению d . Функция followpos может быть вычислена также за один обход дерева по следующим двум правилам

1. Пусть n - внутренний узел с операцией «.» (конкатенация); a , b - его потомки. Тогда для каждой позиции i , входящей в lastpos (a followpos (i ) множество firstpos (b ).
2. Пусть n - внутренний узел с операцией «*» (итерация), a - его потомок. Тогда для каждой позиции i , входящей в lastpos (a ), добавляем к множеству значений followpos (i ) множество firstpos (а ).

Пример

Вычислить значение функции followpos для регулярного выражения (a (b |c ))*c .

Позиция	Значение followpos
1: (a (b |c ))*c	{2, 3}
2: (a (b |c ))*c	{1, 4}
3: (a (b |c ))*c	{1, 4}
4: (a (b |c ))*c	{5}

Построение ДКА

ДКА представляет собой множество состояний и множество переходов между ними. Состояние ДКА представляет собой множество позиций. Построение ДКА заключается в постепенном добавлении к нему необходимых состояний и построении переходов для них. Изначально имеется одно состояние, firstpos (root ) (root - корень дерева), у которого не построены переходы. Переход осуществляется по символам из регулярного выражения. Каждому символу соответствует множество позиций {p i }. Объединение всех followpos (x) есть состояние в которое необходимо перейти, где x - позиция, присутствующая как среди позиций состояния и так и среди позиций символа из РВ, по которому осуществляется переход. Если такого состояния нет, то его необходимо добавить. Процесс нужно повторять, пока не будут построены все переходы для всех состояний. Конечными объявляются все состояния, содержащие позицию добавленного в конец РВ символа #.

ДКА, полученный из РВ (a (b |c ))*c

Пример

Построить ДКА по регулярному выражению (a (b |c ))*c .

Состояние ДКА	Символ
	a {1}	b {2}	c {3, 4}
A {1, 4}	B {2, 3}	-	C {5}
B {2, 3}	-	A {1, 4}	A {1, 4}
C {5}	-	-	-

Построение ДКА с минимальным количеством состояний

ДКА с минимальным числом состояний строится для всюду определённого ДКА, т.е. такого, что . Для любого ДКА существует эквивалентный ему всюду определённый ДКА.

Построение всюду определённого ДКА

Введём новое состояние и определим новое множество состояний .

Определим новую функцию перехода так:

Построение разбиения (формально)

Построим начальное разбиение П множества состояний на две группы: заключительные состояния F и остальные S\F , т. е. П = {F , Q\F }.

Применить к каждой группе G ∈ П следующую процедуру. Разбить G на подгруппы так, чтобы состояния s и t из G оказались в одной группе тогда и только тогда, когда для каждого входного символа a состояния s и t имеют переходы по a в состояния из одной и той же группы в П .

Полученные подгруппы добавляем в новое разбиение П new .

Принимаем П = П new и повторяем построение разбиения до стабилизации, т. е. пока разбиение не перестанет меняться.

Построение разбиения (алгоритм)

Для построения разбиения существует следующий алгоритм. Строим таблицу переходов для исходного автомата, строим начальное разбиение.

Каждой группе из разбиения назначаем идентификатор (для начального разбиения, например, 0 и 1).

Каждому состоянию (каждой строке таблицы) приписываем строку вида “a.bcd…xyz”, где - идентификатор группы, к которой принадледжит состояние из [первого столбца (откуда переходим), второго столбца (куда переходим по первому символу), …, последнего столбца (куда переходим по последнему символу)].

Строим новые группы по совпадению строк, т. е. так, чтобы в одну группу попали состояния с одинаковыми приписанными строками.

Затем, новая итерация. Назначаем получившимся группам новые идентификаторы, например {0, 1, …, n}. И повторяем построение разбиения до стабилизации.

Заметим, что когда в группе осталось одно состояние, на последующих этапах построения разбиения можно уже не выписывать строку идентификаторов для этого состояния, т. к. эта строка в любом случае будет уникальна за счёт первого символа строки. Иначе говоря, при разбиении с группой из одного состояния ничего не случится - она переносится в новое разбиение как есть.

Построение приведённого автомата

Каждая из получившихся групп становится состоянием нового ДКА. Если группа содержит начальное (заключительное) состояние исходного автомата, эта группа становится начальным (соответственно заключительным) состоянием нового ДКА. Переходы строятся очевидным образом: переход в состояние из группы считается переходом в группу.

Приводим автомат. Удаляем сначала непорождающие (бесплодные, «мёртвые»), затем недостижимые состояния (определения даны для символов, но очевидным образом переносятся на состояния автомата).

Вообще говоря, удаление мертвых состояний превращает ДКА в НКА, поскольку в ДКА все переходы должны быть определены. Однако в Dragon Book такое отклонение от формального определения считается всё же допустимым .

Пример

Для построим ДКА с минимальным числом состояния для ДКА следующего вида:

• Начальное разбиение: {C} (конечное состояние ), {A, B, D, E} (все остальные состояния ).
• {C} (без изменений ), {A, D, E}, {B}, (так как из A, D, E по a, c переходим в B и C соответственно ).
• Больше никаких разбиений сделать не можем.

Пусть группе {C} соответствует состояние С, группе {A, D, E} - состояние A, а группе {B} - состояние B. Тогда получаем ДКА с минимальным числом состояний:

Пример (алгоритм построения разбиения)

Таблица переходов для всюду определённого (добавлено состояние Z) ДКА, соответствующего РВ (ab|ε)a*|abb|b*a. Из заданий экзамена 2012 года.

	a	b	I 0	I 1
→A*	B	C	0.01	0.12
B*	D	E	0.00	1.01
C	F	C	1.01
D*	D	Z	0.01	0.04
E*	D	Z	0.00	1.03
F*	Z	Z	0.11
Z	Z	Z	1.11

Итерации:

• I 0: ABCDEF(0), CZ(1).
• I 1: AD(0), BE(1), C(2), F(3), Z(4).
• I 2: A, B, C, D, E, F, Z.

Результат: в автомате и так было минимальное число состояний:-)

ДКА, допускающий дополнение языка

Алгоритм построения ДКА, принимающего дополнение языка L (L̅) состоит из двух шагов:

• Построение полного ДКА
• Построение из него искомого автомата

На самом деле, нет такого понятия, как полный ДКА. Под полным ДКА некоторые преподаватели понимают автомат, в таблице переходов которого нет пустых клеток. Однако в соответствии с определением ДКА - δ: Q × Σ → Q - пустых клеток быть не может в любом случае. Автомат "с пустыми клетками", впрочем, удовлетворяет определению НКА. В ходе решения нередко получается именно такой НКА, которому до ДКА не хватает лишь переходов.

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

Теперь для того, чтобы построить искомый автомат, требуется лишь поменять роли принимающих и непринимающих состояний. Иными словами, F" = Q \ F.

Построение LL(k) анализатора

Преобразование грамматики

Не всякая грамматика является LL(k)-анализируемой. Контекстно-свободная грамматика принадлежит классу LL(1), если в ней нет конфликтов типа FIRST-FIRST (левая рекурсия - частный случай такого конфликта) и FIRST-FOLLOW.

Иногда удаётся преобразовать не LL(1)-грамматики так, чтобы они стали LL(1). Некоторые (точнее, те, которые рассматривались в курсе) преобразования приведены ниже.

Удаление левой рекурсии

Пусть у нас имеется правило вида (здесь и далее в этом разделе, заглавные буквы - нетерминальные символы , строчные - цепочки любых символов ):

• A → Aa | Ab | … | Ak | m | n | … | z

Оно не поддается однозначному анализу, поэтому его следует преобразовать.

Легко показать, что это правило эквивалентно следующей паре правил:

• A → m B | n B | … | z B
• B → a B | b B | … | k B | ε

Левая факторизация

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

Пример

• A → a c | a df | a dg | b

Преобразуется в

• A → a B | b
• B → c | d f | d g

Что в свою очередь превратится в

• A → a B | b
• B → c | d С
• С → f | g

Пример преобразования грамматики

G = {{S, A, B}, {a, b, c}, P, S}

• S → SAbB | a
• A → ab | aa | ε
• B → c | ε

Удаление левой рекурсии для S :

• S → aS 1
• S 1 → AbBS 1 | ε

Левая факторизация для A :

• A → aA 1 | ε
• A 1 → b | a

Итоговая грамматика:

• S → aS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

Построение FIRST и FOLLOW

FIRST(α), где α ∈ (N ∪ T)* - множество терминалов, с которых может начинаться α. Если α ⇒ ε, то ε ∈ FIRST(α). Соответственно, значение функции FOLLOW(A ) для нетерминала A - множество терминалов, которые могут появиться непосредственно после A в какой-либо сентенциальной форме. Если A может являться самым правым символом в некоторой сентенциальной форме, то заключительный маркер $ также принадлежит FOLLOW(A )

Вычисление FIRST

Для терминалов

• Для любого терминала x , x ∈ T , FIRST(x ) = {x }

Для нетерминалов

• Если X - нетерминал, то положим FIRST(X ) = {∅}
• Если в грамматике есть правило X → ε, то добавим ε к FIRST(X )
• Для каждого нетерминала X и для каждого правила вывода X → Y 1 …Y k добавим в FIRST(X ) множества FIRST всех символов в правой части правила до первого, из которого не выводится ε, включая его

Для цепочек

• Для цепочки символов X 1 …X k FIRST есть объединение FIRST входящих в цепочку символов до первого, у которого ε ∉ FIRST, включая его.

Пример

• S → aS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

FIRST нетерминалов в порядке разрешения зависимостей:

• FIRST(S) = {a}
• FIRST(A) = {a, ε}
• FIRST(A 1) = {b, a}
• FIRST(B) = {c, ε}
• FIRST(S 1) = {a, b, ε}

FIRST для правил вывода:

• FIRST(aS 1) = {a}
• FIRST(AbBS 1) = {a, b}
• FIRST(ε) = {ε}
• FIRST(aA 1) = {a}
• FIRST(a) = {a}
• FIRST(b) = {b}
• FIRST(c) = {c}

Вычисление FOLLOW

Вычисление функции FOLLOW для символа X:

• Пусть FOLLOW(X) = {∅}
• Если X - аксиома грамматики, то добавить в FOLLOW маркер $
• Для всех правил вида A → αXβ добавить FIRST(β)\{ε} к FOLLOW(X) (за X могут следовать те символы, с которых начинается β)
• Для всех правил вида A → αX и A → αXβ, ε ∈ FIRST(β) добавить FOLLOW(A) к FOLLOW(X) (то есть, за X могут следовать все символы, которые могут следовать за A, в случае, если в правиле вывода символ X может оказаться крайним правым)
• Повторять предыдущие два пункта, пока возможно добавление символов в множество

Пример

• S → aS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

Результат:

• FOLLOW(S) = {$}
• FOLLOW(S 1) = {$} (S 1 - крайний правый символ в правиле S → aS 1)
• FOLLOW(A) = {b} (после A в правиле S 1 → AbBS 1 следует b)
• FOLLOW(A 1) = {b} (A 1 - крайний правый символ в правиле A → aA 1 , следовательно, добавляем FOLLOW(A) к FOLLOW(A 1))
• FOLLOW(B) = {a, b, $} (добавляем FIRST(S 1)\{ε} (следует из правила S 1 → AbBS 1), FOLLOW(S 1) (так как есть S 1 → ε))

Составление таблицы

В таблице M для пары нетерминал-терминал (в ячейке M [A , a ]) указывается правило, по которому необходимо выполнять свёртку входного слова. Заполняется таблица следующим образом: для каждого правила вывода заданной грамматики A → α (где под α понимается цепочка в правой части правила) выполняются следующие действия:

1. Для каждого терминала a ∈ FIRST(α) добавить правило A → α к M [A , a ]
2. Если ε ∈ FIRST(α), то для каждого b ∈ FOLLOW(A ) добавить A → α к M [A , b ]
3. ε ∈ FIRST(α) и $ ∈ FOLLOW(A ), добавить A → α к M [A , $]
4. Все пустые ячейки - ошибка во входном слове

Пример

Построить таблицу для грамматики

• S → aS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

Результат:

	a	b	c	$
S	S → aS 1 (Первое правило, вывод S → aS 1 , a ∈ FIRST(aS 1))	Error (Четвёртое правило)	Error (Четвёртое правило)	Error (Четвёртое правило)
S 1	S 1 → AbBS 1 (Первое правило, вывод S 1 → AbBS 1 , a ∈ FIRST(AbBS 1))	S 1 → AbBS 1 (Первое правило, вывод S 1 → AbBS 1 , b ∈ FIRST(AbBS 1))	Error (Четвёртое правило)	S 1 → ε (Третье правило, вывод S 1 → ε, ε ∈ FIRST(ε), $ ∈ FOLLOW(S 1))
A	A → aA 1 (Первое правило, вывод A → aA 1 , a ∈ FIRST(aA 1))	A → ε (Второе правило, вывод A 1 → ε, b ∈ FOLLOW(A 1))	Error (Четвёртое правило)	Error (Четвёртое правило)
A 1	A 1 → a (Первое правило, вывод A 1 → a, a ∈ FIRST(a))	A 1 → b (Первое правило, вывод A 1 → b, b ∈ FIRST(b))	Error (Четвёртое правило)	Error (Четвёртое правило)
B	B → ε	B → ε (Второе правило, вывод B → ε, a ∈ FOLLOW(B))	B → c (Первое правило, вывод B → c, c ∈ FIRST(c))	B → ε (Третье правило, вывод B → ε, $ ∈ FOLLOW(B))

Разбор строки

Процесс разбора строки довольно прост. Его суть в следующем: на каждом шаге считывается верхний символ v c входной цепочки.

• Если v - терминальный символ
  • Если v совпадает с с , то они оба уничтожаются, происходит сдвиг
  • Если v не совпадает с с , то сигнализируется ошибка разбора
• Если v - нетерминальный символ, c возвращается в начало строки, вместо v в стек возвращается правая часть правила, которое берется из ячейки таблицы M [v , c ]

Процесс заканчивается, когда и строка и стек дошли до концевого маркера (#).

Пример

разберем строку «aabbaabcb»:

стек	строка	действие
S #	a abbaabcb$	S → aS 1
a S 1 #	a abbaabcb$	сдвиг
S 1 #	a bbaabcb$	S 1 → AbBS 1
A bBS 1 #	a bbaabcb$	A → aA 1
a A 1 bBS 1 #	a bbaabcb$	сдвиг
A 1 bBS 1 #	b baabcb$	A 1 → b
b bBS 1 #	b baabcb$	сдвиг
b BS 1 #	b aabcb$	сдвиг
B S 1 #	a abcb$	B → ε
S 1 #	a abcb$	S 1 → AbBS 1
A bBS 1 #	a abcb$	A → aA 1
A bBS 1 #	a abcb$	A → aA 1
a A 1 bBS 1 #	a abcb$	сдвиг
A 1 bBS 1 #	a bcb$	A 1 → a
a bBS 1 #	a bcb$	сдвиг
b BS 1 #	b cb$	сдвиг
B S 1 #	c b$	B → c
c S 1 #	c b$	сдвиг
S 1 #	b $	S 1 → AbBS 1
A bBS 1 #	b $	A → ε
b BS 1 #	b $	сдвиг
B S 1 #	$	B → ε
S 1 #	$	S 1 → ε
#	$	готово

Построение LR(k) анализатора

Вычисление k в LR(k)

Не существует алгоритма, который позволял бы в общем случае для произвольной грамматики вычислить k. Обычно, стоит попробовать построить LR(1)-анализатор. Если у него на каждое множество приходится не более одной операции (Shift, Reduce или Accept), то грамматика LR(0). Если же при построении LR(1)-анализатора возникает конфликт и коллизия, то данная грамматика не является LR(1) и стоит попробовать построить LR(2). Если не удаётся построить и её, то LR(3) и так далее.

Пополнение грамматики

Добавим новое правило S" → S, и сделаем S" аксиомой грамматики. Это дополнительное правило требуется для определения момента завершения работы анализатора и допуска входной цепочки. Допуск имеет место тогда и только тогда, когда возможно осуществить свёртку по правилу S → S".

Построение канонической системы множеств допустимых LR(1)-ситуаций

В начале имеется множество I 0 с конфигурацией анализатора S" → .S, $. Далее к этой конфигурации применяется операция закрытия до тех пор, пока в результате её применения не перестанут добавляться новые конфигурации. Далее, строятся переходы в новые множества путём сдвига точки на один символ вправо (переходы делаются по тому символу, который стоял после точки до перехода и перед ней после перехода), и в эти множества добавляются те конфигурации, которые были получены из имеющихся данным образом. Для них также применяется операция закрытия, и весь процесс повторяется, пока не перестанут появляться новые множества.

Пример

Построить каноническую систему множеств допустимых LR(1)-ситуаций для указанной грамматики:

• S" → S
• S → ABA
• A → Aa | ε
• B → cBc | d

Решение:

• Строим замыкание для конфигурации S" → .S, $:
  • S → .ABA, $
• Для полученных конфигураций (S → .ABA, $) также строим замыкание:
  • A → .Aa, c
  • A → .Aa, d
  • A → ., c
  • A → ., d
• Для полученных конфигураций (A → .Aa, c; A → .Aa, d) также строим замыкание:
  • A → .Aa, a
  • A → ., a
• Больше конфигураций в состоянии I 0 построить нельзя - замыкание построено

• Из I 0 можно сделать переходы по S и A и получить множество конфигураций I 1 и I 2 , состоящее из следующих элементов:
  • I 1 = {S" → S., $}
  • I 2 = {S → A.BA, $; A → A.a, c; A → A.a, d; A → A.a, a}
• I 1 не требует замыкания
• Построим замыкание I 2:
  • B → .cBc, a
  • B → .cBc, $
  • B → .d, a
  • B → .d, $
• Аналогично строятся все остальные множества.

Построение таблицы анализатора

Заключительным этапом построения LR(1)-анализатора является построение таблиц Action и Goto . Таблица Action строится для символов входной строки, то есть для терминалов и маркера конца строки $, таблица Goto строится для символов грамматики, то есть для терминалов и нетерминалов.

Построение таблицы Goto

Таблица Goto показывает, в какое состояние надо перейти при встрече очередного символа грамматики. Поэтому, если в канонической системе множеств есть переход из I i в I j по символу A, то в Goto(I i , A) мы ставим состояние I j . После заполнения таблицы полагаем, что во всех пустых ячейках Goto(I i , A) = Error

Построение таблицы Actions

• Если есть переход по терминалу a из состояния I i в состояние I j , то Action(I i , a) = Shift(I j)
• Если A ≠ S" и есть конфигруация A → α., a, то Action(I i , a) = Reduce(A → α)
• Для состояния I i , в котором есть конфигурация S" → S., $, Action(I i , $) = Accept
• Для всех пустых ячеек Action(I i , a) = Error

Пример

Построить таблицы Action и Goto для грамматики

• S" → S
• S → ABA
• A → Aa | ε
• B → cBc | d

Решение:

	Action				Goto
	a	c	d	$	S	S"	A	B	a	c	d
I 0	Reduce(A → ε)	Reduce(A → ε)	Reduce(A → ε)		I 1		I 2
I 1				Accept
I 2	Shift(I 6)	Shift(I 4)	Shift(I 5)					I 3	I 6	I 4	I 5
I 3	Reduce(A → ε)			Reduce(A → ε)			I 13
I 4		Shift(I 8)	Shift(I 9)					I 7		I 8	I 9
I 5	Reduce(B → d)			Reduce(B → d)
I 6	Reduce(A → Aa)	Reduce(A → Aa)	Reduce(A → Aa)
I 7		Shift(I 10)								I 10
I 8		Shift(I 8)	Shift(I 9)					I 11		I 8	I 9
I 9		Reduce(B → d)
I 10	Reduce(B → cBc)			Reduce(B → cBc)
I 11		Shift(I 12)								I 12
I 12		Reduce(B → cBc)
I 13	Shift(I 14)			Reduce(S → ABA)					I 14
I 14	Reduce(A → Aa)			Reduce(A → Aa)

Разбор цепочки

На каждом шаге считывается верхний символ v из стека анализатора и берется крайний символ c входной цепочки.

Если в таблице дейстивий на пересечении v и c находится:

• Shift(I k ), то в стек кладется с и затем I k . При этом c удаляется из строки.
• Reduce(A → u ), то из верхушки стека вычищаются все терминальные и нетерминальные символы, составляющие цепочку u , после чего смотрится состояние I m , оставшееся на верхушке. По таблице переходов на пересечении I m и A находится следующее состояние I s . После чего в стек кладется A, а затем I s . Строка остается без измененеий.
• Accept, то разбор закончен
• пустота - ошибка

Пример

Построим разбор строки aaaccdcc:

Стек	Строка	Действие
I 0	a aaccdcc$	Reduce(A → ε), goto I 2
I 0 A I 2	a aaccdcc$	Shift(I 6)
I 0 A I 2 a I 6	a accdcc$	Reduce(A → Aa), goto I 2
I 0 A I 2	a accdcc$	Shift(I 6)
I 0 A I 2 a I 6	a ccdcc$	Reduce(A → Aa), goto I 2
I 0 A I 2	a ccdcc$	Shift(I 6)
I 0 A I 2 a I 6	c cdcc$	Reduce(A → Aa), goto I 2
I 0 A I 2	c cdcc$	Shift(I 4)
I 0 A I 2 c I 4	c dcc$	Shift(I 8)
I 0 A I 2 c I 4 c I 8	d cc$	Shift(I 9)
I 0 A I 2 c I 4 c I 8 d I 9	c c$	Reduce(B → d), goto I 11
I 0 A I 2 c I 4 c I 8 B I 11	c c$	Shift(I 12)
I 0 A I 2 c I 4 c I 8 B I 11 c I 12	c $	Reduce(B → cBc), goto I 7
I 0 A I 2 c I 4 B I 7	c $	Shift(I 10)
I 0 A I 2 c I 4 B I 7 c I 10	$	Reduce(B → cBc), goto I 3
I 0 A I 2 B I 3	$	Reduce(A → ε), goto I 13
I 0 A I 2 B I 3 A I 13	$	Reduce(S → ABA), goto I 1
I 0 S I 1	$	Accept

Трансляция арифметических выражений (алгоритм Сети-Ульмана)

Примечание. Код генерируется doggy style Motorola-like, то есть

Op Arg1, Arg2

обозначает

Arg2 = Arg1 Op Arg2

Построение дерева

Дерево строится как обычно для арифметического выражения: В корне операция с наименьшим приоритетом, далее следуют операции с приоритетом чуть выше и так далее. Скобки имеют наивысший приоритет. Если имеется несколько операций с одинаковым приоритетом - a op b op c, то дерево строится как для выражения (a op b) op с.

Пример

Построить дерево для выражения a + b / (d + a − b × c / d − e) + c × d

Решение: Запишем выражение в виде

((a) + ((b) / ((((d) + (a)) − ((b) × (c)) / (d)) − (e)))) + ((c) × (d))

Тогда в корне каждого поддерева будет операция, а выражения в скобках слева и справа от неё - её поддеревьями. Например, для подвыражения ((b) × (c)) / (d) в корне соответствующего поддерева будет операция «/», а её поддеревьями будут являться подвыражения ((b) × (c)) и (d).

Разметка дерева (вычисление количества регистров)

• Если вершина - левый лист (то есть, переменная), то помечаем её нулём.
• Если вершина - правый лист, то помечаем её единицей
• Если мы разметили для некоторой вершины оба её поддерева, то её размечаем следующим образом:
  • Если левое и правое поддеревья помечены разными числами, то выбираем наибольшее из них
  • Если левое и правое поддеревья помечены одинаковыми числами, то данному поддереву сопоставляем число, на единицу большее того, которым помечены поддеревья

Разметка листьев	Разметка дерева с одинаковыми поддеревьями	Левое поддерево помечено большим числом	Правое поддерево помечено большим числом

правому - такой же , как и предку.

Если метка левого потомка больше метки правого , то правому потомку назначается регистр на единицу больший , чем предку, а левому - такой же , как и предку.

Формируется код путём обхода дерева снизу вверх следующим образом:

1. Для вершины с меткой 0 код не генерируется

2. Если вершина - лист X с меткой 1 и регистром Ri , то ему сопоставляется код

MOVE X, Ri

3. Если вершина внутренняя c регистром Ri и её левый потомок - лист X с меткой 0, то ей соответствует код

<Код правого поддерева> Op X, Ri

4. Если поддеревья вершины с регистром Ri - не листья и метка правой вершины больше или равна метке левой (у которой регистр Rj, j = i + 1), то вершине соответствует код

<Код правого поддерева> <Код левого поддерева> Op Rj, Ri

5. Если поддеревья вершины с регистром Ri - не листья и метка правой вершины (у которой регистр Rj, j = i + 1) меньше метки левой, то вершине соответствует код

Распределение регистров показано на графике справа. Сгенерированный код:

MOVE d, R0 ;R0 = d MOVE c, R1 ;R1 = c MUL b, R1 ;R1 = (b × c) DIV R1, R0 ;R0 = (b × c) / d MOVE a, R1 ;R1 = a ADD d, R1 ;R1 = a + d SUB R1, R0 ;R0 = (a + d) − ((b × c) / d) MOVE e, R1 ;R1 = e SUB R0, R1 ;R1 = ((a + d) − ((b × c) / d)) − e MOVE R1, R0;R0 = ((a + d) − ((b × c) / d)) − e DIV b, R0 ;R0 = b / (((a + d) − ((b × c) / d)) − e) ADD a, R0 ;R0 = a + (b / (((a + d) − ((b × c) / d)) − e)) MOVE d, R1 ;R1 = d MUL c, R1 ;R1 = c × d ADD R0, R1 ;R1 = (a + (b / (((a + d) − ((b × c) / d)) − e))) + (c × d) MOVE R1, R0;R0 = (a + (b / (((a + d) − ((b × c) / d)) − e))) + (c × d)

Трансляция логических выражений

В данном разделе показан способ генерации кода для ленивого вычисления логических выражений. В результате работы алгоритма получается кусок кода, который с помощью операций TST, BNE, BEQ вычисляет логическое выражение путём перехода на одну из меток: TRUELAB или FALSELAB.

Построение дерева

Дерево логического выражения отражает порядок его вычисления в соответствии с приоритетом операций, то есть, для вычисления значения некоего узла дерева (который есть операция от двух операндов, являющимися поддеревьями узла) мы должны сначала вычислить значения его поддеревьев.

Приоритет операций: наивысший приоритет у операции NOT, далее идёт AND, а затем OR. Если в выражении используются другие логические операции то они должны быть выражены через эти три определённым образом (обычно, других операций нет и преобразования выражения не требуется). Ассоциативность у операций одного приоритета - слева направо, то есть A and B and C рассматривается как (A and B) and C

Пример

Построить дерево для логического выражения not A or B and C and (B or not C).

Решение: см. схему справа.

Для каждой вершины дерева вычисляются 4 атрибута:

• Номер узла
• Метка, куда необходимо перейти, если выражение в узле - ложь (false label, fl)
• Метка, куда необходимо перейти, если выражение в узле - истина (true label, tl)
• Метка-знак (sign) (подробнее см. далее)

Нумерация вершин выполняется в произвольном порядке, единственным условием является уникальность номеров узлов.

Разметка дерева производится следующим образом:

• В fl указывается номер вершины, в который делается переход или falselab, если данная вершина false
• В tl указывается номер вершины, в который делается переход или truelab, если данная вершина true

Sign указывает то, в каком случае можно прекратить вычисления текущего поддерева.

Для корня дерева fl=falselab, tl=truelab, sign=false.

Таким образом:

Пример

Разметить дерево, построенное для логического выражения not A or B and C and (B or not C).

Генерация кода

Машинные команды, используемы в сгенерированном коде:

• TST - проверка аргумента на истинность и установка флага, если аргумент ложен
• BNE - переход по метке в случае, если флаг не установлен, то есть проверяенное при помощи TST условие истинно
• BEQ - переход по метке в случае, если флаг установлен, то есть проверяенное при помощи TST условие ложно

Построение кода производится следующим образом:

• дерево обходится от корня, для AND и OR сначала обходится левое поддерево затем правое
• для каждой пройденной вершины печатается ее номер (метка)
• для листа A(номер, tl, fl, sign) печатается TST A
  • если sign == true, печатается BNE tl
  • если sign == false, печатается BEQ fl

Пример

Для рассмотренного выше выражения сгенерируется следующий код:

1:2:4: TST A BEQ TRUELAB 3:5:7: TST B BEQ FALSELAB 8: TST C BEQ FALSELAB 6:9: TST B BNE TRUELAB 10:11: TST C BNE FALSELAB TRUELAB: FALSELAB:

Метод сопоставления образцов

Идея метода заключается в том, что для одного и того же участка программы может быть код сгенерирован различными способами, и, как следствие, можно добиться оптимизации по тому или иному параметру.

Постановка задачи

Имеется множество образцов, для каждого из которых определён кусок промежуточного представления, для которого он применим, вес и генерируемый код. Есть дерево промежуточного представления, представляющее собой фрагмент программы, для которой необходимо код сгенерировать. Целью является построение такого покрытия дерева промежуточного представления образцами, чтобы суммарный вес образцов был минимален.

Образцы - это ассемблерные команды и деревья разбора, которые им соответствуют. Про каждый образец известно время его выполнения (в тактах). С их помощью и будем генерировать оптимальный (по времени выполнения) код.

Примеры образцов

Построение промежуточного представления

Сначала строим дерево разбора для всего выражения.

Построение покрытия

Теперь для каждой вершины (перебираем их в порядке от листьев к корню) будем генерировать оптимальный код для ее поддерева. Для этого просто переберем все образцы, применимые в данной вершине. Время выполнения при использовании конкретного образца будет складываться из времени вычисления его аргументов (а оптимальный код для их вычисления мы уже знаем благодаря порядку обхода дерева) и времени выполнения самого образца. Из всех полученных вариантов выбираем лучший - он и будет оптимальным кодом для поддерева данной вершины. В корне дерева получим оптимальный код для всего выражения.

Генерация кода

Код для всех вершин выписывать не обязательно - достаточно записать минимальное необходимое время и образец, которым нужно воспользоваться. Все остальное из этого легко восстанавливается.

Регистров у нас в этих задачах бесконечное количестов, так что каждый раз можно использовать новый.

Построение РВ по ДКА

Построение НКА по праволинейной грамматике

Приведение грамматики

Для того чтобы преобразовать произвольную КС-грамматику к приведенному виду, необходимо выполнить следующие действия:

• удалить все бесплодные символы;
• удалить все недостижимые символы;

Удаление бесполезных символов

Вход: КС-грамматика G = (T, N, P, S).

Выход: КС-грамматика G’ = (T, N’, P’, S), не содержащая бесплодных символов, для которой L(G) = L(G’).

Метод:

Рекурсивно строим множества N 0 , N 1 , ...

1. N 0 = ∅, i = 1.
2. N i = {A | (A → α) ∈ P и α ∈ (N i - 1 ∪ T)*} ∪ N i-1 .
3. Если N i ≠ N i - 1 , то i = i + 1 и переходим к шагу 2, иначе N’ = N i ; P’ состоит из правил множества P, содержащих только символы из N’ ∪ T; G’ = (T, N’, P’, S).

Определение: символ x ∈ (T ∪ N) называется недостижимым в грамматике G = (T, N, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики.

Пример

Удалить бесполезные символы у грамматики G({A, B, C, D, E, F, S}, {a, b, c, d, e, f, g}, P, S)

• S → AcDe | CaDbCe | SaCa | aCb | dFg
• A → SeAd | cSA
• B → CaBd | aDBc | BSCf | bfg
• C → Ebd | Seb | aAc | cfF
• D → fCE | ac | dEdAS | ε
• E → ESacD | aec | eFf

Решение

• N 0 = ∅
• N 1 = {B (B → bfg) , D (D → ac) , E (E → aec) }
• N 2 = {B, D, E, C (C → Ebd) }
• N 3 = {B, D, E, C, S (S → aCb) }
• N 4 = {B, D, E, C, S} = N 3

G"({B, C, D, E, S}, {a, b, c, d, e, f, g}, P", S)

• S → CaDbCe | SaCa | aCb
• B → CaBd | aDBc | BSCf | bfg
• C → Ebd | Seb
• D → fCE | ac | ε
• E → ESacD | aec

Удаление недостижимых символов

Вход: КС-грамматика G = (T, N, P, S)

Выход: КС-грамматика G’ = (T’, N’, P’, S), не содержащая недостижимых символов, для которой L(G) = L(G’).

Метод:

1. V 0 = {S}; i = 1.
2. V i = {x | x ∈ (T ∪ N), (A → αxβ) ∈ P и A ∈ V i - 1 } ∪ V i-1 .
3. Если V i ≠ V i - 1 , то i = i + 1 и переходим к шагу 2, иначе N’ = V i ∩ N; T’ = V i ∩ T; P’ состоит из правил множества P, содержащих только символы из V i ; G’ = (T’, N’, P’, S).

Определение: КС-грамматика G называется приведенной, если в ней нет недостижимых и бесплодных символов.

Пример

Удалить недостижимые символы у грамматики G"({B, C, D, E, S}, {a, b, c, d, e, f, g}, P", S)

• S → CaDbCe | SaCa | aCb
• B → CaBd | aDBc | BSCf | bfg
• C → Ebd | Seb
• D → fCE | ac | ε
• E → ESacD | aec

Решение

• V 0 = {S}
• V 1 = {S, C (S → CaDbCe) , D (S → CaDbCe) , a (S → CaDbCe) , b (S → CaDbCe) , e (S → CaDbCe) }
• V 2 = {S, C, D, a, b, e, E (C → Ebd) , d (C → Ebd) , f (D → fCE) }
• V 3 = {S, C, D, E, a, b, d, e, f, c (E → ESacD) }
• V 4 = {S, C, D, E, a, b, d, e, f, c} = V 3

G""({C, D, E, S}, {a, b, c, d, e, f}, P"", S)

• S → CaDbCe | SaCa | aCb
• C → Ebd | Seb
• D → fCE | ac | ε
• E → ESacD | aec

Похожие статьи