Способы записи синтаксиса языка

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

Несмотря на большое разнообразие грамматик, при построении трансляторов нашли широкое применение только ряд из них, имеющих некоторые ограничения. Это связано с практической целесообразностью использования определенных типов правил, так как сложность их построения непосредственно влияет на сложность построения трансляторов. По виду правил выделяют несколько классов грамматик. В соответствии с классификацией Хомского грамматика 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.

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

Существуют различные способы записи синтаксических правил, что в основном определяется условными обозначениям и ограничениями на структуру правил, принятыми в используемых метаязыках. Метаязыки используются для задания грамматики языков программирования со времен Алгола 60. Еще раньше они начали использоваться при описании небольших языков в в статьях, посвященных формальным грамматикам. Кратко рассмотрим основные вехи становления и развития метаязыков. Во всех случаях будем определять идентификатор.