Редактирование: Конструирование Компиляторов, Теоретический минимум (2012)

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

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

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

''см. также [[Конструирование Компиляторов, Теоретический минимум|ответы на вопросы теоретического минимума 2007 года]], [[Конструирование Компиляторов, Теоретический минимум (2009)|ответы на вопросы теоретического минимума 2009 года]], [[Конструирование Компиляторов, Определения|список определений]].''
== Алфавит ==

Алфавит - конечное множество символов

== Определение грамматики ==
Грамматика <math>~G = (N,T,P,S)</math> - четверка множеств, где
* <math>~N</math> - алфавит нетерминальных символов 
* <math>~T</math> - алфавит терминальных символов, <math>N \cap T = \varnothing</math>;
* <math>~P</math> - множество правил вида <math>\alpha \rarr \beta</math>, где <math> \alpha \in ( N \cup T)^*N(N \cup T)^*, \beta \in (N \cup T)^*</math>
* <math>S \in N</math> - начальный символ или аксиома грамматики

== Определение грамматик типа 0 по Хомскому ==
Если на грамматику <math>~G = (N, T, P, S)</math> не накладываются никакие ограничения, то её называют грамматикой типа 0, или грамматикой без ограничений.

== Определение грамматик типа 1 (неукорачивающих) по Хомскому ==
Если
# Каждое правило грамматики, кроме <math>S \rarr \epsilon </math> , имеет вид <math>\alpha \rarr \beta, |\alpha| \le |\beta|</math> 
# В том случае, когда <math>S \rarr \epsilon \in P</math>, символ <math>~S</math> не встречается в правых частях правил
то грамматику называют грамматикой типа 1, или неукорачивающей.

== Грамматика типа 2 (Контекстно-свободная, КС) по Хомскому ==

Грамматика типа 2 (Контекстно-свободная, КС) - грамматика, где каждое правило <math>p \in P</math> имеет вид <math>A \rarr \alpha</math>, где <math> A \in N, \alpha \in (N \cup T)^*</math>

== Грамматика типа 3 (Праволинейная) по Хомскому ==

Грамматика типа 3 (Праволинейная) - грамматика, где <math> \forall p \in P </math> имеет вид либо <math> A \rarr xB </math>, либо <math> A \rarr x </math>, где <math> A,B \in N, x \in T^* </math>

== Определение регулярного множества ==

'''Регулярное множество''' в алфавите T определяется следующим образом:
* <math> \varnothing </math> — регулярное множество в алфавите T
* <math> ~\{a\} </math> — регулярное множество в алфавите T для каждого a &isin; T
* <math> ~\{\epsilon\} </math> — регулярное множество в алфавите T
* Если P и Q — регулярные множества в алфавите T, то регулярны множества
** <math>~P \cup Q</math> (объединение)
** <math>~PQ</math> (конкатенация, <math>\{ pq | p \in P, q \in Q\}</math>)
** <math>~P^*</math> (итерация: <math>P^* = \{\epsilon\} \cup P \cup PP \cup PPP \cup ...)</math>
* Ничто другое не является регулярным множеством в алфавите T

