Основы конструирования компиляторов



             

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


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

Определение. Пусть дана грамматика 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, или праволинейной.

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

Язык, порождаемый

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

Теорема 2.1. Каждый контекстно-свободный язык может быть порожден неукорачивающей контекстно-свободной грамматикой.

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

Построим новую грамматику G' = (N', T, P', S') следующим образом:

1. Если в P есть правило вида A

0B1
1...Bk
k, где k
0, Bi
+e для 1
i
k, и ни из одной

цепочки

j (0
j
k) не выводится e, то включить в P' все правила (кроме A
e) вида

где Xi - это либо Bi, либо e.

2. Если S

+e, то включить в P' правила S'
S, S'
e и положить N' = N
{S'}. В противном случае положить N' = N и S' = S.

Порождает ли грамматика пустую цепочку можноо установить следующим простым алгоритмом:

Шаг 1. Строим множество N_0 = N | N

e

Шаг 2. Строим множество N_i = N | N

Ni - 1*

Шаг 3. Если N_i = N_i-1, перейти к шагу 4, иначе шаг 2.




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