Конечные автоматы
Введение
Конечные автоматы являются мощным инструментом для работы. Компиляторы работает на основе конечных автоматов. Любой алгоритм которые вы пишете может быть представлен в виде конечного автомата.
В конечном автомате количесто состояний конечно, а результат его работа определяется по его конченому состоянию (Wikipedia).
Существует несколько видов конечных автоматов:
Детерминированный кончечный автомат (ДКА)
Из любого состояние должен быть только один преход по символову, иначе этот автомат недерминирован.
ДКА является самым удобным из всех конченых автоматов. Его удобнее всего обработаывать, всегда стараются свести задачу к построению ДКА. Но разобрать НКА и ε-НКА также необходимо.
Недетерминированный конечный автомат(НКА)
Предположим нам надо построить автомат, который принимает все строки, состоящие из символов [0, 1], где второй символ будет 0.
ε-Недетерминированный конечный автомат (ε-НКА)
ε-НКА очень похож на НКА, только теперь мы можем преходить по ε. Теперь ничего не считав, мы сможем перейти из одной вершины в другую. 
Принмает теже слова, что и предыдущий
Эквиалетность
Есть свойство у конченых автоматов — это их эквиалетность. ДКА НКА ε-НКА. Благодаря этому мы можем спокойно из ε-НКА сделать ДКА, это нам сильно пригодится.
Вкратце, разобрав какие бывают автоматы, мы можем перейти к более подробному изучению их реализации
Реализация
Обработка автомата
Как же можно проверить принимает ли данный кончечный автомат строку.
Для ДКА все очевидно. Мы храним матрицу преходов, текущее состояние (когда мы ничего не считали, тек. сотояние = начальное состояние) и терминальные вершины. Считываем по одному символу, и переходим в состояние по матрице перехода.
Для НКА вместо текущего состояния мы храним множество текущих состояний. Разберем НКА данный выше.
Пусть мы хотим перейти по символу 0. Текущее множество состояний — множество, состоящее из одной вершины — начальной. У нас есть два прехода по символу 0 => множество состояний у нас будет
Обработка ε-НКА похожа на обработку НКА. Предположим наше текущее множество S. Перед считываением следущего символа: для всех q ∈ S добавить в множество S вершину достигаемую из q по символу ε.
Детерминация автомата
Перевести автомат из ДКА в НКА легко. Нам просто ничего не нужно делать, т.к. ДКА это обобщенный случай НКА.
Но что делать если мы хотим превести из ε-НКА в ДКА (НКА является обобшенным случаем ε-НКА). Этот процесс называется детерминацией автомата.
Начнем обоходить наш ε-НКА, например, DFS-ом. Вершиной графа является множество текущих состояний. Состояниями нового ДКА будут все вершины графа. При переходе к новой веришне мы выбираем символ по которому хотим перейти, и добавляем этот переход. Приведу псевдокод DFS-a для большой ясности:
Если в множестве есть терминальное состояние, то состояние нового ДКА будет тоже терминальным.
К сожалению число состояние нового ДКА будет расти экспоненциально, что не очень хорошо, т.к. это будет потреблять много памяти.
Алгоритм минимизации ДКА
Любой ДКА имеет эквиалетный ему ДКА с минимальным числом состояний. Как его «сжать»? Заметим, что неразличимые вершины мы можем соединить в одну.
Что такое различимое состояние?
Состояние p и q являются различимыми, если есть такое слово s, что преходя из вершины p по слову s мы попадаем в терминальное состояние, а из вершины q в не-терминальное, или наоборот.
1) Терминальное и не-терминальное состояние являются различимыми. Перейдем по пустому слову и окажемся в двух различимых состояниях.
2) Состояния a и b различимы. Если существуют состояния c и d, и из c есть переход по символу x в состояние a, а из веришны d есть переход по символу x в состояние b, то состояние a и b различимы.
Мы нашли все различимые состояния. Теперь нам надо «схлопнуть» все неразличимые.
Регулярные выражения
Регулярные варжения напрямую связаны с конечными автоматами. Введем некоторые обозначения:
∅ — пустое множество.
ε — строка, которая не сожержит символов.
Пусть A и B регулярные выражения. L(A) и L(B) — кончечные языки, которые данные регулярные варжения задают.
Это основные операции прменимые к регулярным варжением. Можно всетрить и другие, но все они могут быть представлены операциями данными выше.
Вот представление основных операций регулярных выражений в виде ε-НКА.
Дале разбираем это выражение рекурсивным спуском и строим ε-НКА.
Чтобы обработать Регулярное выражение построим для ε-НКА, а потом получим из ε-НКА ДКА, который очень легко обрабатывать.
Данная статья не подлежит комментированию, поскольку её автор ещё не является полноправным участником сообщества. Вы сможете связаться с автором только после того, как он получит приглашение от кого-либо из участников сообщества. До этого момента его username будет скрыт псевдонимом.
Регулярные выражения изнутри
Регулярные выражения (РВ) — это очень удобная форма записи так называемых регулярных или автоматных языков. Поэтому РВ используются в качестве входного языка во многих системах, обрабатывающих цепочки. Рассмотрим примеры таких систем:
В данной статье мы сначала ознакомимся с конечными автоматами и их видами (ДКА и НКА), и далее рассмотрим пример построения минимального ДКА по регулярному выражению.
Конечные автоматы
Конечный автомат (КА) — это преобразователь, который позволяет сопоставить входу соответствующий выход, причем выход этот может зависеть не только от текущего входа, но и от того, что происходило раньше, от предыстории работы конечного автомата. Даже поведение человека, а не только искусственных систем можно описать с помощью КА. Например, ваша реакция на то что ваш сосед слушает громко музыку по ночам, будет одной после первого такого случая и совершенно другой после нескольких таких случаев. Таких предысторий может быть бесконечное число, возникает вопрос: какой памятью должен обладать КА, чтобы вести себя по разному для каждой предыстроии? Понятно, что хранить бесконечное число предысторий невозможно. Поэтому автомат как бы разбивает все возможные предыстории на классы эквивалентности. Две истории являются эквивалентными, если они одинаково влияют на поведение автомата в дальнейшем. Класс эквивалентности к которому автомат отнес свою текущую предысторию, называют еще внутренним состоянием автомата.
Рассмотрим пример работы примитивного КА:
Данный КА состоит из:
Считывающее устройство может двигаться в одном направлении, как правило слева на право, тем самым считывая символы входной цепочки. За каждое такое движение оно может считать один символ. Далее, считанный символ передается блоку управлений. Блок управления изменяет состояние автомата на основе правил переходов. Если список правил переходов не содержит правила для считанного символа, то автомат «умирает».
Теперь рассмотрим, какими способами можно задать КА. Они могут задаваться в виде графов или в виде управляющих таблиц. В виде графа КА задается следующим способом:
В виде управляющей таблицы, так:
Пример КА в виде графа и в виде управляющей таблицы будет представлен ниже.
ДКА и НКА
Основное отличие ДКА и НКА состоит в том, что ДКА в процессе работы может находится только в одном состоянии, а НКА в нескольких состояниях одновременно. В качестве примера работы НКА можно привести идею американского физика Хью Эверетта от том, что любое событие разбивает мир на несколько миров, в каждом из которых это событие закончилось по-своему. Например, в одном мире Гитлер выиграл Вторую мировую войну, в другом – Ньютон вместо физики занялся бизнесом и открытие законов классической механики пришлось отложить лет на 50. Чтобы сделать какие-то выводы из работы автомата, следует изучить все «миры». После того как вся входная цепочка будет считана, мы полагаем, что НКА допускает данную цепочку, если он завершил работу в допускающем состоянии хотя бы в одном из множества «миров». Соответственно, автомат отвергает цепочку, если он завершил работу в недопускающем состоянии в каждом «мире». ДКА же принимает цепочку, это очевидно, если после считывания всей входной цепочки он оказывается в допускающем состоянии.
В большинстве случаев построить НКА гораздо проще чем ДКА. Но, не смотря на это использовать НКА для моделирования — не самая хорошая идея. К счастью, для каждого НКА можно построить ДКА, допускающий тот же входной язык. В данной статье мы не будем приводить алгоритм построения ДКА по НКА, а рассмотрим данный алгоритм на основе наглядного примера ниже.
Построение минимального ДКА по регулярному выражению
Для начала приведем список операций РВ используемый в данной статье, в порядке их приоритетности:
Рассмотрим пример, дано регулярное выражение:
xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)
Нужно построить минимальный ДКА по регулярному выражению и продемонстрировать распознавание корректной и некорректной цепочки.
Для начала упростим данное РВ, используя правосторонний дистрибутивный закон конкатенации относительно объединения получаем следующее РВ:
Теперь строим автомат по данному РВ:
По правилу преобразования конкатенации (не будем приводить правила преобразования РВ в КА, так как они довольно очевидные), получаем следующий автомат:
По правилу преобразования объединения:
По правилу преобразования конкатенации:
И в конце применяем правило преобразования замыкания и получаем εНКА. Здесь нужно оговорится, что εНКА — это НКА, который содержит ε-переходы. В свою очередь ε-переход — это переход, при котором автомат не учитывает входную цепочку или другими словами переход по пустому символу.
Избавляемся от ε-переходов («звездочкой» обозначены конечные состояния):
Данный автомат является минимальным ДКА.
Пускай δ — функция переходов, то расширенную функцию переходов, построенную по δ, обозначим δ’, и ω — входная цепочка.
Допустим на вход подается цепочка ω = aaax, мы ожидаем, что автомат окажется в одном из допускающих состояний.
δ’(p0, ε) = p0
δ’(p0, a) = δ(δ’(p0, ε), a) = δ(p0, a) = p3
δ’(p0, aa) = δ(δ’(p0, a), a) = δ(p3, a) = p5
δ’(p0, aaa) = δ(δ’(p0, aa), a) = δ(p5, a) = p5
δ’(p0, aaax) = δ(δ’(p0, aaa), x) = δ(p5, x) = p4
p4 — допустимое конечное состояние, таким образом цепочка aaax является корректной для данного автомата.
Теперь допустим, что ω = xyyb:
δ’(p0, ε) = p0
δ’(p0, x) = δ(δ’(p0, ε), x) = δ(p0, x) = p1
δ’(p0, xy) = δ(δ’(p0, x), y) = δ(p1, y) = p1
δ’(p0, xyy) = δ(δ’(p0, xy), y) = δ(p1, y) = p1
δ’(p0, xyyb) = δ(δ’(p0, xyy), b) = δ(p1, b) = ∅
Здесь мы видим, что если подать на вход автомату символ b, когда он находится в состоянии p1, то данный автомат умрет, следовательно цепочка xyyb — некорректна.
P. S. В данной статье был рассмотрен алгоритм построение ДКА по РВ, но существуют более удобные алгоритмы, в частности для программирования, но это уже тема для другой статьи…
Конструирование Компиляторов, Алгоритмы решения задач
Материал из eSyr’s wiki.
Содержание
Построение НКА по РВ
Автомат для выражения строится композицией автоматов, соответствующих подвыражениям. На каждом этапе ∃! заключительное состояние, и нет переходов из заключительного состояния и в начальное. Для построения НКА используются следующие преобразования (M(s) и M(t) ниже обозначают соответственно автоматы, соответствующие регулярным выражениям s и t; i и f — некоторые номера состояний НКА):
| подвыражение РВ | автомат |
|---|---|
| ε |  |
| a, a ∈ T |  |
| s|t |  |
| st |  |
| s* |  |
Пример
Обычно конечный автомат строится из регулярного выражения, начиная с внутренних символов. То есть, сначала строятся переходы по b и c, потом образуется конструкция b|c, добавляется a, строится автомат для итерации (a(b|c))* и в конце добавляется c.
Построение ДКА по НКА
Необходимо по недетерминированному конечному автомату M = (Q, T, D, q0, F) построить детерминированный конечный автомат M = (Q’, T, D’, q’0, F’). Начальным состоянием для строящегося автомата является ε-замыкание начального состояния автомата исходного. ε-замыкание — множество состояний, которые достижимы из данного путём переходов по ε. Далее, пока есть состояния, для которых не построены переходы (переходы делаются по символам, переходы по которым есть в исходном автомате), для каждого символа вычисляется ε-замыкание множества состояний, которые достижимы из рассматриваемого состояния путём перехода по рассматриваемому символу. Если состояние, которое соответствует найденному множеству, уже есть, то добавляется переход туда. Если нет, то добавляется новое полученное состояние.
Пример
Помечаются состояния, соответствующие ε-замыканию начального. Эти состояния будут соответствовать состоянию A будущего ДКА.
| Состояние ДКА | Множество состояний НКА | Символы, по которым осуществляется переход | ||
|---|---|---|---|---|
| a | b | c | ||
| A | — | — | — | |
Из ε-замыкания есть переходы в состояния НКА 3 и 10 (по a и c, соответственно). Для состояния 3 ε-замыканием является множество состояний <3, 4, 6>, для состояния 10 — <10>. Обозначим соответствующие данным множествам новые состояния ДКА как B и C.
| Состояние ДКА | Множество состояний НКА | Символы, по которым осуществляется переход | ||
|---|---|---|---|---|
| a | b | c | ||
| A | B | — | C | |
| B | — | — | — | |
| C | — | — | — | |
Из множества состояний НКА <3, 4, 6>, соответствующего состоянию ДКА B есть два перехода — в состояние 5 (по b) и 7 (по c). Их ε-замыкания пересекаются, но сами множества различны, поэтому им ставятся в соответствие два новых состояния ДКА — D и E. Из состояний НКА, соответствующих состоянию ДКА C, никаких переходов нет.
| Состояние ДКА | Множество состояний НКА | Символы, по которым осуществляется переход | ||
|---|---|---|---|---|
| a | b | c | ||
| A | B | — | C | |
| B | — | D | E | |
| C | — | — | — | |
| D | — | — | — | |
| E | — | — | — | |
Из множеств состояний НКА, соответствующих состояниям ДКА D и E переходы делаются в множества состояний, соответствующие уже имеющимся состояниям (из множества <2, 5, 8, 9>, соответствующего состоянию D, по a переход в состояние 3, принадлежащее множеству <3, 4, 6>, соответствующему состоянию ДКА B, по c — переход в состояние 10, соответствующее состоянию C; аналогично для множества, соответствующего состоянию ДКА E). Процесс построения таблицы состояний и переходов ДКА завершён.
| Состояние ДКА | Множество состояний НКА | Символы, по которым осуществляется переход | ||
|---|---|---|---|---|
| a | b | c | ||
| A | B | — | C | |
| B | — | D | E | |
| C | — | — | — | |
| D | B | — | C | |
| E | B | — | C | |
Построение праволинейной грамматики по конечному автомату
Каждому состоянию ставим в соответствие нетерминал. Если есть переход из состояния X в состояние Y по а, добавляем правило X → aY. Для конечных состояний добавляем правила X → ε. Для ε-переходов — X → Y.
Пример 1 (детерминированный конечный автомат)
Пример 2 (недетерминированный конечный автомат)
Построение ДКА по РВ
Пусть есть регулярное выражение 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:
Построение followpos
Пример
Вычислить значение функции followpos для регулярного выражения (a(b|c))*c.
| Позиция | Значение followpos |
|---|---|
| 1: ( a (b|c))*c | |
| 2: (a( b |c))*c | |
| 3: (a(b| c ))*c | |
| 4: (a(b|c))* c |
Построение ДКА
ДКА представляет собой множество состояний и множество переходов между ними. Состояние ДКА представляет собой множество позиций. Построение ДКА заключается в постепенном добавлении к нему необходимых состояний и построении переходов для них. Изначально имеется одно состояние, firstpos(root) (root — корень дерева), у которого не построены переходы. Переход осуществляется по символам из регулярного выражения. Каждому символу соответствует множество позиций <pi>. Объединение всех followpos(x) есть состояние в которое необходимо перейти, где x — позиция, присутствующая как среди позиций состояния и так и среди позиций символа из РВ, по которому осуществляется переход. Если такого состояния нет, то его необходимо добавить. Процесс нужно повторять, пока не будут построены все переходы для всех состояний. Конечными объявляются все состояния, содержащие позицию добавленного в конец РВ символа #.
Пример
Построить ДКА по регулярному выражению (a(b|c))*c.
| Состояние ДКА | Символ | ||
|---|---|---|---|
| a | b | c | |
| A | B | — | C |
| B | — | A | A |
| C | — | — | — |
Построение ДКА с минимальным количеством состояний
ДКА с минимальным числом состояний строится для всюду определённого ДКА, т.е. такого, что 
. Для любого ДКА существует эквивалентный ему всюду определённый ДКА.
Построение всюду определённого ДКА
Введём новое состояние 
и определим новое множество состояний 
.
Определим новую функцию перехода так:
Построение разбиения (формально)
Построим начальное разбиение П множества состояний на две группы: заключительные состояния F и остальные S\F, т. е. П = <F, Q\F>.
Применить к каждой группе G ∈ П следующую процедуру. Разбить G на подгруппы так, чтобы состояния s и t из G оказались в одной группе тогда и только тогда, когда для каждого входного символа a состояния s и t имеют переходы по a в состояния из одной и той же группы в П.
Полученные подгруппы добавляем в новое разбиение Пnew.
Принимаем П = Пnew и повторяем построение разбиения до стабилизации, т. е. пока разбиение не перестанет меняться.
Построение разбиения (алгоритм)
Для построения разбиения существует следующий алгоритм. Строим таблицу переходов для исходного автомата, строим начальное разбиение.
Каждой группе из разбиения назначаем идентификатор (для начального разбиения, например, 0 и 1).
Каждому состоянию (каждой строке таблицы) приписываем строку вида “a.bcd…xyz”, где [a, b, …, z] — идентификатор группы, к которой принадледжит состояние из [первого столбца (откуда переходим), второго столбца (куда переходим по первому символу), …, последнего столбца (куда переходим по последнему символу)].
Строим новые группы по совпадению строк, т. е. так, чтобы в одну группу попали состояния с одинаковыми приписанными строками.
Затем, новая итерация. Назначаем получившимся группам новые идентификаторы, например <0, 1, …, n>. И повторяем построение разбиения до стабилизации.
Заметим, что когда в группе осталось одно состояние, на последующих этапах построения разбиения можно уже не выписывать строку идентификаторов для этого состояния, т. к. эта строка в любом случае будет уникальна за счёт первого символа строки. Иначе говоря, при разбиении с группой из одного состояния ничего не случится — она переносится в новое разбиение как есть.
Построение приведённого автомата
Каждая из получившихся групп становится состоянием нового ДКА. Если группа содержит начальное (заключительное) состояние исходного автомата, эта группа становится начальным (соответственно заключительным) состоянием нового ДКА. Переходы строятся очевидным образом: переход в состояние из группы считается переходом в группу.
Приводим автомат. Удаляем сначала непорождающие (бесплодные, «мёртвые»), затем недостижимые состояния (определения даны для символов, но очевидным образом переносятся на состояния автомата).
Пример
Для построим ДКА с минимальным числом состояния для ДКА следующего вида:
Пусть группе
Пример (алгоритм построения разбиения)
Таблица переходов для всюду определённого (добавлено состояние Z) ДКА, соответствующего РВ (ab|ε)a*|abb|b*a. Из заданий экзамена 2012 года.
| a | b | I0 | I1 | |
|---|---|---|---|---|
| →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 |
Результат: в автомате и так было минимальное число состояний 🙂
ДКА, допускающий дополнение языка
Алгоритм построения ДКА, принимающего дополнение языка 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). Некоторые (точнее, те, которые рассматривались в курсе) преобразования приведены ниже.
Удаление левой рекурсии
Пусть у нас имеется правило вида (здесь и далее в этом разделе, заглавные буквы — нетерминальные символы, строчные — цепочки любых символов):
Оно не поддается однозначному анализу, поэтому его следует преобразовать.
Легко показать, что это правило эквивалентно следующей паре правил:
Левая факторизация
Суть данной процедуры — устранение неоднозначности в выборе правил по левому символу. Для этого находится общий левый префикс и то, что за ним может следует выносится в новое правило (строчные буквы — цепочки любых символов)
Пример
Что в свою очередь превратится в
Пример преобразования грамматики
Удаление левой рекурсии для S:
Левая факторизация для A:
Построение FIRST и FOLLOW
Вычисление FIRST
Для терминалов
Для нетерминалов
Для цепочек
Пример
Посчитать FIRST для всех нетерминалов и правил вывода грамматики:
FIRST нетерминалов в порядке разрешения зависимостей:
FIRST для правил вывода:
Вычисление FOLLOW
Вычисление функции FOLLOW для символа X:
Пример
Посчитать FOLLOW для всех нетерминалов грамматики:
Составление таблицы
В таблице M для пары нетерминал-терминал (в ячейке M[A, a]) указывается правило, по которому необходимо выполнять свёртку входного слова. Заполняется таблица следующим образом: для каждого правила вывода заданной грамматики A → α (где под α понимается цепочка в правой части правила) выполняются следующие действия:
Пример
Построить таблицу для грамматики
Разбор строки
Процесс разбора строки довольно прост. Его суть в следующем: на каждом шаге считывается верхний символ v из стека анализатора и берется крайний символ c входной цепочки.
Процесс заканчивается, когда и строка и стек дошли до концевого маркера (#).
Пример
разберем строку «aabbaabcb»:
| стек | строка | действие |
|---|---|---|
| S# | aabbaabcb$ | S → aS1 |
| aS1# | aabbaabcb$ | сдвиг |
| S1# | abbaabcb$ | S1 → AbBS1 |
| AbBS1# | abbaabcb$ | A → aA1 |
| aA1bBS1# | abbaabcb$ | сдвиг |
| A1bBS1# | bbaabcb$ | A1 → b |
| bbBS1# | bbaabcb$ | сдвиг |
| bBS1# | baabcb$ | сдвиг |
| BS1# | aabcb$ | B → ε |
| S1# | aabcb$ | S1 → AbBS1 |
| AbBS1# | aabcb$ | A → aA1 |
| AbBS1# | aabcb$ | A → aA1 |
| aA1bBS1# | aabcb$ | сдвиг |
| A1bBS1# | abcb$ | A1 → a |
| abBS1# | abcb$ | сдвиг |
| bBS1# | bcb$ | сдвиг |
| BS1# | cb$ | B → c |
| cS1# | cb$ | сдвиг |
| S1# | b$ | S1 → AbBS1 |
| AbBS1# | b$ | A → ε |
| bBS1# | b$ | сдвиг |
| BS1# | $ | B → ε |
| S1# | $ | S1 → ε |
| # | $ | готово |
Построение 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)-ситуаций
Пример
Построить каноническую систему множеств допустимых LR(1)-ситуаций для указанной грамматики:
Построение таблицы анализатора
Построение таблицы Goto
Таблица Goto показывает, в какое состояние надо перейти при встрече очередного символа грамматики. Поэтому, если в канонической системе множеств есть переход из Ii в Ij по символу A, то в Goto(Ii, A) мы ставим состояние Ij. После заполнения таблицы полагаем, что во всех пустых ячейках Goto(Ii, A) = Error
Построение таблицы Actions
Пример
Построить таблицы Action и Goto для грамматики
| Action | Goto | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| a | c | d | $ | S | S’ | A | B | a | c | d |
| I0 | Reduce(A → ε) | Reduce(A → ε) | Reduce(A → ε) | I1 | I2 | |||||
| I1 | Accept | |||||||||
| I2 | Shift(I6) | Shift(I4) | Shift(I5) | I3 | I6 | I4 | I5 | |||
| I3 | Reduce(A → ε) | Reduce(A → ε) | I13 | |||||||
| I4 | Shift(I8) | Shift(I9) | I7 | I8 | I9 | |||||
| I5 | Reduce(B → d) | Reduce(B → d) | ||||||||
| I6 | Reduce(A → Aa) | Reduce(A → Aa) | Reduce(A → Aa) | |||||||
| I7 | Shift(I10) | I10 | ||||||||
| I8 | Shift(I8) | Shift(I9) | I11 | I8 | I9 | |||||
| I9 | Reduce(B → d) | |||||||||
| I10 | Reduce(B → cBc) | Reduce(B → cBc) | ||||||||
| I11 | Shift(I12) | I12 | ||||||||
| I12 | Reduce(B → cBc) | |||||||||
| I13 | Shift(I14) | Reduce(S → ABA) | I14 | |||||||
| I14 | Reduce(A → Aa) | Reduce(A → Aa) | ||||||||
Разбор цепочки
На каждом шаге считывается верхний символ v из стека анализатора и берется крайний символ c входной цепочки.
Если в таблице дейстивий на пересечении v и c находится:
Пример
Построим разбор строки aaaccdcc:
| Стек | Строка | Действие |
| I0 | aaaccdcc$ | Reduce(A → ε), goto I2 |
| I0 A I2 | aaaccdcc$ | Shift(I6) |
| I0 A I2 a I6 | aaccdcc$ | Reduce(A → Aa), goto I2 |
| I0 A I2 | aaccdcc$ | Shift(I6) |
| I0 A I2 a I6 | accdcc$ | Reduce(A → Aa), goto I2 |
| I0 A I2 | accdcc$ | Shift(I6) |
| I0 A I2 a I6 | ccdcc$ | Reduce(A → Aa), goto I2 |
| I0 A I2 | ccdcc$ | Shift(I4) |
| I0 A I2 c I4 | cdcc$ | Shift(I8) |
| I0 A I2 c I4 c I8 | dcc$ | Shift(I9) |
| I0 A I2 c I4 c I8 d I9 | cc$ | Reduce(B → d), goto I11 |
| I0 A I2 c I4 c I8 B I11 | cc$ | Shift(I12) |
| I0 A I2 c I4 c I8 B I11 c I12 | c$ | Reduce(B → cBc), goto I7 |
| I0 A I2 c I4 B I7 | c$ | Shift(I10) |
| I0 A I2 c I4 B I7 c I10 | $ | Reduce(B → cBc), goto I3 |
| I0 A I2 B I3 | $ | Reduce(A → ε), goto I13 |
| I0 A I2 B I3 A I13 | $ | Reduce(S → ABA), goto I1 |
| I0 S I1 | $ | Accept |
Трансляция арифметических выражений (алгоритм Сети-Ульмана)
Примечание. Код генерируется doggy style Motorola-like, то есть
Построение дерева
Дерево строится как обычно для арифметического выражения: В корне операция с наименьшим приоритетом, далее следуют операции с приоритетом чуть выше и так далее. Скобки имеют наивысший приоритет. Если имеется несколько операций с одинаковым приоритетом — a op b op c, то дерево строится как для выражения (a op b) op с.
Пример
Построить дерево для выражения a + b / (d + a − b × c / d − e) + c × d
Решение: Запишем выражение в виде
Тогда в корне каждого поддерева будет операция, а выражения в скобках слева и справа от неё — её поддеревьями. Например, для подвыражения ((b) × (c)) / (d) в корне соответствующего поддерева будет операция «/», а её поддеревьями будут являться подвыражения ((b) × (c)) и (d).
Разметка дерева (вычисление количества регистров)
Далее необходимо вычислить для каждого поддерева, сколько регистров потребуется для его вычисления. Делается это разметкой дерева снизу вверх по следующим правилам:
Пример
Разметить дерево, построенное для выражения a + b / (d + a − b × c / d − e) + c × d
Распределение регистров и генерация кода
Распределение регистров происходит следующим образом:
Формируется код путём обхода дерева снизу вверх следующим образом:
1. Для вершины с меткой 0 код не генерируется
2. Если вершина — лист X с меткой 1 и регистром Ri, то ему сопоставляется код
3. Если вершина внутренняя c регистром Ri и её левый потомок — лист X с меткой 0, то ей соответствует код
4. Если поддеревья вершины с регистром Ri — не листья и метка правой вершины больше или равна метке левой (у которой регистр Rj, j = i + 1), то вершине соответствует код
5. Если поддеревья вершины с регистром Ri — не листья и метка правой вершины (у которой регистр Rj, j = i + 1) меньше метки левой, то вершине соответствует код
При этом нельзя сразу сделать Op Rj, Ri так как Op в общем случае некоммутативна. В случае, если Op коммутативна, делать Op Rj, Ri вместо Op Ri, Rj; MOVE Rj, Ri можно всё равно нельзя.
Общее правило: выписывать код снизу вверх сначала для вершины с большей меткой, потом с меньшей (если метки равны, то сначала для правой).
Пример
Распределить регистры и сгенерировать код для выражения a + b / (d + a − 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 атрибута:
Нумерация вершин выполняется в произвольном порядке, единственным условием является уникальность номеров узлов.
Разметка дерева производится следующим образом:
Sign указывает то, в каком случае можно прекратить вычисления текущего поддерева.
Для корня дерева fl=falselab, tl=truelab, sign=false.
| Операнд | fl | tl | sign |
|---|---|---|---|
| Левый операнд OR’a | Номер правого операнда | tl родительского узла | true |
| Правый операнд OR’a | fl родительского узла | tl родительского узла | sign родительского узла |
| Левый операнд AND’a | fl родительского узла | Номер правого операнда | false |
| Правый операнд AND’a | fl родительского узла | tl родительского узла | sign родительского узла |
| Операнд NOT’a | tl родительского узла | fl родительского узла | отрицание sign родительского узла |
Пример
Разметить дерево, построенное для логического выражения not A or B and C and (B or not C).
Генерация кода
Машинные команды, используемы в сгенерированном коде:
Построение кода производится следующим образом:
Пример
Для рассмотренного выше выражения сгенерируется следующий код:
Метод сопоставления образцов
Идея метода заключается в том, что для одного и того же участка программы может быть код сгенерирован различными способами, и, как следствие, можно добиться оптимизации по тому или иному параметру.
Постановка задачи
Имеется множество образцов, для каждого из которых определён кусок промежуточного представления, для которого он применим, вес и генерируемый код. Есть дерево промежуточного представления, представляющее собой фрагмент программы, для которой необходимо код сгенерировать. Целью является построение такого покрытия дерева промежуточного представления образцами, чтобы суммарный вес образцов был минимален.
Примеры образцов
Построение промежуточного представления
Сначала строим дерево разбора для всего выражения.
Построение покрытия
Генерация кода
Регистров у нас в этих задачах бесконечное количестов, так что каждый раз можно использовать новый.
Построение РВ по ДКА
Построение НКА по праволинейной грамматике
Приведение грамматики
Для того чтобы преобразовать произвольную КС-грамматику к приведенному виду, необходимо выполнить следующие действия:
Удаление бесполезных символов
Вход: КС-грамматика G = (T, N, P, S).
Выход: КС-грамматика G’ = (T, N’, P’, S), не содержащая бесплодных символов, для которой L(G) = L(G’).
Пример
Удалить бесполезные символы у грамматики G(
Удаление недостижимых символов
Вход: КС-грамматика G = (T, N, P, S)
Выход: КС-грамматика G’ = (T’, N’, P’, S), не содержащая недостижимых символов, для которой L(G) = L(G’).
Определение: КС-грамматика G называется приведенной, если в ней нет недостижимых и бесплодных символов.
Пример
Удалить недостижимые символы у грамматики G'(