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

Материал из 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 Множество FIRST₁
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|, |xy| ≤ 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 — множество конечных состояний

[править] Грамматика в нормальной форме Хомского

Грамматика находится в нормальной форме Хомского, если правила вывода имеют вид:

Либо A → BC; A, B, C — нетерминалы.
Либо A → a; a — терминал.
Либо S → ε и в этом случае S не встречается в правых частях правил.

[править] Лемма о разрастании (для контекстно-свободного языка)

Для любого контекстно-свободного языка L ∃ l, k: ∀ α ∈ L, |α| > l, α = uvwxy

|vwx| ≤ k
vx ≠ ε
uvⁱwxⁱy ∈ L, ∀ i

[править] Недостижимый символ

x — недостижимый символ, если он не входит ни в одну сентенциальную форму.

x — недостижимый символ, если не существует вывода S ⇒* αxβ

[править] Непорождающий символ

x — непорождающий символ, если из него нельзя вывести терминальную цепочку

x — непорождающий символ, если не существует вывода x ⇒* w, w ∈ T*

[править] Бесполезный символ

Бесполезный символ — недостижимый или непорождающий символ.

[править] Приведённая грамматика

Грамматика называется приведённой, если она не содержит бесполезных символов.

[править] Регулярное множество

Регулярное множество в алфавите T определяется следующим образом:

{} (пустое множество) — регулярное множество в алфавите 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 ∪ …)
Ничто другое не является регулярным множеством в алфавите 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) грамматикой тогда и только тогда, когда выполняются следующие два условия:

Для каждого нетерминала, являющегося левой частью нескольких правил:
< A > → α₁ | α₂ | … | α_n
необходимо, чтобы пересечение множеств FIRST(α_i) и FIRST(α_j) было пусто для всех i ≠ j
Для каждого аннулирующего нетерминала < 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. это скорее объяснение, нежели определение.

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

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16

Календарь

	пн	пн	пн	пн	пн
Февраль		12	19	26
Март	05	12	19	26
Апрель	02	09	16	23	30
Май		07	14	21	28

Материалы к экзамену
Проведение экзамена | Определения | Теормин: 2007, 2009, 2012 | Алгоритмы решения задач

Получено с http://esyr.org/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

