Формальные грамматики

Основные понятия

Алфавит - это конечное множество символов. Цепочка – последовательность символов. Терминальная цепочка – последовательность терминальных символов. Язык – множество терминальных цепочек. Грамматика – это четвёрка G = (N, T, P, S), где:

• N – множество нетерминальных символов (напр. A, B, C...);

• T – алфавит терминальных символов (N ∩ T = ∅);

• P – конечное множество правил вывода P = {α → β | α ∈ (N ∪ T)^{+}; β ∈ (N ∪ T)^{∗}};

• S ∈ N – аксиома (или начальный символ) грамматики. Язык, порождённый грамматикой – множество всех терминальных цепочек, выводимых из аксиомы грамматики. L(G) = {W | W ∈ T^{∗}, S ⇒^{+} W } Сентенциальная форма – последовательность символов (терминалов и нетерминалов), выводимых из начального символа (аксиомы). Основа цепочки – это подцепочка сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода. Основа сентенциальной формы – позиция в сентенциальной форме, которая заменена в следующей сентенциальной форме. Основа правой сентенциальной формы z – это правило вывода A → v и позиция в z, в которой может быть найдена цепочка v такая, что в результате замены v на A получается предыдущая сентенциальная форма в правостороннем выводе z. Таким образом, если S ⇒_{r}avb, то A → v в позиции, следующей за a - это основа цепочки avb. Подцепочка b справа от основы содержит только терминальные символы. Грамматика называется неоднозначной, если для некоторой цепочки существует хотя бы два дерева вывода. Символ x называется недостижимым, если он не входит ни в одну сентенциальную форму (не существует вывода S ⇒^{∗} αxβ). Символ x называется бесплодным, если из него нельзя вывести ни одну терминальную цепочку (не существует вывода x ⇒ w, w ∈ T^{∗}). Бесполезный символ – это недостижимый или бесплодный символ. Приведённая грамматика – это грамматика, не содержащая бесплодных и недостижимых символов. Множество F IRST (A) – множество терминальных символов, которыми начинаются цепочки, выводимые из A в грамматике G.

Множество F OLLOW (A) – множество терминальных символов, которые следуют за цепочками, выводимыми из A в грамматике G. Множество F IRST 1 – множество всех терминальных символов, с которых может начинаться цепочка терминальных символов, выводимых из цели грамматики или ϵ, если u ⇒^{∗} ϵ. Лемма о разрастании Для любого КС-свободного языка L существуют целые числа l, k такие, что ∀α ∈ L, | α |> l представима в виде α = uvwxy, где:

• | vwx |≤ k;

• vx ≠ ϵ;

• uv^{i}wx^{i}y ∈ L ∀i ≥ 0. Лемма о накачке Для любого регулярого языка L существует натуральное число p(L) ≥ 1 такое, что ∀α ∈ L, | w |≥ p, представима в виде α = xyz, где:

• | y |≥ 1;

• | xy |≤ p;

• xy^{i}z ∈ L ∀i ≥ 0.

Иерархия Хомского

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

• каждое правило грамматики, кроме S → ϵ, имеет вид α → β, | α |≤| β |;

• в том случае, когда S → ϵ ∈ P, символ S не встречается в правых частях правил; то грамматику называют грамматикой типа 1, или неукорачивающей грамматикой.

Если каждое правило p ∈ P грамматики имеет вид A → α, A ∈ N, α ∈ (N ∪ T)^{∗}, то такая грамматика называется грамматикой типа 2 или контекстно-свободной грамматикой. Если каждое правило p ∈ P имеет вид A → xB или A → x (соответственно A → Bx или A → x), где A, B ∈ N, x ∈ T^{∗}, то такая грамматика называется грамматикой типа 3 или леволинейной (соответственно, праволинейной) грамматикой. Из определения иерархии следует, что Z_{0} ⊇ Z_{1} ⊇ Z_{2} ⊇ Z_{3}. Утверждение Z_{0} ⊃ Z_{1} ⊃ Z_{2} ⊃ Z_{3}. Данное утверждение доказывается конструктивно (путём построения соответствующих грамматик). Грамматика находится в нормальной форме Хомского, если правила вывода имеют вид:

• либо A → BC; A, B, C ∈ N;

• либо A → a; a ∈ T^{+};

• либо S → ϵ, и в этом случае S не встречается в правых частях правил.

Выводы, однозначность, детерминированность и прочие вопросы

