Конструирование Компиляторов, Определения
Материал из eSyr's wiki.
(→Лемма о разрастании) |
(→Лемма о разрастании (для контекстно-свободного языка)) |
||
| (16 промежуточных версий не показаны.) | |||
| Строка 1: | Строка 1: | ||
* Авторы рукописной версии: Синдеев Михаил (оригинал), Комаров Сергей (обработка) | * Авторы рукописной версии: Синдеев Михаил (оригинал), Комаров Сергей (обработка) | ||
| - | + | ||
| + | == Цепочка == | ||
| + | '''Цепочка''' — последовательность символов. | ||
| + | |||
| + | '''Терминальная цепочка''' — последовательность терминальных символов. | ||
== Язык == | == Язык == | ||
| - | '''Язык''' — множество цепочек. | + | '''Язык''' — множество терминальных цепочек. |
== Грамматика == | == Грамматика == | ||
'''Грамматика''' — 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) | + | ** P = {α → β | α ∈ (N ∪ T)<sup>+</sup>; β ∈ (N ∪ T)*} |
| - | * S ∈ N — аксиома | + | * S ∈ N — аксиома (или начальный символ) грамматики |
== Сентенциальная форма == | == Сентенциальная форма == | ||
| - | '''Сентенциальная форма''' — последовательность символов (терминалов и нетерминалов), выводимых из аксиомы | + | '''Сентенциальная форма''' — последовательность символов (терминалов и нетерминалов), выводимых из начального символа (аксиомы) |
== Язык, порождённый грамматикой == | == Язык, порождённый грамматикой == | ||
| Строка 22: | Строка 26: | ||
== Иерархия по Хомскому == | == Иерархия по Хомскому == | ||
| - | * 0: произвольные грамматики | + | * '''0:''' произвольные грамматики |
| - | * 1: неукорачивающие (контекстно-зависимые) грамматики | + | * '''1:''' неукорачивающие (контекстно-зависимые) грамматики |
** α → β, |α| ≤ |β| | ** α → β, |α| ≤ |β| | ||
** допускается S → ε, если S не входит ни в какую правую часть | ** допускается S → ε, если S не входит ни в какую правую часть | ||
| - | * 2: контекстно-свободные | + | * '''2:''' контекстно-свободные |
** A → α, α ∈ (N ∪ T)* | ** A → α, α ∈ (N ∪ T)* | ||
| - | * 3: праволинейные (A → w, A → wB, w ∈ T*), леволинейные (A → w, A → Bw, w ∈ T*), | + | * '''3:''' праволинейные (A → w, A → wB, w ∈ T*), леволинейные (A → w, A → Bw, w ∈ T*), |
Из определения следует, что Z<sub>0</sub> ⊇ Z<sub>1</sub> ⊇ Z<sub>2</sub> ⊇ Z<sub>3</sub>. | Из определения следует, что Z<sub>0</sub> ⊇ Z<sub>1</sub> ⊇ Z<sub>2</sub> ⊇ Z<sub>3</sub>. | ||
| - | Существует теорема, которая доказывает, что Z<sub>0</sub> ⊃ Z<sub>1</sub> ⊃ Z<sub>2</sub> ⊃ Z<sub>3</sub>. | + | Существует теорема, которая доказывает (конструктивно, путём построения соответствующих грамматик), что Z<sub>0</sub> ⊃ Z<sub>1</sub> ⊃ Z<sub>2</sub> ⊃ Z<sub>3</sub>. |
== Машина Тьюринга == | == Машина Тьюринга == | ||
| Строка 38: | Строка 42: | ||
* Q — конечное множество состояний | * Q — конечное множество состояний | ||
* Г — конечное множество символов (конечный алфавит) | * Г — конечное множество символов (конечный алфавит) | ||
| - | * Σ — входной алфавит | + | * Σ — входной алфавит - подмножество Г, не включающее пустой символ |
* D — правила перехода | * D — правила перехода | ||
** D: (Q\F) × Г → Q × Г × {L, R} — для детерминированной машины Тьюринга | ** D: (Q\F) × Г → Q × Г × {L, R} — для детерминированной машины Тьюринга | ||
| Строка 50: | Строка 54: | ||
== Рекурсивно-перечислимый язык == | == Рекурсивно-перечислимый язык == | ||
'''Язык''' является '''рекурсивно-перечислимым''', если он может быть распознан машиной Тьюринга. | '''Язык''' является '''рекурсивно-перечислимым''', если он может быть распознан машиной Тьюринга. | ||
| + | ''(доп.)'' '''Язык''' - '''рекурсивно-перечислим''', если имеется процедура, распознающая предложения языка. | ||
== Линейно-ограниченный автомат == | == Линейно-ограниченный автомат == | ||
| Строка 55: | Строка 60: | ||
== Лемма о разрастании == | == Лемма о разрастании == | ||
| - | Если язык L — регулярный, то ∃ k: ∀ w ∈ L, |w| ≥ k | w = xyz, 0 | + | Если язык L — регулярный, то ∃ k: ∀ w ∈ L, |w| ≥ k | w = xyz, 0 < |y|, |xy| ≤ k, xy<sup>i</sup>z ∈ L, ∀ i ≥ 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 → BC; A, B, C — нетерминалы. | |
| - | + | # Либо A → a; a — терминал. | |
| + | # Либо S → ε и в этом случае S не встречается в правых частях правил. | ||
== Лемма о разрастании (для контекстно-свободного языка) == | == Лемма о разрастании (для контекстно-свободного языка) == | ||
| - | Для любого контекстно-свободного языка L ∃ l, k: α ∈ L, |α| > l, α = uvwxy | + | Для любого контекстно-свободного языка L ∃ l, k: ∀ α ∈ L, |α| > l, α = uvwxy |
# |vwx| ≤ k | # |vwx| ≤ k | ||
# vx ≠ ε | # vx ≠ ε | ||
| Строка 103: | Строка 112: | ||
x — '''непорождающий символ''', если из него нельзя вывести терминальную цепочку | x — '''непорождающий символ''', если из него нельзя вывести терминальную цепочку | ||
| - | x — '''непорождающий символ''', если | + | x — '''непорождающий символ''', если не существует вывода x ⇒* w, w ∈ T* |
== Бесполезный символ == | == Бесполезный символ == | ||
| Строка 120: | Строка 129: | ||
## PQ (конкатенация, то есть множество таких pq, что p ∈ P, q ∈ Q) | ## PQ (конкатенация, то есть множество таких pq, что p ∈ P, q ∈ Q) | ||
## P* (итерация: P* = {ε} ∪ P ∪ PP ∪ PPP ∪ …) | ## P* (итерация: P* = {ε} ∪ P ∪ PP ∪ PPP ∪ …) | ||
| - | # Ничто | + | # Ничто другое не является регулярным множеством в алфавите T |
== Регулярное выражение == | == Регулярное выражение == | ||
| Строка 126: | Строка 135: | ||
== Длина пути от листа к корню == | == Длина пути от листа к корню == | ||
| - | '''Длиной пути от листа к корню''' называется число вершин в | + | '''Длиной пути от листа к корню''' называется число вершин в пути от листа до корня, считая сам лист и сам корень (то есть, <число дуг в пути> + 1) |
== Высота дерева == | == Высота дерева == | ||
| Строка 155: | Строка 164: | ||
== Леворекурсивная грамматика == | == Леворекурсивная грамматика == | ||
| - | '''Грамматика''' называется '''леворекурсивной''', если в ней имеется нетерминал A такой, что существует вывод A ⇒ Au для некоторой | + | '''Грамматика''' называется '''леворекурсивной''', если в ней имеется нетерминал A такой, что существует вывод A ⇒<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 — множество конечных состояний
[править] Грамматика в нормальной форме Хомского
Грамматика находится в нормальной форме Хомского, если правила вывода имеют вид:
- Либо A → BC; A, B, C — нетерминалы.
- Либо A → a; a — терминал.
- Либо S → ε и в этом случае S не встречается в правых частях правил.
[править] Лемма о разрастании (для контекстно-свободного языка)
Для любого контекстно-свободного языка L ∃ l, k: ∀ α ∈ L, |α| > l, α = uvwxy
- |vwx| ≤ k
- vx ≠ ε
- uviwxiy ∈ L, ∀ i
[править] Недостижимый символ
x — недостижимый символ, если он не входит ни в одну сентенциальную форму.
x — недостижимый символ, если не существует вывода S ⇒* αxβ
[править] Непорождающий символ
x — непорождающий символ, если из него нельзя вывести терминальную цепочку
x — непорождающий символ, если не существует вывода x ⇒* w, w ∈ T*
[править] Бесполезный символ
Бесполезный символ — недостижимый или непорождающий символ.
[править] Приведённая грамматика
Грамматика называется приведённой, если она не содержит бесполезных символов.
[править] Регулярное множество
Регулярное множество в алфавите T определяется следующим образом:
- {} (пустое множество) — регулярное множество в алфавите T
- {a} — регулярное множество в алфавите T для каждого a ∈ T
- {ε} — регулярное множество в алфавите T
- Если P и Q — регулярные множества в алфавите T, то таковы же и множества
- P ∪ Q (объединение)
- PQ (конкатенация, то есть множество таких pq, что p ∈ P, q ∈ Q)
- P* (итерация: P* = {ε} ∪ P ∪ PP ∪ PPP ∪ …)
- Ничто другое не является регулярным множеством в алфавите 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) грамматикой тогда и только тогда, когда выполняются следующие два условия:
- Для каждого нетерминала, являющегося левой частью нескольких правил:
< A > → α1 | α2 | … | αn
необходимо, чтобы пересечение множеств FIRST(αi) и FIRST(αj) было пусто для всех i ≠ j - Для каждого аннулирующего нетерминала < 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. это скорее объяснение, нежели определение.
