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

Конструирование Компиляторов,ОпределенияМатериал из ESyr's Wiki.Авторы рукописной версии: Синдеев Михаил (оригинал), Комаров Сергей(обработка)Обработанная рукописная версия: h p://www.komserg.ru/botva/konstr.rarСодержание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 Высота дереваСтр.

1 из 1026 Множество FIRST(u)27 Множество FOLLOW(A)28 Множество FIRST129 Основа сентенциальной формы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 — аксиома (или начальный символ) грамматикиСентенциальная формаСтр.

2 из 10Сентенциальная форма — последовательность символов (терминалов инетерминалов), выводимых из аксиомыЯзык, порождённый грамматикойЯзык, порождённый грамматикой — 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 — множество конечных состоянийСтр.

3 из 10Универсальная машина ТьюрингаУниверсальная машина Тьюринга — такая машина Тьюринга, которая моделируетлюбую машину Тьюринга.Рекурсивно-перечислимый языкЯзык является рекурсивно-перечислимым, если он может быть распознан машинойТьюринга. (доп.) Язык - рекурсивно-перечислим, если имеется процедура,распознающая предложения языка.Линейно-ограниченный автоматЛинейно-ограниченный автомат — это машина Тьюринга, которая не можетвыходить за область входной строки.Лемма о разрастанииЕсли язык L — регулярный, то ∃ k: ∀ w ∈ L, |w| ≥ k | w = xyz, 0 < |y| ≤ k, xyiz ∈ L, ∀ i ≥0Неоднозначная грамматикаГрамматика называется неоднозначной, если для некоторой цепочки существует хотябы два дерева вывода.Левосторонний выводЛевосторонний вывод — такой вывод, на каждом шаге которого заменяется самыйлевый нетерминал.Магазинный автоматМагазинный автомат — M = (Q, T, Г, D, q0, z0, F)Q — конечное множество состоянийT — конечный входной алфавитГ — конечный алфавит магазинных символовСтр.

4 из 10D — D: Q × (T ∪ {ε}) × Г → 2Q × Г*q0 ∈ Q — начальное состояниеz0 — начальный символ магазинаF ⊆Q — множество конечных состоянийРасширенный магазинный автоматРасширенный магазинный автомат — M = (Q, T, Г, D, q0, z0, F)Q — конечное множество состоянийT — конечный входной алфавитГ — конечный алфавит магазинных символовD — D: Q × (T ∪ {ε}) × Г* → 2Q × Г*q0 ∈ Q — начальное состояниеz0 — начальный символ магазинаF ⊆Q — множество конечных состоянийГрамматика в нормальной форме ХомскогоГрамматика находится в нормальной форме Хомского, если правила вывода имеютвид:A → BC; B, C ∈ NA→aS → ε (если ε ∈ L; S не входит ни в одну правую часть)Лемма о разрастании (для контекстно-свободногоязыка)Для любого контекстно-свободного языка L ∃ l, k: α ∈ L, |α| > l, α = uvwxy1.

|vwx| ≤ k2. vx ≠ ε3. uviwxiy ∈ L, ∀ iНедостижимый символx — недостижимый символ, если он не входит ни в одну сентенциальную форму.Стр. 5 из 10x — недостижимый символ, если не существует вывода S ⇒* αxβНепорождающий символx — непорождающий символ, если из него нельзя вывести терминальную цепочкуx — непорождающий символ, если из не существует вывода x ⇒* w, w ∈ T*Бесполезный символБесполезный символ — недостижимый или непорождающий символ.Приведённая грамматикаГрамматика называется приведённой, если она не содержит бесполезных символов.Регулярное множествоРегулярное множество в алфавите T определяется следующим образом:1.2.3.4.{} (пустое множество) — регулярное множество в алфавите T{a} — регулярное множество в алфавите T для каждого a ∈ T{ε} — регулярное множество в алфавите TЕсли P и Q — регулярные множества в алфавите T, то таковы же и множества1.

P ∪ Q (объединение)2. PQ (конкатенация, то есть множество таких pq, что p ∈ P, q ∈ Q)3. P* (итерация: P* = {ε} ∪ P ∪ PP ∪ PPP ∪ …)5. Ничто друге не является регулярным множеством в алфавите TРегулярное выражениеРегулярное выражение — форма записи регулярного множества.Длина пути от листа к корнюДлиной пути от листа к корню называется число вершин в этом пути, считая сам лист(то есть, <число дуг> + 1)Стр. 6 из 10Высота дереваВысота дерева — максимальная длина пути (по всем терминальным символам).Множество FIRST(u)Если u — любая строка символов грамматики, положим FIRST(u) — множествотерминалов, с которых начинаются строки, выводимые из u. Если u ⇒* ε, то ε так жепринадлежит FIRST(u).Множество FOLLOW(A)Пусть A — нетерминал.

Тогда FOLLOW(A) — множество терминалов a, которые могутпоявиться непосредственно справа от A в некоторой сентенциальной форме, то есть,множество терминалов a таких, что существует вывод вида S ⇒* uAav для некоторыхu и v.Множество FIRST1FIRST1 — множество всех терминальных символов, с которых может начинатьсяцепочка терминальных символов, выводимых из цели грамматики или ε, если u ⇒* ε.Пример:S → aS | AA → 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)*}Стр. 7 из 10Множество 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 > → α 1 | α 2 | … | αnнеобходимо, чтобы пересечение множеств FIRST(αi) и FIRST(αj) было пусто длявсех i ≠ j2. Для каждого аннулирующего нетерминала < 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 .Стр.

8 из 10Атрибутная грамматикаАтрибутной грамматикой называется четвёрка AG = (G, AS, AI, R), гдеG = (N, T, P, S) — приведённая контекстно-свободная грамматикаAS — конечное множество синтезируемых элементовAI — конечное множество наследуемых атрибутов, AS ∩ AI = ∅R — конечное множество семантических правилОснова сентенциальной формыПодцепочка сентенциальной формы, которая может быть сопоставлена правой частинекоторого правила вывода, свертка по которому к левой части правиласоответствует одному шагу в обращении правостороннего вывода, называетсяосновой цепочки.Пролог подпрограммыПролог подпрограммы — инициализация стека для подпрограммы (то есть, это PUSHBP, MOV BP, SP и подобное)ДисплейДисплей — это массив, i-й элемент которого представляет собой указатель на областьактивации процедуры i-го статического уровня.Статическая цепочкаСтатическая цепочка — список, в который связаны все статические контексты.Динамическая цепочкаДинамическая цепочка — «база» динамически предыдущей процедуры.P.S.

это скорее объяснение, нежели определение.Стр. 9 из 10Конструирование Компиляторов01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16Календарьпн пн пн пн пнФевральМарт12 19 2605 12 19 26Апрель 02 09 16 23 30Май07 14 21 28Материалы к экзаменуПроведение экзамена | Определения | Теормин: 2007, 2009 | Алгоритмы решения задачПолучено с h p://esyr.nizm.ru/wiki/%D0%9A%D0%BE%D0%BD%D1%81%D1%82%D1%80%D1%83%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%9A%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D0%BE%D0%B2%2C_%D0%9E%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8FПоследнее изменение этой страницы: 01:23, 29 мая 2009.Стр. 10 из 10.