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

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

Версия от 09:06, 29 июня 2009; 87.251.153.156 (Обсуждение)

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

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

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

''см. также [[Конструирование Компиляторов, Теоретический минимум|ответы на вопросы теоретического минимума 2007 года]], [[Конструирование Компиляторов, Определения|список определений]].''
== Определение грамматики ==
Грамматкиа G = (N,T,P,S) - четверка множеств, где
* N - алфавит нетерминальных символов 
* T - алфавит терминальных символов, пересечение N и T = &empty;
* P - множество правил вида &alpha; &rarr; &beta;, &alpha; &isin; ( N &cup; T)*N(N &cup; T)*, &beta; &isin; (N &cup; T)*
* S &isin; N - начальный символ или аксиома грамматики

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

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

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

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

== Определение конфигурации машины Тьюринга ==
Конфигурацией машины Тьюринга называется тройка (q, w, i), где
* q &isin; Q — состояние машины Тьюринга
* w &isin; Г* —текущее содержимое занятого участка ленты, w = a1 &hellip; an
* i &isin; Z — положение головки машины Тьюринга

== Определение языка, допускаемого машиной Тьюринга ==
Язык, допускаемый машиной Тьюринга — множество таких слов w, что, машина Тьюринга, находясь в состоянии (q0, w, 1) может достигнуть через конечное число переходов состояния q &isin; F.

== Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга ==
Класс языков, допускаемых машиной Тьюринга, эквивалентен классу языков, порождаемых грамматиками типа 0.

== Объяснить разницу между недетерминированной и  детерминированной машиной Тьюринга ==
Детерминированная машина Тьюринга из данного состояния по данному символу может сделать не более одного перехода, недетерминированная же таким свойством не обладает.

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

'''Регулярное множество''' в алфавите 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

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

Регулярное выражение и обозначаемое им регулярное множество определяются следующим образом:
* &empty; — обозначает множество {}
* &epsilon; — обозначает множество {&epsilon;}
* ''a'' — обозначает множество {''a''}
* Если РВ ''p'' и ''q'' обозначают множества ''P'' и ''Q'' соответственно, то:
** (''p''|''q'') обозначает ''P'' &cup; ''Q''
** ''pq'' обозначает ''PQ''
** (''p''*) обозначет ''P''*
* Ничто другое не является регулярным выражением в данном алфавите

== Определение праволинейной грамматики ==
Праволинейная грамматика или грамматика типа 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*).

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

== Определение эквивалентных состояний ДКА ==
== Определение различимых состояний ДКА ==

== Определение контекстно-свободной грамматики без &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''}

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

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

== Определение неоднозначной КС-грамматики ==
КС-грамматика 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; &alpha;, &alpha; - терминал
# либо S &rarr; e, в таком случае 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) ситуаций? ==
Shift-Reduce и Reduce-Reduce
== Определение конфигурации LR-анализатора ==
Пара (Содержимое магазина, непросмотренный вход)
== Как меняется конфигурация LR-анализатора при действии reduce? ==
Убрать из стека правую часть правила, добавить левую и состояние goto(последнее состояние в магазине, символ из левой части правила)
== Какие типы действий выполняет LR-анализатор? ==
Shift, Reduce, Accept, Reject
== Как меняется конфигурация LR-анализатора при действии shift? ==
Перенести верхний символ входа в магазин, занести наверх магазина состояние action(предыдущее состояние, взятый символ)
== Что такое основа правой сентенциальной формы ==

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

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

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

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