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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Грамматика)
(Лемма о разрастании (для контекстно-свободного языка))
 
(20 промежуточных версий не показаны.)
Строка 1: Строка 1:
* Авторы рукописной версии: Синдеев Михаил (оригинал), Комаров Сергей (обработка)
* Авторы рукописной версии: Синдеев Михаил (оригинал), Комаров Сергей (обработка)
-
* Обработанная рукописная версия: http://www.komserg.ru/botva/konstr.rar
+
 
 +
== Цепочка ==
 +
'''Цепочка''' — последовательность символов.
 +
 
 +
'''Терминальная цепочка''' — последовательность терминальных символов.
== Язык ==
== Язык ==
-
'''Язык''' — множество цепочек.
+
'''Язык''' — множество терминальных цепочек.
== Грамматика ==
== Грамматика ==
'''Грамматика''' — G = (N, T, P, S)
'''Грамматика''' — G = (N, T, P, S)
-
* N — множество нетерминальных символов (A, B, C)
+
* N — множество нетерминальных символов (напр. A, B, C...)
-
* T (иногда E) — алфавит терминальных символов
+
* T (иногда E) — алфавит терминальных символов (N ∩ T = ∅)
-
* P — множество правил вывода
+
* P — конечное множество правил вывода
-
** P = {α → β | α ∈ (N ∪ T)* N (N ∪ T)*, B ∈ (N ∪ T)* }
+
** P = {&alpha; &rarr; &beta; | &alpha; &isin; (N &cup; T)<sup>+</sup>; &beta; &isin; (N &cup; T)*}
-
* S &isin; N — аксиома
+
* S &isin; N — аксиома (или начальный символ) грамматики
== Сентенциальная форма ==
== Сентенциальная форма ==
-
'''Сентенциальная форма''' — последовательность символов (терминалов и нетерминалов), выводимых из аксиомы
+
'''Сентенциальная форма''' — последовательность символов (терминалов и нетерминалов), выводимых из начального символа (аксиомы)
== Язык, порождённый грамматикой ==
== Язык, порождённый грамматикой ==
Строка 22: Строка 26:
== Иерархия по Хомскому ==
== Иерархия по Хомскому ==
-
* 0: произвольные грамматики
+
* '''0:''' произвольные грамматики
-
* 1: неукорачивающие (контекстно-зависимые) грамматики
+
* '''1:''' неукорачивающие (контекстно-зависимые) грамматики
** &alpha; &rarr; &beta;, |&alpha;| &le; |&beta;|
** &alpha; &rarr; &beta;, |&alpha;| &le; |&beta;|
** допускается S &rarr; &epsilon;, если S не входит ни в какую правую часть
** допускается S &rarr; &epsilon;, если S не входит ни в какую правую часть
-
* 2: контекстно-свободные
+
* '''2:''' контекстно-свободные
** A &rarr; &alpha;, &alpha; &isin; (N &cup; T)*
** A &rarr; &alpha;, &alpha; &isin; (N &cup; T)*
-
* 3: праволинейные (A &rarr; w, A &rarr; wB, w &isin; T*), леволинейные (A &rarr; w, A &rarr; Bw, w &isin; T*),
+
* '''3:''' праволинейные (A &rarr; w, A &rarr; wB, w &isin; T*), леволинейные (A &rarr; w, A &rarr; Bw, w &isin; T*),
Из определения следует, что Z<sub>0</sub> &supe; Z<sub>1</sub> &supe; Z<sub>2</sub> &supe; Z<sub>3</sub>.
Из определения следует, что Z<sub>0</sub> &supe; Z<sub>1</sub> &supe; Z<sub>2</sub> &supe; Z<sub>3</sub>.
-
Существует теорема, которая доказывает, что Z<sub>0</sub> &sup; Z<sub>1</sub> &sup; Z<sub>2</sub> &sup; Z<sub>3</sub>.
+
Существует теорема, которая доказывает (конструктивно, путём построения соответствующих грамматик), что Z<sub>0</sub> &sup; Z<sub>1</sub> &sup; Z<sub>2</sub> &sup; Z<sub>3</sub>.
== Машина Тьюринга ==
== Машина Тьюринга ==
Строка 38: Строка 42:
* Q — конечное множество состояний
* Q — конечное множество состояний
* Г — конечное множество символов (конечный алфавит)
* Г — конечное множество символов (конечный алфавит)
-
* &Sigma; — входной алфавит
+
* &Sigma; — входной алфавит - подмножество Г, не включающее пустой символ
* D — правила перехода
* D — правила перехода
** D: (Q\F) &times; Г &rarr; Q &times; Г &times; {L, R} — для детерминированной машины Тьюринга
** D: (Q\F) &times; Г &rarr; Q &times; Г &times; {L, R} — для детерминированной машины Тьюринга
Строка 50: Строка 54:
== Рекурсивно-перечислимый язык ==
== Рекурсивно-перечислимый язык ==
'''Язык''' является '''рекурсивно-перечислимым''', если он может быть распознан машиной Тьюринга.
'''Язык''' является '''рекурсивно-перечислимым''', если он может быть распознан машиной Тьюринга.
 +