Определим на множестве (N ∪ T)^{∗} грамматики G = (N, T, P, S) бинарное отношение выводимости ⇒ следующим образом: если δ → γ ∈ P, то αδβ ⇒ αγβ ∀α, β ∈ (N ∪ T)^{∗}.

• Eсли α_{1} ⇒ α_{2}, то α_{2} непосредственно выводима из α_{1}.

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

γ_{0} ⇒ γ_{1} ⇒ … ⇒ Γ_{k}, где α = γ_{0} и beta = γ_{k}. Последовательность цепочек γ_{0}, γ_{1}, …, γ_{k} в этом случае называется выводом β из α. КС-грамматика называется однозначной или детерминированной, если всякая выводимая терминальная цепочка имеет только одно дерево вывода (соотвественно только один левый и только один правый вывод). КС-грамматика называется неоднозначной, если для некоторой цепочки существует хотя бы два различных дерева вывода. Левосторонний вывод – такой вывод, на каждом шаге которого заменяется самый левый нетерминал. Правосторонний вывод – такой вывод, на каждом шаге которого заменяется самый правый нетерминал. Грамматика называется леворекурсивной, если в ней имеется нетерминал A такой, что существует вывод A ⇒^{+} Aw для некоторой цепочки w. Атрибутная грамматика – это четвёрка AG = (G, A_{S}, A_{I}, R), где:

• G = (N, T, P, S) – приведённая контекстно-свободная грамматика;

• A_{S} - конечное множество синтезируемых элементов;

• A_{I} –конечное множество наследуемых атрибутов, A_{S} ∩ A_{I} = ∅;

• R – конечное множество семантических правил.

Машина Тьюринга и связанные определения

Недетерминированная машина Тьюринга – это шестёрка M = (Q, Γ, T, F, q_{0}, σ), где:

• Q – конечное непустое множество состояний;

• Γ – конечный алфавит;

• T – входной алфавит, T ⊆ Γ ∪ ϵ;

• q_{0} ∈ Q – начальное состояние;

• F ⊆ Q – множество конечных состояний; • σ – функция переходов, определённая как отображение

σ : (Q \ F) × Γ → 2^{Q×Γ×{L,R}}. Детерминированная машина Тьюринга – это шестёрка M = (Q, Γ, T, F, q_{0}, σ), где:

• Q – конечное непустое множество состояний;

• Γ – конечный алфавит;

• T – входной алфавит, T ⊆ Γ ∪ ϵ;

• q_{0} ∈ Q – начальное состояние;

• F ⊆ Q – множество конечных состояний;

• σ – функция переходов, определённая как отображение

σ : (Q \ F) × Γ → Q × Γ × {L, R}. Детерминированная машина Тьюринга из данного состояния по данному символу может сделать не более одного перехода, недетерминированная же таким свойством не обладает. Конфигурацией машины Тьюринга называется тройка (q, w, i), где:

• q ∈ Q – состояние машины Тьюринга;

• w ∈ Γ^{∗} – вход, помещаемый на ленту машины Тьюринга (w = a_{1} … a_{n});

• i ∈ Z – положение головки машины Тьюринга. Язык, допускаемый машиной Тьюринга – множество таких слов w, что машина Тьюринга, находясь в состоянии (q_{0}, w, 1), может достигнуть через конечное число переходов состояния q ∈ F. Линейно-ограниченный автомат – это недетерминированная машина Тьюринга, которая не может выходить за область входной строки. Утверждения

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

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

Регулярные множества, выражения и грамматики

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

• {a} – регулярное множество в алфавите T для каждого a ∈ T;

• {ϵ} – регулярное множество в алфавите T;

• если P и Q – регулярные множества в алфавите T, то регулярны множе-

ства:

• P ∪ T (объединение);

