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

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

Версия 22:52, 2 июня 2013 (править) 89.249.162.88 (Обсуждение) (→Лемма о разрастании) ← К предыдущему изменению		Текущая версия (13:45, 28 июня 2013) (править) (отменить) 176.100.246.254 (Обсуждение) (→Лемма о разрастании (для контекстно-свободного языка))
Строка 99:		Строка 99:
	== Лемма о разрастании (для контекстно-свободного языка) ==		== Лемма о разрастании (для контекстно-свободного языка) ==
-	Для любого контекстно-свободного языка L ∃ l, k: α ∈ L, |α| > l, α = uvwxy	+	Для любого контекстно-свободного языка L ∃ l, k: ∀ α ∈ L, |α| > l, α = uvwxy
	# |vwx| ≤ k		# |vwx| ≤ k
	# vx ≠ ε		# vx ≠ ε

---

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

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

Содержание 1 Цепочка 2 Язык 3 Грамматика 4 Сентенциальная форма 5 Язык, порождённый грамматикой 6 Иерархия по Хомскому 7 Машина Тьюринга 8 Универсальная машина Тьюринга 9 Рекурсивно-перечислимый язык 10 Линейно-ограниченный автомат 11 Лемма о разрастании 12 Неоднозначная грамматика 13 Левосторонний вывод 14 Магазинный автомат 15 Расширенный магазинный автомат 16 Грамматика в нормальной форме Хомского 17 Лемма о разрастании (для контекстно-свободного языка) 18 Недостижимый символ 19 Непорождающий символ 20 Бесполезный символ 21 Приведённая грамматика 22 Регулярное множество 23 Регулярное выражение 24 Длина пути от листа к корню 25 Высота дерева 26 Множество FIRST(u) 27 Множество FOLLOW(A) 28 Множество FIRST1 29 Основа сентенциальной формы 30 Множество FIRST(A) 31 Множество FOLLOW(A) 32 Леворекурсивная грамматика 33 LL(1) грамматика 34 LR грамматика 35 Конфигурация LR анализатора 36 Атрибутная грамматика 37 Основа сентенциальной формы 38 Пролог подпрограммы 39 Дисплей 40 Статическая цепочка 41 Динамическая цепочка

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

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

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

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

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

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

Грамматика — 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*),

Из определения следует, что Z₀ ⊇ Z₁ ⊇ Z₂ ⊇ Z₃.

Существует теорема, которая доказывает (конструктивно, путём построения соответствующих грамматик), что Z₀ ⊃ Z₁ ⊃ Z₂ ⊃ Z₃.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Q — конечное множество состояний
• T — конечный входной алфавит
• Г — конечный алфавит магазинных символов
• D — D: Q × (T ∪ {ε}) × Г* → 2^{Q × Г*}
• q₀ ∈ Q — начальное состояние
• z₀ — начальный символ магазина
• 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. uvⁱwxⁱy ∈ 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.

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

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

Пример:

• S → aS | A
• A → b | bSd | bA | ε
• FIRST₁ = {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 > → α₁ | α₂ | … | α_n
   необходимо, чтобы пересечение множеств FIRST(α_i) и FIRST(α_j) было пусто для всех i ≠ j
2. Для каждого аннулирующего нетерминала < A > ⇒ *$ необходимо, чтобы пересечение FIRST(A) и FOLLOW(A) было пустым

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

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

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

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

Конфигурация LR анализатора — пара, первая компонента которой —содержимое стека, вторая — непросмотренный вход:
(S₀ X₁ S₁ X₂ S₂ … X_m S_m, A_i A_{i + 1} … A_n $).
Эта конфигурация соответствует правой сентенциальной форме X₁ X₂ … X_m A_i A_{i + 1} … A_n.

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

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

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

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

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

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

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

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

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

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

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

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

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

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