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

UptoLike

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

Основное использование распознавательных средств задания языков состоит в
построении алгоритмов грамматического разбора. Поэтому необходимо для произвольной
КС-грамматики уметь строить эквивалентный МП-автомат.
МП-автомат представляет интерес как средство разбора в КС-грамматиках
произвольного вида. Этот факт сформулирован в следующей теореме.
Теорема. Языки, порождаемые КС-грамматиками, совпадают с языками,
распознаваемыми МП-автоматами.
Доказательство. Существуют две стратегии разбора: восходящий и нисходящий разбор.
Рассмотрим обе стратегии разбора.
5.4.1. Восходящий разбор в МП-автомате
При восходящей стратегии необходимо найти основу и редуцировать ее к какому-нибудь
нетерминалу в соответствии с правилами данной грамматики. Это можно сделать в том
случае, если реализовать следующий алгоритм функционирования МП-автомата:
1) любой входной символ записывается в магазин;
2) если в верхушке магазина сформирована основа, совпадающая с правой частью
правила, то она заменяется на нетерминал в левой части этого правила;
3) разбор заканчивается, если в магазине остается аксиома, а входная цепочка
рассмотрена полностью.
В соответствии с этим алгоритмом для КС-грамматики G = (V
T
, V
N
, P, S) построим МП-
автомат:
M = (К, V
T
, Г, δ, p
0
, F, B
0
), где Г = V
T
V
N
{B
0
},
K = {p
0
, F}, F = {f}.
Функция переходов δ будет содержать следующие команды:
а) p
0
, a, ε p
0
, a - для любых a V
T
;
б) p
0
, ε, ϕ p
0
, A - для всех правил A ϕ P, где ϕ’ - зеркальное отображение ϕ;
в) p
0
, ε, SB
0
f, B
0
.
В общем случае команда выглядит так:
p
i
, σ, γ p
j
, λ , где p
i
K – состояние автомата до выполнения команды, σ∈V
t
символ
на входной ленте, γ∈Γ - символ верхушки магазина, p
j
K – состояние автомата после
выполнения команды, λ∈Γ - символ, который записывается в магазин.
Таким образом, любому выводу в грамматике G взаимно однозначно соответствует
последовательность команд построенного МП-автомата. Обратное построение КС-
грамматики по произвольному МП-автомату также возможно, но не представляет
практического интереса.
Рассмотрим пример восходящей стратегии разбора.
Пусть дана грамматика G:
S S+A | S/A | A
A a | (S);
V
N
={S, A}, V
T
={a, (, ), +, /}.
Для заданной КС-грамматики G необходимо построить МП-автомат.
Эквивалентный МП-автомат должен содержать следующие команды:
1. Команды переноса терминальных символов в магазин:
p
0
, a, ε p
0
, a ;
p
0
, +, ε p
0
, + ;
p
0
, /, ε p
0
, / ;
p
0
, (, ε p
0
, (;
p
0
, ), ε p
0
, ).