Редактирование: Конструирование Компиляторов, Теоретический минимум (2009)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 31 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
''см. также [[Конструирование Компиляторов, Теоретический минимум|ответы на вопросы теоретического минимума 2007 года]], [[Конструирование Компиляторов, Определения|список определений]].'' | ''см. также [[Конструирование Компиляторов, Теоретический минимум|ответы на вопросы теоретического минимума 2007 года]], [[Конструирование Компиляторов, Определения|список определений]].'' | ||
- | == Алфавит == | ||
- | + | # Определение грамматик типа 0 по Хомскому | |
- | + | # Определение грамматик типа 1 (неукорачивающих) по Хомскому | |
- | + | # Определение детерминированной машины Тьюринга | |
- | + | # Определение недетерминированной машины Тьюринга | |
- | + | # Определение конфигурации машины Тьюринга | |
- | + | # Определение языка, допускаемого машиной Тьюринга | |
- | + | # Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга | |
- | + | # Объяснить разницу между недетерминированной и детерминированной машиной Тьюринга | |
+ | # Определение регулярного множества | ||
+ | # Определение регулярного выражения | ||
+ | # Определение праволинейной грамматики | ||
+ | # Определение недетерминированного конечного автомата | ||
+ | # Определение детерминированного конечного автомата | ||
+ | # Объяснить разницу между недетерминированным и детерминированным конечным автоматом | ||
+ | # Определение конфигурации конечного автомата | ||
+ | # Определение языка, допускаемого конечным автоматом | ||
+ | # Определение ε-замыкания для подмножества состояний НКА | ||
+ | # Определение расширенной функции переходов для ДКА | ||
+ | # Определение расширенной функции переходов для НКА | ||
+ | # Определение функции firstpos для поддерева в дереве регулярного выражения | ||
+ | # Определение функции lastpos для поддерева в дереве регулярного выражения | ||
+ | # Определение функции followpos для позиций в дереве регулярного выражения | ||
+ | # Сформулировать соотношение между регулярными множествами и языками, допускаемыми КА | ||
+ | # Определение регулярной грамматики | ||
+ | # Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками и языками, допускаемыми КА | ||
+ | # Определение эквивалентных состояний ДКА | ||
+ | # Определение различимых состояний ДКА | ||
+ | # Определение контекстно-свободной грамматики без е-правил | ||
+ | # Определение контекстно-свободной грамматики | ||
+ | # Определение вывода в КС-грамматике | ||
+ | # Определение языка, порождаемого КС-грамматикой | ||
+ | # Определение сентенциальной формы | ||
+ | # Определение однозначной КС-грамматики | ||
+ | # Определение неоднозначной КС-грамматики | ||
+ | # Определение недетерминированного МП автомата | ||
+ | # Определение детерминированного МП автомата | ||
+ | # Определение конфигурации МП автомата | ||
+ | # Определение языка, допускаемого МП автоматом | ||
+ | # Что означает то, что недетерминированный МП автомат допускает опустошением магазина | ||
+ | # Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами | ||
+ | # Формулировка леммы о разрастании для КС-языков | ||
+ | # Определение нормальной формы Хомского для КС-грамматики | ||
+ | # Определение правостороннего вывода в КС-грамматике | ||
+ | # Определение левостороннего вывода в КС-граммати | ||
+ | # Какая грамматика называется леворекурсивной? | ||
+ | # Определение множества FIRST1 | ||
+ | # Определение множества FOLLOW1 | ||
+ | # Определение LL(1) Грамматики | ||
+ | # Определение LR(1) ситуации | ||
+ | # Определение LR(1) грамматики | ||
+ | # Какого типа конфликты могут появиться в канонической системе множеств LR(1) ситуаций? | ||
+ | # Определение конфигурации LR-анализатора | ||
+ | # Как меняется конфигурация LR-анализатора при действии reduce? | ||
+ | # Какие типы действий выполняет LR-анализатор? | ||
+ | # Как меняется конфигурация LR-анализатора при действии shift? | ||
+ | # Что такое основа правой сентенциальной формы | ||
== Определение грамматик типа 0 по Хомскому == | == Определение грамматик типа 0 по Хомскому == | ||
- | Если на грамматику | + | Если на грамматику G = (N, T, P, S) не накладываются никакие ограничения, то её называют грамматикой типа 0, или грамматикой без ограничений. |
== Определение грамматик типа 1 (неукорачивающих) по Хомскому == | == Определение грамматик типа 1 (неукорачивающих) по Хомскому == | ||
Если | Если | ||
- | # Каждое правило грамматики, кроме | + | # Каждое правило грамматики, кроме S → ε, имеет вид α → β, |α| ≤ |β| |
- | # В том случае, когда | + | # В том случае, когда S → ε ∈ P, символ S не встречается в правых частях правил |
то грамматику называют грамматикой типа 1, или неукорачивающей. | то грамматику называют грамматикой типа 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<sub>m</sub> = (Q, Г, Σ, D, q<sub>0</sub>, F) | '''Детерминированная машина Тьюринга''' — T<sub>m</sub> = (Q, Г, Σ, D, q<sub>0</sub>, F) | ||
* Q — конечное множество состояний | * Q — конечное множество состояний | ||
- | * Г — конечное множество | + | * Г — конечное множество символов (конечный алфавит) |
* Σ — входной алфавит, Σ ⊆ Г\{b} (b - пустой символ) | * Σ — входной алфавит, Σ ⊆ Г\{b} (b - пустой символ) | ||
* D — правила перехода | * D — правила перехода | ||
Строка 38: | Строка 77: | ||
* F ⊆ Q — множество конечных состояний | * F ⊆ Q — множество конечных состояний | ||
- | + | == Определение недетерминированной машины Тьюринга == | |
+ | '''Недетерминированная машина Тьюринга''' — T<sub>m</sub> = (Q, Г, Σ, D, q<sub>0</sub>, F) | ||
+ | * Q — конечное множество состояний | ||
+ | * Г — конечное множество символов (конечный алфавит) | ||
+ | * Σ — входной алфавит, Σ ⊆ Г\{b} (b - пустой символ) | ||
+ | * D — правила перехода | ||
+ | ** D: (Q\F) × Г → 2<sup>Q × Г × {L, R}</sup> | ||
+ | * q<sub>0</sub> ∈ Q — начальное состояние | ||
+ | * F ⊆ Q — множество конечных состояний | ||
== Определение конфигурации машины Тьюринга == | == Определение конфигурации машины Тьюринга == | ||
Конфигурацией машины Тьюринга называется тройка (q, w, i), где | Конфигурацией машины Тьюринга называется тройка (q, w, i), где | ||
* q ∈ Q — состояние машины Тьюринга | * q ∈ Q — состояние машины Тьюринга | ||
- | * w ∈ Г* | + | * w ∈ Г* — вход, помещаемый на ленту машины Тьюринга, w = a<sub>1</sub> … a<sub>n</sub> |
* i ∈ Z — положение головки машины Тьюринга | * i ∈ Z — положение головки машины Тьюринга | ||
Строка 58: | Строка 105: | ||
'''Регулярное множество''' в алфавите T определяется следующим образом: | '''Регулярное множество''' в алфавите T определяется следующим образом: | ||
- | * | + | * {} (пустое множество) — регулярное множество в алфавите T |
- | * | + | * {a} — регулярное множество в алфавите T для каждого a ∈ T |
- | * | + | * {ε} — регулярное множество в алфавите T |
- | * Если P и Q — регулярные множества в алфавите T, то | + | * Если P и Q — регулярные множества в алфавите T, то таковы же и множества |
- | ** | + | ** P ∪ Q (объединение) |
- | ** | + | ** PQ (конкатенация, то есть множество таких pq, что p ∈ P, q ∈ Q) |
- | ** | + | ** P* (итерация: P* = {ε} ∪ P ∪ PP ∪ PPP ∪ …) |
* Ничто другое не является регулярным множеством в алфавите T | * Ничто другое не является регулярным множеством в алфавите T | ||
Строка 106: | Строка 153: | ||
== Объяснить разницу между недетерминированным и детерминированным конечным автоматом == | == Объяснить разницу между недетерминированным и детерминированным конечным автоматом == | ||
Недетерминированный конечный автомат является обобщением детерминированного. Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). | Недетерминированный конечный автомат является обобщением детерминированного. Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). | ||
- | В детерменированном автомате из одного состояния допускается не более одного перехода для каждого символа алфавита, в недетерменированном - произвольное количество. Кроме того, в НКА возможны эпсилон-переходы. | ||
== Определение конфигурации конечного автомата == | == Определение конфигурации конечного автомата == | ||
Строка 186: | Строка 232: | ||
== Определение эквивалентных состояний ДКА == | == Определение эквивалентных состояний ДКА == | ||
- | Два состояния <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> | ||
- | |||
== Определение различимых состояний ДКА == | == Определение различимых состояний ДКА == | ||
Строка 197: | Строка 241: | ||
A → α, α ∈ (N ∪ T)* | A → α, α ∈ (N ∪ T)* | ||
- | == Определение | + | == Определение вывода в КС-грамматике == |
Определим на множестве (''N'' ∪ ''T'')* грамматики ''G'' = (''N'', ''T'', ''P'', ''S'') бинарное отношение выводимости «⇒» следующим образом: если ''δ'' → ''γ'' ∈ ''P'', то ''αδβ'' ⇒ ''αγβ'' для всех ''α'', ''β'' ∈ (''N'' ∪ ''T'')*. Если ''α''<sub>1</sub> ⇒ ''α''<sub>2</sub>, то ''α''<sub>2</sub> непосредственно выводима из ''α''<sub>1</sub>. | Определим на множестве (''N'' ∪ ''T'')* грамматики ''G'' = (''N'', ''T'', ''P'', ''S'') бинарное отношение выводимости «⇒» следующим образом: если ''δ'' → ''γ'' ∈ ''P'', то ''αδβ'' ⇒ ''αγβ'' для всех ''α'', ''β'' ∈ (''N'' ∪ ''T'')*. Если ''α''<sub>1</sub> ⇒ ''α''<sub>2</sub>, то ''α''<sub>2</sub> непосредственно выводима из ''α''<sub>1</sub>. | ||
Строка 209: | Строка 253: | ||
== Определение сентенциальной формы == | == Определение сентенциальной формы == | ||
- | '''Сентенциальная форма''' — цепочка | + | '''Сентенциальная форма''' — цепочка (состоящая, в общем случае, из терминалов и нетерминалов), выводимая из аксиомы грамматики |
== Определение однозначной КС-грамматики == | == Определение однозначной КС-грамматики == | ||
Строка 249: | Строка 293: | ||
Цепочка ''w'' допускается МП автоматом, если (''q''<sub>0</sub>, ''w'', ''Z''<sub>0</sub>)⊢* (''q'', ε, ''u'') для некоторых ''q'' ∈ ''F'' и ''u'' ∈ ''Г''*. Язык, допускаемый МП-автоматом ''M'' — множество всех цепочек, допускаемых автоматом ''M''. | Цепочка ''w'' допускается МП автоматом, если (''q''<sub>0</sub>, ''w'', ''Z''<sub>0</sub>)⊢* (''q'', ε, ''u'') для некоторых ''q'' ∈ ''F'' и ''u'' ∈ ''Г''*. Язык, допускаемый МП-автоматом ''M'' — множество всех цепочек, допускаемых автоматом ''M''. | ||
- | == Определение недетерминированного МП автомата, допускающего | + | == Определение недетерминированного МП автомата, допускающего опустошение магазина == |
Цепочка ''w'' допускается МП автоматом, если (''q''<sub>0</sub>, ''w'', ''Z''<sub>0</sub>)⊢* (''q'', ε, ε) для некоторого ''q'' ∈ ''Q''. В таком случае говорят, что автомат допускает цепочку ''опустошением магазина''. | Цепочка ''w'' допускается МП автоматом, если (''q''<sub>0</sub>, ''w'', ''Z''<sub>0</sub>)⊢* (''q'', ε, ε) для некоторого ''q'' ∈ ''Q''. В таком случае говорят, что автомат допускает цепочку ''опустошением магазина''. | ||
Строка 256: | Строка 300: | ||
== Формулировка леммы о разрастании для КС-языков == | == Формулировка леммы о разрастании для КС-языков == | ||
- | Для любого контекстно-свободного языка L существуют такие целые l и k, что любая цепочка α ∈ L, |α| > l представима в виде α = uvwxy, где | ||
- | # |vwx| <= k | ||
- | # vx != e | ||
- | # uv<sup>i</sup>wx<sup>i</sup>y ∈ L для любого i >= 0 | ||
== Определение нормальной формы Хомского для КС-грамматики == | == Определение нормальной формы Хомского для КС-грамматики == | ||
- | говорят что КС-грамматика находится в нормальной форме Хомского если каждое правило имеет вид: | ||
- | # Либо A → BC, A,B,C - нетерминалы | ||
- | # либо A → α, α - терминал | ||
- | # либо S → e, в таком случае S не встречается в правых частях правил | ||
== Определение правостороннего вывода в КС-грамматике == | == Определение правостороннего вывода в КС-грамматике == | ||
Строка 274: | Строка 310: | ||
== Что такое леворекурсивная грамматика? == | == Что такое леворекурсивная грамматика? == | ||
- | '''Грамматика''' называется '''леворекурсивной''', если в ней имеется нетерминал A такой, что существует вывод A ⇒ | + | '''Грамматика''' называется '''леворекурсивной''', если в ней имеется нетерминал A такой, что существует вывод A ⇒ Au для некоторой строки u. |
== Определение множества FIRST1 == | == Определение множества FIRST1 == | ||
- | FIRST1 — множество всех терминальных символов, с которых может начинаться цепочка терминальных символов, выводимых из цели грамматики или ε, если u ⇒* ε. | ||
- | |||
- | Пример: | ||
- | |||
- | * S → aS | A | ||
- | * A → b | bSd | bA | ε | ||
- | * FIRST1 = {a, b, ε} | ||
- | |||
== Определение множества FOLLOW1 == | == Определение множества FOLLOW1 == | ||
== Определение LL(1) грамматики == | == Определение LL(1) грамматики == | ||
- | LL(1)-грамматика - грамматика, для которой таблица предсказывающего анализатора не имеет неоднозначно определенных входов | ||
== Определение LR(1) ситуации == | == Определение LR(1) ситуации == | ||
Строка 293: | Строка 320: | ||
== Определение LR(1) грамматики == | == Определение 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) ситуаций? == | == Какого типа конфликты могут появиться в канонической системе множеств LR(1) ситуаций? == | ||
- | Shift-Reduce и Reduce-Reduce | ||
== Определение конфигурации LR-анализатора == | == Определение конфигурации LR-анализатора == | ||
- | Пара (Содержимое магазина, непросмотренный вход) | ||
== Как меняется конфигурация LR-анализатора при действии reduce? == | == Как меняется конфигурация LR-анализатора при действии reduce? == | ||
- | Убрать из стека правую часть правила, добавить левую и состояние goto(последнее состояние в магазине, символ из левой части правила) | ||
== Какие типы действий выполняет LR-анализатор? == | == Какие типы действий выполняет LR-анализатор? == | ||
- | Shift, Reduce, Accept, Reject | ||
== Как меняется конфигурация LR-анализатора при действии shift? == | == Как меняется конфигурация 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 справа от основы содержит только терминальные символы. | ||
{{Курс Конструирование Компиляторов}} | {{Курс Конструирование Компиляторов}} |