''(доп.)'' '''Язык''' - '''рекурсивно-перечислим''', если имеется процедура, распознающая предложения языка.
== Линейно-ограниченный автомат ==
== Линейно-ограниченный автомат ==
Строка 55: Строка 60:
== Лемма о разрастании ==
== Лемма о разрастании ==
-
Если язык L — регулярный, то &exist; k: &forall; w &isin; L, |w| &ge; k | w = xyz, 0 &le; |y| &le; k, xy<sup>i</sup>z &isin; L, &forall; i &ge; 0
+
Если язык L — регулярный, то &exist; k: &forall; w &isin; L, |w| &ge; k | w = xyz, 0 < |y|, |xy| &le; k, xy<sup>i</sup>z &isin; L, &forall; i &ge; 0
== Неоднозначная грамматика ==
== Неоднозначная грамматика ==
Строка 74: Строка 79:
== Расширенный магазинный автомат ==
== Расширенный магазинный автомат ==
 +
 +
Отличается от магазинного автомата только областью определения D.
 +
'''Расширенный магазинный автомат''' — M = (Q, T, Г, D, q<sub>0</sub>, z<sub>0</sub>, F)
'''Расширенный магазинный автомат''' — M = (Q, T, Г, D, q<sub>0</sub>, z<sub>0</sub>, F)
* Q — конечное множество состояний
* Q — конечное множество состояний
Строка 84: Строка 92:
== Грамматика в нормальной форме Хомского ==
== Грамматика в нормальной форме Хомского ==
-
'''Грамматика''' находится '''в нормальной форме Хомского''', если правила вывода имеют вид:
+
 
-
* A &rarr; BC; B, C &isin; N
+
Грамматика находится '''в нормальной форме Хомского''', если правила вывода имеют вид:
-
* A &rarr; a
+
# Либо A &rarr; BC; A, B, C — нетерминалы.
-
* S &rarr; &epsilon; (если &epsilon; &isin; L; S не входит ни в одну правую часть)
+
# Либо A &rarr; a; a — терминал.
 +
