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