Грамматики типа 3

Этот класс грамматик задает алгоритм порождения цепочек присоединением некоторого количества терминальных символов с правого или левого края порождаемой цепочки. Очевидно, что правила для такого метода порождения должны иметь вид A —> alpha B или A —> B alpha, где alpha — цепочка, состоящая из терминальных символов. В этом случае, если имеется промежуточная (в процессе порождения) цепочка X1. Xn A, то замена в соответствии с правилом A —> alpha B даст цепочку X1. Xn alpha B. Например, для правил S —> aaaA, A —> abcA и A —> bbb можно задать порождение S => aaaA => aaaabcA => aaaabcbbb.

Синтаксическое отношение, которое задается грамматиками типа 3, можно обозначить термином «быть рядом». Под «рядом» здесь подразумевается как непосредственно рядом, если это задано в правой части какого-то правила порождения, так и опосредованно рядом, через нетерминальные символы в связанных между собой правилах порождения.

Для математической строгости строку терминальных символов в правилах грамматик типа 3 разбивают на несколько правил с одним терминальным символом в правой части. Например, если имеется правило A —> abcB, то его можно заменить на следующие правила, применение которых в результате порождает ту же цепочку:

A —> a A1, A1 —> b A2, A2 —> cB.

Иначе говоря, подстановка.

A => abc.

эквивалентна последовательности подстановок.

A => a A1 => a b A2 => abcB.

Такие грамматики, где нетерминальный символ стоит справа в правой части правила, называют праволинейными грамматиками, если в правой части нетерминальный символ стоит слева от терминала, то грамматику называют леволинейной.

Зададим, например леволинейную грамматику для языка.

A = {a+a, a+a+a, a+a+a+a, …}.

Правила грамматики типа 3, как было рассмотрено выше, это:

S —> aA, A —> +aA, A —> +a.

Здесь цепочки порождаются присоединением пары символов справа. Изменим грамматику так, чтобы символы присоединялись слева, а также добавим нетерминальные символы, чтобы каждый раз добавлять только по одному символу. Получим грамматику:

S —> Aa.

A —> B+.

B —> Aa.

B —> a.

Вот как выглядит порождение цепочки.

a+a+a: S => Aa => B+a => Aa+a => B+a+a => a+a+a.

Внимательный читатель вероятно заметил, что грамматика типа 3 похожа на попрождающий автомат, в котором роль состояний играют нетерминальный символы грамматики. Одна из возможных интерпретаций этой грамматики — это, действительно, конечный автомат.