Теория и реализация языков программирования




Типы грамматик и их свойства


Рассмотрим классификацию грамматик (предложенную Н.Хомским), основанную на виде их правил.

Определение. Пусть дана грамматика G = (N, T, P, S). Тогда

(1) если правила грамматики не удовлетворяют никаким ограничениям, то ее называют грамматикой типа 0, или грамматикой без ограничений.

(2) если

  1. каждое правило грамматики, кроме
    S \rightarrow e
    , имеет вид
    \alpha \rightarrow \beta
    , где
    |\alpha|\leq |\beta|
    , и
  2. в том случае, когда
    S \; \rightarrow \; e \; \in \; P
    , символ S не встречается в правых частях правил, то грамматику называют грамматикой типа 1, или неукорачивающей или контекстно-зависимой (КЗ- грамматикой) или контекстно - чувствительной (КЧ- грамматикой).

(3) если каждое правило грамматики имеет вид

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

(4) если каждое правило грамматики имеет вид либо

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

Легко видеть, что грамматика в примере 2.5 - неукорачивающая, в примере 2.6 - контекстно-свободная, в примере 2.7 - праволинейная.

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




Содержание  Назад  Вперед