45. Грамматики с ограничениями на правила

Грамматики с ограничениями на правила

Несмотря на большое разнообразие грамматик, при построении трансляторов нашли широкое применение только ряд из них, имеющих некоторые ограничения. Это связано с практической целесообразностью использования определенных типов правил, так как сложность их построения непосредственно влияет на сложность построения трансляторов. По виду правил выделяют несколько классов грамматик. В соответствии с классификацией Хомского грамматика G называется:

·         праволинейной, если каждое правило из Р имеет вид: A®xB или A®x, где A, B - нетерминалы, x - цепочка, состоящая из терминалов;

·         контекстно-свободной (КС) или бесконтекстной, если каждое правило из Р имеет вид: A®a, где A Î N, а a Î (N È T)*, то есть является цепочкой, состоящей из множества терминалов и нетерминалов, возможно пустой;

·         контекстно-зависимой или неукорачивающей, если каждое правило из P имеет вид: a ® b, где |a| £ |b|. То есть, вновь порождаемые цепочки не могут быть короче, чем исходные, а, значит, и пустыми (другие ограничения отсутствуют);

·         грамматикой свободного вида, если в ней отсутствуют выше упомянутые ограничения.

Пример праволинейной грамматики:

G2 = ({S,}, {0,1}, P, S), где

P:

1. S ® 0S;
2. S ® 1S;
3. S ® e,

определяет язык {0, 1}*.

Пример КС-грамматики:

G3 = ({E, T, F}, {a, +, *, (,)}, P, E) где

P:

1. E ®T
2. E ® E + T
3. T ® F
4. T ® T * F
5. F ® (E)
6. F ® a.

Данная грамматика порождает простейшие арифметические выражения.

Пример КЗ-грамматики:

G4 = ({B, C, S}, {a, b, c}, P, S) где

P:

1. S ® aSBC;

2. S ® abc;

3. CB ® BC;

4. bB ® bb;

5. bC ® bc;

6. cC ® сc,

порождает язык { a ⁿ b ⁿ c ⁿ }, n ≥ 1.

Примечание 1. Согласно определению каждая праволинейная грамматика является контекстно- свободной.

Примечание 2. По определению КЗ-грамматика не допускает правил: А ® e, где e - пустая цепочка. Т.е. КС-грамматика с пустыми цепочками в правой части правил не является контекстно-зависимой. Наличие пустых цепочек ведет к грамматике без ограничений.

Соглашение. Если язык L порождается грамматикой типа G, то L называется языком типа G.

Пример: L(G3) - КС язык типа G3.

Наиболее широкое применение при разработке трансляторов нашли КС-грамматики и порождаемые ими КС языки. В процессе изучения КС языков остановимся только на тех, которые будут полезны для нас с практической точки зрения (теория языков обширна и для детального ее изучения необходимо много времени). Те, кто желает приобрести более глубокие познания в данной области, могут обратиться к монографии Ахо и Ульмана.