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

     Грамматика типа 2 - контекстно-свободные, при чем в левой части нетерминал может быть всем, чем угодно. Они распознаются в информатике так называемыми автоматами с магазинной памятью (стековые автоматы). Используются для генерации элементов языков программирования (выражений, команд).

     Грамматика типа 3 - называют регулярными, самые простые и ограниченные грамматики, распознаются конечными автоматами. Используется для простых элементов языков (числа, константы, переменные).

 

      3.2 Неограниченные грамматики

       К типу 0 по классификации Хомского относятся неограниченные грамматики (также известные как грамматики с фразовой структурой). Это — все без исключения формальные грамматики. Для грамматики G = (T,N,P,S), α=T∪N все правила имеют вид:

• α→β, где α — любая цепочка, содержащая хотя бы один нетерминальный символ, а β — любая цепочка символов из алфавита.

     Практического применения в силу своей сложности  такие грамматики не имеют.

 

      3.3 Контекстно-зависимые грамматики

       Контекстно-зависимая грамматика - частный случай формальной грамматики, у которой левые и правые части всех продукций могут быть окружены терминальными и нетерминальными символами.

     Формальная  грамматика G = (N, T, S, P) является контекстно-зависимой, если все правила P имеют вид: αSβ → αωβ, где:

• S ∈ N - одиночный нетерминальный символ;
• ω ∈ (N ∪ T)⁺ - непустая цепочка, состоящая из терминальных и/или нетерминальных символов (А⁺ - множество всевозможных конечных последовательностей символов и слов в алфавите А, не включая пустое слово λ);
• α, β ∈ (N ∪ T)* - любая цепочка, состоящая из терминальных и/или нетерминальных символов (А* - множество конечных слов в алфавите А, включая пустое слово λ).

     Язык, который может быть задан Контекстно-зависимой грамматикой, называется контекстно-зависимым языком или Контекстно-зависимым языком.

 

      3.4 Контекстно-свободные грамматики

       Контекстно-свободная грамматика — частный случай формальной грамматики, у которой левые части всех продукций являются одиночными нетерминалами. Смысл термина «контекстно-свободная» заключается в том, что возможность применить продукцию к нетерминалу, в отличие от общего случая грамматики Хомского, не зависит от контекста этого нетерминала.

     Формальная  грамматика G = (N, T, S, P) является контекстно-свободной, если все правила P имеют вид: α→β, где:

• S ∈ N - одиночный нетерминальный символ;
• α ∈ (N ∪ T)⁺ - непустая цепочка, состоящая из терминальных и/или нетерминальных символов (А⁺ - множество всевозможных конечных последовательностей символов и слов в алфавите А, не включая пустое слово λ);
• β ∈ (N ∪ T)* - любая цепочка, состоящая из терминальных и/или нетерминальных символов (А* - множество конечных слов в алфавите А, включая пустое слово λ).

     Язык, который может быть задан Контекстно-свободной грамматикой, называется контекстно-свободным языком. Контекстно-свободная грамматика описывается БНФ (Формой Бэкуса-Наура).

     3.5 Регулярные грамматики

      Регулярные  языки  играют  важную  роль  в  математических  теориях  и  в приложениях. К наиболее известным формализмам, описывающим регулярные языки, относятся: регулярные выражения, конечные автоматы, регулярные грамматики.

       Они являются контекстно-свободными, но с ограниченными возможностями.

     Все регулярные грамматики могут быть разделены  на два эквивалентных класса, которые  будут иметь правила следующего вида:

• A→Ba, A→a или A→ε, где:

• ε∈T^*;
• A, B∈N (для леволинейных грамматик).

• A→aB, A→ε или A→a, где:

• a∈T^*;
• A, B∈N (для праволинейных грамматик).

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

       Регулярные выражения состоят из констант и операторов, которые определяют множества строк и множества операций на них соответственно. На данном конечном алфавите Σ определены следующие константы:

• пустое множество - ∅.
• пустая строка - ε обозначает строку, не содержащую ни одного символа. Эквивалентно «».
• символьный литерал - «a», где a — символ алфавита Σ.

     и следующие операции:

• конкатенация – сцепление строк в одну, RхS обозначает множество {αβ | α ∈ R & β ∈ S}. Например, {"А", "B"}{"x", "y"} = {"Ax", "Bx", "Ay", "By"}.
• дизъюнкция - R|S обозначает объединение R и S. Например, {"ab", "c"}|{"ab", "d", "ef"} = {"ab", "c", "d", "ef"}.
• звезда Клини  R* обозначает минимальное надмножество множества R, которое содержит ε и замкнуто относительно конкатенации. Это есть множество всех строк, полученных конкатенацией нуля или более строк из R. Например, {"0", "1"}* = {ε, "0", "1", "00", "01", "10", "11", "000", "001", "010", …}.

     Любая регулярная грамматика G=(N,T, P, S) может быть представлена направленным графом с помеченными узлами и дугами. Каждый узел такого графа может быть помечен символом, являющимся элементом множества N, кроме одного специального – «конечного» узла, помеченного символом #.

     Недетерминированный конечный автомат (НКА) — это пятерка A = (K, T, t, k, F), где:

     К — конечное множество состояний, или вершин;

     T — входной алфавит (также конечный);

     t — множество команд, или дуг;

     k — множество начальных состояний;

     F — множество заключительных состояний.

     Множество  t  можно также интерпретировать  как  отображение  KxT  в множество подмножеств K.

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

       Алгоритм построения НКА по праволинейной грамматике

     1. Множество вершин НКА состоит  из нетерминалов грамматики и  еще одной новой вершины F, которая  объявляется заключительной.

     2. Каждому  правилу  вида  А → аВ  в  автомате  соответствует  дуга  из  вершины  А  в вершину  В,  помеченная  символом  а: A⎯⎯^a→B.  Каждому  правилу  вида  A → a соответствует дуга  A⎯⎯^a→F . Других дуг в автомате нет.

     3. Начальной  вершиной  автомата  является  вершина,  соответствующая  начальному символу грамматики. Вершина В является заключительной, если в грамматике есть правило В → ε. Кроме того, заключительной является F, построенная на шаге 1.

     Алгоритм построения НКА по леволинейной грамматике

     1. Множество вершин НКА состоит из нетерминалов грамматики и еще одной новой вершины Н, которая объявляется начальной.

     2. Каждому  правилу   вида  А → Ва  в  автомате  соответствует  дуга  из  вершины   В  в вершину  А,  помеченная  символом  а: B⎯⎯^a→A.  Каждому  правилу вида  А → а соответствует дуга H⎯⎯^a→A. Других дуг нет.

     3. Заключительной  вершиной  автомата  является  вершина,  соответствующая начальному  символу грамматики. Вершина B является  начальной, если в грамматике  есть  правило B → ε. Кроме   того,  начальной  является  вершина H,  построенная  на шаге 1.

 

     Для  любого НКА, имеющего несколько начальных  вершин, можно построить эквивалентный  ему НКА  с  единственной  начальной  вершиной. По  такому  автомату легко  построить эквивалентную праволинейную грамматику.

      

     Алгоритм  построения праволинейной грамматики  по НКА с единственной начальной  вершиной

     1. Нетерминалами грамматики будут  вершины автомата, терминалами —  пометки дуг. 

     2. Для каждой дуги вида A⎯⎯^a→B в  грамматику добавляется правило А → аВ. Для каждой заключительной вершины B в грамматику добавляется правило В → ε.

     3. Начальным символом является  нетерминал, соответствующий начальной  вершине. 

     4. К  построенной  по  пунктам  1—3 грамматике  применить   алгоритм  устранения  ε-правил,  затем —  алгоритм  удаления  бесполезных символов (приведения грамматики).

     Для  построения  леволинейной  грамматики  по  НКА,  НКА  следует  сначала  преобразовать  в  эквивалентный  автомат  с  единственной  заключительной  вершиной (такое преобразование всегда возможно).

      

     Алгоритм  построения леволинейной грамматики по НКА с единственным заключительным состоянием

     1. Нетерминалами грамматики будут  вершины автомата, терминалами —  пометки дуг. 

     2. Для каждой дуги A⎯⎯^a→B в грамматику добавляется правило В → Аа. Для каждой начальной вершины В в грамматику добавляется правило В → ε.

     3. Начальным  символом  будет   нетерминал,  соответствующий   заключительной вершине. 

     4. К  построенной  по  пунктам  1—3 грамматике  применить   алгоритм  устранения  ε-правил, затем  — алгоритм приведения грамматики.

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

     Все автоматы в примерах 1—4 не являются детерминированными.