# Либо S &rarr; &epsilon; и в этом случае S не встречается в правых частях правил.
== Лемма о разрастании (для контекстно-свободного языка) ==
== Лемма о разрастании (для контекстно-свободного языка) ==
-
Для любого контекстно-свободного языка L &exist; l, k: &alpha; &isin; L, |&alpha;| &gt; l, &alpha; = uvwxy
+
Для любого контекстно-свободного языка L &exist; l, k: &forall; &alpha; &isin; L, |&alpha;| &gt; l, &alpha; = uvwxy
# |vwx| &le; k
# |vwx| &le; k
# vx &ne; &epsilon;
# vx &ne; &epsilon;
Строка 103: Строка 112:
x — '''непорождающий символ''', если из него нельзя вывести терминальную цепочку
x — '''непорождающий символ''', если из него нельзя вывести терминальную цепочку
-
x — '''непорождающий символ''', если из не существует вывода x &rArr;* w, w &isin; T*
+
x — '''непорождающий символ''', если не существует вывода x &rArr;* w, w &isin; T*
== Бесполезный символ ==
== Бесполезный символ ==
Строка 120: Строка 129:
## PQ (конкатенация, то есть множество таких pq, что p &isin; P, q &isin; Q)
## PQ (конкатенация, то есть множество таких pq, что p &isin; P, q &isin; Q)
## P* (итерация: P* = {&epsilon;} &cup; P &cup; PP &cup; PPP &cup; &hellip;)
## P* (итерация: P* = {&epsilon;} &cup; P &cup; PP &cup; PPP &cup; &hellip;)
-
# Ничто друге не является регулярным множеством в алфавите T
+
# Ничто другое не является регулярным множеством в алфавите T
== Регулярное выражение ==
== Регулярное выражение ==
Строка 126: Строка 135:
== Длина пути от листа к корню ==
== Длина пути от листа к корню ==
-
'''Длиной пути от листа к корню''' называется число вершин в этом пути, считая сам лист (то есть, &lt;число&nbsp;дуг&gt; + 1)
+
'''Длиной пути от листа к корню''' называется число вершин в пути от листа до корня, считая сам лист и сам корень (то есть, &lt;число&nbsp;дуг в пути&gt; + 1)
== Высота дерева ==
== Высота дерева ==
Строка 155: Строка 164:
== Леворекурсивная грамматика ==
== Леворекурсивная грамматика ==
-
'''Грамматика''' называется '''леворекурсивной''', если в ней имеется нетерминал A такой, что существует вывод A &rArr; Au для некоторой строки u.
+
'''Грамматика''' называется '''леворекурсивной''', если в ней имеется нетерминал A такой, что существует вывод A &rArr;<sup>+</sup> Au для некоторой цепочки u.
== LL(1) грамматика ==
== LL(1) грамматика ==

Текущая версия

  • Авторы рукописной версии: Синдеев Михаил (оригинал), Комаров Сергей (обработка)

Содержание

[править] Цепочка

Цепочка — последовательность символов.

Терминальная цепочка — последовательность терминальных символов.

[править] Язык

Язык — множество терминальных цепочек.

[править] Грамматика

Грамматика — G = (N, T, P, S)

  • N — множество нетерминальных символов (напр. A, B, C...)
  • T (иногда E) — алфавит терминальных символов (N ∩ T = ∅)
  • P — конечное множество правил вывода
    • P = {α → β | α ∈ (N ∪ T)+; β ∈ (N ∪ T)*}
  • S ∈ N — аксиома (или начальный символ) грамматики

[править] Сентенциальная форма

Сентенциальная форма — последовательность символов (терминалов и нетерминалов), выводимых из начального символа (аксиомы)

[править] Язык, порождённый грамматикой

Язык, порождённый грамматикой — L(G) = {W | W ∈ T*, S ⇒+ W}

Язык, порождённый грамматикой — множество всех терминальных цепочек, выводимых из аксиомы грамматики

[править] Иерархия по Хомскому

  • 0: произвольные грамматики
  • 1: неукорачивающие (контекстно-зависимые) грамматики
    • α → β, |α| ≤ |β|
    • допускается S → ε, если S не входит ни в какую правую часть
  • 2: контекстно-свободные
    • A → α, α ∈ (N ∪ T)*
  • 3: праволинейные (A → w, A → wB, w ∈ T*), леволинейные (A → w, A → Bw, w ∈ T*),

Из определения следует, что Z0 ⊇ Z1 ⊇ Z2 ⊇ Z3.

Существует теорема, которая доказывает (конструктивно, путём построения соответствующих грамматик), что Z0 ⊃ Z1 ⊃ Z2 ⊃ Z3.

[править] Машина Тьюринга

Машина Тьюринга — Tm = (Q, Г, Σ, D, q0, F)

  • Q — конечное множество состояний
  • Г — конечное множество символов (конечный алфавит)
  • Σ — входной алфавит - подмножество Г, не включающее пустой символ
  • D — правила перехода
    • D: (Q\F) × Г → Q × Г × {L, R} — для детерминированной машины Тьюринга
    • D: (Q\F) × Г → 2Q × Г × {L, R} — для недетерминированной машины Тьюринга
  • q0 ∈ Q — начальное состояние
  • F ⊆ Q — множество конечных состояний

