Классы грамматик в соответствии с классификацией Хомского.

Date: 2015-10-07; view: 499.

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

Соглашение – альтернатива правила вывода из цепочки.

Для записи правил вывода с одинаковыми левыми частями α → β₁ α → β₂ ... α → β_n пользуются сокращенной записью через операцию или: α → β₁ | β₂ |...| β_n

Каждое β_i (i=1, 2, ... , n) называется альтернативой правила вывода из цепочки α.

Несмотря на большое разнообразие грамматик, при построении трансляторов применяются только некоторые из них, имеющие ограничения, что связано с практической целесообразностью использования определенных типов правил, так как сложность их построения непосредственно влияет на сложность построения трансляторов.

По виду правил выделяют несколько классов грамматик. Классификация формальных языков и грамматик, согласно которой они делятся на 4 типа по их условной сложности, была предложена американским лингвистом Ноамом Хомским.

1. Праволинейная (выровненная вправо) грамматика – грамматика G, каждое правило Р которой имеет вид: A® xB или A® x, где A, B – нетерминалы, x – цепочка, состоящая из терминалов. Например, грамматика G2=({0,1}, {S}, S, P), где P: S ® 0S; S ® 1S; S ® e, определяет язык {0, 1}.

2. Контекстно-свободная (бесконтекстная) грамматика (КС-грамматика) – грамматика G, каждое правило Р которой имеет вид: A® a, где AÎN, aÎ (T È N)*, т.е. является цепочкой, состоящей из множества терминалов и нетерминалов, и может быть пустой. Например, грамматика G3=({E, T, F}, {a, +, *, (,)}, P, E), где P: E®T; E® E + T; T® F; T® T * F; F® (E); F® a, порождает простейшие арифметические выражения.

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

Нетерминал А контекстно-свободной грамматики G=(T, N, S, P) для некоторых a и b, если a=ε, называется леворекурсивным, а если b=ε, называется праворекурсивным.

Грамматика G называется леворекурсивной (соответственно праворекурсивной), если в G имеется хотя бы один леворекурсивный (соответственно праворекурсивный) нетерминал.

Грамматика, в которой рекурсивны все нетерминалы (возможно, кроме, начального символа) называется рекурсивной.

3. Контекстно-зависимая (неукорачивающая) грамматика (КЗ-грамматика)– грамматика G, каждое правило P которой имеет вид: a ® b, где |a | £ |b |, т.е. вновь порождаемые цепочки не могут быть короче, чем исходные, а также пустыми (другие ограничения отсутствуют). Например, грамматика G=({a, b, c}, {B, C, S}, S, P), где P: S ® aSBC; S ® abc; CB ® BC; bB ® bb; bC ® bc; cC ® сc, порождает язык {a ⁿb ⁿc ⁿ}, n≥1 (n>0).

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

Запрещение в контекстно-зависимой грамматике использования правил вида A→ε сделано для того, чтобы алгоритм, определяющий принадлежность цепочки языку, не зацикливался.

Наличие пустых цепочек ведет к грамматике без ограничений.

4. Грамматика свободного (общего) вида(без ограничений) – грамматика G, в которой отсутствуют выше упомянутые ограничения.

Наиболее широкое применение при разработке трансляторов нашли контекстно-свободные грамматики (КС-грамматики) и порождаемые ими КС-языки. Если язык L порождается грамматикой типа G (например, контекстно-свободной), то L называется языком типа, т.е. L(G) – контекстно-свободный язык (КС-язык) типа G.

Такая классификация называется включающей, т.е. все контекстно-свободные грамматики являются контекстно-зависимыми, а все контекстно-зависимые грамматики являются грамматиками общего вида и т.д.

Существуют языки, принадлежащие к типу i, но не к типу i+1: например, язык грамматики G_i является контекстно-зависимым, но не контекстно-свободным, т.е. не существует контекстно-свободной грамматики, порождающий этот язык.