Формальная грамматика. Терминальный и нетерминальные знаки. Продукция. Сентенциальная форма.


Вопрос 3. Формальная грамматика. Терминальный и нетерминальные знаки. Продукция. Сентенциальная форма.
Формальной грамматикой G называется алгебраическая система G = < V, W, P, I > , где
V — алфавит терминальных знаков (основных) , W — алфавит нетерминальных знаков (вспомогательных) , P — множество продукций (правил вывода) , I — аксиома грамматики (начальный знак) , I ? W
Пример формальной грамматики : зададим 4 множества: G = < V, W, P, I >
V = {a; b} ; W = {I, A, B} ; P = {I?A, I?B, A?a, A?aA, B?b, B?bB}
I ? A ? a ; I ? A ? aA ? aa ; …. ; I ? A ? aA ? … ? aa..a
Язык, порождаемый грамматикой G является множеством строк состоящим из знака А или из знака В.
Сентенциальная форма грамматики G есть строка ? ? ( V ? W )* такая, что существует последовательность вывода I? ?1? ?2 ? … ? ?n ? ? , IG ? ? приводящая к этой строке или строка ? порождена грамматикой G.
Сентенция грамматики G — это сентенциальная форма не имеющая нетерминальных знаков ? ? V* , ? IG ? ?.
Теорема 1.4. Классификация формальных грамматик.
Формальным языком L, порождаемый грамматикой G называется множество всех сентенций G.
Формальный язык : L(G) = {x | x ? V* , IG ? x} , где G = <V, W, P, I >
Эквивалентные грамматики — это грамматики G1 и G2 , которые порождают один и тот же язык.

Вопрос 4. Способы задания формальной грамматики. Синтаксические диаграммы. Нотация Бэкуса-Наура.
Синтаксические диаграммы — это способ задания формального языка. Это — ориентированный граф с вершинами 4-х типов. Вершина 1-го типа I — начальная вершина графа, ? — заключительная вершина , (x) (x — терминальный знак) — терминальный узел. [y] (y — нетерминальный знак) — нетерминальный узел или вершина, а также из дуг соединяющих эти вершины и задающие направление обхода графа.
I ? I , ? ? строка ; (x) ? x ? V ; [y] ? y ? W , дуги p ? p ? P
Нотация Наура-Бэкуса. (БНФ)
Правила нотации:
1. Нетерминальные знаки заключаются в угловые скобки <…>
2. Вместо знака продукции ? используется знак := или ::
3. Знак | означает “или” и разделяет альтернативные строки в правой части определения (продукции).

< два_унарных_числа>::=<унарное_А> | <унарное_В>
<унарное_А>::=а | а <унарное_А>
<унарное_В>::=b | b <унарное_В>
Строгое определение продукции. Пусть задана грамматика G=<V, W, P, I >. Пускай строка ?1 ? ?2 ? (V ? W)+, т.е. состоит из терминальных и нетерминальных знаков не равных пустой строке. Пусть имеется продукция вида ? ? ? , где ? ? (V ? W)+ , ?1 , ?2 , ? ? (V ? W)*. Подстрока ? в ?1 ? ?2 может быть заменена ?1 ? ?2 ? ?1 ? ?2

Вопрос 5. Классификация языков по Хомскому.
Грамматика типа 0, имеет особенность, что на всю продукцию этой грамматики не накладывается ограничений: ??? , ? ? (V?W)+ , ? ? (V?W)* .
Грамматика типа 1 (контекстная, неукорачивающая). На неё накладываются следующие ограничения : ? А ? ? ? ? ? ; ? , ? ? (V?W)* , ? ? (V?W)+ ; A ? W.
Грамматика типа 2 (контекстно-свободная), продукции которой имеют вид : А? ? , A?W , ? ? (V?W)*
Грамматика типа 3 (регулярная) : А? а | А ? aB ; a ? V ; A ,B ? W
Замечание: один и тот же язык может порождать грамматики разных типов, поэтому классифицировать язык на основе классификации порождающих их грамматик не всегда оправданно.

Загрузка...