Национальный исследовательский университет «Московский энергетический институт» Институт автоматики и вычислительной техники Кафедра математического моделирования

Лабораторная работа №4

«Построение транслятора»

Выполнил студент Киришко Ф.С.

вариант №8 учебной группы А-14-10.

Проверил Анатолий Васильевич Князев

Москва 2012

1. Задание

1. Преобразовать заданную грамматику в L-атрибутную транслирующую грамматику в форме простого присваивания.

2. Разработать атрибутный автомат для трансляции предложений данной грамматики

3. Разработать программу, реализующую МП-транслятор.

4. Разработать программу-интерпретатор для данного объектного языка.

2. Описание языка

Оператор присваивания:

<идентификатор>=<ар.выр>;

Условный оператор:

if(<лог.выр.>)then<оператор>[else<оператор>]

Оператор цикла:

while(<лог.выр.>)

<совокупность операторов>

end_while

Арифметическое выражение:

<E>::=<T><E-список>

<E-список>::=+<T><E-список>

<E-список>::=!

<T>::=<F><T-список>

<T-список>::=*<F><T-список>

<T-список>::=!

<F>::=<P>

<F>::=<R>

<P>::=<Id>

<P>::=<Int>

Логическое выражение:

<лог.выр.>::=<P><лог.опер.><P>

<лог.опер.>::= =

<лог.опер.>::= #

3. LL-1 грамматика

1. <S><совок.операторов>

2. <совок.операторов><оператор><совок.операторов>

3. <совок.операторов> !

4. <оператор><операторприсваивания>

5. <оператор><условныйоператор>

6. <оператор><операторцикла>

7. <оператор присваивания>Id= <E>;

8. <E><T><E-список>

9. <E-список>+<T> <E-список>

10. <E-список>!

11. <T><F><T-список>

12. <T-список>* <F> <T-список>

13. <T-список> !

14. <F><P><F-список>

15. <F-список>^ <P><F-список>

16. <F-список> !

17. <P>Id

18. <P>Con

19. <условный оператор>if<лог.выр.>then<оператор><else-часть>

20. <else-часть>else<оператор>

21. <else-часть>!

22. <оператор цикла>for(<Id>=<E>;<лог.выр.>;<Id> = <E>) <совокупность операторов>end

23. <лог.выр.>(<P><лог.-список>)

24. <лог.-список>= <P>

25. <лог.-список># <P>

4. L – атрибутная транслирующая грамматика в форме простого присваивания для заданного языка

1. <S><совок.операторов>

2. <совок.операторов><оператор><совок.операторов>

3. <совок.операторов> !

4. <оператор><операторприсваивания>

5. <оператор><условныйоператор>

6. <оператор><операторцикла>

7. <оператор присваивания>Id_p1= <E>_q1{Присвоить_p2,q2};

p2p1, q2q1

8. <E>_q2<T>_p1<E-список>_p2,q1

p2  p1, q2  q1

9. <E-список>_p1,t2 +<T>_q1 {Сложить_p2,q2,r1} <E-список>_r2,t1

p2  p1, q2  q1, (r1, r2) Нов, t2  t1

10. <E-список>_p1,t2!

t2  p1

11. <T>_q2<F>_p1<T-список>_p2,q1

p2  p1, q2  q1

12. <T-список>_p1,t2 * <F>_q1 {Умножить_p2,q2,r1} <T-список>_r2,t1

p2 p1, q2 q1, (r1, r2) Нов, t2 t1

13. <T-список>_p1,t2 !

t2  p1

14. <F>_q2<P>_p1<F-список>_p2,q1

p2  p1, q2  q1

15. <F-список>_p1,t2^ <P>_q1{В степень_p2,q2,r1} <F-список>_r2,t1

p2 p1, q2 q1, (r1, r2) Нов, t2 t1

16. <F-список>_p1,t2 !

t2  p1

17. <P>_pId_q

pq

18. <P>_pCon_q

pq

19. <условный оператор>if<лог.выр.>_p1{Переход по 0_p2,z1}

then<оператор><else-часть>_z2

p2p1, (z1,z2)НовМ

20. <else-часть>_z1else{Безусловный переход_w1}{Метка_z2} <оператор> {Метка_w2}

z1  z2, (w1,w2)НовМ

21. <else-часть>_z1{Метка_z2}

z2z1

22. <оператор цикла>for(<Id_p1>=<E_q1>{Присвоить_p2,q2};<лог.выр._t1>;<Id_r1> = <E_s1>){Метка_z1} {Переход по сравнению_t2,w1} <совокупность операторов> {Присвоить_r2,s2} {Безусловный переход_z2} {Метка_w2}end

p2p1,q2q1,t2t1,r2r1,s2s1, (z1,z2)НовМ, (w1,w2)НовМ

23. <лог.выр.>_t2(<P>_p1<лог.-список>_p2,t1)

p2p1,t2t1

24. <лог.-список>_p1,t2 =<P>_q1 {Равно_p2,q2,t1}

p2p1,q2q1, (t1,t2)Нов

25. <лог.-список>_p1,t2#<P>_q1{Не равно_p2,q2,t1}

p2  p1, q2  q1, (t1, t2) Нов

5. Множества выбора для L-атрибутной грамматики

_{¶ - концевой маркер}

1. Найти аннулирующие нетерминалы и правила:

   1. Вычеркивание правил, содержащих терминальные символы:

      1. <S><совок.операторов>

      2. <совок.операторов> <оператор> <совок.операторов>

      3. <совок.операторов> !

      4. <оператор> <оператор присваивания>

      5. <оператор> <условный оператор>

      6. <оператор> <оператор цикла>

      7. <оператор присваивания>  Id = <E>;

      8. <E><T><E-список>

      9. <E-список>  +<T><E-список>

      10. <E-список>  !

      11. <T>  <F><T-список>

      12. <T-список>  *<F><T-список>

      13. <T-список>  !

      14. <F>  <P><F-список>

      15. <F-список>  ^<P><F-список>

      16. <F-список>  !

      17. <P>  Id

      18. <P>  Con

      19. <условный оператор>  if <лог.выр.> then <оператор> <else-часть>

      20. <else-часть>  else <оператор>

      21. <else-часть>!

      22. <оператор цикла>  while <лог.выр.> <совок.операторов> end_while

      23. <лог.выр.>  (<P> <лог.спис.>)

      24. <лог.спис.>  = <P>

      25. <лог.спис.>  # <P>

   2. Список аннулирующих нетерминальных грамматик:

      1. <совок.операторов>

      2. <E-список>

      3. <T-список>

      4. <F-список>

      5. <else-часть>

   3. Дополнение списка:

      1. <S>

   4. Полный список аннулирующих правил: 1,3,10,13,16,21

2. Построение отношения Начинается-Прямо-С:

3. Вычисление отношения Начинается-С:

4. Вычисление множества Первдля каждого нетерминала:

Перв(<S>) = {Id, if, while}

Перв(<совок.операторов>) = { Id,if,while}

Перв(<оператор>) = { Id,if,while}

Перв(<оператор присваивания>) = {Id}

Перв(<E>) = {Con,Id}

Перв(<E-список>) = { + }

Перв(<T>) = {Con,Id}

Перв(<T-список>) = { * }

Перв(<F>) = {Con,Id}

Перв(<F-список>) = { ^ }

Перв(<P>) = {Con,Id}

Перв(<условный оператор>) = {if}

Перв(<else-часть>) = {else}

Перв(<оператор цикла>) = {while}

Перв(<лог.выр.>) = { ( }

Перв(<лог.-список>) = {=, #}

5. Вычисление множества Первдля каждого правила:

Перв(<совок.операторов>) = { Id,if,while}

Перв(<оператор><совок.операторов>)= Перв(<оператор>) = { Id,if,while}

Перв( ! ) = { }

Перв(<оператор присваивания>) = {Id}

Перв(<условный оператор>) = {if}

Перв(<оператор цикла>) = {while}

Перв(Id= <E>;) = {Id}

Перв(<T><E-список>) = Перв(<T>) = {Con,Id}

Перв( +<T> <E-список>) = { + }

Перв( ! ) = { }

Перв(<F><T-список>) = Перв(<F>) = {Con,Id}

Перв( * <F> <T-список>) = { * }

Перв( ! ) = { }

Перв(<P><F-список>) = Перв(<P>) = {Con,Id}

Перв( ^ <P><F-список>) = { ^ }

Перв( ! ) = { }

Перв(Id) = {Id}

Перв(Con) = {Con}

Перв(if<лог.выр.>then<оператор><else-часть>) = {if}

Перв(else<оператор> ) = {else}

Перв( ! ) = { }

Перв(while<лог.выр.><совокупность операторов>end_while) = {while}

Перв( (<P><лог.-список>) ) = { ( }

Перв( =<P>) = { = }

Перв( #<P>) = { # }

6. Построение отношения Прямо-Перед:

7. Построение отношения Прямо-На-Конце:

8. Вычисление отношения На-Конце:

9. Вычисление отношения Перед= (На-Конце*Прямо-Перед) *Начинается-С.

10. Расширение отношения Передпутем включения концевого маркера.

11. Вычисление множества След для каждого аннулирующего нетерминала:

След(<S>) = {_¶}

След(<совок.операторов>) = { end_while,_¶}

След(<E-список>) = { ; }

След(<T-список>) = { + , ; }

След(<F-список>) = { *, +, ; }

След(<else-часть>) = { Id, if, while, else, end_while, _¶ }

12. Вычисление множества Выбора:

    1. Перв(<совок.операторов>) + След(<S>) = {Id,if,while,_¶}

    2. Перв(<оператор><совок.операторов>)= Перв(<оператор>) = { Id,if,while}

    3. Перв( ! ) + След(<совок.операторов>) = { end_while,_¶}

    4. Перв(<оператор присваивания>) = {Id}

    5. Перв(<условный оператор>) = {if}

    6. Перв(<оператор цикла>) = {while}

    7. Перв(Id= <E>;) = {Id}

    8. Перв(<T><E-список>) = Перв(<T>) = {Con,Id}

    9. Перв( +<T> <E-список>) = { + }

    10. Перв( ! ) + След(<E-список>) = { ; }

    11. Перв(<F><T-список>) = Перв(<F>) = {Con,Id}

    12. Перв( * <F> <T-список>) = { * }

    13. Перв( ! ) + След(<T-список>) = { + , ; }

    14. Перв(<P><F-список>) = Перв(<P>) = {Con,Id}

    15. Перв( ^ <P><F-список>) = { ^ }

    16. Перв( ! ) + След(<F-список>) = { *, +, ; }

    17. Перв(Id) = {Id}

    18. Перв(Con) = {Con}

    19. Перв(if<лог.выр.>then<оператор><else-часть>) = {if}

    20. Перв(else<оператор> ) = {else}

    21. Перв( ! ) + След(<else-часть>) = { Id, if, while, else, end_while, _¶ }

    22. Перв(while<лог.выр.><совокупность операторов>end_while) = { while }

    23. Перв( (<P><лог.-список>) ) = { ( }

    24. Перв( =<P>) = { = }

    25. Перв( #<P>) = { # }

//Вообще говоря, множество выбора правил 20 и 21 пересекаются, но прога работает. =)

6. Управляющая таблица МП-автомата транслирующей грамматики

Con

Id

if

while

else

#

=

^

*

+

;

(

)

then

end_while

¶

<S>

#1

#1

#1

#1

<совокупность операторов>

#2

#2

#2

#3

#3

<оператор>

#4

#5

#6

<оператор присваивания>

#7

<E>

#8

#8

<E-список>

#9

#10

<T>

#11

#11

<T-список>

#12

#13

#13

<F>

#14

#14

<F-список>

#15

#16

#16

#16

<P>

#18

#17

<условный оператор>

#19

<else-часть>

#21

#21

#21

#20

#21

<оператор цикла>

#22

<логическое выражение>

#23

<логический-список>

#25

#24

=

ВС

;

ВС

)

ВС

Then

ВС

end_while

ВС



Д

{Присвоить}

Выдать (Присвоить), Вытолкнуть, Держать

{Сложить}

Выдать (Сложить), Вытолкнуть, Держать

{Умножить}

Выдать (Умножить), Вытолкнуть, Держать

{В степень}

Выдать (В степень), Вытолкнуть, Держать

{Переход по 0}

Выдать (Переход по 0), Вытолкнуть, Держать

{Безусловный переход}

Выдать (Безусловный переход), Вытолкнуть, Держать

{Метка}

Выдать (Метка), Вытолкнуть, Держать

{Переход по сравнению}

Выдать (Переход по сравнению), Вытолкнуть, Держать

{Равно}

Выдать (Равно), Вытолкнуть, Держать

{Не равно}

Выдать (Не равно), Вытолкнуть, Держать

Начальное содержимое автомата: <S> 

#1 Заменить (<совокупность операторов>), Держать

#2 Заменить (<оператор><совокупность операторов>), Держать

#3 Вытолкнуть, Держать

#4 Заменить (<оператор присваивания>), Держать

#5 Заменить (<условный оператор>), Держать

#6 Заменить (<оператор цикла>), Держать

#7 Заменить (‘=’<E> {Присвоить}‘;’), Сдвиг

#8 Заменить (<T><E-список>), Держать

#9 Заменить (<T> {Сложить}<E-список>), Сдвиг

#10 Вытолкнуть, Держать

#11 Заменить (<F><T-список>), Держать

#12 Заменить (<F> {Умножить}<T-список>), Сдвиг

#13 Вытолкнуть, Держать

#14 Заменить (<P><F-список>), Держать

#15 Заменить (<P> {В степень}<F-список>), Сдвиг

#16 Вытолкнуть, Держать

#17 Вытолкнуть, Сдвиг

#18 Вытолкнуть, Сдвиг

#19 Заменить (<лог.выр.>{Переход по 0}then<оператор><else-часть>), Сдвиг

#20 Заменить ({Безусловный переход} {Метка}<оператор> {Метка}), Сдвиг

#21 Заменить ({Метка}), Держать

#22 Заменить ({Метка}<лог.выр.>{Переход по сравнению}<совокупность операторов>

{Безусловный переход} {Метка}end_while), Сдвиг

#23 Заменить (<P><логический-список>’)’), Сдвиг

#24 Заменить (<P>{Равно}), Сдвиг

#25 Заменить (<P>{Не равно}), Сдвиг

ВС Вытолкнуть, Сдвиг

Д Допустить

7. Пример замены магазинных символов, содержащих атрибутные поля:

• Оператор цикла:

Текущая входная цепочка	Содержание магазина
while (i # 10)	1	<оператор цикла>
i = i + 1;	0	
end_while¶

while (i # 10)	14	While
i = i + 1;	13	{Метка}
end_while¶	12	1
	11	<логическое выражение>
	10	8
	9	{Переход по сравнению}
	8	(-1)
	7	0
	6	<совокупность операторов>
	5	{Безусловный переход}
	4	1
	3	{Метка}
	2	0
	1	end_while
	0	

В массив меток добавляется два указателя на массив команд, а в магазин записываются адреса этих ячеек в массиве меток.

• Условный оператор:

Текущая входная цепочка	Содержание магазина
if(d=c)then	1	<условный оператор>
a=d*2;	0	
else a=d^3;¶
if(d=c)then	10	If
a=d*2;	9	<логическое выражение>
else a=d^3;¶	8	6
	7	{Переход по 0}
	6	(-1)
	5	0
	4	Then
	3	<оператор>
	2	<else-часть>
	1	0
	0	

8. Тестовый пример

9. Текст программы