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

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

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

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

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

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

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

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

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

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

Грамматика — 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. это скорее объяснение, нежели определение.