Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 43 стр.

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

Составители: 

Рубрика: 

Эти команды обеспечивают занесение терминального символа из входной ленты в
магазин.
2. Команды редукции по правилам грамматики:
p
0
, ε, A+S → p
0
, S ;
p
0
, ε, A/S → p
0
, S ;
p
0
, ε, A → p
0
, S ;
p
0
, ε, )S( → p
0
, A ;
p
0
, ε, a → p
0
, A.
Эти команды заменяют зеркальное отображение правила, полученного в верхушке
магазина, на нетерминал в левой части данного правила грамматики.
3. Команды проверки на завершение разбора:
p
0
, ε, SB
0
→ f, B
0
.
Разбор завершается, если в магазине остались аксиома и маркер дна магазина, а входная
цепочка полностью рассмотрена.
Подадим на вход автомата цепочку a/(a+a) и выполним разбор. Процесс разбора
представлен в таблице 1.
5.4.2. Нисходящий разбор в МП-автомате
На любом шаге нисходящего разбора должно применяться какое-либо правило. В
начальный момент таким нетерминалом является аксиома. МП-автомат, выполняющий
нисходящий разбор, работает по следующему алгоритму:
1) в начальный момент времени в магазин заносится аксиома: p
0
, ε, ε → p
1
, S;
2) для каждого правила A→ϕ∈P нетерминал в верхушке магазина заменяется на правую
часть правила с помощью команды: p
1
, ε, A → p
1
, ϕ;
3) для каждого терминала a∈V
T
выполняется сравнение символа на входной ленте с
символом в верхушке магазина и его поглощение: p
1
,
a, a →p
1,
ε
4) разбор заканчивается по команде: p
1
,ε,B
0
→ f, B
0.
Для грамматики, рассмотренной в предыдущем примере, разбор той же входной
цепочки по нисходящей стратегии будет выполняться посредством следующего
множества команд:
1) команда занесения аксиомы в магазин:
p
0
, ε, ε → p
0
, S;
2) команды замены нетерминала правой частью правила:
p
1
, ε, S → p
1
, S+A
p
1
, ε, S → p
1
, S/A
p
1
, ε, S → p
1
, A
p
1
, ε, A → p
1
, a
p
1
, ε, A → p
1
, (S); 
    Эти команды обеспечивают занесение терминального символа из входной ленты в
магазин.
    2. Команды редукции по правилам грамматики:
                                   p0, ε, A+S → p0, S ;
                                   p0, ε, A/S → p0, S ;
                                   p0, ε, A → p0, S ;
                                   p0, ε, )S( → p0, A ;
                                   p0, ε, a → p0, A.
         Эти команды заменяют зеркальное отображение правила, полученного в верхушке

  магазина, на нетерминал в левой части данного правила грамматики.

    3. Команды проверки на завершение разбора:
                                     p0, ε, SB0 → f, B0.
    Разбор завершается, если в магазине остались аксиома и маркер дна магазина, а входная
цепочка полностью рассмотрена.
    Подадим на вход автомата цепочку      a/(a+a)   и выполним разбор. Процесс разбора
представлен в таблице 1.

      5.4.2. Нисходящий разбор в МП-автомате
         На любом шаге нисходящего разбора должно применяться какое-либо правило. В

  начальный момент таким нетерминалом является аксиома. МП-автомат, выполняющий

  нисходящий разбор, работает по следующему алгоритму:

    1) в начальный момент времени в магазин заносится аксиома: p0, ε, ε → p1, S;
    2) для каждого правила A→ϕ∈P нетерминал в верхушке магазина заменяется на правую
часть правила с помощью команды: p1, ε, A → p1, ϕ;
    3) для каждого терминала a∈VT выполняется сравнение символа на входной ленте с
символом в верхушке магазина и его поглощение: p1, a, a →p1, ε
    4) разбор заканчивается по команде: p1,ε,B0 → f, B0.
          Для грамматики, рассмотренной в предыдущем примере, разбор той же входной

  цепочки по нисходящей стратегии         будет выполняться посредством следующего

  множества команд:

   1) команда занесения аксиомы в магазин:

                                         p0, ε, ε → p0, S;
   2) команды замены нетерминала правой частью правила:
                             p1, ε, S → p1, S+A
                             p1, ε, S → p1, S/A
                             p1, ε, S → p1, A
                             p1, ε, A → p1, a
                             p1, ε, A → p1, (S);

Страницы