Файл: Отчет Л.р.4 ШАВРОВА.docx

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

Лабораторная работа №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. Управляющая таблица МП-автомата транслирующей грамматики