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

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

Перейти к: навигация, поиск

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

Текущая версия Ваш текст
Строка 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 ∩ 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:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!


Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с 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
Личные инструменты
Разделы