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

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

Текущая версия

[править] Определение грамматик типа 0 по Хомскому

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

[править] Определение грамматик типа 1 (неукорачивающих) по Хомскому

Если

1. Каждое правило грамматики, кроме S → ε, имеет вид α → β, |α| ≤ |β|
2. В том случае, когда S → ε ∈ P, символ S не встречается в правых частях правил

то грамматику называют грамматикой типа 1, или неукорачивающей.

[править] Определение детерминированной машины Тьюринга

Детерминированная машина Тьюринга — T_m = (Q, Г, Σ, D, q₀, F)

• Q — конечное множество состояний
• Г — конечное множество символов (конечный алфавит)
• Σ — входной алфавит, Σ ⊆ Г\{b} (b - пустой символ)
• D — правила перехода
  • D: (Q\F) × Г → Q × Г × {L, R}
• q₀ ∈ Q — начальное состояние
• F ⊆ Q — множество конечных состояний

[править] Определение недетерминированной машины Тьюринга

Недетерминированная машина Тьюринга — T_m = (Q, Г, Σ, D, q₀, F)

• Q — конечное множество состояний
• Г — конечное множество символов (конечный алфавит)
• Σ — входной алфавит, Σ ⊆ Г\{b} (b - пустой символ)
• D — правила перехода
  • D: (Q\F) × Г → 2^{Q × Г × {L, R}}
• q₀ ∈ Q — начальное состояние
• F ⊆ Q — множество конечных состояний

[править] Определение конфигурации машины Тьюринга

Конфигурацией машины Тьюринга называется тройка (q, w, i), где

• q ∈ Q — состояние машины Тьюринга
• w ∈ Г* — вход, помещаемый на ленту машины Тьюринга, w = a₁ … a_n
• i ∈ Z — положение головки машины Тьюринга

[править] Определение языка, допускаемого машиной Тьюринга

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

[править] Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга

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

[править] Объяснить разницу между недетерминированной и детерминированной машиной Тьюринга

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

[править] Определение линейно-ограниченного автомата

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

[править] Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми линейно-ограниченными автоматами

Линейно-ограниченные автоматы распознают контекстно-зависимые языки (то есть языки класса 1). Языки класса 0 распознаются только машинами Тьюринга с неограниченной памятью.

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

Регулярное множество в алфавите T определяется следующим образом:

• {} (пустое множество) — регулярное множество в алфавите T
• {a} — регулярное множество в алфавите T для каждого a ∈ T
• {ε} — регулярное множество в алфавите T
• Если P и Q — регулярные множества в алфавите T, то таковы же и множества
  • P ∪ Q (объединение)
  • PQ (конкатенация, то есть множество таких pq, что p ∈ P, q ∈ Q)
  • P* (итерация: P* = {ε} ∪ P ∪ PP ∪ PPP ∪ …)
• Ничто другое не является регулярным множеством в алфавите T

[править] Определение регулярного выражения

Регулярное выражение — форма записи регулярного множества.

Регулярное выражение и обозначаемое им регулярное множество определяются следующим образом:

• ∅ — обозначает множество {}
• ε — обозначает множество {ε}
• a — обозначает множество {a}
• Если РВ p и q обозначают множества P и Q соответственно, то:
  • (p|q) обозначает P ∪ Q
  • pq обозначает PQ
  • (p*) обозначет P*
• Ничто другое не является регулярным выражением в данном алфавите

[править] Определение праволинейной грамматики

Праволинейная грамматика или грамматика типа 3 по Хомскому — грамматика вида A → w, A → wB, w ∈ T*.

[править] Определение недетерминированного конечного автомата

Недетерминированный конечный автомат - M = (Q, Σ, D, q₀, F)

• Q — конечное непустое множество состояний
• Σ — входной алфавит
• D — правила перехода
  • Q × ( Σ ∪ {ε} ) → 2^Q
• q₀ ∈ Q — начальное состояние
• F ⊆ Q — множество конечных состояний

[править] Определение детерминированного конечного автомата

Детерминированный конечный автомат - M = (Q, Σ, D, q₀, F)

• Q — конечное непустое множество состояний
• Σ — конечный входной алфавит
• D — правила перехода
  • Q × Σ → Q
• q₀ ∈ Q — начальное состояние
• F ⊆ Q — множество конечных состояний

