Редактирование: Конструирование Компиляторов, Определения
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 1: | Строка 1: | ||
* Авторы рукописной версии: Синдеев Михаил (оригинал), Комаров Сергей (обработка) | * Авторы рукописной версии: Синдеев Михаил (оригинал), Комаров Сергей (обработка) | ||
| + | * Обработанная рукописная версия: http://www.komserg.ru/botva/konstr.rar | ||
== Цепочка == | == Цепочка == | ||
| Строка 12: | Строка 13: | ||
'''Грамматика''' — G = (N, T, P, S) | '''Грамматика''' — G = (N, T, P, S) | ||
* N — множество нетерминальных символов (напр. A, B, C...) | * N — множество нетерминальных символов (напр. A, B, C...) | ||
| - | * T (иногда E) — алфавит терминальных символов (N & | + | * T (иногда E) — алфавит терминальных символов (N ∪ T = ∅) |
* P — конечное множество правил вывода | * P — конечное множество правил вывода | ||
** P = {α → β | α ∈ (N ∪ T)<sup>+</sup>; β ∈ (N ∪ T)*} | ** P = {α → β | α ∈ (N ∪ T)<sup>+</sup>; β ∈ (N ∪ T)*} | ||
| Строка 18: | Строка 19: | ||
== Сентенциальная форма == | == Сентенциальная форма == | ||
| - | '''Сентенциальная форма''' — последовательность символов (терминалов и нетерминалов), выводимых из | + | '''Сентенциальная форма''' — последовательность символов (терминалов и нетерминалов), выводимых из аксиомы |
== Язык, порождённый грамматикой == | == Язык, порождённый грамматикой == | ||
| Строка 26: | Строка 27: | ||
== Иерархия по Хомскому == | == Иерархия по Хомскому == | ||
| - | * | + | * 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>. |
== Машина Тьюринга == | == Машина Тьюринга == | ||
| Строка 60: | Строка 61: | ||
== Лемма о разрастании == | == Лемма о разрастании == | ||
| - | Если язык L — регулярный, то ∃ k: ∀ w ∈ L, |w| ≥ k | w = xyz, 0 < |y | + | Если язык L — регулярный, то ∃ k: ∀ w ∈ L, |w| ≥ k | w = xyz, 0 < |y| ≤ k, xy<sup>i</sup>z ∈ L, ∀ i ≥ 0 |
== Неоднозначная грамматика == | == Неоднозначная грамматика == | ||
| Строка 79: | Строка 80: | ||
== Расширенный магазинный автомат == | == Расширенный магазинный автомат == | ||
| - | |||
| - | Отличается от магазинного автомата только областью определения 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: | Строка 90: | ||
== Грамматика в нормальной форме Хомского == | == Грамматика в нормальной форме Хомского == | ||
| - | + | '''Грамматика''' находится '''в нормальной форме Хомского''', если правила вывода имеют вид: | |
| - | Грамматика находится '''в нормальной форме Хомского''', если правила вывода имеют вид: | + | * 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: | Строка 109: | ||
x — '''непорождающий символ''', если из него нельзя вывести терминальную цепочку | x — '''непорождающий символ''', если из него нельзя вывести терминальную цепочку | ||
| - | x — '''непорождающий символ''', если не существует вывода x ⇒* w, w ∈ T* | + | x — '''непорождающий символ''', если из не существует вывода x ⇒* w, w ∈ T* |
== Бесполезный символ == | == Бесполезный символ == | ||
| Строка 129: | Строка 126: | ||
## PQ (конкатенация, то есть множество таких pq, что p ∈ P, q ∈ Q) | ## PQ (конкатенация, то есть множество таких pq, что p ∈ P, q ∈ Q) | ||
## P* (итерация: P* = {ε} ∪ P ∪ PP ∪ PPP ∪ …) | ## P* (итерация: P* = {ε} ∪ P ∪ PP ∪ PPP ∪ …) | ||
| - | # Ничто | + | # Ничто друге не является регулярным множеством в алфавите T |
== Регулярное выражение == | == Регулярное выражение == | ||
| Строка 135: | Строка 132: | ||
== Длина пути от листа к корню == | == Длина пути от листа к корню == | ||
| - | '''Длиной пути от листа к корню''' называется число вершин в пути | + | '''Длиной пути от листа к корню''' называется число вершин в этом пути, считая сам лист (то есть, <число дуг> + 1) |
== Высота дерева == | == Высота дерева == | ||
