Формальные грамматики типа 0 и 1. Вывод цепочек терминальных символов.

Грамматика типа 0 - грамматика произвольного типа без каких-либо ограничений на цепочки символов. Продукции этой грамматики имеют вид: α ::= β. В обеих частях продукции могут быть в произвольном порядке и любом количестве терминальные и нетерминальные символы, т. е. α, β  V*. Такой тип грамматики порождает множество перечислимых языков, для которых существует перечисляющий алгоритм. Такой алгоритм может быть реализован на машине Тьюринга, являющейся классической моделью рекурсивной функции. Поэтому такие языки называют также рекурсивно- перечислимыми. Однако такой тип грамматики не нашел применения в языках программирования. Пример. Пусть дана грамматика G1 = , где VT = {alb}; VN = {A; B; C; J};Р ={р1: J ::= AbBb; р2: Ab ::= Bba; р3: Bb ::= Cba; р4: Cb ::= ba}. Какие цепочки терминальных символов формирует грамматика?К цепочке символов AbBb, заданной начальным символом J. можно применить два правила (Ab ::= Bba и Bb ::= Cba) и организовать два вывода: левосторонний и правосторонний. Левосторонний вывод: J => AbBb => BbaBb => CbaaBb => baaaBb => baaaCba => baaabaa;Правосторонний вывод: J => AbBb => AbCba => Abbaa => Bbabaa => Cbaabaa => baaabaa. Грамматика G1 вне зависимости от направления вывода формирует для заданной начальной цепочки AbBb единственную цепочку терминальных символов языка L(G 1): L(G 1) = {ba3ba2}Грамматика типа 1 это контекстно-зависимая грамматика или грамматика непосредственных составляющих (HC-грамматика). Второе название грамматики объясняется тем, что любую цепочку можно разложить на синтаксические составляющие (члены предложения естественного языка) и выполнить разбор каждой синтаксической переменной (части речи естественного языка) в составе синтаксической составляющей. В естественных языках для этого проводят грамматической разбор структуры предложения. В языках программирования - грамматический разбор структуры программы, что всегда необходимо при трансляции исходной программы на язык вычислительной машины. Продукции этой грамматики имеют вид: ω1Aω2 ::= ω1βω2,где A  VN;ω1, ω2, β  V*;ω1 – левый контекст;ω2 – правый контекст. Каждый шаг вывода состоит в замене одного вхождения нетерминального символа вхождением цепочки терминальных и/или нетерминальных символов. Эта замена обусловлена наличием левого и правого контекстов. Для HC-грамматики существенным является исполнение условия: |ω1Aω2| ≤ |ω1βω2|где |. . . | означает длину цепочки символов, заключенных между вертикальными линиями. Это требует исполнения в каждом правиле второго условия: β ≠ ε. Грамматики, в которых все правила обладают этими свойствами называют неукорачивающими. Множество языков HC-грамматики является собственным подмножеством языков грамматики типа 0. Для HC-грамматики возможны случаи: 1) ω1A ::= ω1β, когда ω2 = ε, 2) Aω2 ::= βω2, когда ω1 = ε. Для HC-грамматик также допустим лево- и правосторонний вывод, когда продукции грамматики применяются к самому левому или самому правому нетерминальному символу анализируемой цепочки. Пример. Пусть дана грамматика G5 = , где VT = {a; b; c}; VN = {B; c; J};Р = {р1: J ::= aJBC I aBC; p2: CB ::= DB;р3: DB ::= DC; p4: DC ::= BC; p5: aB::=ab; р6: bB ::= bb; p7 bC ::= bc; р8: cC ::= cc}. Какие цепочки терминальных символов формирует грамматика? В каждом правиле есть либо левый, либо правый контексты. Используем также левосторонний вывод терминальных цепочек:J => aBC => abC => abc; J => aJBC => ааВСВС => aabCBC => aabDBC => aabDCC => aabBCC => aabbCC => aabbcC => aabbcc = a2b2c2;J => aJBC => aaJBCBC => . . . => aaabbbccc = a2b2c2 и т. д. Грамматика G5 формирует цепочки терминальных символов, используя операцию итерации:L(G 5) = {aibici | i = 1; 2; 3;…}