[править] Объяснить разницу между недетерминированным и детерминированным конечным автоматом

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

[править] Определение конфигурации конечного автомата

Пусть M = (Q, T, D, q₀, F) — НКА. Конфигурацией автомата M называется пара (q, ω) ∈ Q × T*, где q — текущее состояние управляющего устройства, а ω — цепочка символов на входной ленте, состоящая из символов под головкой и всех символов справа от неё.

[править] Определение языка, допускаемого конечным автоматом

Автомат M допускает цепочку ω, если (q₀, ω) ⊦* (q, ε) для некоторого q ∈ F. Языком, допускаемым автоматом M, называется множество входных цепочек,допускаемых автоматом M. То есть:

• L(M) = {ω | ω ∈ T* и (q₀, ω) ⊦* (q, ε) для некоторого q ∈ F}

[править] Определение ε-замыкания для подмножества состояний НКА

ε-замыкание множества состояний R, R ⊆ Q — множество состояний НКА, достижимых из состояний, входящих в R, посредством только переходов по ε, то есть множество

• S = ⋃_q ∈ R {p | (q, ε) ⊦* (p, ε)}

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

Расширенная функция переходов множества состояний R, R ⊆ Q по a — множество состояний НКА, в которые есть переход на входе a для состояний из R, то есть множество

• S = ⋃_q ∈ R {p | p ∈ D(q, a)}

[править] Определение функции firstpos для поддерева в дереве регулярного выражения

Функция firstpos(n) для каждого узла n узла синтаксического дерева регулярных выражений даёт множество позиций, которые соответствуют первым символам в цепочках, генерируемых подвыражением с вершиной n. Построение:

[править] Определение функции lastpos для поддерева в дереве регулярного выражения

Функция lastpos(n) для каждого узла n узла синтаксического дерева регулярных выражений даёт множество позиций, которым соответствуют последние символы в цепочках, генерируемых подвыражениями с вершиной n. Построение lastpos(n):

[править] Определение функции followpos для позиций в дереве регулярного выражения

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

[править] Сформулировать соотношение между регулярными множествами и языками, допускаемыми КА

Любой конечный автомат распознает регулярное множество цепочек символов входного алфавита. Верно и обратное — для любого регулярного языка можно построить распознающий его конечный автомат.

[править] Определение регулярной грамматики

Регулярные грамматики — праволинейные (A → w, A → wB, w ∈ T*), леволинейные (A → w, A → Bw, w ∈ T*).

[править] Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами

Они совпадают.

[править] Определение контекстно-свободной грамматики

A → α, α ∈ (N ∪ T)*

[править] Определение левостороннего вывода в КС-грамматике

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

[править] Определение правостороннего вывода в КС-грамматике

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

[править] Определение сентенциальной формы

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

[править] Определение приведенной грамматики

Грамматика называется приведённой, если она не содержит бесполезных символов.

[править] Определение множества FOLLOW(A)

Пусть A — нетерминал. Тогда FOLLOW(A) — множество терминалов a, которые могут появиться непосредственно справа от A в некоторой сентенциальной форме, то есть, множество терминалов a таких, что существует вывод вида S ⇒* uAav для некоторых u и v.

[править] Определение LR(1) ситуации

LR(1)-ситуацией называется пара [A → α . β, a], где A → α β — правило грамматики, a — терминал или правый концевой маркер $. Вторая компонента ситуации называется аванцепочкой.

[править] Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками и языками, допускаемыми КА

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

[править] Определение однозначной КС-грамматики

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

[править] Определение неоднозначной КС-грамматики

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

[править] Определение контекстно-свободной грамматики без ε-правил

• A → α, α ∈ (N ∪ T)⁺
• допускается S → ε, если S не входит ни в какую правую часть

[править] Определение вывода в КС-грамматике

Определим на множестве (N ∪ T)* грамматики G = (N, T, P, S) бинарное отношение выводимости «⇒» следующим образом: если δ → γ ∈ P, то αδβ ⇒ αγβ для всех α, β ∈ (N ∪ T)*. Если α₁ ⇒ α₂, то α₂ непосредственно выводима из α₁.

Если α ⇒^k β (k ≥ 0), то существует последовательность шагов

• γ₀ ⇒ γ₁ ⇒ γ₂ ⇒ … ⇒ γ_{k − 1} ⇒ γ_k

