Теоретический минимум 2007, страница 2

Верно и обратное — для любого регулярного языка можнопостроить распознающий его конечный автомат.Определение регулярной грамматикиРегулярные грамматики — праволинейные (A → w, A → wB, w ∈ T*), леволинейные(A → w, A → Bw, w ∈ T*).Соотношение, между языками, порождаемымиКС-грамматиками, и языками, допускаемыминедетерминированными МП автоматамиОни совпадают.Определение контекстно-свободной грамматикиA → α, α ∈ (N ∪ T)*Стр. 8 из 13Определение левостороннего вывода в КС-грамматикеВывод, в котором в любой сентенциальной форме на каждом шаге делаетсяподстановка самого левого нетерминала, называется левосторонним.Определение правостороннего вывода в КС-грамматикеВывод, в котором в любой сентенциальной форме на каждом шаге делаетсяподстановка самого правого нетерминала, называется правосторонним.Определение сентенциальной формыСентенциальная форма — цепочка (состоящая, в общем случае, из терминалов инетерминалов), выводимая из аксиомы грамматикиОпределение приведенной грамматикиГрамматика называется приведённой, если она не содержит бесполезных символов.Определение множества FOLLOW(A)Пусть A — нетерминал.

Тогда FOLLOW(A) — множество терминалов a, которые могутпоявиться непосредственно справа от A в некоторой сентенциальной форме, то есть,множество терминалов a таких, что существует вывод вида S ⇒* uAav для некоторыхu и v.Определение LR(1) ситуацииLR(1)-ситуацией называется пара [A → α . β, a], где A → α β — правило грамматики,a — терминал или правый концевой маркер $. Вторая компонента ситуацииназывается аванцепочкой.Сформулировать соотношение между языками,порождаемыми праволинейными грамматиками иязыками, допускаемыми КАДля любой праволинейной грамматики существует конечный автомат, проверяющийСтр.

9 из 13порождаемый грамматикой язык. Для любого конечного автомата существуетправолинейная грамматика, порождающая проверяемый конечным автоматом язык.Определение однозначной КС-грамматикиКС грамматика называется однозначной или детерминированной, если всякаявыводимая терминальная цепочка имеет только одно дерево вывода (соотвественнотолько один левый и только один правый вывод).Определение неоднозначной КС-грамматикиКС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка α⊂L(G), для которой может быть построено два или более различных деревьеввывода.Определение контекстно-свободной грамматики безε-правилA → α, α ∈ (N ∪ T)+допускается S → ε, если S не входит ни в какую правую частьОпределение вывода в КС-грамматикеОпределим на множестве (N ∪ T)* грамматики G = (N, T, P, S) бинарное отношениевыводимости «⇒» следующим образом: если δ → γ ∈ P, то αδβ ⇒ αγβ для всех α, β∈ (N ∪ T)*.

Если α1 ⇒ α 2, то α2 непосредственно выводима из α1.Если α ⇒k β (k ≥ 0), то существует последовательность шаговγ0 ⇒ γ1 ⇒ γ2 ⇒ … ⇒ γk − 1 ⇒ γkгде α = γ0 и β = γk. Последовательность цепочек γ0, γ1, γ2, …, γk − 1, γk в этом случаеназывается выводом β из α.Определение языка, порождаемого КС-грамматикойЯзыком, порождаемым грамматикой G = (N, T, P, S) (обозначается L(G)) называетсямножество всех цепочек терминалов, выводимых из аксиомы, то есть:Стр. 10 из 13L(G) = {w | w ∈ T*, S ⇒+ w}Определение недетерминированного МП автоматаНедетерминированный автомат с магазинной памятью (МП-автомат) — семёрка M =(Q, T, Г, D, q0, Z0, F), где1.

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

q0 ∈Q — начальное состояние управляющего устройства6. Z0 ∈Г — символ, находящийся в магазине в начальный момент (начальныйсимвол магазина)7. F ⊆Q — множество заключительных состоянийОпределение детерминированного МП автоматаДетерминированный автомат с магазинной памятью (МП-автомат) — семёрка M = (Q,T, Г, D, q0, Z0, F), где1.

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

Множество D(q, a, Z) содержит не более одного элемента для любых q ∈ Q,a ∈ T ∪ {ε}, Z0 ∈ Г2. Если D(q, ε, Z) ≠ ∅, то D(q, a, Z) = ∅ для всех a ∈ TСтр. 11 из 13Определение конфигурации МП автоматаКонфигурацией автомата с магазинной памятью (МП автомата) называется тройка (q,w, u), гдеq ∈ Q — текущее состояние магазинного устройстваw ∈ T* — непрочитанная часть входной цепочки; первый символ цепочки wнаходится под входной головкой; если w = ε, то считается, что входная лентапрочитанаu ∈ Г* — содержимое магазина; самый левый символ цепочки u считаетсявершиной магазина; если u = ε, то магазин считается пустымОпределение языка, допускаемого МП автоматомЦепочка w допускается МП автоматом, если (q0, w, Z0) * (q, ε, u) для некоторых q ∈ Fи u ∈ Г*.

Язык, допускаемый МП-автоматом M — множество всех цепочек,допускаемых автоматом M.Определение недетерминированного МП автомата,допускающего опустошением магазинаЦепочка w допускается МП автоматом, если (q0, w, Z0) * (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), пока это возможно.//Ильдар: Мне кажется это не совсем определение, а процедура построения. Я быСтр. 12 из 13предварительно написал, что замыкание множества LR(1)-ситуаций, допустимых длянекоторого активного префикса z, - это множество всех LR(1)-ситуаций, допустимыхдля этого префикса.Что такое леворекурсивная грамматика?Грамматика называется леворекурсивной, если в ней имеется нетерминал A такой,что существует вывод A ⇒ Au для некоторой строки u.Конструирование Компиляторов01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16Календарьпн пн пн пн пнФевральМарт12 19 2605 12 19 26Апрель 02 09 16 23 30Май07 14 21 28Материалы к экзаменуПроведение экзамена | Определения | Теормин: 2007, 2009 | Алгоритмы решения задачПолучено с h p://esyr.nizm.ru/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_%282007%29Последнее изменение этой страницы: 17:29, 31 мая 2009.Стр.

13 из 13.