[править] Универсальная машина Тьюринга

Универсальная машина Тьюринга — такая машина Тьюринга, которая моделирует любую машину Тьюринга.

[править] Рекурсивно-перечислимый язык

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

[править] Линейно-ограниченный автомат

Линейно-ограниченный автомат — это машина Тьюринга, которая не может выходить за область входной строки.

[править] Лемма о разрастании

Если язык L — регулярный, то ∃ k: ∀ w ∈ L, |w| ≥ k | w = xyz, 0 < |y|, |xy| ≤ k, xyiz ∈ L, ∀ i ≥ 0

[править] Неоднозначная грамматика

Грамматика называется неоднозначной, если для некоторой цепочки существует хотя бы два дерева вывода.

[править] Левосторонний вывод

Левосторонний вывод — такой вывод, на каждом шаге которого заменяется самый левый нетерминал.

[править] Магазинный автомат

Магазинный автомат — M = (Q, T, Г, D, q0, z0, F)

  • Q — конечное множество состояний
  • T — конечный входной алфавит
  • Г — конечный алфавит магазинных символов
  • D — D: Q × (T ∪ {ε}) × Г → 2Q × Г*
  • q0 ∈ Q — начальное состояние
  • z0 — начальный символ магазина
  • F ⊆ Q — множество конечных состояний

[править] Расширенный магазинный автомат

Отличается от магазинного автомата только областью определения D.

Расширенный магазинный автомат — M = (Q, T, Г, D, q0, z0, F)

  • Q — конечное множество состояний
  • T — конечный входной алфавит
  • Г — конечный алфавит магазинных символов
  • D — D: Q × (T ∪ {ε}) × Г* → 2Q × Г*
  • q0 ∈ Q — начальное состояние
  • z0 — начальный символ магазина
  • F ⊆ Q — множество конечных состояний

[править] Грамматика в нормальной форме Хомского

Грамматика находится в нормальной форме Хомского, если правила вывода имеют вид:

  1. Либо A → BC; A, B, C — нетерминалы.
  2. Либо A → a; a — терминал.
  3. Либо S → ε и в этом случае S не встречается в правых частях правил.

[править] Лемма о разрастании (для контекстно-свободного языка)

Для любого контекстно-свободного языка L ∃ l, k: ∀ α ∈ L, |α| > l, α = uvwxy

  1. |vwx| ≤ k
  2. vx ≠ ε
  3. uviwxiy ∈ L, ∀ i

[править] Недостижимый символ

x — недостижимый символ, если он не входит ни в одну сентенциальную форму.

x — недостижимый символ, если не существует вывода S ⇒* αxβ

[править] Непорождающий символ

x — непорождающий символ, если из него нельзя вывести терминальную цепочку

x — непорождающий символ, если не существует вывода x ⇒* w, w ∈ T*

[править] Бесполезный символ

Бесполезный символнедостижимый или непорождающий символ.

[править] Приведённая грамматика

Грамматика называется приведённой, если она не содержит бесполезных символов.

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

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

  1. {} (пустое множество) — регулярное множество в алфавите T
  2. {a} — регулярное множество в алфавите T для каждого a ∈ T
  3. {ε} — регулярное множество в алфавите T
  4. Если P и Q — регулярные множества в алфавите T, то таковы же и множества
    1. P ∪ Q (объединение)
    2. PQ (конкатенация, то есть множество таких pq, что p ∈ P, q ∈ Q)
    3. P* (итерация: P* = {ε} ∪ P ∪ PP ∪ PPP ∪ …)
  5. Ничто другое не является регулярным множеством в алфавите T

[править] Регулярное выражение

Регулярное выражение — форма записи регулярного множества.

[править] Длина пути от листа к корню

Длиной пути от листа к корню называется число вершин в пути от листа до корня, считая сам лист и сам корень (то есть, <число дуг в пути> + 1)