• P Q (конкатенация, {pq | p ∈ P, q ∈ Q};

• P^{∗} (итерация, P^{∗} = {ϵ} ∪ P ∪ P P ∪ P P P ∪ …);

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

• ∅ – обозначает множество ∅ в данном алфавите T;

• a - обозначает множество {a};

• ϵ – обозначает множество {ϵ} в данном алфавите T;

• если регулярные выражения p и q обозначают регулярные множества P и

Q в данном алфавите T соответственно, то регулярное выражение: • (p | q) обозначает множество P ∪ Q в данном алфавите T;

• (pq) обозначает множество P Q в данном алфавите T;

• (p^{∗}) обозначает множество P^{∗} в данном алфавите T;

• ничто другое не является регулярным выражением в данном алфавите T. Регулярные грамматики – это праволинейные и леволинейные грамматики. Функция nullable(n) для каждого узла n синтаксического дерева регулярных выражений даёт значение true, если поддеревья данного узла могут породить пустое слово, и false в противном случае. Функция firstpos(n) для каждого узла n синтаксического дерева регулярных выражений даёт множество позиций, которые соответствуют первым символам в цепочках, генерируемых подвыражением с вершиной n. Функция lastpos(n) для каждого узла n синтаксического дерева регулярных

\begin{matrix}узел n & firstpos(n) \\ ϵ & ∅ \\ i ≠ ϵ & \{i\} \\ u | v & firstpos(u)|firstpos(v) \\ u.v & nullable(u) ? firstpos(u) ∪ firstpos(v) : firstpos(u) \\ v^{∗} & firstpos(v) \end{matrix}

Таблица 1: Построение firstpos(n)

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

\begin{matrix}узел n & lastpos(n) \\ ϵ & ∅ \\ i ≠ ϵ & \{i\} \\ u | v & lastpos(u)|lastpos(v) \\ u.v & nullable(v) ? lastpos(u) ∪ lastpos(v) : lastpos(v) \\ v^{∗} & lastpos(v) \end{matrix}

Таблица 2: Построение lastpos(n)

Автоматы

Недетерминированный конечный автомат – это пятёрка M = (Q, T, F, q_{0}, σ), где:

• Q – конечное непустое множество состояний;

• T – входной алфавит;

• q_{0} ∈ Q – начальное состояние;

• F ⊆ Q – множество конечных состояний;

• σ – функция переходов, определённая как отображение

σ : Q × (T ∪ {ϵ}) → 2^{Q}, такое, что σ(q, a) = {r : q →_{a} r}. Детерминированный конечный автомат – это пятёрка M = (Q, T, F, q_{0}, σ), где:

• Q – конечное непустое множество состояний;

• T – конечный входной алфавит;

• q_{0} ∈ Q – начальное состояние;

• F ⊆ Q – множество конечных состояний;

• σ – функция переходов, определённая как отображение σ : Q × T → Q Недетерминированный конечный автомат является обобщением детерминированного. Утверждение Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали (такие автоматы называются эквивалентными). В детерменированном автомате из одного состояния допускается не более одного перехода для каждого символа алфавита, в недетерменированном - произвольное количество. Кроме того, в НКА возможны ϵ-переходы. Конфигурацией автомата M = (Q, T, D, q_{0}, σ) называется пара (q, ω) ∈ Q × T^{∗}, где q – текущее состояние управляющего устройства, а ω – цепочка символов на входной ленте, состоящая из символов под головкой и всех символов справа от неё. Два состояния q_{i} и q_{j} называются эквивалентными (q_{i} ∼ q_{j}), если ∀z ∈ T^{∗}σ(q_{i}, z) ∈ T ⇔ σ(q_{j}, z) inT.

Два состояния q_{i} и q_{j} называются различимыми, если они не являются эквивалентными. Автомат M допускает цепочку ω, если M(q_{0}, ω) | −^{∗}(q, ω), ∀q ∈ σ. Языком, допускаемым автоматом M, называется множество входных цепочек, допускаемых автоматом M, то есть множество L(M) = {ω | ω ∈ T^{∗} и (q_{0}, ω) | −^{∗}(q, ϵ), ∀q ∈ σ}. ϵ-замыкание множества состояний R, R ⊆ Q – множество состояний НКА, достижимых из состояний, входящих в R, посредством только переходов по ϵ, то есть множество S = U_{q∈R}{p | (q, ϵ) | −^{∗}(p, ϵ)}. Расширенная функция переходов множества состояний R, R ⊆ Q по a – множество состояний КА, в которые есть переход на входе a для состояний из R, то есть множество S = U_{q∈R}{p | p ∈ σ(q, a)}.

Автоматы с магазинной памятью

Недетерминированный МП-автомат – это семёрка M = (Q, T, Γ, σ, q_{0}, Z_{0}, F), где:

• Q – конечное множество состояний, представляющее всевозможные состояния управляющего устройства;

• T – конечный входной алфавит;

• Γ – конечный алфавит магазинных символов;

• σ – отображение Q × (T ∪ {ϵ}) × Γ → 2^{Q×Γ^{∗}}, называемое функцией переходов;

• q_{0} ∈ Q – начальное состояние управляющего устройства;

• Z_{0} ∈ Γ – символ, находящийся в магазине в начальный момент (начальный символ магазина);

• F ⊆ Q – множество заключительных состояний. Детерминированный МП-автомат – это семёрка M = (Q, T, Γ, σ, q_{0}, Z_{0}, F), где:

• Q – конечное множество состояний, представляющее всевозможные состояния управляющего устройства;

• T – конечный входной алфавит;

• Γ – конечный алфавит магазинных символов;

• σ – отображение Q × (T ∪ {ϵ}) × Γ → Q × Γ^{∗}, называемое функцией переходов;

• q_{0} ∈ Q – начальное состояние управляющего устройства;

• Z_{0} ∈ Γ – символ, находящийся в магазине в начальный момент (начальный символ магазина);

• F ⊆ Q – множество заключительных состояний. Кроме того, должны выполняться следующие условия:

• множество D(q, a, Z) содержит не более одного элемента ∀q ∈ Q, a ∈ T ∪ {ϵ}, Z_{0} ∈ Γ;

• если D(q, ϵ, Z) ≠ ∅, то D(q, a, Z) = ∅∀a ∈ T. Конфигурацией МП-автомата называется тройка (q, w, u), где

• q ∈ Q – текущее состояние магазинного устройства;

• w ∈ T^{∗} – непрочитанная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w = ϵ, то считается, что входная лента прочитана;

• u ∈ Γ^{∗} — содержимое магазина; самый левый символ цепочки u считается

вершиной магазина; если u = ϵ, то магазин считается пустым. Тактом работы МП-автомата называется бинарное отношение | −, определённое на множестве конфигураций: (q, aw, Zu) | −(p, w, vu), если D(q, a, z) ∋ (p, v); q, p ∈ Q, a ∈ T ∪ {ϵ}, w ∈ T^{∗}, Z ∈ Γ, u, v ∈ Γ^{∗}. Цепочка w допускается МП-автоматом, если (q_{0}, w, Z_{0}) | −^{∗}(q, ϵ, u) для некоторых q ∈ F и u ∈ Γ^{∗}. Язык, допускаемый МП-автоматом – множество всех цепочек, допускаемых этим автоматом. В случае, когда цепочка w допускается МП-автоматом, если (q_{0}, w, Z_{0}) | −^{∗}(q, ϵ, ϵ) для некоторого q ∈ Q, говорят, что автомат допускает цепочку опустошением магазина. Утверждение Языки, порождаемые КС-грамматиками, и языки, допускаемые недетерминированными МП-автоматами, совпадают.

LL(k) и LR(k)

Контекстно-свободная грамматика называется LL(1) грамматикой тогда и только тогда, когда выполняются следующие два условия:

• для каждого нетерминала, являющегося левой частью нескольких правил, A → α_{1}|α_{2}| … |α_{n} необходимо, чтобы F IRST (α_{i})∩F IRST (α_{j}) = ∅, i ≠ j;

• для каждого аннулирующего нетерминала A ⇒^{∗} $ необходимо, чтобы

F IRST (A) ∩ F OLLOW (A) = ∅. Грамматика, для которой таблицы анализа не имеют неоднозначно определённых входов, называется LL(1). Грамматика, для которой можно построить таблицу LR разбора, называется LR грамматикой. Грамматика называется LR(1), если из условий:

• S′ ⇒_{r}uAw ⇒_{r}uvw;

• S′ ⇒_{r}zBx ⇒_{r}uvy;

• F IRST (v) = F IRST (y) следует, что uAy = zBx (т.е. u = z, A = B и x = y). Конфигурация LR анализатора – это пара, первая компонента которой – содержимое стека, а вторая – непросмотренный вход: (S_{0}X_{1}S_{1}X_{2}S_{2} … X_{m}S_{m}, A_{i}A_{i+1} … A_{n}$). Эта конфигурация соответствует правой сентенциальной форме X_{1}X_{2} … mA_{i}A_{i+1} … A_{n}. Замыкание множества LR(1) ситуаций, допустимых для некоторого активного префикса z – это множество всех LR(1) ситуаций, допустимых для этого префикса. LR анализатор выполняет 4 типа действий:

• Shift;

• Reduce;

• Accept;

• Reject. При выполнении действия Shift, верхний символ входа переносится в магазин, а затем на верх магазина помещается состояние action (предыдущее состояние, взятый символ. При выполнении действия Reduce, из стека убирается правая часть правила и добавляется левая и состояние goto (последнее состояние в магазине, символ из левой части правила). В канонической системе множеств LR(1) ситуаций может возникать 2 типа конфликтов:

• Shift - Reduce (невозможно выбрать действие);

• Reduce - Reduce (невозможно выбрать правило, относительно которого применяется действие).