Конструирование Компиляторов, 03 лекция (от 26 февраля)

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

Пусть дана некая МТ, и мы строим грамматику. Грамматика строится следующим образом:

A₁ → q₀A₂
A₂ → [a, a]A₂, a ∈ Σ
A₂ → A₃
A₃ → [ε, B]A₃
A₃ → ε
q[a, C] → [a, E], p, a ∈ Σ ∪ {e}, q ∈ Q, C ∈ Γ, D(q, C) = (P, E, R)
[b, I]q[a, C] → p[b, I][a, J], C, I, J ∈ Γ, a, b ∈ Σ ∪ {e}, D(q, C) = (P, J, L)
[a, C]q → qaq, q[a, C] → qaq, q → e, a ∈ Σ ∪ {e}, C ∈ Γ, q ∈ Γ

Некоторые нетерминалы имеют странноватый вид: [a, C]. Это всего лишь обозначения. Можно было придумать специальное имя, но это неважно. Это наименование несёт некий подсказывательный смысл. А₁ — аксиома. Из А₁ выводится q₀. Из А₂ выводится некоторое количество пар [a1, a1][a2, a2]...[aL, aL]А₂: А₁ ⇒ q₀А₂ ⇒* [a1, a1][a2, a2]...[an, an]А₂ ⇒ [a1, a1][a2, a2]...[an, an]А₂₃ ⇒* [a1, a1][a2, a2]...[an, an][e, B] ⇒

Далее применяем правило 6, когда головка сдвигается вправо, 7, когда влево.

Картинка:

a₁	...	a_n	ε	...	ε
a₁	...	a_n	B	...	B

Если есть переход МТ:

(q₀, a₁…a_n, 1) |—* (q, x₁…x_s, r)

то есть вывод

q₀[a₁, a₁][a₂, a₂]…[a_n, a_n][e, B]^m ⇒* [a₁, x₁][a₂, x₂]…[a_r − 1, x_r − 1]q[a_r, xr]…[a_n + m, x_n + m]

a₁	a₂	...	a_i	...	a_n	ε	...		ε
x₁	x₂	...	x_i	...		xs	B	...	B
				↑r

Доказывается по индукции, ибо каждый шаг сохраняет это свойство.

Что такое m — ежели цепочка a1...an допускается МТ, то в конечном счёте МТ впадает в конечное состояние, и поскольку она дискретная, то она использует конечное количество ленты, и m — то дополнительное количество ячеек цепочки, которое использует МТ в процессе работы.

Что делает 8 правило: если q принадлежит F, то ликвидируем второй трек, и сводим слово к a1...an. И, следовательно, в грамматике будет выводить a1...an.

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

Так как по МТ построили грамматику, по грамматике построили МТ, то если язык определяется грамматикой типа 0, то он же определяется с помощью распознавания МТ.

В этом доказательстве существенно используется то, что грамматика укорачивающая, и её нельзя отнести к 1 классу.

Определение. Языки типа 0 — рекурсивно перечислимые множества.

[править] Грамматики уровня 1

Определение.

Утверждение 1. Любой контекстно-чувствительный язык является рекурсивным. (рекурсивное множество — множество, определяемое алгоритмом). То есть, существует алгоритм (умеет останавливаться на любом входе).

Пример. Пусть грамматика G=(N,T,P,S) — неукорачивающая. Рассмотрим L(G). Утверждение: L(G) екурсивен.

Доказательство. Рассмотрим w ∈ T*, |w| = n. Если w = 0, то это ε. Мы проверяем, есть ли правило S → &epsilon. Пусть теперь w ≠ 0. Определим T_m таких цепочек u ∈ (N ∪ T)₊, что |u| ≤ n, S ⇒* m (длина вывода не превосходит m). Некое рекуррентное построение: T₀ = {S}. S попадает под наше определение. Поэтому теперь пишем рекуррентную формулу: T_m = T_m − 1 ∪ {u | V →→ u, V ∈ T_m − 1, |u| ≤ n}. Сколько может быть цепочек длины не больше n? Если можность алфавита |T ∪ N| = K, то число строк ограничено kⁿ. Соответственно, найдётся такое m, что T_m = T_m − 1. Мы на этом можем остановиться, и поскольку мочность T_m конечна, мы можем проверить, принадлежит ли w T_m. Если принадлежит, то выводится, так как каждый элемент T_m — сентенциальная форма, иначе не выводится. Это алгоритм.

Определение. Линейно ограниченный автомат — машина Тьюринга, но такая МТ, что она если на вход подаётся цепочка a1...an, то вот эта МТ не использует в процессе своей работы ленту за пределами an.

Теорема. Язык является контекстно-чувствительным тогда и только тогда, когда он допускается линейно ограниченным автоматом.

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

Кто заинтересуется доказательством, есть книжка Мартыненко "Языки и трансляции", там грамматика приведена.

[править] Конечные автоматы и регулярные множества

Рассмотрим лексический анализ (ЛА): принцип работы компилятор следующий: есть синтаксический анализ (СА), который периодически говорит "дай лексему", ЛА смотрит, выделяет лексему и возвращает СА символ. Обычно, ЛА это некая функция, которая вырабатывает некое значение (скалярный перечислимый тип). На Си это

int yylex()
{
  ...
  return v;
}

Кроме возвращения типа лексемы происходит некий побочный эффект — формируются таблицы, которые идут контекстному анализу, генерации кода... Поэтому основной задачей ЛА является выделение слов из потока. Наука, которая поддерживает этот процесс, называется конечные автоматы и регулярные выражения.

Мы будем рассматривать:

Регулярные грамматики
Регулярные выражения
Конечные автоматы

Определение 1. Регулярное множество — пусть задан алфавит T. Регулярное множество определяется рекурсивно следующим образом:

пустое множество является регулярным
множество из {ε} является регулярным
множество {a}, a ∈ T является регулярным
Если есть P, Q — регулярные множества, то:
- P ∪ Q является регулярным
- PQ является регулярным
- P* = ∪_{n = 0}^∞ Pⁿ является регулярным
Больше ничто не является регулярным множеством

Обозначения:

Пустое множество: ∅, {}
ε
a
(p | q)
(p.q)
(p*)

Примеры, когда скобки можно опускать:

(a|((ba)(a*))) → a|ba⁺

Алгебраические свойства:

p|q = q|p
∅* = e
p(q|r) = (p|q)|r = (p|q|r)
p(qr) = (pq)r = pqr
p(q|r) = pq|pr
(p|q|r) = pr|qr
pe = ep = p
∅p = p∅ = p
p* = p|p*
(p*)* = p*
p|p = p
p|∅

Макроопределение:

d1 = r1
d2 = r2
...
dk = rk

Ограничения: нельзя использовать неопределённые определения

Пример:

digit = 0|1|...|9
letter = a|...|z|A|...|Z
ident = letter(letter|digit)*

Пример с описанием паскалевского числа.

Некоторый алгоритм распознавания: конечный автоматом

КА — частная маленькая МТ, которая определяется следующим образом:

M = (Q, T, D, q₀, F)
D: Q × (T ∪ {e}) → 2^Q = {q1, q2, ...}
q0 ∈ Q
F <= Q

Есть лента, есть головка, есть функция управления D, которая делает следующую вещь: если автомат находится в состоянии q и читает символ t под головкой, то если опеределена пара (q, t), то автомат недетерминированно переходит в новое состояние. На самом деле, из этого автомата появляется набор новых автоматов, каждый из которых переходит в своё состояние, и они плодятся, плодятся, плодятся. Если функция определена на {q, e}, то автомат имеет право ничего не читать. Иногда КА будем изображать диаграммой переходов автоматов. Нарисовали кружочки для каждого состояния, и рисуем стрелки из состояния в состояния с символом a, если есть по a переход из первого состояния во второе. Кроме того, могут быть переходы по e, и по одному символу в два разных состояния. Если же D: Q × T → Q, то он детерминированный.

Конфигурация автомата — двойка (q, w).

Кроме того, КА не может писать и может двигаться только вперёд.

(q, aw) |— (p, w), D(q, a) &inis; P, a ∈ T ∪ {e} — такт автомата. Это бинарное отношение

Определяем рефлексивное, транзитивное замыкание отношения такта: |—* — существует последовательность конфигураций, которая приводит из левой части в правую.

Определяемый язык: L(m) = {w|(q0, w) |—* (p, e), p ∈ F}

Вопросы:

Эквивалентны ли НКА и ДКА
Описывают ли РВ, КА одно и то же множество языков

Пример: Числа Паскаля: (см. рисунок)

Теорема. Для всякого НКА существует эквивалентный ему ДКА.

e-closure(R), r <= Q — множество состояний, в которые можно попасть из R оп эпсилон-переходам: S = ∪_{q ∈ R} {p|(q,e) |—* (p, e)}
move(R, a), R <= Q, a ∈ T — S = ∪_{q ∈ R} {p|p ∈ D(q, a)}

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

НКА M = (Q, T, D, q0, F
ДКА M'=(Q', T, D', q0', F')

q0' = e_closure({q0})
Q = {q0', ..., qi'v, ...}, q0' — непомеченное, состояния помечены, если с ними мы что-то проделали
Цикл:

while (R ∈ Q' && R — непомеченное)
{
  пометить R;
  for (∀a ∈ T)
  {
    S = e_closure(move(R, a));

    if (S ≠ Q)
      if (S ∉ Q')
        добавить S в Q' как непомеченный

    D'(R, a) = S;
  }
}

Написано следующее — крутиться, пока во множестве Q' есть некое R непомеченное.

Заключительное состояние — F' = {S|S ∈ Q', q ∈ S, q ∈ F}

В чём идея — берём НКА, у него есть две неприятности — одна неприятность в том, что есть эпсилон переходы, вторая неприятность в том, что он может по одному символу перейти в разные состояния. Переходы опред следующим образом: объединяем все состояния, в которые можно перейти по данному символу и делаем эпсилон-замыкание, и делаем туда переход.

Напишем простенький алгоритм получения эпсилон-замыкания.

поместить все состояния из R с стек stack
Цикл:

{
while (stack ≠ {})
{ пусть t — верхний элемент stack;
  удалить t из stack;
  for (u ∈ D(t, e))
    if (u ∉ ε_closure(R))
      добавить u к ε_closure(R)
      поместить u в stack
  }
return(e_closure);
}

Теорема. ДКА и НКА эквивалентны по мощности.

Доказательство. Определим:

_DДКА = (q, a) = D(q, a)
_DДКА = (q, wa) = D(_DДКА(q, a), a)
_DНКА(q, ε) = ε_closure({q}), w = xa
_DНКА(q, ε) = ∪_{i = 1}^kε_closure(DНКА(pi, a))

формулировка теоремы: _DДКА(&epsilon_closure({q0})), w) = _DНКА(q0, w)

Предположение индукции: w = e, |w| = 0, _DНКА(q0, e) = q0 = e_closure({q0}), Шаг индукции: w = ma, _DДКА(e_closure({q0}, m)) = _DНКА(q0, m) = {p1, ..., pk}, _DДКА({q0}, na = _DНКА(q0, na)) = ∪_{i = 1}^kε_closure(DНКА(pi, a))

РВ ГЗ КА, РВ → КА

РВ строится при помощи ∅, e, a, ∪, ., *.