Теормин (2009), страница 2

Определение контекстно-свободной грамматики без е-правилГрамматика называется контекстно-свободной без е-правил, если:1) Если каждое правило грамматики имеет вид A → α, где A ∈ N, α ∈ (N ∪ T)+2) Допускается S → , если S не входит ни в какую правую часть29. Определение контекстно-свободной грамматикиЕсли каждое правило грамматики имеет вид A → α, где A ∈ N, α ∈ (N ∪ T)*, то ее называют контекстно-свободной.30. Определение вывода в КС-грамматикеОпределим на множестве (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 в этом случае называется выводом β из α.31.

Определение языка, порождаемого КС-грамматикойЯзыком, порождаемым грамматикой G = (N, T, P, S) (обозначается L(G)) называется множество всех цепочек терминалов,выводимых из аксиомы, то есть: L(G) = {w | w ∈ T*, S ⇒+ w}32. Определение сентенциальной формыСентенциальная форма — последовательность символов (терминалов и нетерминалов), выводимых из аксиомы.33. Определение однозначной КС-грамматикиУпорядоченное помеченное дерево D называется деревом вывода цепочки ω КС-грамматике G=(N,T,P,S), если выполненыследующие условия:1) корень дерева D помечен S2) каждый лист помечен либо a ∈ T, либо 3) каждый внутренняя вершина помечена нетерминалом A ∈ N.4) если X – нетерминал, которым помечена внутренняя вершина и X1,…Xn – метки ее прямых потомков в указанномпорядке, то X → X1,…Xn – правило из множества P.5) Цепочка, составленная из выписанных слева направо меток листьев, равна w.КС грамматика называется однозначной или детерминированной, если всякая выводимая терминальная цепочка имееттолько одно дерево вывода.34.

Определение неоднозначной КС-грамматикиКС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка α ⊂ L(G), для которой может бытьпостроено два или более различных деревьев вывода.35. Определение недетерминированного МП автоматаНедетерминированный автомат с магазинной памятью (МП-автомат) — семёрка 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 — множество заключительных состояний36. Определение детерминированного МП автоматаДетерминированный автомат с магазинной памятью (МП-автомат) — семёрка 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 ∪ {ε}, Z ∈ Г2. Если D(q, ε, Z) ≠ ∅, то D(q, a, Z) = ∅ для всех a ∈ T37. Определение конфигурации МП автоматаКонфигурацией автомата с магазинной памятью (МП автомата) называется тройка (q, w, u), гдеq ∈ Q — текущее состояние магазинного устройстваw ∈ T* — непрочитанная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w = ε,то считается, что входная лента прочитанаu ∈ Г* — содержимое магазина; самый левый символ цепочки u считается вершиной магазина; если u = ε, то магазинсчитается пустым38.

Определение языка, допускаемого МП автоматомЦепочка w допускается МП автоматом M = (Q, T, Г, D, q0, Z0, F), если (q0, w, Z0)⊢* (q, ε, u) для некоторых q ∈ F и u ∈ Г*.Язык, допускаемый МП-автоматом M — множество всех цепочек, допускаемых автоматом M.39. Что означает то, что недетерминированный МП автомат допускает опустошением магазинаЦепочка w допускается МП автоматом, если (q0, w, Z0)⊢* (q, ε, ε) для некоторого q ∈ Q. В таком случае говорят, что автоматдопускает цепочку опустошением магазина.40.

Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыминедетерминированными МП автоматамиЯзык является КС тогда и только тогда, когда он допускается магазинным автоматом.41. Формулировка леммы о разрастании для КС-языковДля любого контекстно-свободного языка L ∃ l: ∀ α ∈ L, |α| ≥ l, α = xyz1. |xy| ≤ l2. |y| > 03. xyiz ∈ L, ∀ i ≥ 042. Определение нормальной формы Хомского для КС-грамматикиГрамматика находится в нормальной форме Хомского, если правила вывода имеют вид: A → BC; где B, C ∈ N A→a S → ε (если ε ∈ L; S не входит ни в одну правую часть)43.

Определение правостороннего вывода в КС-грамматикеВывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого правого нетерминала,называется правосторонним.44. Определение левостороннего вывода в КС-грамматикиВывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала,называется левосторонним.45. Какая грамматика называется леворекурсивной?Грамматика называется леворекурсивной, если в ней имеется нетерминал A такой, что существует вывод A ⇒+ Au длянекоторой цепочки u.46.

