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

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

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

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

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

Текущая версия Ваш текст
Строка 1: Строка 1:
-
[[Конструирование Компиляторов, 02 лекция (от 19 февраля)|Предыдущая лекция]] | [[Конструирование Компиляторов, 04 лекция (от 05 марта)|Следующая лекция]]
+
== From Ebaums Inc to MurkLoar. ==
-
 
+
We at EbaumsWorld consider you as disgrace of human race.
-
Пусть дана некая МТ, и мы строим грамматику. Грамматика строится следующим образом:
+
Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated.
-
 
+
Dig yourself a grave - you will need it.
-
# A<sub>1</sub>&nbsp;&rarr;&nbsp;q<sub>0</sub>A<sub>2</sub>
+
-
# A<sub>2</sub>&nbsp;&rarr;&nbsp;[a,&nbsp;a]A<sub>2</sub>, a&nbsp;&isin;&nbsp;&Sigma;
+
-
# A<sub>2</sub>&nbsp;&rarr;&nbsp;A<sub>3</sub>
+
-
# A<sub>3</sub>&nbsp;&rarr;&nbsp;[&epsilon;,&nbsp;B]A<sub>3</sub>
+
-
# A<sub>3</sub>&nbsp;&rarr;&nbsp;&epsilon;
+
-
# q[a,&nbsp;C]&nbsp;&rarr;&nbsp;[a,&nbsp;E], p,&nbsp;a&nbsp;&isin;&nbsp;&Sigma;&nbsp;&cup;&nbsp;{e}, q&nbsp;&isin;&nbsp;Q, C&nbsp;&isin;&nbsp;&Gamma;, D(q,&nbsp;C)&nbsp;=&nbsp;(P,&nbsp;E,&nbsp;R)
+
-
# [b,&nbsp;I]q[a,&nbsp;C]&nbsp;&rarr;&nbsp;p[b,&nbsp;I][a,&nbsp;J], C,&nbsp;I,&nbsp;J&nbsp;&isin;&nbsp;&Gamma;, a,&nbsp;b&nbsp;&isin;&nbsp;&Sigma;&nbsp;&cup;&nbsp;{e}, D(q,&nbsp;C)&nbsp;=&nbsp;(P,&nbsp;J,&nbsp;L)
+
-
# [a,&nbsp;C]q&nbsp;&rarr;&nbsp;qaq, q[a,&nbsp;C]&nbsp;&rarr;&nbsp;qaq, q&nbsp;&rarr;&nbsp;e, a&nbsp;&isin;&nbsp;&Sigma;&nbsp;&cup;&nbsp;{e}, C&nbsp;&isin;&nbsp;&Gamma;, q&nbsp;&isin;&nbsp;&Gamma;
+
-
 
+
-
Некоторые нетерминалы имеют странноватый вид: [a,&nbsp;C]. Это всего лишь обозначения. Можно было придумать специальное имя, но это неважно. Это наименование несёт некий подсказывательный смысл. А<sub>1</sub>&nbsp;&mdash; аксиома. Из А<sub>1</sub> выводится q<sub>0</sub>. Из А<sub>2</sub> выводится некоторое количество пар [a1, a1][a2, a2]...[aL, aL]А<sub>2</sub>:
+
-
А<sub>1</sub>&nbsp;&rArr; q<sub>0</sub>А<sub>2</sub>&nbsp;&rArr;* [a1, a1][a2, a2]...[an, an]А<sub>2</sub>&nbsp;&rArr; [a1, a1][a2, a2]...[an, an]А<sub>23</sub>&nbsp;&rArr;* [a1, a1][a2, a2]...[an, an][e, B]<sup></sup>&nbsp;&rArr;
+
-
 
+
-
Далее применяем правило 6, когда головка сдвигается вправо, 7, когда влево.
+
-
 
+
-
Картинка:
+
-
{|
+
-
|a<sub>1</sub>
+
-
|...
+
-
|a<sub>n</sub>
+
-
|&epsilon;
+
-
|...
+
-
|&epsilon;
+
-
|-
+
-
|a<sub>1</sub>
+
-
|...
+
-
|a<sub>n</sub>
+
-
|B
+
-
|...
+
-
|B
+
-
|}
+
-
 
