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

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

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

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

ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 30 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.

''см. также [[Конструирование Компиляторов, Теоретический минимум|ответы на вопросы теоретического минимума 2007 года]], [[Конструирование Компиляторов, Определения|список определений]].'' == Алфавит == Алфавит - конечное множество символов == Определение грамматики == Грамматика <math>~G = (N,T,P,S)</math> - четверка множеств, где * <math>~N</math> - алфавит нетерминальных символов * <math>~T</math> - алфавит терминальных символов, <math>N \cap T = \empty</math>; * <math>~P</math> - множество правил вида <math>\alpha \rarr \beta, \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, или неукорачивающей. == Определение детерминированной машины Тьюринга == '''Детерминированная машина Тьюринга''' — T_m = (Q, Г, &Sigma;, D, q₀, F) * Q — конечное множество состояний * Г — конечное множество ленточных символов (конечный алфавит), один из которых называется пустым и обозначается обычно b * &Sigma; — входной алфавит, &Sigma; &sube; Г\{b} (b - пустой символ) * D — правила перехода ** D: (Q\F) &times; Г &rarr; Q &times; Г &times; {L, R} * q₀ &isin; Q — начальное состояние * F &sube; Q — множество конечных состояний == Определение недетерминированной машины Тьюринга == '''Недетерминированная машина Тьюринга''' — T_m = (Q, Г, &Sigma;, D, q₀, F) * Q — конечное множество состояний * Г — конечное множество символов (конечный алфавит) * &Sigma; — входной алфавит, &Sigma; &sube; Г\{b} (b - пустой символ) * D — правила перехода ** D: (Q\F) &times; Г &rarr; 2^{Q &times; Г &times; {L, R}} * q₀ &isin; Q — начальное состояние * F &sube; Q — множество конечных состояний == Определение конфигурации машины Тьюринга == Конфигурацией машины Тьюринга называется тройка (q, w, i), где * q &isin; Q — состояние машины Тьюринга * w &isin; Г* —текущее содержимое занятого участка ленты, w = a₁ &hellip; a_n * i &isin; Z — положение головки машины Тьюринга == Определение языка, допускаемого машиной Тьюринга == Язык, допускаемый машиной Тьюринга — множество таких слов w, что, машина Тьюринга, находясь в состоянии (q₀, 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, q₀, F) * Q — конечное непустое множество состояний * &Sigma; — входной алфавит * D — правила перехода ** Q &times; ( &Sigma; &cup; {&epsilon;} ) &rarr; 2^Q * q₀ &isin; Q — начальное состояние * F &sube; Q — множество конечных состояний <!-- про epsilon - моя отсебятина, его обычно потом отдельно добавляют --> <!-- или от нас требуется только нестрогое определение? --> == Определение детерминированного конечного автомата == '''Детерминированный конечный автомат''' - M = (Q, &Sigma;, D, q₀, F) * Q — конечное непустое множество состояний * &Sigma; — конечный входной алфавит * D — правила перехода ** Q &times; &Sigma; &rarr; Q * q₀ &isin; Q — начальное состояние * F &sube; Q — множество конечных состояний <!-- или от нас требуется только нестрогое определение? --> == Объяснить разницу между недетерминированным и детерминированным конечным автоматом == Недетерминированный конечный автомат является обобщением детерминированного. Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). В детерменированном автомате из одного состояния допускается не более одного перехода для каждого символа алфавита, в недетерменированном - произвольное количество. Кроме того, в НКА возможны эпсилон-переходы. == Определение конфигурации конечного автомата == Пусть ''M'' = (''Q'', ''T'', ''D'', ''q''₀, ''F'') — НКА. Конфигурацией автомата ''M'' называется пара (''q'', &omega;)&nbsp;&isin;&nbsp;''Q''&nbsp;&times;&nbsp;''T''*, где ''q''&nbsp;— текущее состояние управляющего устройства, а &omega;&nbsp;— цепочка символов на входной ленте, состоящая из символов под головкой и всех символов справа от неё. == Определение языка, допускаемого конечным автоматом == Автомат ''M'' допускает цепочку &omega;, если (''q''₀, &omega;)&nbsp;⊦*&nbsp;(''q'',&nbsp;&epsilon;) для некоторого ''q''&nbsp;&isin;&nbsp;''F''. Языком, допускаемым автоматом ''M'', называется множество входных цепочек,допускаемых автоматом ''M''. То есть: * ''L(M)'' = {&omega; | &omega; &isin; ''T''* и (''q''₀, &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 T \Leftrightarrow D(q_j, z)\in T</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;''₁ &rArr; ''&alpha;''₂, то ''&alpha;''₂ непосредственно выводима из ''&alpha;''₁. Если ''&alpha;'' &rArr;^''k'' ''&beta;'' (''k'' &ge; 0), то существует последовательность шагов * ''&gamma;''₀ &rArr; ''&gamma;''₁ &rArr; ''&gamma;''₂ &rArr; &hellip; &rArr; ''&gamma;''_{''k'' &minus; 1} &rArr; ''&gamma;''_''k'' где ''&alpha;'' = ''&gamma;''₀ и ''&beta;'' = ''&gamma;''_''k''. Последовательность цепочек ''&gamma;''₀, ''&gamma;''₁, ''&gamma;''₂, &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''₀, ''Z''₀, ''F''), где # ''Q'' — конечное множество состояний, представляющее всевозможные состояния управляющего устройства # ''T'' — конечный входной алфавит # ''Г'' — конечный алфавит магазинных символов # ''D'' — отображение множества ''Q'' &times; (''T'' &cup; {&epsilon;}) &times; ''Г'' в множество всех конечных подмножеств ''Q''&nbsp;&times;&nbsp;''Г''*, называемое функцией переходов # ''q''₀&nbsp;&isin;''Q'' — начальное состояние управляющего устройства # ''Z''₀&nbsp;&isin;''Г'' — символ, находящийся в магазине в начальный момент (начальный символ магазина) # ''F''&nbsp;&sube;''Q'' — множество заключительных состояний == Определение детерминированного МП автомата == Детерминированный автомат с магазинной памятью (МП-автомат) — семёрка ''M'' = (''Q'', ''T'', ''Г'', ''D'', ''q''₀, ''Z''₀, ''F''), где # ''Q'' — конечное множество состояний, представляющее всевозможные состояния управляющего устройства # ''T'' — конечный входной алфавит # ''Г'' — конечный алфавит магазинных символов # ''D'' — отображение множества ''Q'' &times; (''T'' &cup; {&epsilon;}) &times; ''Г'' в множество всех конечных подмножеств ''Q''&nbsp;&times;&nbsp;''Г''*, называемое функцией переходов # ''q''₀&nbsp;&isin;&nbsp;''Q'' — начальное состояние управляющего устройства # ''Z''₀&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''₀&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''₀, ''w'', ''Z''₀)⊢* (''q'', &epsilon;, ''u'') для некоторых ''q''&nbsp;&isin;&nbsp;''F'' и ''u''&nbsp;&isin;&nbsp;''Г''*. Язык, допускаемый МП-автоматом ''M'' — множество всех цепочек, допускаемых автоматом ''M''. == Определение недетерминированного МП автомата, допускающего опустошением магазина == Цепочка ''w'' допускается МП автоматом, если (''q''₀, ''w'', ''Z''₀)⊢* (''q'', &epsilon;, &epsilon;) для некоторого ''q''&nbsp;&isin;&nbsp;''Q''. В таком случае говорят, что автомат допускает цепочку ''опустошением магазина''. == Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами == Они совпадают. == Формулировка леммы о разрастании для КС-языков == Для любого контекстно-свободного языка L существуют такие целые l и k, что любая цепочка &alpha; &isin; L, |&alpha;| > l представима в виде &alpha; = uvwxy, где # |vwx| <= k # vx != e # uvⁱwxⁱy &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), если из условий 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:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

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

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

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

• Шаблон:Курс Конструирование Компиляторов