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

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

Версия от 22:52, 2 июня 2013; 89.249.162.88 (Обсуждение)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

ПРЕДУПРЕЖДЕНИЕ: Вы редактируете устаревшую версию данной страницы. После сохранения страницы будут потеряны изменения, сделанные в последующих версиях.

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

* Авторы рукописной версии: Синдеев Михаил (оригинал), Комаров Сергей (обработка)

== Цепочка ==
'''Цепочка''' — последовательность символов.

'''Терминальная цепочка''' — последовательность терминальных символов.

== Язык ==
'''Язык''' — множество терминальных цепочек.

== Грамматика ==
'''Грамматика''' — G = (N, T, P, S)
* N — множество нетерминальных символов (напр. A, B, C...)
* T (иногда E) — алфавит терминальных символов (N &cap; T = ∅)
* P — конечное множество правил вывода
** P = {&alpha; &rarr; &beta; | &alpha; &isin; (N &cup; T)+; &beta; &isin; (N &cup; T)*}
* S &isin; N — аксиома (или начальный символ) грамматики

== Сентенциальная форма ==
'''Сентенциальная форма''' — последовательность символов (терминалов и нетерминалов), выводимых из начального символа (аксиомы)

== Язык, порождённый грамматикой ==
'''Язык, порождённый грамматикой''' — L(G) = {W | W &isin; T*, S &rArr;+ 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*),

Из определения следует, что Z0 &supe; Z1 &supe; Z2 &supe; Z3.

Существует теорема, которая доказывает (конструктивно, путём построения соответствующих грамматик), что Z0 &sup; Z1 &sup; Z2 &sup; Z3.

== Машина Тьюринга ==
'''Машина Тьюринга''' — Tm = (Q, Г, &Sigma;, D, q0, F)
* Q — конечное множество состояний
* Г — конечное множество символов (конечный алфавит)
* &Sigma; — входной алфавит - подмножество Г, не включающее пустой символ
* D — правила перехода
** D: (Q\F) &times; Г &rarr; Q &times; Г &times; {L, R} — для детерминированной машины Тьюринга
** D: (Q\F) &times; Г &rarr; 2Q &times; Г &times; {L, R} — для недетерминированной машины Тьюринга
* q0 &isin; Q — начальное состояние
* F &sube; Q — множество конечных состояний

== Универсальная машина Тьюринга ==
'''Универсальная машина Тьюринга''' — такая машина Тьюринга, которая моделирует любую машину Тьюринга.

== Рекурсивно-перечислимый язык ==
'''Язык''' является '''рекурсивно-перечислимым''', если он может быть распознан машиной Тьюринга.
''(доп.)'' '''Язык''' - '''рекурсивно-перечислим''', если имеется процедура, распознающая предложения языка.

== Линейно-ограниченный автомат ==
'''Линейно-ограниченный автомат''' — это машина Тьюринга, которая не может выходить за область входной строки.

== Лемма о разрастании ==
Если язык L — регулярный, то &exist; k: &forall; w &isin; L, |w| &ge; k | w = xyz, 0 < |y|, |xy| &le; k, xyiz &isin; L, &forall; i &ge; 0

== Неоднозначная грамматика ==
'''Грамматика''' называется '''неоднозначной''', если для некоторой цепочки существует хотя бы два дерева вывода.

== Левосторонний вывод ==
'''Левосторонний вывод''' — такой вывод, на каждом шаге которого заменяется самый левый нетерминал.

== Магазинный автомат ==
'''Магазинный автомат''' — M = (Q, T, Г, D, q0, z0, F)
* Q — конечное множество состояний
* T — конечный входной алфавит
* Г — конечный алфавит магазинных символов
* D — D: Q &times; (T &cup; {&epsilon;}) &times; Г &rarr; 2Q &times; Г*
* q0 &isin; Q — начальное состояние
* z0 — начальный символ магазина
* F &sube; Q — множество конечных состояний