Определение множества FIRST1В1. FIRST1 — множество всех терминальных символов, с которых может начинаться цепочка терминальных символов,выводимых из цели грамматики или ε, если u ⇒* ε.В2. Множество FIRST(A) — множество терминальных символов, которыми начинаются цепочки, выводимые из A вграмматике G = (VT, VN, P, S), то есть, FIRST(A) = {a ∈ VT | A ⇒ aα, A ∈ VN, α ∈ (VT ∪ VN)*}47. Определение множества FOLLOW1Пусть A — нетерминал. Тогда FOLLOW(A) — множество терминалов a, которые могут появиться непосредственно справаот A в некоторой сентенциальной форме, то есть, множество терминалов a таких, что существует вывод вида S ⇒* uAavдля некоторых u и v.48. Определение LL(1) ГрамматикиГрамматики, для которых таблица предсказывающего анализатора не имеет неоднозначно определенных входов,называются LL(1)-грамматиками.49.

Определение LR(1) ситуацииLR(1)-ситуацией называется пара [A → α.β, a], где A → αβ — правило грамматики, a — терминал или правый концевоймаркер $. Вторая компонента ситуации называется аванцепочкой.50. Определение LR(1) грамматикиВ1. Если для КС-грамматики G функция Action, полученная в результате работы алгоритма построения LR(1)-таблицы, несодержит неоднозначно определенных входов, то грамматика называется LR(1)-грамматикой.В2.

Грамматика называется LR(1)-грамматикой, если из условий:1) S’ ⇒r* uAw ⇒ r uvw,2) S’ ⇒ r * zBx ⇒ r uvy,3) FIRST(w) = FIRST(y)cледует, что uAy = zBx (т.е. u=z, A=B, x=y).51. Какого типа конфликты могут появиться в канонической системе множеств LR(1) ситуаций?Анализатор типа сдвиг-свертка при анализе некоторой цепочки может достигнуть конфигурации, в которой он, знаясодержимое магазина и следующий входной символ, не может решить:1) Делать ли сдвиг или свертку (конфликт сдвиг/свертка)2) Какую из нескольких сверток применить (конфликт свертка/свертка)52.

Определение конфигурации LR-анализатораКонфигурация LR анализатора — пара, первая компонента которой —содержимое стека, вторая — непросмотренныйвход:(S0 X1 S1 X2 S2 … Xm Sm, ai ai + 1 … an $).Эта конфигурация соответствует правой сентенциальной форме X 1 X2 … Xm ai ai + 1 … an.53. Как меняется конфигурация LR-анализатора при действии reduce?Если выполняется reduce A→µ, то анализатор выполняет свертку, переходя в конфигурацию(S0 X1 S1 X2 S2 … Xm-r Sm-rAS, ai ai + 1 … an $), где S = Goto[Sm-r,A] и r – длина µ, правой части вывода.Анализатор сначала удаляет из магазина r символов состояния и r символов грамматики, так что на верхушкеоказывается состояние Sm-r.

Затем анализатор помещает в магазин A – левую часть правила вывода, и S – символсостояния, определяемый Goto[Sm-r,A]. На шаге свертки текущий входной символ не меняется. Для LR(1)-анализаторов Xmr … Xm – последовательность символов грамматики, удаляемых из магазина, всегда соответствует µ - правой частиправила вывода, по которому делается свертка.54. Какие типы действий выполняет LR-анализатор?Анализатор выполняет 4 вида действий:1) Сдвиг2) Свертка3) Успешное завершение разбора4) Обнаружение ошибки55.

Как меняется конфигурация LR-анализатора при действии shift?Если выполняется shift S , то анализатор выполняет сдвиг, переходя в конфигурацию(S0 X1 S1 X2 S2 … Xm SmaiS, ai + 1 … an $).Таким образом, в магазин помещаются входной символ ai и символ состояния S, определяемый Action[Sm, ai]. Текущимвходным символом становится ai + 1.56. Что такое основа правой сентенциальной формыПодцепочка сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода,свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода,называется основой цепочки.Составители и редакторы: Кононов Алексей,Коляскина Екатерина, Кийко Александргруппа 328.Часть материалов взята с http://www.esyr.us2009 год..