Построение магазинного автомата
- Для грамматик, удовлетворяющих условиям LL(1) грамматик, справедливо следующее утверждение.
| Утверждение. Для каждой LL(1) грамматики Г можно построить детерминированный магазинный автомат М , допускающий язык, порождаемый заданной грамматикой: L ( Г ) = L ( М ). |
Задача построения магазинного автомата для заданной LL(1) грамматики формулируется следующим образом.
Задана грамматика Г = {Vт,Va, I, R}, и требуется определить
об'екты, определяющие автомат М = { P , S , s0
, F , H , h0 , f }.
Учитывая, что автомат должен допускать цепочки языка, порождаемого заданной грамматикой, примем P = Vт. Чтобы упростить описание автомата, допустим, что он имеет одно состояние s0, которое является и начальным и заключительным, то есть - S = {s0}и F = {s0}.
В качестве магазинного алфавита примем следующее объединение: H = {Vт И
Va И
{h0}}.
Построение функции переходов выполним с использованием множеств ВЫБОР правил заданной грамматики следующим образом:
1 ) Для каждого правила грамматики, начинающегося терминальным символом вида
<A> ®
b a, построим команду автомата
- f ( s0 , b , <A> ) = ( s0
, a
' ) ,
где a
' является зеркальным отображением цепочки
a .
2) Для каждого правила грамматики, начинающегося нетерминальным символом вида
<A>
® <B>
a, построим команду автомата
- f* ( s0 , x , <A> ) = ( s0
, <B> a
' )
где f* - команда автомата без сдвига входной головки, а a
' является зеркальным
отображением цепочки a
.
Количество команд, которые необходимо построить для заданного правила, определяется числом элементов множества ВЫБОР.
Команды магазинного автомата, работающие без сдвига входной головки, выполняют замену нетерминаала, соответствующего левой части правила, цепочкой, соответствующей правой части этого правила. В этом случае сопоставление терминального символа, получаемого при выводе, и очередного символа входной цепочки не производится, поэтому для таких команд сдвиг входной головки не нужен.
3) Для каждого аннулирующего правила грамматики вида
<A>
® $
построим команды автомата
- f* ( s0 , x , <A> ) = ( s0
, $ )
для каждого элемента x из множества ВЫБОР(<A>
® $). Количество таких команд определяется числом элементов множества ВЫБОР.
4) Для каждого терминального символа b, расположенного в середине или на конце правых
частей правил грамматики, построим команду
- f ( s0 , b , b ) = ( s0
, $ ).
5) Для перехода в заключительное состояние построим команду
- f* ( s0 , e
, h0 ) = ( s0 , $ , $ ).
В качестве начальной конфигурации автомата условимся использовать следующее выражение с заданной входной цепочкой µ :
- (s0,µ,h0<I>).
Пользуясь приведенными правилами, построим магазинный автомат для грамматики Г12, схема которой в символических обозначениях может быть записана так
- Г3. 5
: R = {<A>
® x | (<B>),
- <B>
® <A> <C>,
<C>
® +<A> <C>
| $}.
- Вначале построим множества ВЫБОР для каждого из правил и проверим, является ли эта грамматика LL(1) грамматикой.
- (1) ВЫБОР(<A> ®x) = ПЕРВ(x) = {x}
(2) ВЫБОР(<A> ®
((<B>))) = ПЕРВ((<B>)) = {(}