@@ Строка 1: / Строка 1: @@
-== From Ebaums Inc to MurkLoar. ==
+* Авторы рукописной версии: Синдеев Михаил (оригинал), Комаров Сергей (обработка)
-We at EbaumsWorld consider you as disgrace of human race.
-Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated.
+== Цепочка ==
-Dig yourself a grave - you will need it.
+'''Цепочка''' — последовательность символов.
+'''Терминальная цепочка''' — последовательность терминальных символов.
+== Язык ==
+'''Язык''' — множество терминальных цепочек.
+== Грамматика ==
+'''Грамматика''' — G = (N, T, P, S)
+* N — множество нетерминальных символов (напр. A, B, C...)
+* T (иногда E) — алфавит терминальных символов (N &cap; T = ∅)
+* P — конечное множество правил вывода
+** P = {&alpha; &rarr; &beta; | &alpha; &isin; (N &cup; T)<sup>+</sup>; &beta; &isin; (N &cup; T)*}
+* S &isin; N — аксиома (или начальный символ) грамматики
+== Сентенциальная форма ==
+'''Сентенциальная форма''' — последовательность символов (терминалов и нетерминалов), выводимых из начального символа (аксиомы)
+== Язык, порождённый грамматикой ==
+'''Язык, порождённый грамматикой''' — L(G) = {W | W &isin; T*, S &rArr;<sup>+</sup> W}
+'''Язык, порождённый грамматикой''' — множество всех терминальных цепочек, выводимых из аксиомы грамматики
+== Иерархия по Хомскому ==
+* '''0:''' произвольные грамматики
+* '''1:''' неукорачивающие (контекстно-зависимые) грамматики
+** &alpha; &rarr; &beta;, |&alpha;| &le; |&beta;|
+** допускается S &rarr; &epsilon;, если S не входит ни в какую правую часть
+* '''2:''' контекстно-свободные
+** A &rarr; &alpha;, &alpha; &isin; (N &cup; T)*
+* '''3:''' праволинейные (A &rarr; w, A &rarr; wB, w &isin; T*), леволинейные (A &rarr; w, A &rarr; Bw, w &isin; T*),
+Из определения следует, что Z<sub>0</sub> &supe; Z<sub>1</sub> &supe; Z<sub>2</sub> &supe; Z<sub>3</sub>.
+Существует теорема, которая доказывает (конструктивно, путём построения соответствующих грамматик), что Z<sub>0</sub> &sup; Z<sub>1</sub> &sup; Z<sub>2</sub> &sup; Z<sub>3</sub>.
+== Машина Тьюринга ==
+'''Машина Тьюринга''' — T<sub>m</sub> = (Q, Г, &Sigma;, D, q<sub>0</sub>, F)
+* Q — конечное множество состояний
+* Г — конечное множество символов (конечный алфавит)
+* &Sigma; — входной алфавит - подмножество Г, не включающее пустой символ
+* D — правила перехода
+** D: (Q\F) &times; Г &rarr; Q &times; Г &times; {L, R} — для детерминированной машины Тьюринга
+** D: (Q\F) &times; Г &rarr; 2<sup>Q &times; Г &times; {L, R}</sup> — для недетерминированной машины Тьюринга
+* q<sub>0</sub> &isin; Q — начальное состояние
+* F &sube; Q — множество конечных состояний
+== Универсальная машина Тьюринга ==
+'''Универсальная машина Тьюринга''' — такая машина Тьюринга, которая моделирует любую машину Тьюринга.
+== Рекурсивно-перечислимый язык ==
+'''Язык''' является '''рекурсивно-перечислимым''', если он может быть распознан машиной Тьюринга.
+''(доп.)'' '''Язык''' - '''рекурсивно-перечислим''', если имеется процедура, распознающая предложения языка.
+== Линейно-ограниченный автомат ==
+'''Линейно-ограниченный автомат''' — это машина Тьюринга, которая не может выходить за область входной строки.
+== Лемма о разрастании ==
+Если язык L — регулярный, то &exist; k:  &forall; w &isin; L, |w| &ge; k | w = xyz, 0 < |y|, |xy| &le; k, xy<sup>i</sup>z &isin; L, &forall; i &ge; 0
+== Неоднозначная грамматика ==
+'''Грамматика''' называется '''неоднозначной''', если для некоторой цепочки существует хотя бы два дерева вывода.
+== Левосторонний вывод ==
+'''Левосторонний вывод''' — такой вывод, на каждом шаге которого заменяется самый левый нетерминал.
+== Магазинный автомат ==
+'''Магазинный автомат''' — M = (Q, T, Г, D, q<sub>0</sub>, z<sub>0</sub>, F)
+* Q — конечное множество состояний
+* T — конечный входной алфавит
+* Г — конечный алфавит магазинных символов
+* D — D: Q &times; (T &cup; {&epsilon;}) &times; Г &rarr; 2<sup>Q &times; Г*</sup>
+* q<sub>0</sub> &isin; Q — начальное состояние
+* z<sub>0</sub> — начальный символ магазина
+* F &sube; Q — множество конечных состояний
+== Расширенный магазинный автомат ==
+Отличается от магазинного автомата только областью определения D.
+'''Расширенный магазинный автомат''' — M = (Q, T, Г, D, q<sub>0</sub>, z<sub>0</sub>, F)
+* Q — конечное множество состояний
+* T — конечный входной алфавит
+* Г — конечный алфавит магазинных символов
+* D — D: Q &times; (T &cup; {&epsilon;}) &times; Г* &rarr; 2<sup>Q &times; Г*</sup>
+* q<sub>0</sub> &isin; Q — начальное состояние
+* z<sub>0</sub> — начальный символ магазина
+* F &sube; Q — множество конечных состояний
+== Грамматика в нормальной форме Хомского ==
+Грамматика находится '''в нормальной форме Хомского''', если правила вывода имеют вид:
+# Либо A &rarr; BC; A, B, C — нетерминалы.
+# Либо A &rarr; a; a — терминал.
+# Либо S &rarr; &epsilon; и в этом случае S не встречается в правых частях правил.
+== Лемма о разрастании (для контекстно-свободного языка) ==
+Для любого контекстно-свободного языка L &exist; l, k: &forall; &alpha; &isin; L, |&alpha;| &gt; l, &alpha; = uvwxy
+# |vwx| &le; k
+# vx &ne; &epsilon;
+# uv<sup>i</sup>wx<sup>i</sup>y &isin; L, &forall; i
+== Недостижимый символ ==
+x — '''недостижимый символ''', если он не входит ни в одну [[#Сентенциальная форма|сентенциальную форму]].
+x — '''недостижимый символ''', если не существует вывода S &rArr;* &alpha;x&beta;
+== Непорождающий символ ==
+x — '''непорождающий символ''', если из него нельзя вывести терминальную цепочку
+x — '''непорождающий символ''', если не существует вывода x &rArr;* w, w &isin; T*
+== Бесполезный символ ==
+'''Бесполезный символ''' — [[#Недостижимый символ|недостижимый]] или [[#Непорождающий символ|непорождающий символ]].
+== Приведённая грамматика ==
+'''Грамматика''' называется '''приведённой''', если она не содержит [[#Бесполезный символ|бесполезных символов]].
+== Регулярное множество ==
+'''Регулярное множество''' в алфавите T определяется следующим образом:
+# {} (пустое множество) — регулярное множество в алфавите T
+# {a} — регулярное множество в алфавите T для каждого a &isin; T
+# {&epsilon;} — регулярное множество в алфавите T
+# Если P и Q — регулярные множества в алфавите T, то таковы же и множества
+## P &cup; Q (объединение)
+## PQ (конкатенация, то есть множество таких pq, что p &isin; P, q &isin; Q)
+## P* (итерация: P* = {&epsilon;} &cup; P &cup; PP &cup; PPP &cup; &hellip;)
+# Ничто другое не является регулярным множеством в алфавите T
+== Регулярное выражение ==
+'''Регулярное выражение''' — форма записи [[#Регулярное монжество|регулярного множества]].
+== Длина пути от листа к корню ==
+'''Длиной пути от листа к корню''' называется число вершин в пути от листа до корня, считая сам лист и сам корень (то есть, &lt;число&nbsp;дуг в пути&gt; + 1)
+== Высота дерева ==
+'''Высота дерева''' — максимальная длина пути (по всем терминальным символам).
+== Множество FIRST(u) ==
+Если u — любая строка символов грамматики, положим '''FIRST(u)''' — множество терминалов, с которых начинаются строки, выводимые из u. Если u &rArr;* &epsilon;, то &epsilon; так же принадлежит FIRST(u).
+== Множество FOLLOW(A) ==
+Пусть A — нетерминал. Тогда '''FOLLOW(A)''' — множество терминалов a, которые могут появиться непосредственно справа от A в некоторой [[#Сентенциальная форма|сентенциальной форме]], то есть, множество терминалов a таких, что существует вывод вида S &rArr;* uAav для некоторых u и v.
+== Множество FIRST<sub>1</sub> ==
+'''FIRST<sub>1</sub>''' — множество всех терминальных символов, с которых может начинаться цепочка терминальных символов, выводимых из цели грамматики или &epsilon;, если u &rArr;* &epsilon;.
+'''Пример:'''
+* S &rarr; aS | A
+* A &rarr; b | bSd | bA | &epsilon;
+* FIRST<sub>1</sub> = {a, b, &epsilon;}
+== Основа сентенциальной формы ==
+'''Основа сентенциальной формы''' — позиция в сентенциальной форме, которая заменена в следующей сентенциальной форме.
+== Множество FIRST(A) ==
+'''Множество FIRST(A)''' — множество терминальных символов,которыми начинаются цепочки, выводимые из A в грамматике G = (VT, VN, P, S), то есть, FIRST(A) = {a &isin; VT | A &rArr; a&alpha;, A &isin; VN, &alpha; &isin; (VT &cup; VN)*}
+== Множество FOLLOW(A) ==
+'''Множество FOLLOW(A)''' — множество терминальных символов, которые следуют за цепочками, выводимыми из A в грамматике G = (VT, VN, P, S), то есть, FOLLOW(A) = {a &isin; VT | S &rArr; &alpha;A&beta;, &beta; &rarr; a&gamma;, A &isin; VN, &alpha;, &beta;, &gamma; &isin; (VT &cup; VN)*}
+== Леворекурсивная грамматика ==
+'''Грамматика''' называется '''леворекурсивной''', если в ней имеется нетерминал A такой, что существует вывод A &rArr;<sup>+</sup> Au для некоторой цепочки u.
+== LL(1) грамматика ==
+Контекстно-свободная грамматика называется '''LL(1) грамматикой''' тогда и только тогда, когда выполняются следующие два условия:
+# Для каждого нетерминала, являющегося левой частью нескольких правил:<br />&lt; A &gt; &rarr; &alpha;<sub>1</sub> | &alpha;<sub>2</sub> | &hellip; | &alpha;<sub>n</sub><br />необходимо, чтобы пересечение множеств FIRST(&alpha;<sub>i</sub>) и FIRST(&alpha;<sub>j</sub>) было пусто для всех i &ne; j
+# Для каждого аннулирующего нетерминала &lt; A &gt; &rArr; *$ необходимо, чтобы пересечение FIRST(A) и FOLLOW(A) было пустым
+'''Грамматика'', для которой таблицы анализа не имеют неоднозначно определённых входов, называются '''LL(1)'''.
+== LR грамматика ==
+Грамматика, для которой можно построить таблицу LR разбора, называется '''LR грамматикой'''.
+== Конфигурация LR анализатора ==
+'''Конфигурация LR анализатора''' — пара, первая компонента которой —содержимое стека, вторая — непросмотренный вход:<br />
+(S<sub>0</sub> X<sub>1</sub> S<sub>1</sub> X<sub>2</sub> S<sub>2</sub> &hellip; X<sub>m</sub> S<sub>m</sub>, A<sub>i</sub> A<sub>i + 1</sub> &hellip; A<sub>n</sub> $).<br />
+Эта конфигурация соответствует правой сентенциальной форме X<sub>1</sub> X<sub>2</sub>  &hellip; X<sub>m</sub> A<sub>i</sub> A<sub>i + 1</sub> &hellip; A<sub>n</sub>.
+== Атрибутная грамматика ==
+'''Атрибутной грамматикой''' называется четвёрка AG = (G, A<sub>S</sub>, A<sub>I</sub>, R), где
+* G = (N, T, P, S) — приведённая контекстно-свободная грамматика
+* A<sub>S</sub> — конечное множество синтезируемых элементов
+* A<sub>I</sub> — конечное множество наследуемых атрибутов, A<sub>S</sub> &cap; A<sub>I</sub> = &empty;
+* R — конечное множество семантических правил
+== Основа сентенциальной формы ==
+Подцепочка сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода, называется '''основой цепочки'''.
+== Пролог подпрограммы ==
+'''Пролог подпрограммы''' — инициализация стека для подпрограммы (то есть, это PUSH BP, MOV BP, SP и подобное)
+== Дисплей ==
+'''Дисплей''' — это массив, i-й элемент которого представляет собой указатель на область активации процедуры i-го статического уровня.
+== Статическая цепочка ==
+'''Статическая цепочка''' — список, в который связаны все статические контексты.
+== Динамическая цепочка ==
+'''Динамическая цепочка''' — «база» динамически предыдущей процедуры.
+''P.S.'' это скорее объяснение, нежели определение.
+{{Курс Конструирование Компиляторов}}

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

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

Текущая версия

Содержание

[править] Цепочка

[править] Язык

[править] Грамматика

[править] Сентенциальная форма

[править] Язык, порождённый грамматикой

[править] Иерархия по Хомскому

[править] Машина Тьюринга

[править] Универсальная машина Тьюринга

[править] Рекурсивно-перечислимый язык

[править] Линейно-ограниченный автомат

[править] Лемма о разрастании

[править] Неоднозначная грамматика

[править] Левосторонний вывод

[править] Магазинный автомат

[править] Расширенный магазинный автомат

[править] Грамматика в нормальной форме Хомского

[править] Лемма о разрастании (для контекстно-свободного языка)

[править] Недостижимый символ

[править] Непорождающий символ

[править] Бесполезный символ

[править] Приведённая грамматика

[править] Регулярное множество

[править] Регулярное выражение

[править] Длина пути от листа к корню

[править] Высота дерева

[править] Множество FIRST(u)

[править] Множество FOLLOW(A)

[править] Множество FIRST1

[править] Основа сентенциальной формы

[править] Множество FIRST(A)

[править] Множество FOLLOW(A)

[править] Леворекурсивная грамматика

[править] LL(1) грамматика

[править] LR грамматика

[править] Конфигурация LR анализатора

[править] Атрибутная грамматика

[править] Основа сентенциальной формы

[править] Пролог подпрограммы

[править] Дисплей

[править] Статическая цепочка

[править] Динамическая цепочка

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

[править] Множество FIRST₁