3.2.2. Связь между КС-языками и недетерминированными автоматами

Связь между КС-языками и недетерминированными автоматами выража­ются теоремами, которые показывают, что класс языков, допускаемых мага­зинными автоматами при пустом магазине, есть в точности класс КС-языков.

Теорема 3.2.1. [4] Пусть L(G) — КС-язык, порождаемый грамматикой G = <N, T, P, S> в нормальной форме Грейбах. Тогда существует недетерминированный нисходящий МП-автомат М, такой, что он допускает все слова языка L(G) и только их, причем автомат М = <A, Q, Г, , q0, Z0, F> строится следующим образом:

1) A = T;

2) Q = {q1};

3) Г = N;

4) q0 = q1;

5) Z0 = S;

6) F =;

7) (q1, )(q1, a, B) всегда, когда подстановка Ba принадлежит множеству правил Р грамматики G, здесь BN, aT, {NT}*.

Теорема 3.2.2. [4] Пусть L(M) — язык, допускаемый магазинным автоматом М = <A, Q, Г, , q0, Z0, F>. Тогда существует такая КС-грамматика G = <N, T, P, S>, что L(G)=L(M),

1) где T =A;

2) N — множество вида (q, B, p), q, p Q и ВГ;

3) подстановка S(q0, z0, q) принадлежит множеству правил Р при любом qQ;

4) подстановки (q, B, p)(q1, B1, q2) (q2, B2, q3) … (qm, Bm, qm+1) принадлежат множеству Р для всех q, q1, q2, …,qm+1Q, p = qm+1, для любого a{A{}} и любых B, B1, B2, …, Bm  Г таких, что (q1, B1B2…Bm)(q, a, B). Если же m = 0, то q1 = p, p(q, a, B) и (q, B, p)  а принадлежит множеству Р.

Пример 3.2.1. [14]. Дана КС-грамматика G = <N, T, P, S>, у которой

N = {S, D, B}, T = {a, b},

  P = {    S  aB

              S  bD

              D aS

              D a

              D bDD

              B aBB

              B bS

              B b}

В соответствии с теоремой 3.2.1 МП-автомат М = <A, Q, Г, , q0, Z0, F>, допускающий данный КС-язык, будет включать в себя компоненты A = {a, b}, Q = {q1},       Г = {S, D, B}, q0=q1, z0=S  и отображение , заданное в виде:

1) (q1, a, S)  (q1, B),                                     т.к. (SaB)P;

2) (q1, b, S)  (q1, D),                                    т.к. (SbD)P;

3) (q1, a, D)  {(q1, S), (q1, )},                   т.к. (DaS) и (Da)

входят во множество P;

4) (q1, b, D)  (q1, DD),                                 т.к. (DbDD)P;

5) (q1, a, B)  (q1, BB),                                  т.к. (BaBB)P;

6) (q1, b, B)  {(q1, S), (q1, )},                   т.к. (BbS) и (Bb)

входят во множество P.

Отметим, что построенный МП-автомат является недетерминированным, т.к. в нем в правилах 3 и 6 допускается неоднозначность перехода для одной и той же комбинации состояния входного и магазинного символов. В общем случае классы языков, допускаемых детерминированными и недетерминирован­ными МП-автоматами не совпадают. На практике же получили наибольшее применение детерминированные методы разбора для, так называемых, детер­минированных КС-языков, которые хотя и меньше всего класса КС-языков, но боль­шинство языков программирования можно отнести к классу этих языков. Последнее позволяет строить высокоэффективные алгоритмы синтаксическо­го разбора.