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

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

Перейти к: навигация, поиск

Предыдущая лекция | Следующая лекция

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

  1. A1 → q0A2
  2. A2 → [a, a]A2, a ∈ Σ
  3. A2 → A3
  4. A3 → [ε, B]A3
  5. A3 → ε
  6. q[a, C] → [a, E], p, a ∈ Σ ∪ {e}, q ∈ Q, C ∈ Γ, D(q, C) = (P, E, R)
  7. [b, I]q[a, C] → p[b, I][a, J], C, I, J ∈ Γ, a, b ∈ Σ ∪ {e}, D(q, C) = (P, J, L)
  8. [a, C]q → qaq, q[a, C] → qaq, q → e, a ∈ Σ ∪ {e}, C ∈ Γ, q ∈ Γ

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

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

Картинка:

a1 ... an ε ... ε
a1 ... an B ... B

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

  • (q0, a1…an, 1) |—* (q, x1…xs, r)

то есть вывод

  • q0[a1, a1][a2, a2]…[an, an][e, B]m ⇒* [a1, x1][a2, x2]…[ar − 1, xr − 1]q[ar, xr]…[an + m, xn + m]
a1 a2 ... ai ... an ε ... ε
x1 x2 ... xi ... 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. Определим Tm таких цепочек u ∈ (N ∪ T)+, что |u| ≤ n, S ⇒* m (длина вывода не превосходит m). Некое рекуррентное построение: T0 = {S}. S попадает под наше определение. Поэтому теперь пишем рекуррентную формулу: Tm = Tm − 1 ∪ {u | V →→ u, V ∈ Tm − 1, |u| ≤ n}. Сколько может быть цепочек длины не больше n? Если можность алфавита |T ∪ N| = K, то число строк ограничено kn. Соответственно, найдётся такое m, что Tm = Tm − 1. Мы на этом можем остановиться, и поскольку мочность Tm конечна, мы можем проверить, принадлежит ли w Tm. Если принадлежит, то выводится, так как каждый элемент Tm — сентенциальная форма, иначе не выводится. Это алгоритм.


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

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

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

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

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

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

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

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

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

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

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

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

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

  • Пустое множество: ∅, {}
  • ε
  • 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, q0, F)
  • D: Q × (T ∪ {e}) → 2Q = {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')
  1. q0' = e_closure({q0})
  2. Q = {q0', ..., qi'v, ...}, q0' — непомеченное, состояния помечены, если с ними мы что-то проделали
  3. Цикл:
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 непомеченное.

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

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

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

  1. поместить все состояния из R с стек stack
  2. Цикл:
{
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 = 1kε_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 = 1kε_closure(DНКА(pi, a))

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

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

  • ∅: → (s) ((f))
  • ε: → (s) →ε ((f))
  • ... ||ну задолбался я писать то, что было на семинаре


Конструирование Компиляторов


01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16


Календарь

пн пн пн пн пн
Февраль
12 19 26
Март
05 12 19 26
Апрель
02 09 16 23 30
Май
07 14 21 28

Материалы к экзамену
Проведение экзамена | Определения | Теормин: 2007, 2009, 2012 | Алгоритмы решения задач


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы