Пред.СтраницаСлед.Страница  Раздел Содержание

---

5.4.5.  Пример построения АП

Следуя приведенному порядку, построим АТ-преобразователь для грамматики Г_5.4 и проанализируем его работу. Вначале приведем эту грамматику  к форме простого присваивания. В результате получаем грамматику:

Г_5.6:

<E>%a/b ® i%x<R>%e/c/d
!! c=x; d=b;a=e;
<R>%e1/c1/d1 ® +{СЛЕДУК}%wi%x{СЛОЖ/f1/g1/h1}<R>%e2/c2/d2
!! f1=c1; g1=x1; (h1,c2)=d1; d2=w;e1=e2;
<R> %e3/c3/d3 ® -{СЛЕДУК}%wi%x{ВЫЧИТ/f2/g2/h2}<R>%e4/c4/d4
!! f2=c3; g2=x2; (h2,c4)=d3; d4=w;e3=e4;
<R>%e5/c5/d5 ® .
!! e5=d5;

1) После удаления атрибутов из грамматики Г_5.6 получаем  грамматику Г_5.3.
2) Команды преобразователя для грамматики Г_5.3 имеют вид:

(1)   f*(s₀,i,h₀)=(s₀,h₀<E>,$),
(2)   f*(s₀,i,<E>)=(s₀,<R>i,$),
(3)   f(s₀,+,<R>)=(,s₀<R>{СЛОЖ}i,$),
(4)   f(s₀,-,<R>)=(s₀,<R>{ВЫЧИТ}i,$),
(5)   f(s₀,.,<R>)=(s₀,$,$),
(6)   f(s₀,i,i)=(s₀,$,$),
(7)   f*(,s₀+,{СЛОЖ})=(s₀,$,{СЛОЖ}),
(8)   f*(s₀,-,{СЛОЖ})=(s₀,$,{СЛОЖ}),
(9)   f*(s₀,.,{СЛОЖ})=(s₀,$,{СЛОЖ})
(10)   f*(s_0,+,{ВЫЧИТ})=(s₀,$,{ВЫЧИТ}),
(11)   f*(s₀,-,{ВЫЧИТ})=(s₀,$,{ВЫЧИТ}),
(12)   f*(s₀,.,{ВЫЧИТ})=(s₀,$,{ВЫЧИТ}),
(13)   f*(s₀,e,h₀)=(s₁,$,$).

3) Для каждой команды, выполняющей запись цепочки символов в магазин, в нашем случае это команды (1)-(5), построим инструкцию, определяющую значения  указателей. Такие инструкции , построенные в соответствии с правилами вычисления значений атрибутов, имеют вид:

#1 {ЗАПИСАТЬ(h₀ba<E>) b=<начальное значение>}

#2 {ЗАПИСАТЬ(dce<R>xi)
STACK[SP-1]=-3
STACK[SP-5]=-2
STACK[SP-3]=-3  }

#3 {ЗАПИСАТЬ(d2c2e2<R>h1g1f1{СЛОЖ}x1iw1{СЛЕДУК})
STACK[SP-5]=-8
STACK[SP-3]=-3
STACK[SP-7]=-3
STACK[SP-10]=-4
STACK[SP-1]=-10
STACK[SP-9]=-3  }

#4 {ЗАПИСАТЬ(d4c4e4<R>h2g2f2{ВЫЧИТ}x2iw1{СЛЕДУК})
STACK[SP-5]=-8
STACK[SP-3]=-3
STACK[SP-7]=-3
STACK[SP-10]=-4
STACK[SP-1]=-10
STACK[SP-9]=-3  }

#5 {STACK[SP-1]=-2; {УДАЛИТЬ(3)}  }

Содержание символов действия, используемых в инструкциях, можно описать следующим образом :

{СЛЕДУК} - определяет следующий свободный адрес таблицы значений
                        и присаваивает его своему атрибуту,
{СЛОЖ} - читает из магазина атрибуты, формирует атом, состоящий из
                   знака операции сложения, адресов операндов и результата, и
                   передает атом на выход,
{ВЫЧИТ} -  читает из магазина атрибуты, формирует атом, состоящий из
                   знака операции вычитания, адресов операндов и результата,
                   и передает атом на выход,
{УДАЛИТЬ(3)} - удаляет из вершины магазина три символа.

4) Включая обозначение построенных инструкций в команды преобразователя  и учитывая, что обработка символов действия была включена в правила  работы АП, команды (7) - (12) можно исключить из списка команд. В результате получаем систему команд в виде:

(1)   f*(s₀,i,h₀)=(s₀,#1,$),
(2)   f(s₀,i,<E>)=(s₀,#2,$),
(3)   f(s₀,+,<R>)=(s₀,#3,$),
(4)   f(s₀,-,<R>)=(s₀,#4,$),
(5)   f(s₀,.,<R>)=(s₀,#5,$),
(6)   f(s₀, i, i )=(s₀,$,$),
(7)   f*(s₀,e,h₀)=(s₁,$,$).

---

Пред.СтраницаСлед.Страница  Раздел Содержание