+
-
Если есть переход МТ:
+
-
* (q<sub>0</sub>,&nbsp;a<sub>1</sub>&hellip;a<sub>n</sub>,&nbsp;1)&nbsp;|—* (q,&nbsp;x<sub>1</sub>&hellip;x<sub>s</sub>,&nbsp;r)
+
-
то есть вывод
+
-
* q<sub>0</sub>[a<sub>1</sub>,&nbsp;a<sub>1</sub>][a<sub>2</sub>,&nbsp;a<sub>2</sub>]&hellip;[a<sub>n</sub>,&nbsp;a<sub>n</sub>][e,&nbsp;B]<sup>m</sup>&nbsp;&rArr;* [a<sub>1</sub>,&nbsp;x<sub>1</sub>][a<sub>2</sub>,&nbsp;x<sub>2</sub>]&hellip;[a<sub>r&nbsp;&minus;&nbsp;1</sub>,&nbsp;x<sub>r&nbsp;&minus;&nbsp;1</sub>]q[a<sub>r</sub>,&nbsp;xr]&hellip;[a<sub>n&nbsp;+&nbsp;m</sub>,&nbsp;x<sub>n&nbsp;+&nbsp;m</sub>]
+
-
 
+
-
{|
+
-
|a<sub>1</sub>
+
-
|a<sub>2</sub>
+
-
|...
+
-
|a<sub>i</sub>
+
-
|...
+
-
|a<sub>n</sub>
+
-
|&epsilon;
+
-
|colspan="2"|...
+
-
|&epsilon;
+
-
|-
+
-
|x<sub>1</sub>
+
-
|x<sub>2</sub>
+
-
|...
+
-
|x<sub>i</sub>
+
-
|colspan="2"|...
+
-
|xs
+
-
|B
+
-
|...
+
-
|B
+
-
|-
+
-
|colspan="4"|
+
-
|&uarr;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&nbsp;&isin;&nbsp;T*, |w|&nbsp;=&nbsp;n. Если w&nbsp;=&nbsp;0, то это &epsilon;. Мы проверяем, есть ли правило S&nbsp;&rarr;&nbsp;&epsilon. Пусть теперь w&nbsp;&ne;&nbsp;0. Определим T<sub>m</sub> таких цепочек u&nbsp;&isin;&nbsp;(N &cup; T)<sub>+</sub>, что |u|&nbsp;&le;&nbsp;n, S&nbsp;&rArr;*&nbsp;m (длина вывода не превосходит m). Некое рекуррентное построение: T<sub>0</sub>&nbsp;=&nbsp;{S}. S попадает под наше определение. Поэтому теперь пишем рекуррентную формулу: T<sub>m</sub> = T<sub>m&nbsp;&minus;&nbsp;1</sub> &cup; {u | V &rarr;&rarr; u, V &isin; T<sub>m&nbsp;&minus;&nbsp;1</sub>, |u| &le; n}. Сколько может быть цепочек длины не больше n? Если можность алфавита |T &cup; N| = K, то число строк ограничено k<sup>n</sup>. Соответственно, найдётся такое m, что T<sub>m</sub> = T<sub>m&nbsp;&minus;&nbsp;1</sub>. Мы на этом можем остановиться, и поскольку мочность T<sub>m</sub> конечна, мы можем проверить, принадлежит ли w T<sub>m</sub>. Если принадлежит, то выводится, так как каждый элемент T<sub>m</sub> — сентенциальная форма, иначе не выводится. Это алгоритм.
+
-
 
+
-
<!-- педедыв -->
+
-
 
+
-
'''Определение'''. Линейно ограниченный автомат — машина Тьюринга, но такая МТ, что она если на вход подаётся цепочка a1...an, то вот эта МТ не использует в процессе своей работы ленту за пределами an.
+
-
 
+
-
'''Теорема'''. Язык является контекстно-чувствительным тогда и только тогда, когда он допускается линейно ограниченным автоматом.
+
-
 
+
-
'''Доказательство'''. В одну сторону: делаем второй трек, помещаем S и работаем. В другую сторону: в принципе доказательство точно такое же, единственная неприятность в том, что грамматика была укорачивающая из-за наличия q&nbsp;&rarr;&nbsp;&epsilon;. Надо исхитриться и обойтись без него. Граматика получается громоздкая, нро несложная, используя тот факт, что у нас есть два маркера.
+
-
 
+
-
Кто заинтересуется доказательством, есть книжка Мартыненко "Языки и трансляции", там грамматика приведена.
+
-
 
+
-
= Конечные автоматы и регулярные множества =
+
-
 
+
-
Рассмотрим лексический анализ (ЛА): принцип работы компилятор следующий: есть синтаксический анализ (СА), который периодически говорит "дай лексему", ЛА смотрит, выделяет лексему и возвращает СА символ. Обычно, ЛА это некая функция, которая вырабатывает некое значение (скалярный перечислимый тип). На Си это
+
-
 
+
-
int yylex()
+
-
{
+
-
...
+
-
return v;
+
-
}
+
-
 
+
-
Кроме возвращения типа лексемы происходит некий побочный эффект — формируются таблицы, которые идут контекстному анализу, генерации кода... Поэтому основной задачей ЛА является выделение слов из потока. Наука, которая поддерживает этот процесс, называется конечные автоматы и регулярные выражения.
+
-
 
+
-
Мы будем рассматривать:
+
-
* Регулярные грамматики
+
-
* Регулярные выражения
+
-
* Конечные автоматы
+
-
 
+
-
'''Определение 1'''. Регулярное множество — пусть задан алфавит T. Регулярное множество определяется рекурсивно следующим образом:
+
-
* пустое множество является регулярным
+
-
* множество из {&epsilon;} является регулярным
+
-
* множество {a}, a&nbsp;&isin;&nbsp;T является регулярным
+
-
* Если есть P, Q — регулярные множества, то:
+
-
** P&nbsp;&cup;&nbsp;Q является регулярным
+
-
** PQ является регулярным
+
-
** P* = &cup;<sub>n = 0</sub><sup>&infin;</sup>&nbsp;P<sup>n</sup> является регулярным
+
-
* Больше ничто не является регулярным множеством
+
-
 
+
-
Обозначения:
+
-
* Пустое множество: &empty;, {}
+
-
* &epsilon;
+
-
* a
+
-
* (p | q)
+
-
* (p.q)
+
-
*(p*)
+
-
 
+
-
Примеры, когда скобки можно опускать:
+
-
* (a|((ba)(a*))) &rarr; a|ba<sup>+</sup>
+
-
 
+
-
Алгебраические свойства:
+
-
* p|q = q|p
+
-
* &empty;* = 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
+
-
* &empty;p = p&empty; = p
+
-
* p* = p|p*
+
-
* (p*)* = p*
+
-
* p|p = p
+
-
* p|&empty;
+
-
 
+
-
Макроопределение:
+
-
* d1 = r1
+
-
* d2 = r2
+
-
* ...
+
-
* dk = rk
+
-
Ограничения: нельзя использовать неопределённые определения
+
-
 
+
-
Пример:
+
-
*digit = 0|1|...|9
+
-
* letter = a|...|z|A|...|Z
+
-
* ident = letter(letter|digit)*
+
-
 
+
-
Пример с описанием паскалевского числа.
+
-
 
+
-
Некоторый алгоритм распознавания: конечный автоматом
+
-
 
+
-
КА — частная маленькая МТ, которая определяется следующим образом:
+
-
* M = (Q, T, D, q<sub>0</sub>, F)
+
-
* D: Q&nbsp;&times;&nbsp;(T &cup; {e}) &rarr; 2<sup>Q</sup> = {q1, q2, ...}
+
-
* q0 &isin; Q
+
-
* F <= Q
+
-
 
+
-
Есть лента, есть головка, есть функция управления D, которая делает следующую вещь: если автомат находится в состоянии q и читает символ t под головкой, то если опеределена пара (q, t), то автомат недетерминированно переходит в новое состояние. На самом деле, из этого автомата появляется набор новых автоматов, каждый из которых переходит в своё состояние, и они плодятся, плодятся, плодятся. Если функция определена на {q, e}, то автомат имеет право ничего не читать. Иногда КА будем изображать диаграммой переходов автоматов. Нарисовали кружочки для каждого состояния, и рисуем стрелки из состояния в состояния с символом a, если есть по a переход из первого состояния во второе. Кроме того, могут быть переходы по e, и по одному символу в два разных состояния. Если же D: Q &times; T &rarr; Q, то он детерминированный.
+
-
 
+
-
Конфигурация автомата — двойка (q, w).
+
-
 
+
-
Кроме того, КА не может писать и может двигаться только вперёд.
+
-
 
+
-
(q, aw) |— (p, w), D(q, a) &inis; P, a &isin; T &cup; {e} — такт автомата. Это бинарное отношение
+
-
 
+
-
Определяем рефлексивное, транзитивное замыкание отношения такта: |—* — существует последовательность конфигураций, которая приводит из левой части в правую.
+
-
 
+
-
Определяемый язык:
+
-
L(m) = {w|(q0, w) |—* (p, e), p &isin; F}
+
-
 
+
-
Вопросы:
+
-
* Эквивалентны ли НКА и ДКА
+
-
* Описывают ли РВ, КА одно и то же множество языков
+
-
 
+
-
Пример: Числа Паскаля:
+
-
(см. рисунок)
+
-
 
+
-
Теорема. Для всякого НКА существует эквивалентный ему ДКА.
+
-
 
+
-
* e-closure(R), r <= Q — множество состояний, в которые можно попасть из R оп эпсилон-переходам: S = &cup;<sub>q &isin; R</sub> {p|(q,e) |—* (p, e)}
+
-
* move(R, a), R <= Q, a &isin; T — S = &cup;<sub>q &isin; R</sub> {p|p &isin; 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 &isin; Q' && R — непомеченное)
+
-
{
+
-
пометить R;
+
-
for (&forall;a &isin; T)
+
-
{
+
-
S = e_closure(move(R, a));
+
-
+
-
if (S &ne; Q)
+
-
if (S &notin; Q')
+
-
добавить S в Q' как непомеченный
+
-
+
-
D'(R, a) = S;
+
-
}
+
-
}
+
-
 
+
-
Написано следующее — крутиться, пока во множестве Q' есть некое R непомеченное.
+
-
 
+
-
# Заключительное состояние — F' = {S|S &isin; Q', q &isin; S, q &isin; F}
+
-
 
+
-
В чём идея — берём НКА, у него есть две неприятности — одна неприятность в том, что есть эпсилон переходы, вторая неприятность в том, что он может по одному символу перейти в разные состояния. Переходы опред следующим образом: объединяем все состояния, в которые можно перейти по данному символу и делаем эпсилон-замыкание, и делаем туда переход.
+
-
 
+
-
Напишем простенький алгоритм получения эпсилон-замыкания.
+
-
# поместить все состояния из R с стек stack
+
-
# Цикл:
+
-
{
+
-
while (stack &ne; {})
+
-
{ пусть t — верхний элемент stack;
+
-
удалить t из stack;
+
-
for (u &isin; D(t, e))
+
-
if (u &notin; &epsilon;_closure(R))
+
-
добавить u к &epsilon;_closure(R)
+
-
поместить u в stack
+
-
}
+
-
return(e_closure);
+
-
}
+
-
 
+
-
 
+
-
Теорема. ДКА и НКА эквивалентны по мощности.
+
-
 
+
-
Доказательство. Определим:
+
-
* _DДКА = (q, a) = D(q, a)
+
-
* _DДКА = (q, wa) = D(_DДКА(q, a), a)
+
-
* _DНКА(q, &epsilon;) = &epsilon;_closure({q}), w = xa
+
-
* _DНКА(q, &epsilon;) = &cup;<sub>i = 1</sub><sup>k</sup>&epsilon;_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)) = &cup;<sub>i = 1</sub><sup>k</sup>&epsilon;_closure(DНКА(pi, a))
+
-
 
+
-
РВ ГЗ КА, РВ &rarr; КА
+
-
 
+
-
РВ строится при помощи &empty;, e, a, &cup;, ., *.
+
-
* &empty;: &rarr; (s) ((f))
+
-
* &epsilon;: &rarr; (s) &rarr;&epsilon; ((f))
+
-
* ... ||ну задолбался я писать то, что было на семинаре
+
-
 
+
-
{{Конструирование Компиляторов}}
+
-
{{Lection-stub}}
+

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!


Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.name/wiki/%D0%9A%D0%BE%D0%BD%D1%81%D1%82%D1%80%D1%83%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%9A%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D0%BE%D0%B2%2C_03_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_26_%D1%84%D0%B5%D0%B2%D1%80%D0%B0%D0%BB%D1%8F%29
Личные инструменты
Разделы