где α = γ₀ и β = γ_k. Последовательность цепочек γ₀, γ₁, γ₂, …, γ_{k − 1}, γ_k в этом случае называется выводом β из α.

[править] Определение языка, порождаемого КС-грамматикой

Языком, порождаемым грамматикой G = (N, T, P, S) (обозначается L(G)) называется множество всех цепочек терминалов, выводимых из аксиомы, то есть:

• L(G) = {w | w ∈ T*, S ⇒⁺ w}

[править] Определение недетерминированного МП автомата

Недетерминированный автомат с магазинной памятью (МП-автомат) — семёрка M = (Q, T, Г, D, q₀, Z₀, F), где

1. Q — конечное множество состояний, представляющее всевозможные состояния управляющего устройства
2. T — конечный входной алфавит
3. Г — конечный алфавит магазинных символов
4. D — отображение множества Q × (T ∪ {ε}) × Г в множество всех конечных подмножеств Q × Г*, называемое функцией переходов
5. q₀ ∈Q — начальное состояние управляющего устройства
6. Z₀ ∈Г — символ, находящийся в магазине в начальный момент (начальный символ магазина)
7. F ⊆Q — множество заключительных состояний

[править] Определение детерминированного МП автомата

Детерминированный автомат с магазинной памятью (МП-автомат) — семёрка M = (Q, T, Г, D, q₀, Z₀, F), где

1. Q — конечное множество состояний, представляющее всевозможные состояния управляющего устройства
2. T — конечный входной алфавит
3. Г — конечный алфавит магазинных символов
4. D — отображение множества Q × (T ∪ {ε}) × Г в множество всех конечных подмножеств Q × Г*, называемое функцией переходов
5. q₀ ∈ Q — начальное состояние управляющего устройства
6. Z₀ ∈ Г — символ, находящийся в магазине в начальный момент (начальный символ магазина)
7. F ⊆ Q — множество заключительных состояний

Кроме того, должны выполняться следующие условия:

1. Множество D(q, a, Z) содержит не более одного элемента для любых q ∈ Q, a ∈ T ∪ {ε}, Z₀ ∈ Г
2. Если D(q, ε, Z) ≠ ∅, то D(q, a, Z) = ∅ для всех a ∈ T

[править] Определение конфигурации МП автомата

Конфигурацией автомата с магазинной памятью (МП автомата) называется тройка (q, w, u), где

• q ∈ Q — текущее состояние магазинного устройства
• w ∈ T* — непрочитанная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w = ε, то считается, что входная лента прочитана
• u ∈ Г* — содержимое магазина; самый левый символ цепочки u считается вершиной магазина; если u = ε, то магазин считается пустым

[править] Определение языка, допускаемого МП автоматом

Цепочка w допускается МП автоматом, если (q₀, w, Z₀)⊢* (q, ε, u) для некоторых q ∈ F и u ∈ Г*. Язык, допускаемый МП-автоматом M — множество всех цепочек, допускаемых автоматом M.

[править] Определение недетерминированного МП автомата, допускающего опустошением магазина

Цепочка w допускается МП автоматом, если (q₀, w, Z₀)⊢* (q, ε, ε) для некоторого q ∈ Q. В таком случае говорят, что автомат допускает цепочку опустошением магазина.

[править] Определение множества FIRST(u)

Если u — любая строка символов грамматики, положим FIRST(u) — множество терминалов, с которых начинаются строки, выводимые из u. Если u ⇒* ε, то ε так же принадлежит FIRST(u).

[править] Определение замыкания множества LR(1) ситуаций

Пусть есть множество ситуаций I тогда определим функцию closure(I) как добавление к I ситуаций вида [B → .γ, b] для каждых ситуации [A → α.Bβ, a], правила вывода B → γ, принадлежащего Г, каждого терминала b из FIRST(βa), пока это возможно.

//Ильдар: Мне кажется это не совсем определение, а процедура построения. Я бы предварительно написал, что замыкание множества LR(1)-ситуаций, допустимых для некоторого активного префикса z, - это множество всех LR(1)-ситуаций, допустимых для этого префикса.

[править] Что такое леворекурсивная грамматика?

Грамматика называется леворекурсивной, если в ней имеется нетерминал A такой, что существует вывод A ⇒ Au для некоторой строки u.