==  Определение регулярного выражения ==
'''Регулярное выражение''' — форма записи [[Конструирование Компиляторов, Определения#Регулярное монжество|регулярного множества]].

Регулярное выражение и обозначаемое им регулярное множество определяются следующим образом:
* <math> ~\varnothing </math> — обозначает множество <math> \varnothing </math>
* <math> ~\epsilon </math> — обозначает множество <math>~\{ \epsilon \}</math>
* <math>~a</math> — обозначает множество <math>~\{ a \}</math>
* Если регулярные выражения ''p'' и ''q'' обозначают множества ''P'' и ''Q'' соответственно, то:
** <math>~(p|q)</math> обозначает <math>~P \cup Q</math>
** <math>~(pq)</math> обозначает <math>~PQ</math>
** <math>~(p^*)</math> обозначает <math>~P^*</math>
* Ничто другое не является регулярным выражением в данном алфавите

== Определение праволинейной грамматики ==
Праволинейная грамматика или грамматика типа 3 по Хомскому — грамматика вида A &rarr; w, A &rarr; wB, w &isin; T*.

== Определение недетерминированного конечного автомата ==
'''Недетерминированный конечный автомат''' - M = (Q, &Sigma;, D, q0, F)
* Q — конечное непустое множество состояний
* &Sigma; — входной алфавит
* D — правила перехода
** Q &times; ( &Sigma; &cup; {&epsilon;} ) &rarr; 2Q
* q0 &isin; Q — начальное состояние
* F &sube; Q — множество конечных состояний

== Определение детерминированного конечного автомата ==
'''Детерминированный конечный автомат''' - M = (Q, &Sigma;, D, q0, F)
* Q — конечное непустое множество состояний
* &Sigma; — конечный входной алфавит
* D — правила перехода
** Q &times; &Sigma; &rarr; Q
* q0 &isin; Q — начальное состояние
* F &sube; Q — множество конечных состояний

== Объяснить разницу между недетерминированным и  детерминированным конечным автоматом ==
Недетерминированный конечный автомат является обобщением детерминированного. Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными).
В детерменированном автомате из одного состояния допускается не более одного перехода для каждого символа алфавита, в недетерменированном - произвольное количество. Кроме того, в НКА возможны эпсилон-переходы.

== Определение конфигурации конечного автомата ==
Пусть ''M'' = (''Q'', ''T'', ''D'', ''q''0, ''F'') — НКА. Конфигурацией автомата ''M'' называется пара (''q'', &omega;)&nbsp;&isin;&nbsp;''Q''&nbsp;&times;&nbsp;''T''*, где ''q''&nbsp;— текущее состояние управляющего устройства, а &omega;&nbsp;— цепочка символов на входной ленте, состоящая из символов под головкой и всех символов справа от неё.

== Определение языка, допускаемого конечным автоматом ==
Автомат ''M'' допускает цепочку &omega;, если (''q''0, &omega;)&nbsp;⊦*&nbsp;(''q'',&nbsp;&epsilon;) для некоторого ''q''&nbsp;&isin;&nbsp;''F''. Языком, допускаемым автоматом ''M'', называется множество входных цепочек,допускаемых автоматом ''M''. То есть:
* ''L(M)'' = {&omega; | &omega; &isin; ''T''* и (''q''0, &omega;)&nbsp;⊦*&nbsp;(''q'',&nbsp;&epsilon;)'' для некоторого ''q''&nbsp;&isin;&nbsp;''F''}

== Определение &epsilon;-замыкания для подмножества состояний НКА ==
&epsilon;-замыкание множества состояний ''R'', ''R''&nbsp;&sube;&nbsp;''Q''&nbsp;— множество состояний НКА, достижимых из состояний, входящих в ''R'', посредством только переходов по &epsilon;, то есть множество 
* S&nbsp;=&nbsp;⋃q&nbsp;&isin;&nbsp;R&nbsp;{p&nbsp;| (q,&nbsp;&epsilon;)&nbsp;⊦*&nbsp;(p,&nbsp;&epsilon;)}

== Определение расширенной функции переходов для КА ==

Расширенная функция переходов множества состояний ''R'', ''R''&nbsp;&sube;&nbsp;''Q'' по ''a''&nbsp;— множество состояний НКА, в которые есть переход на входе ''a'' для состояний из ''R'', то есть множество 
* S&nbsp;=&nbsp;⋃q&nbsp;&isin;&nbsp;R&nbsp;{p&nbsp;| p&nbsp;&isin;&nbsp;D(q,&nbsp;a)}

== Определение расширенной функции переходов для НКА ==
== Определение расширенной функции переходов для ДКА ==

== Определение функции firstpos для поддерева в дереве регулярного выражения ==
Функция ''firstpos(n)'' для каждого узла ''n'' узла синтаксического дерева регулярных выражений даёт множество позиций, которые соответствуют первым символам в цепочках, генерируемых подвыражением с вершиной ''n''. Построение:
{|
 !узел ''n''
 !''firstpos(n)''
 |-
 |&epsilon;
 |&empty;
 |-
 |''i''&nbsp;&ne;&nbsp;&epsilon;
 |{''i''}
 |-
 |u &#124; v
 |''firstpos''(''u'')&nbsp;&cup;&nbsp;''firstpos''(''v'')
 |-
 |u . v
 |if ''nullable''(''u'') then ''firstpos''(''u'')&nbsp;&cup;&nbsp;''firstpos''(''v'') else ''firstpos''(''u'')
 |-
 |v*
 |''firstpos''(''v'')
 |}

== Определение функции lastpos для поддерева в дереве регулярного выражения ==
Функция ''lastpos(n)'' для каждого узла ''n'' узла синтаксического дерева регулярных выражений даёт множество позиций, которым соответствуют последние символы в цепочках, генерируемых подвыражениями с вершиной ''n''.
Построение ''lastpos''(''n''):
{|
 !узел ''n''
 !''lastpos(n)''
 |-
 |&epsilon;
 |&empty;
 |-
 |''i''&nbsp;&ne;&nbsp;&epsilon;
 |{''i''}
 |-
 |u &#124; v
 |''lastpos''(''u'')&nbsp;&cup;&nbsp;''lastpos''(''v'')
 |-
 |u . v
 |if ''nullable''(''v'') then ''lastpos''(''u'')&nbsp;&cup;&nbsp;''lastpos''(''v'') else ''lastpos''(''v'')
 |-
 |v*
 |''lastpos''(''v'')
 |}

== Определение функции followpos для позиций в дереве регулярного выражения ==
Функция ''followpos(i)'' для позиции ''i'' есть множество позиций ''j'' таких, что существует некоторая строка ''&hellip;cd&hellip;'', входящая в язык, описываемый регулярным выражением, такая, что позиция ''i'' соответствует вхождению ''c'', а позиция ''j''&nbsp;— вхождению ''d''.

== Сформулировать соотношение между регулярными множествами и языками, допускаемыми КА ==
Любой конечный автомат распознает регулярное множество цепочек символов входного алфавита.
Верно и обратное&nbsp;— для любого регулярного языка можно построить распознающий его конечный автомат.

== Определение регулярной грамматики ==
Регулярные грамматики — праволинейные (A &rarr; w, A &rarr; wB, w &isin; T*), леволинейные (A &rarr; w, A &rarr; Bw, w &isin; T*).

== Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками и языками, допускаемыми КА ==
Для любой праволинейной грамматики существует конечный автомат, проверяющий порождаемый грамматикой язык. Для любого конечного автомата существует праволинейная грамматика, порождающая проверяемый конечным автоматом язык.

== Определение эквивалентных состояний ДКА ==
Два состояния <math>q_i</math> и <math>q_j</math> называются эквивалентными (<math>q_i</math> ~ <math>q_j</math>), если <math>\forall z\in</math> T* верно, что <math>D(q_i, z)\in F \Leftrightarrow D(q_j, z)\in F</math>

== Определение различимых состояний ДКА ==
Два состояния <math>q_i</math> и <math>q_j</math> называются различимыми, если они не эквивалентны.

== Определение контекстно-свободной грамматики без &epsilon;-правил ==
* A &rarr; &alpha;, &alpha; &isin; (N &cup; T)+
* допускается S &rarr; &epsilon;, если S не входит ни в какую правую часть

== Определение контекстно-свободной грамматики ==
A &rarr; &alpha;, &alpha; &isin; (N &cup; T)*

== Определение выводимости в грамматике ==
Определим на множестве (''N'' &cup; ''T'')* грамматики ''G'' = (''N'', ''T'', ''P'', ''S'') бинарное отношение выводимости «&rArr;» следующим образом: если ''&delta;'' &rarr; ''&gamma;'' &isin; ''P'', то ''&alpha;&delta;&beta;'' &rArr; ''&alpha;&gamma;&beta;'' для всех ''&alpha;'', ''&beta;'' &isin; (''N'' &cup; ''T'')*. Если ''&alpha;''1 &rArr; ''&alpha;''2, то ''&alpha;''2 непосредственно выводима из ''&alpha;''1.

Если ''&alpha;'' &rArr;''k'' ''&beta;'' (''k'' &ge; 0), то существует последовательность шагов
* ''&gamma;''0 &rArr; ''&gamma;''1 &rArr; ''&gamma;''2 &rArr; &hellip; &rArr; ''&gamma;''''k'' &minus; 1 &rArr; ''&gamma;''''k''
где ''&alpha;'' = ''&gamma;''0 и ''&beta;'' = ''&gamma;''''k''. Последовательность цепочек ''&gamma;''0, ''&gamma;''1, ''&gamma;''2, &hellip;, ''&gamma;''''k'' &minus; 1, ''&gamma;''''k'' в этом случае называется выводом ''&beta;'' из ''&alpha;''.

== Определение языка, порождаемого КС-грамматикой ==
Языком, порождаемым грамматикой ''G'' = (''N'', ''T'', ''P'', ''S'') (обозначается ''L''(''G'')) называется множество всех цепочек терминалов, выводимых из аксиомы, то есть: 
* ''L''(''G'') = {''w'' | ''w'' &isin; ''T''*, ''S'' &rArr;+ ''w''}

== Определение сентенциальной формы ==
'''Сентенциальная форма''' — цепочка над алфавитом <math> (T \cup N)^* </math>, выводимая из аксиомы грамматики

== Определение однозначной КС-грамматики ==
КС грамматика называется однозначной или детерминированной, если всякая выводимая терминальная цепочка имеет только одно дерево вывода (соотвественно только один левый и только один правый вывод).

== Определение неоднозначной КС-грамматики ==
КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка α ⊂ L(G), для которой может быть построено два или более различных деревьев вывода.

== Определение недетерминированного МП автомата ==
Недетерминированный автомат с магазинной памятью (МП-автомат) — семёрка ''M'' = (''Q'', ''T'', ''Г'', ''D'', ''q''0, ''Z''0, ''F''), где
# ''Q'' — конечное множество состояний, представляющее всевозможные состояния управляющего устройства
# ''T'' — конечный входной алфавит
# ''Г'' — конечный алфавит магазинных символов
# ''D'' — отображение множества ''Q'' &times; (''T'' &cup; {&epsilon;}) &times; ''Г'' в множество всех конечных подмножеств ''Q''&nbsp;&times;&nbsp;''Г''*, называемое функцией переходов
# ''q''0&nbsp;&isin;''Q'' — начальное состояние управляющего устройства
# ''Z''0&nbsp;&isin;''Г'' — символ, находящийся в магазине в начальный момент (начальный символ магазина)
# ''F''&nbsp;&sube;''Q'' — множество заключительных состояний

== Определение детерминированного МП автомата ==
Детерминированный автомат с магазинной памятью (МП-автомат) — семёрка ''M'' = (''Q'', ''T'', ''Г'', ''D'', ''q''0, ''Z''0, ''F''), где
# ''Q'' — конечное множество состояний, представляющее всевозможные состояния управляющего устройства
# ''T'' — конечный входной алфавит
# ''Г'' — конечный алфавит магазинных символов
# ''D'' — отображение множества ''Q'' &times; (''T'' &cup; {&epsilon;}) &times; ''Г'' в множество всех конечных подмножеств ''Q''&nbsp;&times;&nbsp;''Г''*, называемое функцией переходов
# ''q''0&nbsp;&isin;&nbsp;''Q'' — начальное состояние управляющего устройства
# ''Z''0&nbsp;&isin;&nbsp;''Г'' — символ, находящийся в магазине в начальный момент (начальный символ магазина)
# ''F''&nbsp;&sube;&nbsp;''Q'' — множество заключительных состояний
Кроме того, должны выполняться следующие условия:
# Множество ''D''(''q'', ''a'', ''Z'') содержит не более одного элемента для любых ''q''&nbsp;&isin;&nbsp;''Q'', ''a''&nbsp;&isin;&nbsp;''T'' &cup; {&epsilon;}, ''Z''0&nbsp;&isin;&nbsp;''Г''
# Если ''D''(''q'', &epsilon;, ''Z'') &ne; &empty;, то ''D''(''q'', ''a'', ''Z'') = &empty; для всех ''a''&nbsp;&isin;&nbsp;''T''

== Определение конфигурации МП автомата ==
Конфигурацией автомата с магазинной памятью (МП автомата) называется тройка (''q'', ''w'', ''u''), где
* ''q''&nbsp;&isin;&nbsp;''Q'' — текущее состояние магазинного устройства
* ''w''&nbsp;&isin;&nbsp;''T''* — непрочитанная часть входной цепочки; первый символ цепочки ''w'' находится под входной головкой; если ''w'' = &epsilon;, то считается, что входная лента прочитана
* ''u''&nbsp;&isin;&nbsp;''Г''* — содержимое магазина; самый левый символ цепочки ''u'' считается вершиной магазина; если ''u = &epsilon;, то магазин считается пустым

== Определение языка, допускаемого МП автоматом ==
Цепочка ''w'' допускается МП автоматом, если (''q''0, ''w'', ''Z''0)⊢* (''q'', &epsilon;, ''u'') для некоторых ''q''&nbsp;&isin;&nbsp;''F'' и ''u''&nbsp;&isin;&nbsp;''Г''*. Язык, допускаемый МП-автоматом ''M'' — множество всех цепочек, допускаемых автоматом ''M''.

== Определение недетерминированного МП автомата, допускающего опустошением магазина ==
Цепочка ''w'' допускается МП автоматом, если (''q''0, ''w'', ''Z''0)⊢* (''q'', &epsilon;, &epsilon;) для некоторого ''q''&nbsp;&isin;&nbsp;''Q''. В таком случае говорят, что автомат допускает цепочку ''опустошением магазина''.

== Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами ==
Они совпадают.

== Формулировка леммы о разрастании для КС-языков ==
Для любого контекстно-свободного языка L существуют такие целые l и k, что любая цепочка &alpha; &isin; L, |&alpha;| > l представима в виде &alpha; = uvwxy, где 
# |vwx| <= k
# vx != e
# uviwxiy &isin; L для любого i >= 0

== Определение нормальной формы Хомского для КС-грамматики ==

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

== Определение правостороннего вывода в КС-грамматике ==
Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого правого нетерминала, называется '''правосторонним'''.

== Определение левостороннего вывода в КС-грамматике ==
Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется '''левосторонним'''.

== Что такое леворекурсивная грамматика? ==
'''Грамматика''' называется '''леворекурсивной''', если в ней имеется нетерминал A такой, что существует вывод A &rArr;+ Au для некоторой строки u.

== Определение множества FIRST1 ==
FIRST1 — множество всех терминальных символов, с которых может начинаться цепочка терминальных символов, выводимых из цели грамматики или ε, если u ⇒* ε.

Пример:

* S → aS | A
    * A → b | bSd | bA | ε
    * FIRST1 = {a, b, ε}

== Определение множества FOLLOW1 ==
== Определение LL(1) грамматики ==
LL(1)-грамматика - грамматика, для которой таблица предсказывающего анализатора не имеет неоднозначно определенных входов

== Определение LR(1) ситуации ==
LR(1)-ситуацией называется пара [''A''&nbsp;&rarr;&nbsp;&alpha; . &beta;, ''a''], где ''A''&nbsp;&rarr;&nbsp;&alpha; &beta;&nbsp;— правило грамматики, ''a''&nbsp;— терминал или правый концевой маркер $. Вторая компонента ситуации называется аванцепочкой.

== Определение LR(1) грамматики ==
Грамматика называется LR(1), если из условий

1. <math>S' =>_r uAw =>_r uvw</math>,

2. <math>S' =>_r zBx =>_r uvy</math>,

3. FIRST(w) = FIRST(y)

следует, что uAy = zBx (т.е. u = z, A = B и x = y).

== Какого типа конфликты могут появиться в канонической системе множеств LR(1) ситуаций? ==
Shift-Reduce и Reduce-Reduce
== Определение конфигурации LR-анализатора ==
Пара (Содержимое магазина, непросмотренный вход)
== Как меняется конфигурация LR-анализатора при действии reduce? ==
Убрать из стека правую часть правила, добавить левую и состояние goto(последнее состояние в магазине, символ из левой части правила)
== Какие типы действий выполняет LR-анализатор? ==
Shift, Reduce, Accept, Reject
== Как меняется конфигурация LR-анализатора при действии shift? ==
Перенести верхний символ входа в магазин, занести наверх магазина состояние action(предыдущее состояние, взятый символ)
== Что такое основа правой сентенциальной формы ==

Основа правой сентенциальной формы z - это правило вывода <math>A -> v</math> и позиция в z, в которой может быть найдена цепочка v такие, что в результате замены v на A получается предыдущая сентенциальная форма в правостороннем выводе z. Таким образом, если <math>S =>_r avb</math>, то <math>A -> v</math> в позиции, следующей за a - это основа цепочки <math>avb</math>. Подцепочка b справа от основы содержит только терминальные символы.

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. 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%A2%D0%B5%D0%BE%D1%80%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D1%83%D0%BC_%282012%29

Редактирование: Конструирование Компиляторов, Теоретический минимум (2012)

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

Просмотры

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

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 211: / Строка 211: @@
 # ''F''&nbsp;&sube;&nbsp;''Q'' — множество заключительных состояний
 Кроме того, должны выполняться следующие условия:
-# Множество ''D''(''q'', ''a'', ''Z'') содержит не более одного элемента для любых ''q''&nbsp;&isin;&nbsp;''Q'', ''a''&nbsp;&isin;&nbsp;''T'' &cup; {&epsilon;}, ''Z''&nbsp;&isin;&nbsp;''Г''
+# Множество ''D''(''q'', ''a'', ''Z'') содержит не более одного элемента для любых ''q''&nbsp;&isin;&nbsp;''Q'', ''a''&nbsp;&isin;&nbsp;''T'' &cup; {&epsilon;}, ''Z''<sub>0</sub>&nbsp;&isin;&nbsp;''Г''
 # Если ''D''(''q'', &epsilon;, ''Z'') &ne; &empty;, то ''D''(''q'', ''a'', ''Z'') = &empty; для всех ''a''&nbsp;&isin;&nbsp;''T''