Конструирование Компиляторов, Алгоритмы решения задач

Материал из eSyr's wiki.

Версия 11:05, 12 ноября 2011

Алгоритмы решения задач в pdf файле

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

Автомат для выражения строится композицией автоматов, соответствующих подвыражениям. На каждом этапе ∃! заключительное состояние, и нет переходов из заключительного состояния и в начальное. Для построения НКА используются следующие преобразования (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, q₀, F) построить детерминированный конечный автомат M = (Q', T, D', q'₀, F'). Начальным состоянием для строящегося автомата является ε-замыкание начального состояния автомата исходного. ε-замыкание — множество состояний, которые достижимы из данного путём переходов по ε. Далее, пока есть состояния, для которых не построены переходы (переходы делаются по символам, переходы по которым есть в исходном автомате), для каждого символа вычисляется ε-замыкание множества состояний, которые достижимы из рассматриваемого состояния путём перехода по рассматриваемому символу. Если состояние, которое соответствует найденному множеству, уже есть, то добавляется переход туда. Если нет, то добавляется новое полученное состояние.

Пример

Конечный автомат после пометки состояний, соответствующих ε-замыканию начального

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

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

Конечный автомат после первой итерации

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

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

Конечный автомат после второй итерации

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

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

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

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

Результат:

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

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

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

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

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

• A → aB | cC
• B → bD | cE
• C → ε
• D → aB | cC
• E → aB | cC

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

• 1 → 2 | 9
• 2 → a3
• 3 → 4 | 6
• 4 → b5
• 5 → 8
• 6 → c7
• 7 → 8
• 8 → 2 | 9
• 9 → c10
• 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:

Построение 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.

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

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

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

Пример

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

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

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

Разобъём множество состояний на две группы: заключительные состояния (q ∈ F) и остальные (q ∈ S\F).

Построение разбиения

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

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

Выберем по одному состоянию из каждой группы в полученном разбиении в качестве представителя для этой группы. Представители будут состояниями приведенного ДКА М. Пусть s — представитель. Предположим, что на входе a в M существует переход из t. Пусть r — представитель группы t. Тогда М имеет переход из s в r по a. Пусть начальное состояние М — представитель группы, содержащей начальное состояние s₀ исходного автомата, и пусть заключительные состояния М — представители в F. Отметим, что каждая группа полученного разбиения либо состоит только из состояний из F, либо не имеет состояний из F.

Удаление лишних состояний

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

Пример

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

• Инициализация: {C} конечное состояние {A,B,D,E} все остальные состояния
• {C} без изменений {A,D,E}, {B}, так как из A,D,E по a,c переходим в B и C соответственно
• больше никаких разбиений сделать не можем.
• Пусть группе {C} соответствует состояние С, группе {A,D,E} - состояние A, а группе {B} - состояние B. Тогда получаем ДКА с минимальным числом состояний:

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

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

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

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

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

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

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

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

• A → mB | nB | … | zB
• B → aB | bB | … | kB | ε

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

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

Пример

• A → ac | adf | adg | b

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

• A → aB | b
• B → c | df | dg

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

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

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

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

P:

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

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

• S → aS₁
• S₁ → AbBS₁ | ε

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

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

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

• S → aS₁
• S₁ → AbBS₁ | ε
• A → aA₁ | ε
• A₁ → 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₁…Y_k добавим в FIRST(X) множества FIRST всех символов в правой части правила до первого, из которого не выводится ε, включая его

Для цепочек

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

Пример

Посчитать FIRST для всех нетерминалов и правил вывода грамматики:

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

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

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

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

• FIRST(aS₁) = {a}
• FIRST(AbBS₁) = {a, b}
• FIRST(ε) = {ε}
• FIRST(aA₁) = {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 может оказаться крайним правым)
• Повторять предыдущие два пункта, пока возможно добавление символов в множество

Пример

Посчитать FOLLOW для всех нетерминалов грамматики:

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

Результат:

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

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

В таблице 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₁
• S₁ → AbBS₁ | ε
• A → aA₁ | ε
• A₁ → b | a
• B → c | ε

Результат:

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

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

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

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

Пример

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

Построение 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₀ с конфигурацией анализатора 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₀ построить нельзя — замыкание построено

• Из I₀ можно сделать переходы по S и A и получить множество конфигураций I₁ и I₂, состоящее из следующих элементов:
  • I₁ = {S' → S., $}
  • I₂ = {S → A.BA, $; A → A.a, c; A → A.a, d; A → A.a, a}
• I₁ не требует замыкания
• Построим замыкание I₂:
  • 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

Решение: