Класифікація породжувальних граматик

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

Если каждое правило грамматики, кроме S e, имеет вид , где | | | |, и в том случае, когда S e P, символ S не встречается в правых частях правил,то грамматику называют грамматикой типа 1, или неукорачивающей.

Если каждое правило грамматики имеет вид A , где A N, (N T)*, то ее называют грамматикой типа 2, или контекстно-свободной (КС-грамматикой).

Если каждое правило грамматики имеет вид либо A xB, либо A x, где A, B N, x T* то ее называют грамматикой типа 3, или праволинейной.

Язык типа 1 - контекстно-зависимым (КЗ), язык типа 2 - контекстно-свободным (КС), язык типа 3 - праволинейным.

K3 K2 K1 K0.

Грамматика G называется неоднозначной, если существует цепочка w, для которой имеется два или более различных деревьев вывода в G.

Грамматика G называется леворекурсивной, если в ней имеется нетерминал A такой, что существует вывод для некоторой цепочки w.

Атрибутной грамматикой называется четверка AG = (G, AS, AI, R), где

· G = (N, T, P, S) - приведенная КС-грамматика;

· A_S - конечное множество синтезируемых атрибутов;

· A_I - конечное множество наследуемых атрибутов, A_S A_I = ;

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

Атрибутная грамматика AG сопоставляет каждому символу X из N T множество AS(X) синтезируемых атрибутов и множество AI(X) наследуемых атрибутов.