[править] Высота дерева

Высота дерева — максимальная длина пути (по всем терминальным символам).

[править] Множество FIRST(u)

Если u — любая строка символов грамматики, положим FIRST(u) — множество терминалов, с которых начинаются строки, выводимые из u. Если u ⇒* ε, то ε так же принадлежит FIRST(u).

[править] Множество FOLLOW(A)

Пусть A — нетерминал. Тогда FOLLOW(A) — множество терминалов a, которые могут появиться непосредственно справа от A в некоторой сентенциальной форме, то есть, множество терминалов a таких, что существует вывод вида S ⇒* uAav для некоторых u и v.

[править] Множество FIRST1

FIRST1 — множество всех терминальных символов, с которых может начинаться цепочка терминальных символов, выводимых из цели грамматики или ε, если u ⇒* ε.

Пример:

  • S → aS | A
  • A → b | bSd | bA | ε
  • FIRST1 = {a, b, ε}

[править] Основа сентенциальной формы

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

[править] Множество FIRST(A)

Множество FIRST(A) — множество терминальных символов,которыми начинаются цепочки, выводимые из A в грамматике G = (VT, VN, P, S), то есть, FIRST(A) = {a ∈ VT | A ⇒ aα, A ∈ VN, α ∈ (VT ∪ VN)*}

[править] Множество FOLLOW(A)

Множество FOLLOW(A) — множество терминальных символов, которые следуют за цепочками, выводимыми из A в грамматике G = (VT, VN, P, S), то есть, FOLLOW(A) = {a ∈ VT | S ⇒ αAβ, β → aγ, A ∈ VN, α, β, γ ∈ (VT ∪ VN)*}

[править] Леворекурсивная грамматика

Грамматика называется леворекурсивной, если в ней имеется нетерминал A такой, что существует вывод A ⇒+ Au для некоторой цепочки u.

[править] LL(1) грамматика

Контекстно-свободная грамматика называется LL(1) грамматикой тогда и только тогда, когда выполняются следующие два условия:

  1. Для каждого нетерминала, являющегося левой частью нескольких правил:
    < A > → α1 | α2 | … | αn
    необходимо, чтобы пересечение множеств FIRST(αi) и FIRST(αj) было пусто для всех i ≠ j
  2. Для каждого аннулирующего нетерминала < A > ⇒ *$ необходимо, чтобы пересечение FIRST(A) и FOLLOW(A) было пустым

'Грамматика, для которой таблицы анализа не имеют неоднозначно определённых входов, называются LL(1).

[править] LR грамматика

Грамматика, для которой можно построить таблицу LR разбора, называется LR грамматикой.

[править] Конфигурация LR анализатора

Конфигурация LR анализатора — пара, первая компонента которой —содержимое стека, вторая — непросмотренный вход:
(S0 X1 S1 X2 S2 … Xm Sm, Ai Ai + 1 … An $).
Эта конфигурация соответствует правой сентенциальной форме X1 X2 … Xm Ai Ai + 1 … An.

[править] Атрибутная грамматика

Атрибутной грамматикой называется четвёрка AG = (G, AS, AI, R), где

  • G = (N, T, P, S) — приведённая контекстно-свободная грамматика
  • AS — конечное множество синтезируемых элементов
  • AI — конечное множество наследуемых атрибутов, AS ∩ AI = ∅
  • R — конечное множество семантических правил

[править] Основа сентенциальной формы

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

[править] Пролог подпрограммы

Пролог подпрограммы — инициализация стека для подпрограммы (то есть, это PUSH BP, MOV BP, SP и подобное)

[править] Дисплей

Дисплей — это массив, i-й элемент которого представляет собой указатель на область активации процедуры i-го статического уровня.

[править] Статическая цепочка

Статическая цепочка — список, в который связаны все статические контексты.

[править] Динамическая цепочка

Динамическая цепочка — «база» динамически предыдущей процедуры.


P.S. это скорее объяснение, нежели определение.



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


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 | Алгоритмы решения задач

Личные инструменты
Разделы