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

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

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

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