== Расширенный магазинный автомат ==

Отличается от магазинного автомата только областью определения D.

'''Расширенный магазинный автомат''' — M = (Q, T, Г, D, q0, z0, F)
* Q — конечное множество состояний
* T — конечный входной алфавит
* Г — конечный алфавит магазинных символов
* D — D: Q &times; (T &cup; {&epsilon;}) &times; Г* &rarr; 2Q &times; Г*
* q0 &isin; Q — начальное состояние
* z0 — начальный символ магазина
* F &sube; Q — множество конечных состояний

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

Грамматика находится '''в нормальной форме Хомского''', если правила вывода имеют вид:
# Либо A &rarr; BC; A, B, C — нетерминалы.
# Либо A &rarr; a; a — терминал.
# Либо S &rarr; &epsilon; и в этом случае S не встречается в правых частях правил.

== Лемма о разрастании (для контекстно-свободного языка) ==
Для любого контекстно-свободного языка L &exist; l, k: &alpha; &isin; L, |&alpha;| &gt; l, &alpha; = uvwxy
# |vwx| &le; k
# vx &ne; &epsilon;
# uviwxiy &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.

== Множество FIRST1 ==
'''FIRST1''' — множество всех терминальных символов, с которых может начинаться цепочка терминальных символов, выводимых из цели грамматики или &epsilon;, если u &rArr;* &epsilon;.

'''Пример:'''
* S &rarr; aS | A
* A &rarr; b | bSd | bA | &epsilon;
* FIRST1 = {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;+ Au для некоторой цепочки u.

== LL(1) грамматика ==
Контекстно-свободная грамматика называется '''LL(1) грамматикой''' тогда и только тогда, когда выполняются следующие два условия:
# Для каждого нетерминала, являющегося левой частью нескольких правил: &lt; A &gt; &rarr; &alpha;1 | &alpha;2 | &hellip; | &alpha;n необходимо, чтобы пересечение множеств FIRST(&alpha;i) и FIRST(&alpha;j) было пусто для всех i &ne; j
# Для каждого аннулирующего нетерминала &lt; A &gt; &rArr; *$ необходимо, чтобы пересечение FIRST(A) и FOLLOW(A) было пустым

'''Грамматика'', для которой таблицы анализа не имеют неоднозначно определённых входов, называются '''LL(1)'''.

== LR грамматика ==
Грамматика, для которой можно построить таблицу LR разбора, называется '''LR грамматикой'''.

== Конфигурация LR анализатора ==
'''Конфигурация LR анализатора''' — пара, первая компонента которой —содержимое стека, вторая — непросмотренный вход: 
(S0 X1 S1 X2 S2 &hellip; Xm Sm, Ai Ai + 1 &hellip; An $). 
Эта конфигурация соответствует правой сентенциальной форме X1 X2 &hellip; Xm Ai Ai + 1 &hellip; An.

== Атрибутная грамматика ==
'''Атрибутной грамматикой''' называется четвёрка AG = (G, AS, AI, R), где
* G = (N, T, P, S) — приведённая контекстно-свободная грамматика
* AS — конечное множество синтезируемых элементов
* AI — конечное множество наследуемых атрибутов, AS &cap; AI = &empty;
* R — конечное множество семантических правил

== Основа сентенциальной формы ==
Подцепочка сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода, называется '''основой цепочки'''.

== Пролог подпрограммы ==
'''Пролог подпрограммы''' — инициализация стека для подпрограммы (то есть, это PUSH BP, MOV BP, SP и подобное)

== Дисплей ==
'''Дисплей''' — это массив, i-й элемент которого представляет собой указатель на область активации процедуры i-го статического уровня.

== Статическая цепочка ==
'''Статическая цепочка''' — список, в который связаны все статические контексты.

== Динамическая цепочка ==
'''Динамическая цепочка''' — «база» динамически предыдущей процедуры.

''P.S.'' это скорее объяснение, нежели определение.

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

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

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