37276

Исследование методов и алгоритмов работы трансляторов предметно-ориентированных языков

Курсовая

Информатика, кибернетика и программирование

Для описания семантических функций синтаксической диаграммы расстановки ссылок использованы следующие обозначения: Tb_Lexems[.Code массив кодов лексем; Tb_Lexems[.Vlue массив значений лексем; Number_Lexem номер очередной рассматриваемой лексемы в массиве лексем; Stek_do стек для циклов WHILE; Stek_if стек для развилок IF; Stek_cse – стек для операторовпереключателей SWITCH; Stek_to – стек для циклов FOR. Рисунок 3 Рсхема расстановки ссылок Семантические функции к Рсхеме расстановки ссылок на рисунке 3: y0:...

Русский

2013-09-24

889.5 KB

43 чел.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное образовательное учреждение

высшего профессионального образования

«Волгоградский государственный технический университет»

Камышинский  технологический  институт (филиал)

федерального государственного образовательного учреждения

высшего профессионального образования

«Волгоградский государственный технический университет»

Факультет

Информационных технологий

Кафедра

Автоматизированные системы обработки информации

и управления»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе

по дисциплине  Основы трансляции  

на тему  Исследование методов и алгоритмов работы

трансляторов предметно-ориентированных языков  

(вариант № 28)

Студент  Иванов Иван Иванович _____        ___________________

                                     (фамилия, имя, отчество)                                                           (подпись)

Группа ____КВТ-111_______________

Руководитель работы ___________________________        __А.Э. Панфилов___

            (подпись и дата подписания)        (инициалы и фамилия)                                             

Члены комиссии:

   ________________________        __________________

  (подпись и дата подписания)        (инициалы и фамилия)

   ________________________        __________________

  (подпись и дата подписания)        (инициалы и фамилия)

   ________________________        __________________

  (подпись и дата подписания)        (инициалы и фамилия)

Нормоконтролер ___________________________        ____А.Э. Панфилов____

          (подпись и дата подписания)                (инициалы и фамилия)                                             

Камышин 2012                                       


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное образовательное учреждение

высшего профессионального образования

«Волгоградский государственный технический университет»

Камышинский  технологический  институт (филиал)

федерального государственного образовательного учреждения

высшего профессионального образования

«Волгоградский государственный технический университет»

Факультет

Информационных технологий

Направление

230100.62 «Информатика и вычислительная техника»

Кафедра

Автоматизированные системы обработки информации

и управления»

Дисциплина

Основы трансляции

                                      

УТВЕРЖДАЮ:

Зав. кафедрой АСОИУ

_____________ И. В. Степанченко

«___» _____________ 2012 г.

Задание

на курсовую работу (проект)

Студент   Иванов Иван Иванович 

(фамилия, имя, отчество)

Группа___КВТ-111___________________

1. Тема: _Исследование методов и алгоритмов работы

трансляторов предметно-ориентированных языков  

(вариант № 28)

Утверждено приказом от «_____» ______________ 2012 г.  № _________

2. Срок представления работы (проекта) к защите «_20_»__декабря__2012 г.

3. Содержание расчетно-пояснительной записки: 1) обзор методов и

алгоритмов работы  интерпретатора языка MILAN;  

2) описание лексического и синтаксического анализаторов

модифицированного языка MILAN; 3) программная реализация

интерпретатора модифицированного языка MILAN;  

4) проведение тестирования интерпретатора

модифицированного языка MILAN.  

4. Перечень графического материала: 

 

5. Дата выдачи задания «_15_» __сентября__ 2012 г.

Руководитель проекта (работы)_______________________ __А.Э. Панфилов__

подпись, дата                                    инициалы и фамилия

Задание принял к исполнению________________________ __И.И. Иванов____

подпись, дата                                    инициалы и фамилия


РЕФЕРАТ

Отчет 39 страниц, 12 рисунков, 3 таблицы, 4 источника.

СИНТАКСИС, ЛЕКСЕМА, КОНСТАНТА, АВТОМАТ – РАСПОЗНАВАТЕЛЬ, ФОРМАЛЬНАЯ ГРАМАТИКА, ТЕРМИНАЛ, НЕТЕРМИНАЛ, АВТОМАТ С МАГАЗИННОЙ ПАМЯТЬЮ

Данная курсовая работа реализует лексический и синтаксический анализатор для учебного языка программирования MILAN на основе теории формальных грамматик и теории автоматов.

В работе рассмотрен синтаксис заданного языка программирования, разработана формальная грамматика для его описания, произведена модификация грамматики для учета дополнительных программных конструкций. Спроектированы автоматы для лексического анализа и распознавания лексем. Синтаксический анализ реализован по нисходящему методу рекурсивного спуска. Написана программа на языке высокого уровня Microsoft Visual C# для лексического и синтаксического анализа текста на учебном языке программирования.


СОДЕРЖАНИЕ

Лист

[1] 1 ПОСТАНОВКА ЗАДАЧИ

[2]
2 ОПИСАНИЕ ЯЗЫКА MILAN

[3]
3 ГРАММАТИКА МОДИФИЦИРОВАННОГО ЯЗЫКА MILAN

[4]
4 ОПИСАНИЕ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА МОДИФИЦИРОВАННОГО ЯЗЫКА MILAN

[4.1] 4.1 Лексемы языка MILAN

[4.2] 4.2 Синтаксическая диаграмма лексического анализатора

[4.3] 4.3 Расстановка ссылок передачи управления

[5]
5 ОПИСАНИЕ ИНТЕРПРЕТАТОРА МОДИФИЦИРОВАННОГО ЯЗЫКА MILAN

[6]
6 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ИНТЕРПРЕТАТОРА МОДИФИЦИРОВАННОГО ЯЗЫКА MILAN (С КОММЕНТАРИЯМИ)

[7]
7 ТЕСТИРОВАНИЕ ИНТЕРПРЕТАТОРА МОДИФИЦИРОВАННОГО ЯЗЫКА MILAN

[8]
ЗАКЛЮЧЕНИЕ

[9] СПИСОК ЛИТЕРАТУРЫ

КР 230100. 28. Д. ПЗ

Изм.

Лист

№ докум.

Подп.

Дата

Разраб.

Иванов И.И.

Исследование методов и алгоритмов работы трансляторов предметно-ориентированных языков (вариант № 28)

Лит.

Лист

Листов

Пров.

Панфилов А.Э.

У

3

39

КТИ ВолгГТУ

Н.контр.

Панфилов А.Э.

Утв.

Степанченко И.В.


1 ПОСТАНОВКА ЗАДАЧИ

Спроектировать и программно реализовать интерпретатор учебного языка MILAN  (MIni LANguage, МИЛАН), расширенного программными конструкциями, согласно варианту. В рамках интерпретатора спроектировать и построить лексический и синтаксический анализаторы для языка MILAN.

Расширенные программные конструкции в нотации БНФ, согласно варианту №28:

а) конструкция <оператор-переключатель>

<оператор-переключатель>::= SWITCH (<выражение>) {

                                 CASE <константа> : <последовательность операторов>

                             { CASE <константа> : <последовательность операторов> }

                              [ DEFAUT : <последовательность операторов> ] };

б) конструкция <оператор цикла>

<цикл-FОR>::= FOR <идентификатор> := <выражение> TO

<выражение> [STEP <выражение>]

          <последовательность операторов>

ENDFOR;

в) комментарии, заключенные внутри косых черт со звездочкой (/*…*/);

г) дополнительная арифметическая операция декремента (--), выполняющая уменьшение значения переменной на 1.

Интерпретатор языка MILAN должен быть написан на любом языке программирования. Входной язык интерпретатора должен удовлетворять следующим требованиям:

- входная программа должна соответствовать грамматике входного языка (согласно варианту задания);

- входная программа может быть разбита на строки произвольным образом, т. е. все пробелы и переводы строк должны игнорироваться интерпретатором;

- текст входной программы может содержать комментарии любой длины, которые должны игнорироваться интерпретатором.


2 ОПИСАНИЕ ЯЗЫКА MILAN

Начальным символом грамматики языка MILAN естественно выбран нетерминал <программа>. Каждая программа на языке MILAN начинается со слова BEGIN и заканчивается словом END. Между этими словами расположены операторы, разделенные символом «;». Типов операторов в MILAN четыре: вывод, присваивание, развилка, цикл. Будем считать, что в качестве условия в MILAN можно использовать пару выражений, разделенных знаками отношения. Терминалы грамматики языка MILAN приведены в таблице 1.

Таблица 1 - Терминалы грамматики языка MILAN

Терминалы

Обозначения

Ключевые слова

BEGIN, END, IF, THEN, ENDIF, ELSE, WHILE, DO, ENDDO,OUTPUT, READ

Знаки операций и отношений

+, -, *, /, =, >, <, >=, <=, <>

Латинские буквы в нижнем регистре

a, b, ..., z

Цифры

0, 1, ..., 9

Знак присваивания

:=

Разделитель операторов

;

Круглые скобки

(, )

 

Правила грамматики языка MILAN в нормальной форме Бэкуса-Наура:

W= <программа> ::= BEGIN <последовательность операторов> END

L = <последовательность операторов> ::= <оператор>|

<оператор>;<последовательность операторов>

S = <оператор> ::= <идентификатор>:=<выражение> |

OUTPUT(<выражение>) |

WHILE <условие> DO <последовательность операторов> ENDDO |

IF <условие> THEN <последовательность операторов> ENDIF |

IF <условие> THEN <последовательность операторов> ELSE <последовательность операторов> ENDIF

B = <условие> ::= <выражение> <знак отношения> <выражение>

E= <выражение> ::= <терм> |

<операция типа сложения> <терм> |

<терм> <операция типа сложения> <терм> |

<операция типа сложения> <терм> <операция типа сложения><терм>

T=<терм> ::= <множитель> | <множитель> <операция типа умножения> <множитель>

P=<множитель> ::= <идентификатор> | <константа> | READ | (<выражение>)

Y=<идентификатор>::= <буква> | <идентификатор><буква>|

<идентификатор> <цифра>

K=<константа> ::= <цифра> | <константа> <цифра>

O=<знак отношения> ::= > | < | >= | <= | = |<>

M=<операция типа умножения> ::= * | /

N=<операция типа сложения> ::= + | -

A= <буква> ::= a | b | ...| z

C= <цифра> ::= 0 | 1 | ...| 9

Данная грамматика недостаточно полно описывает синтаксис входной программы. Например, ключевые слова являются цепочками символов, хотя в языке это терминалы, между словами языка в тексте может быть произвольное количество пробелов и т.д.

Для устранения этих проблем предложения исходной программы удобнее представлять в виде последовательности лексем - элементов языка, внутреннее строение которых несущественно при синтаксическом анализе.

Например, лексемой может быть ключевое слово, имя переменной, константа и т.д. Просмотр исходного текста программы, распознавание и классификация различных лексем называется лексическим анализом.


3 ГРАММАТИКА МОДИФИЦИРОВАННОГО ЯЗЫКА MILAN

Модификация языка программирования MILAN заключается в добавлении программных конструкций, согласно заданию из раздела 1. В связи с этим, модифицированный язык MILAN будет содержать дополнительные символы-терминалы (таблица 2).

 

Таблица 2 - Дополнительные терминалы грамматики языка MILAN

Терминалы

Обозначения

Ключевые слова

SWITCH, CASE, DEFAUT, FOR, TO, STEP, ENDFOR

Двоеточие

:

Фигурные скобки

{, }

Комментарий

/*, */

Декремент

--

Правила грамматики модифицированного языка MILAN, также изменяться. Изменятся и добавятся следующие правила:

L = <последовательность операторов> ::= <оператор>|

<оператор>;<последовательность операторов>|

<оператор><комментарий>|

<оператор>;<комментарий><последовательность операторов>

S = <оператор> ::= <идентификатор>:=<выражение> |

OUTPUT(<выражение>) |

  WHILE<условие>DO<последовательность операторов>ENDDO|

IF<условие>THEN<последовательность операторов>ENDIF|

IF <условие> THEN <последовательность операторов> ELSE <последовательность операторов> ENDIF|

FOR <идентификатор>:=<выражение> TO <выражение> <последовательность операторов> ENDFOR|

FOR <идентификатор>:=<выражение> TO <выражение> STEP <выражение> <последовательность операторов> ENDFOR|

SWITCH(<выражение>){CASE <константа>: <последовательность операторов>}|

SWITCH(<выражение>){CASE <константа>: <последовательность операторов><содержимое>}

X= <содержимое> ::= CASE <константа>:<последовательность операторов>|

CASE <константа>:<последовательность операторов> <содержимое>|

DEFAUT : <последовательность операторов>

Y=<идентификатор>::=<идентификатор2>|--<идентификатор2>| <идентификатор2>--

I=<идентификатор2>::= <буква> | <идентификатор2><буква>|

<идентификатор2> <цифра>

Z= <комментарий> ::=/**/ | /*<любая цепочка>*/

R= <любая цепочка> ::=<символ>|<символ><любая цепочка>

Q= <символ> ::= a |...| z | 0 |...| 9 | а |...| я


4 ОПИСАНИЕ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА МОДИФИЦИРОВАННОГО ЯЗЫКА MILAN 

4.1 Лексемы языка MILAN

Часть транслятора, которая выполняет лексический анализ, называется лексическим анализатором. Лексический анализатор воспринимает исходный текст программы и преобразует его в последовательность лексем - промежуточный язык, удобный для синтаксического анализа. Кроме этого, лексический анализатор строит таблицы (массивы) идентификаторов и констант. Таким образом, основными функциями лексического анализатора являются: построение последовательности лексем; построение таблицы идентификаторов; построение таблицы констант; расстановка ссылок для передачи управления.

Для повышения эффективности последующих действий лексемы обычно представляются в виде пары (код, значение). На этапе синтаксического анализа используется первая компонента пары - код. Вторая компонента - значение, используется при семантических вычислениях. Для языка MILAN будем использовать определения лексем, представленные в таблице 3. Заметим, что при распознавании идентификаторов и констант лексическим анализатором используются следующие правила грамматики: IA | IA | IC, KC | KC, a | b | ... | z, C → 0 | 1 | ... | 9 .

Таким образом, в последовательности лексем идентификаторы и константы становятся терминалами и грамматика языка упрощается.

Таблица 3 - Таблица лексем

Название лексемы

Код

Запись в языке

Обозначение на Р-схеме

Значение

Служебные слова:

BEGIN

DO

ELSE

END

ENDDO

ENDIF

IF

OUTPUT

READ

THEN

WHILE

SWITСH

CASE

DEFAUT

FOR

TO

STEP

ENDFOR

1

2

3

4

5

6

7

8

9

10

11

21

22

23

24

25

26

27

BEGIN

DO

ELSE

END

ENDDO

ENDIF

IF

OUTPUT

READ

THEN

WHILE

SWITСH

CASE

DEFAUT

FOR

TO

STEP

ENDFOR

BEGIN

DO

ELSE

END

ENDDO

ENDIF

IF

OUTPUT

READ

THEN

WHILE

SWITСH

CASE

DEFAUT

FOR

TO

STEP

ENDFOR

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

Точка с запятой

12

;

tz

0

Знак отношения:

=

<>

>

<

>=

<=

13

=

<>

>

<

>=

<=

otn

0

1

2

3

4

5

Операция типа сложения:

+

-

14

+

-

ots

0

1

Операция типа умножения:

*

/

15

*

/

otu

0

1

Присваивание

16

:=

oprsv

0

Открывающаяся скобка

17

(

os

0

Закрывающаяся скобка

18

)

zs

0

Идентификатор

19

a, b23

id

Указатель на таблицу идентификаторов

Константа без знака

20

32, 0274

int

Указатель на таблицу констант

Операция декремента

28

--

dec

0

Открывающая фигурная скобка

29

{

ofs

0

Закрывающая фигурная скобка

30

}

zfs

0

4.2 Синтаксическая диаграмма лексического анализатора

Рассмотрим синтаксическую диаграмму (Р-схему) лексического анализатора языка MILAN (рисунок 1), которая описывает первые три функции: построение массив лексем, таблицы констант и идентификаторов.

Рисунок 1 – Р-схема лексического анализатора языка MILAN

На рисунке 1 введены следующие обозначения:

- *  – любое условие (любой символ).

- *’ – символ умножения. Апостроф добавлен для того, чтобы отличать его от символа *, обозначающего любой символ (любое условие).

Семантические функции к Р-схеме лексического анализатора (здесь, Position - текущая позиция в строке, просматриваемая лексическим анализатором; Number_String - текущая строка программы, просматриваемая лексическим анализатором):

y0: инициализация таблиц и переменных (Position=0, Number_String=1);

y1: чтение следующего символа программы на языке MILAN;

y2: увеличение счётчика текущей позиции (Position++);

y3: переход на новую строку в программе, увеличение счётчика текущей строки, и сброс счётчика позиции (Number_String++, Position=0);

y4: накопление символов ключевого слова или идентификатора;

y5: проверка на принадлежность выделенного слова к ключевым словам;

y6: проверка на принадлежность выделенного слова к идентификаторам;

y7: накопление символов константы;

y8: проверка на принадлежность выделенной константы таблице констант;

y9: запись сформированной лексемы в массив лексем;

y10: завершение работы лексического анализатора;

y11: формирование лексемы;

4.3 Расстановка ссылок передачи управления

В языке MILAN имеются операторы, изменяющие линейный порядок вычислений. Это операторы цикла, развилки и переключателя. Для организации правильных вычислений необходимо на некоторые лексемы поставит ссылки на номера лексем, куда будет передано управление при выполнении определенных условий. Такие ссылки записываются в качестве значения лексемы.

Для оператора цикла на лексему DO необходимо поставить ссылку r - номер лексемы, следующей за лексемой ENDDO. На эту лексему будет передано управление, если условие цикла - ложь. Для лексемы ENDDO поставить ссылку s - номер лексемы WHILE, увеличенный на 1. Это лексема, с которой начинается условие цикла. На нее передается управление после выполнения тела цикла (рисунок 2а).

Для оператора развилки на лексему IF необходимо поставить ссылку r - номер лексемы, стоящей после лексемы ELSE в полной форме оператора развилки (рисунок 2б), и стоящей после лексемы ENDIF в сокращенной форме (рисунок 2в). На эти лексемы передается управление при ложном условии оператора развилки.

Для оператора переключателя на лексему { необходимо поставить ссылку на следующую лексему CASE этого оператора; на каждую лексему : нужно поставить ссылку на следующую лексему CASE или DEFAUT из этого оператора. Переход по ссылкам на : будет осуществляться, если не нужно выполнять действия после : , установка ссылки на { необходимо для корректной работы вложенностей (рисунок 2г).

Для цикла со счётчиком на лексему TO ставится ссылка на лексему, следующую за ENDFOR (чтобы иметь возможность покинуть цикл), а на лексему ENDFOR ставится ссылка на следующую после TO лексему – чтобы можно было вернуться и повторить действия (рисунок 2д).

Рисунок 2 - Расстановка ссылок

Алгоритм расстановки ссылок в общем случае должен обрабатывать вложенные структуры циклов и развилок. Для такой обработки необходимо использовать четыре независимых стека: один для циклов WHILE, другой для развилок IF, третий для оператора переключателя SWITCH, четвёртый для циклов FOR. Синтаксическая диаграмма (Р-схема) расстановки ссылок представлена на рисунке 3.

Для описания семантических функций синтаксической диаграммы расстановки ссылок использованы следующие обозначения:

- Tab_Lexems[..].Code - массив кодов лексем;

- Tab_Lexems[..].Value -массив значений лексем;

- Number_Lexem - номер очередной рассматриваемой лексемы в массиве лексем;

- Stek_do - стек для циклов WHILE;

- Stek_if - стек для развилок IF;

- Stek_case – стек для операторов-переключателей SWITCH;

- Stek_to – стек для циклов FOR.

Рисунок 3 - Р-схема расстановки ссылок

Семантические функции к Р-схеме расстановки ссылок на рисунке 3:

y0: инициализация стеков и переменных, номер очередной лексемы Number_Lexem = 1, прочитать лексему с номером Number_Lexem;

y1: значение Number_Lexem занести в стек Stek_do (Number_LexemStek_do);

y2: снять вершину стека Stek_do в переменную s (s ← Stek_do), снять вершину стека Stek_do в переменную r (r ← Stek_do), значение r+1 присвоить лексеме с номером Number_Lexem [ENDDO → WHILE+1] (Tab_Lexems[ Number_Lexem].Value = r+1), значение Number_Lexem + 1 присвоить лексеме с номером s [DO → ENDDO+1] (Tab_Lexems[s].Value = Number_Lexem+1);

y3: значение Number_Lexem занести в стек Stek_if (Number_Lexem → Stek_if);

y4: снять вершину стека Stek_if в переменную r (r ← Stek_if), присвоить значение Number_Lexem+1 лексеме c номером r [THEN → ELSE+1] (Tab_Lexems[r].Value = Number_Lexem+1), занести в Stek_if значение Number_Lexem (Number_Lexem → Stek_if);

y5: снять вершину стека Stek_if в переменную r (r ← Stek_if), присвоить значение Number_Lexem+1 лексеме c номером r [THEN → ENDIF+1, ELSE → ENDIF+1] (Tab_Lexems[r].Value = Number_Lexem+1) занести в Stek_if значение Number_Lexem (Number_Lexem → Stek_if);

y6: завершить работу;

y7: Number_Lexem++, прочитать очередную лексему с номером Number_Lexem;

y8: значение Number_Lexem занести в стек Stek_case;

y9: снять вершину стека Stek_case в переменную r (r ← Stek_case), присвоить значение Number_Lexem лексеме c номером r [ : → CASE, : → DEFAUT, : → } ] (Tab_Lexems[r].Value = Number_Lexem);

y10: значение Number_Lexem занести в стек Stek_to;

y11: снять вершину стека Stek_to в переменную r (r ← Stek_to), присвоить значение Number_Lexem+1 лексеме c номером r [TO → ENDFOR+1] (Tab_Lexems[r].Value = Number_Lexem+1), присвоить значение r+1 лексеме с номером Number_Lexem [ENDFOR → TO+1] (Tab_Lexems[Number_Lexem]. Value = r+1.


5 ОПИСАНИЕ ИНТЕРПРЕТАТОРА МОДИФИЦИРОВАННОГО ЯЗЫКА MILAN 

После лексической обработки и расстановки ссылок последовательность лексем, массивы идентификаторов и констант поступают на обработку интерпретатору. Задача интерпретатора - распознать конструкции языка и выполнить действия, предписанные входной программой. Учитывая, что синтаксический разбор будет производиться над массивом лексем, уточним грамматику языка MILAN, которая будет использована для синтаксического анализа последовательности лексем. Множество терминалов в уточненной грамматике - это множество лексем.

Уточненная грамматика языка MILAN:

1) W → BEGIN L END

2) LS | S ; L

3) S I := E | OUTPUT (E) | WHILE B DO L ENDDO |

 IF B THEN L ENDIF | IF B THEN L ELSE L ENDIF |

 FOR I := E TO E U L ENDFOR |

 SWITCH (E) {CASE K : L Z }

4) BE O E

5) ET | NT | T N T | N T N T

6) T → P | P M P

7) P → X I Y | K | READ | (E)

8) I  id(0) | ... | id(i)

9) K  int(0) | ... | int(j)

10) O  otn(0) | ... | otn(5)

11) M → otu(0) | otu(1)

12) N → ots(0) | ots(1)

13) U → STEP E | ε 

14) X → dec | ε 

15) Y → dec | ε 

16) Z → CASE K : L Z | DEFAULT : L | ε 

Здесь i и j - число идентификаторов и констант; нетерминалы обозначают конструкции языка: W - <программа>; L - <последовательность операторов>; S - <оператор>; B - <условие>; E - <выражение>; T - <терм>;        P - <множитель>; K - <константа>; O - <знак отношения>; M - <операция типа умножения>; N - <операция типа сложения>; I - <идентификатор>, U - <шаг>,  X - <преддекремент>, Y - <постдекремент>,  Z - <содержимое>.

Для описания семантических функций синтаксической диаграммы интерпретатора используются следующие обозначения: Number_Lexem - номер очередной рассматриваемой лексемы в массиве лексем; Stek Res - стек результатов вычислений; StekIdent - стек идентификаторов; StekMul - стек для операций типа умножения; StekSum - стек для операций типа сложения; StekRel - стек для операции отношения; ArrIdent – массив текущих значений идентификаторов; StekCaseValue, StekDefaultValue – стеки для работы с оператором-переключателем; StekForExit – стек, хранящий адреса лексем, идущих сразу после ENDFOR; StekPostDec – стек, хранящий номера идентификаторов, которые после выполнения оператора нужно уменьшить на 1; StekPostDecCount – количество уменьшаемых идентификаторов в одном операторе.

Р-схема интерпретатора модифицированного языка MILAN приведена на рисунках 4-5.

Рисунок 4 - Р-схема интерпретатора: нетерминальные символы W, L, S, B, E, T

Рисунок 5 - Р-схема интерпретатора: нетерминальные символы Z, U, P, X, Y

 

Семантические функции к Р-схеме интерпретатора на рисунках 4-5:

y0: инициализация стеков и переменных;

y1: занесение в стек StekRes идентификатора Tab_Lexems[ Number_Lexem].Value;

y2: занесение в стек StekRes константы Tab_Lexems[Number_Lexem]. Value;

y3: прочитать целое число с терминала в переменную Cifra и положить его в StekRes (Cifra → StekRes);

y4: чтение следующей лексемы (Number_Lexem++);

y5: занесение в стек StekMul значение операции типа умножения (Tab_Lexems[ Number_Lexem].Value → StekMul);

y6: в переменную Bi снять элемент со стека StekRes (Bi ← StekRes), в переменную Ai снять элемент со стека StekRes (Ai ← StekRes), в переменную kmul снять элемент со стека StekMul (kmul ← StekMul), выполнить операцию типа умножение Ai otu(kmul) Bi и результат занести в стек StekRes;

y7: занесение в стек StekSum кода операции типа сложения;

y8: в переменную ksum снять со стека StekSum значение лексемы ots (ksum ← StekSum), если ksum=1, то снять в переменную Ai элемент со стека StekRes (Ai ← StekRes), сменить знак этого числа и занести его в стек StekRes  (-Ai → StekRes);

y9: занесение в стек StekSum кода операции типа сложения;

y10: в переменную Bi снять элемент со стека StekRes (Bi ← StekRes), в переменную Ai снять элемент со стека StekRes (Ai ← StekRes), в переменную ksum снять элемент со стека StekSum (ksum ← StekSum), выполнить операцию типа сложение Ai ots(ksum) Bi и результат занести в стек StekRes;

y11: добавление в стек StekRel значения операции типа отношение (Tab_Lexems[Number_Lexem].Value → StekRel);

y12: в переменную Bi снять элемент со стека StekRes (Bi ← StekRes), в переменную Ai снять элемент со стека StekRes (Ai ← StekRes), в переменную krel снять элемент со стека StekRel (krel ← StekRel), выполнить операцию сравнения Ai otn(krel) Bi и результат занести в стек StekRes ([0, 1] → StekRes);

y13: добавить значение лексемы с номером Number_Lexem в стек StekIdent (Tab_Lexems[Number_Lexem].ValueStekIdent);

y14: в переменную Ai снять элемент со стека StekRes (Ai ← StekRes), прочитать (без удаления) вершину стека StekIdent в переменную Bi (Bi ← StekIdent), идентификатору с номером Bi, присвоить значение Ai (ArrIdent[Bi] = Ai);

y15: в переменную Ai снять элемент со стека StekRes (Ai ← StekRes), напечатать переменную Ai;

y16: в переменную Ai снять элемент со стека StekRes (Ai ← StekRes), если Ai=1, то это истина, иначе - ложь;

y17: перейти на лексему номер Tab_Lexems[Number_Lexem].Value;

y18: в переменную Ai снять элемент со стека StekRes (Ai ← StekRes), если Ai=1, то это истина, иначе - ложь;

y19: перейти на лексему номер Tab_Lexems[Number_Lexem].Value-1;

y20: завершение работы;

y21: снять вершину стека StekRes в переменную Ai [StekRes →Ai]; отправить значение переменной Ai в стек StekCaseValue [Ai → StekCaseValue]; в стек StekDefaultValue занести 1 [1 → StekDefaultValue]

y22: прочитать (без удаления) вершину стека StekCaseValue в переменную Ai [StekCaseValue → Ai]; значение прочитанной константы занести в Bi [Tab_Constants[Tab_Lexems[Number_Lexem].Value] → Bi]; сравнить Ai и Bi: Ai==Bi – движение по TRUE, иначе по FALSE;

y23: снять вершину стека StekDefaultValue в переменную Ai [StekDefaultValue → Ai]; отправить значение 0 в стек StekDefaultValue [0 → StekDefaultValue];

y24: снять значение текущей лексемы в переменную Ai [Tab_Lexems[Number_Lexem].Value → Ai]; номеру текущей лексемы присвоить значение Ai [Number_Lexem=Ai];

y25: снять вершину стека StekDefaultValue в переменную Ai [StekDefaultValueAi]; сравнить Ai с 1: Ai==1 – движение по TRUE, иначе по FALSE;

y26: снять вершину стека StekCaseValue в перменную Ai [StekCaseValue → Ai];

y27: снять вершину стека StekRes в переменную Ai [StekRes → Ai];

y28: значение текущей лексемы занести в Ai [Tab_Lexems[Number_Lexem].Value → Ai]; номеру текущей лексемы присвоить значение переменной Ai [Number_Lexem=Ai];

y29: значение текущей лексемы занести в стек StekForExit [Tab_Lexems[Number_Lexem].Value → StekForExit];

y30: снять вершину стека StekRes в переменную ForAi [StekRes → ForAi];

y31: значение Ai занести в переменную ForBi [Ai → ForBi]; прочитать (без удаления) вершину стека StekIdent в переменную ForCi [StekIdent → ForCi]; занести в переменную ForDi значение идентификатора с номером ForCi [ForDi=ArrIdent[ForCi]]; сравнить ForDi+ForBi и ForAi: ForDi+ForB<=ForAi – движение по ветке TRUE, иначе по FALSE

y32: значение идентификатора с номером ForCi увеличить на значение переменной ForBi [ArrIdent[ForCi] += ForBi];

y33: снять вершину стека StekIdent в переменную Bi [StekIdentBi]; снять вершину стека StekForExit в Ai [StekForExit → Ai]; текущему номеру лексемы присвоить значение переменной Ai [Number_Lexem=Ai]

y34: значение следующей лексемы занести в Ai [Tab_Lexems[Number_Lexem+1].Value → Ai]; идентификатор c номером Ai уменьшить на 1[ArrIdent[Ai]--];

y35: в Ai занести значение лексемы Number_Lexem-1; переменную Ai занести в стек StekPostDec [Ai → StekPostDec];

y36: пока в StekPostDec есть элементы выполнять: снять вершину StekPostDec в переменную Ai (StekPostDec → Ai), идентификатор с номером Ai уменьшить на 1   (ArrIdent[Ai]--) ;

y37: снять вершину стека StekRes в переменную Ai [StekRes → Ai];

y38: в переменную Ai занести 1 [Ai=1].


6 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ИНТЕРПРЕТАТОРА МОДИФИЦИРОВАННОГО ЯЗЫКА MILAN (С КОММЕНТАРИЯМИ) 

Ниже приводятся фрагменты текста программной реализации интерпретатора языка MILAN, связанные с обработкой дополнительных конструкций языка.

6.1 Описание переменных класса интерпретатора

/* Коды ключевых слов языка МИЛАН */

const int _SWITCH_ = 21;

const int _CASE_ = 22;

const int _DEFAULT_ = 23;

const int _FOR_ = 24;

const int _TO_ = 25;

const int _STEP_ = 26;

const int _ENDFOR_ = 27;

const int _LBRACE_ = 30;    /*      {       */

const int _RBRACE_ = 31;    /*      }       */

const int _COLON_= 32;      /*      :       */

const int _DECREMENT_ = 33; /*     --       */

//Объявление стековых переменных для СА

static Stack<int> StekPostDec = new Stack<int>();

static Stack<int> StekCaseValue = new Stack<int>();

static Stack<int> StekDefaultValue = new Stack<int>();

static Stack<int> StekForExit= new Stack<int>();

6.2 Конструктор класса интерпретатора

static TranslatorMiLan()

{

//создаём массив ключевых слов

Table_Key_Words = new List<Element_Key_Words>();

//добавление «стандартных» ключевых слов

// ...

Table_Key_Words.Add(new Element_Key_Words( "SWITCH", _SWITCH_));

Table_Key_Words.Add(new Element_Key_Words("CASE", _CASE_));

Table_Key_Words.Add(new Element_Key_Words( "DEFAULT", _DEFAULT_));

Table_Key_Words.Add(new Element_Key_Words("FOR", _FOR_));

Table_Key_Words.Add(new Element_Key_Words("TO", _TO_));

Table_Key_Words.Add(new Element_Key_Words("STEP", _STEP_));

Table_Key_Words.Add(new Element_Key_Words( "ENDFOR", _ENDFOR_));

/* массив сообщений об ошибках */

Error_Message = new string[]{

//список «стандартных» сообщений об ошибках

// ...

/* 21 */ "Нехватка элементов в стеке Stack_case.",

/* 22 */ "Несоответствие в операторах SWITCH-{-CASE-:-DEFAULT-}.",

/* 23 */ "Нехватка элементов в стеке Stack_to.",

/* 24 */ "Несоответствие в операторах FOR-TO-STEP-ENDFOR.",

/* 25 */ "Конструкция <оператор>. Неверный оператор SWITCH.",

/* 26 */ "Конструкция <оператор>. Неверный оператор FOR."

};

} /* End TranslatorMiLan */

6.3 Метод расстановки ссылок

static void Setup_Refference()

{

 int r = 0;

 int s = 0;

Stack<int> Stek_if = new Stack<int>();

Stack<int> Stek_do = new Stack<int>();

Stack<int> Stek_case = new Stack<int>();

Stack<int> Stek_to = new Stack<int>();

Number_Lexem = 0;

do {

 switch (Tab_Lexems[Number_Lexem].Code) {

  /* обработка ссылок для WHILE, DO, ENDDO, THEN, ELSE, ENDIF */

  // ...

  case _SWITCH_:

   /*y7: Number_Lexem++, прочитать очередную лексему*/

   Number_Lexem++;

   while (Tab_Lexems[Number_Lexem].Code != _COLON_) {

    /*y7:Number_Lexem++, прочитать очередную лексему*/

    Number_Lexem++;

    if (Number_Lexem >= Number_Lexems_Programm) {

     /* Несоответствие в операторах SWITCH-CASE */

     Code_Error = 22; return;

    }

   }

   /* y8: Number_Lexem занести стек Stek_case */

   Stek_case.Push(Number_Lexem);

   break;

 case _COLON_:

  /* y8: Number_Lexem занести в стек Stek_case */

  Stek_case.Push(Number_Lexem);                     

  break;

 case _CASE_:

 case _DEFAULT_:

 case _RBRACE_:

  /* y9: снять вершину стека Stek_case в переменную r (r <-- Stek_case), присвоить значение Number_Lexem лексеме c номером r [:->CASE, :->DEFAUT, :->} ]         */

  try {

   r = Stek_case.Pop();

  }

  catch (InvalidOperationException) {

   /* Нехватка элементов в стеке CASE */

    Code_Error = 21; return;

  }

  /* :->CASE, :->DEFAUT, :->}  */

  Tab_Lexems[r].Value = Number_Lexem;

  break;

 case _TO_:

  /* y10: Number_Lexem занести в стек Stek_to */

  Stek_to.Push(Number_Lexem);

  break;

 case _ENDFOR_:

  /* y11: снять вершину стека Stek_to в переменную r (r <- Stek_to), присвоить значение Number_Lexem+1 лексеме c номером r [TO -> ENDFOR+1], присвоить значение r+1 лексеме с номером Number_Lexem [ENDFOR -> TO+1] */

  try {

   r = Stek_to.Pop();

  }

  catch (InvalidOperationException) {

   /* Нехватка элементов в стеке TO */

   Code_Error = 23; return;

  }

  /* TO --> ENDFOR+1 */

  Tab_Lexems[r].Value = Number_Lexem+1;

  /* ENDFOR --> TO+1 */

  Tab_Lexems[Number_Lexem].Value = r + 1;

  break;                      

 }

 /* y7: Number_Lexem++, прочитать очередную лексему */

 Number_Lexem++;

} while (Number_Lexem < Number_Lexems_Programm);

if (Stek_if.Count != 0)

 /* Несоответствие в операторах IF-THEN-ELSE-ENDIF */

 Code_Error = 4;

if (Stek_do.Count != 0)

 /* Несоответствие в операторах WHILE-DO-ENDDO */

 Code_Error = 3;

if (Stek_case.Count != 0)

 /* Несоответствие в операторах SWITCH-CASE-DEFAULT */

 Code_Error = 22;

if (Stek_to.Count != 0)

 /* Несоответствие в операторах FOR-TO-STEP-ENDFOR */

 Code_Error = 24;

} /* End Setup_Refference */

6.4 Метод выполнения лексического анализа

static public void Lexical_Analyzer()

{ /* Основной блок Лексического Анализатора */

 /* у0: инициализация таблиц и переменных */

bool isComment;

Position = 0;

Number_String = 1;

/* у1: чтение следующего символа */

if ((Input_Letter = Read_Next_Letter()) == '\x1a') {

 Console.WriteLine("ОШИБКА: Отсутствуют данные для разбора");                                        

 return;// Завершение работы интерпретатора

}

string ct_spec = "\x9\xa\xd\x20";

do {

 isComment = false;

 /* Игнорирование спец. символов и пробела */

 while (ct_spec.IndexOf(Input_Letter) != -1) {

  // обработка пробельных символов

  // ...

 }

 // если введённый символ является буквой

 if (char.IsLetter(Input_Letter)) Letter();

 // если введённый символ является цифрой

 else if (char.IsDigit(Input_Letter)) Digit();

 else {

  switch (Input_Letter) {

   /* обработка случаев для ‘;’, ‘=’, ‘>’, ‘<’, ‘+’, ‘*’, ‘(’, ‘)’,’\x1a’ */

   // ...

   case '-':

    /* у1: чтение следующего символа */

    Input_Letter = Read_Next_Letter(); Position++;

    if (Input_Letter == '-') {

     /* у11: формирование лексемы */

     Current_Lexem.Code = _DECREMENT_;

     Current_Lexem.Value = 0;

     /* у1: чтение следующего символа */

     Input_Letter = Read_Next_Letter(); Position++;

    }

    else {

     /* у11: формирование лексемы */

     Current_Lexem.Code = _SUMM_;

     Current_Lexem.Value = _MINUS_;

    }

    break;

   case '/':

    /* у1: чтение следующего символа */

    Input_Letter = Read_Next_Letter(); Position++;

    //проверка на комментарий

    if (Input_Letter == '*') {

     isComment = true;

     do {

      /* у1: чтение следующего символа */

      Input_Letter = Read_Next_Letter(); Position++;

      if (Input_Letter == '*') {

       /* у1: чтение следующего символа */

       Input_Letter = Read_Next_Letter(); Position++;

       if (Input_Letter == '/') {

       /* у1: чтение следующего символа */

        Input_Letter = Read_Next_Letter();Position++;

        break;

       }

      }

     } while (Input_Letter != '\x1a');

    }

    else {

     /* у11: формирование лексемы */

     Current_Lexem.Code = _MUL_;

     Current_Lexem.Value = _SLASH_;

    }

    break;

   case ':':

    /* у1: чтение следующего символа */

    Input_Letter = Read_Next_Letter(); Position++;

    if (Input_Letter == '=') {

     /* у11: формирование лексемы */

     Current_Lexem.Code = _ASSIGNMENT_;

     Current_Lexem.Value = 0;

     /* у1: чтение следующего символа */

     Input_Letter = Read_Next_Letter(); Position++;

    }

    else {

     /* у11: формирование лексемы */

     Current_Lexem.Code = _COLON_;

     Current_Lexem.Value = 0;

    }

    break;

   case '{':

    /* у11: формирование лексемы */

    Current_Lexem.Code = _LBRACE_;

    Current_Lexem.Value = 0;

    /* у1: чтение следующего символа */

    Input_Letter = Read_Next_Letter(); Position++;

    break;

   case '}':

    /* у11: формирование лексемы */

    Current_Lexem.Code = _RBRACE_;

    Current_Lexem.Value = 0;

    /* у1: чтение следующего символа */

    Input_Letter = Read_Next_Letter(); Position++;

    break;

   }

  }

 /* Проверка на ошибку */

 if (Code_Error >= 0) {

  Print_Error(1); return;

 }

 if (isComment == false) {

  /*у9:запись сформированной лексемы в массив лексем*/

  Number_Lexem++;

  Tab_Lexems.Add(new Element_Lexems( Current_Lexem));

 }

} while (true);

}

6.5 Метод обработки преддекремента

/* <преддекремент>::= -- |<пусто> */

static void ProcedureX()

{

if (Tab_Lexems[Number_Lexem].Code == _DECREMENT_){

 /* y34: значение следующей лексемы занести в Ai, идентификатор c номером Ai уменьшить на 1  */

 int Ai = Tab_Lexems[Number_Lexem + 1].Value;

 ArrIdent[Ai]--;

 /* y4: чтение следующей лексемы  */

 Number_Lexem++;

}

}

6.6 Метод обработки постдекремента

/* <постдекремент>::= -- |<пусто>    */

static void ProcedureY()

{

if (Tab_Lexems[Number_Lexem].Code == _DECREMENT_) {

 /* y35: в Ai занести значение лексемы, переменную Ai занести в стек StekPostDec (Ai -> StekPostDec) */ 

 int Ai = Tab_Lexems[Number_Lexem - 1].Value;

 StekPostDec.Push(Ai);

 /* y4: чтение следующей лексемы */

 Number_Lexem++;

}

}

6.7 Метод обработки конструкции «множитель»

/* <множитель> ::= [--]<идентификатор>[--] | <константа> | READ | (<выражение>)  */

static void ProcedureP()

{

int NomIdent = 0;

int Cifra = 0;

switch (Tab_Lexems[Number_Lexem].Code) {

 case _DECREMENT_:

  /* Обработка конструкции <преддекремент> */

  ProcedureX();

  /*  y1: занесение в стек StekRes идентификатора  Tab_Lexems[Number_Lexem]->Value */

  NomIdent = Tab_Lexems[Number_Lexem].Value;

  StekRes.Push(ArrIdent[NomIdent]);

  /* y4: чтение следующей лексемы */

  Number_Lexem++;

  /* Обработка конструкции <постдекремент> */

  ProcedureY();

  return;

 /* Обработка для случаев _IDENTIFIER_, _CONSTANT_, _READ_, _LPARENT_ */

 // ...

}

} /* End ProcedureP */

6.8 Метод обработки конструкции «оператор»

/* <оператор> ::= <идентификатор>:=<выражение> | OUTPUT(<выражение>) | WHILE <условие> DO <последовательность операторов> ENDDO| IF <условие> THEN <последовательность операторов> ENDIF | IF <условие> THEN <последовательность операторов> ELSE <последовательность операторов> ENDIF | FOR <идентификатор>:=<выражение> TO <выражение> <последовательность операторов> ENDFOR | FOR <идентификатор>:=<выражение> TO <выражение> STEP <выражение> <последовательность операторов> ENDFOR |  SWITCH(<выражение>) {CASE <константа>: <последовательность операторов>} | SWITCH (<выражение>){CASE <константа>: <последовательность операторов><содержимое>} */

static void ProcedureS()

{

int Ai, Bi;

int ForAi, ForBi, ForCi, ForDi;

switch (Tab_Lexems[Number_Lexem].Code) {

 /* Обработка для случаев _IDENTIFIER_, _OUTPUT_, _WHILE_, _IF_ */

 // ...

 case _SWITCH_:

   /* y4: чтение следующей лексемы */

  Number_Lexem++;

  if (Tab_Lexems[Number_Lexem].Code == _LPAREN_){

   /* y4: чтение следующей лексемы */

    Number_Lexem++;

   /* Обработка конструкции <выражение> */

   ProcedureE();

   /* Проверка на ошибки при обработке <выражение> */

   if (Code_Error != -1) return;

  }

  else {

   /* Неверный оператор SWITCH.*/

   Code_Error = 25; return;

  }

  if (Tab_Lexems[Number_Lexem].Code == _RPAREN_){

   /* y4: чтение следующей лексемы */

    Number_Lexem++;

  }

  else {

   /* Неверный оператор SWITCH.*/

    Code_Error = 25; return;

  }

  if (Tab_Lexems[Number_Lexem].Code == _LBRACE_){

   /* y21: снять вершину стека StekRes в переменную Ai (StekRes -> Ai); отправить значение переменной Ai в стек StekCaseValue (Ai -> StekCaseValue); в стек StekDefaultValue занести 1 (1 -> StekDefaultValue)*/

   Ai = StekRes.Pop();

   StekCaseValue.Push(Ai);

   StekDefaultValue.Push(1);

   /* y4: чтение следующей лексемы */

   Number_Lexem++;

  }

  else {

   /* Неверный оператор SWITCH.*/

   Code_Error = 25; return;

  }

  if (Tab_Lexems[Number_Lexem].Code == _CASE_)

   /* y4: чтение следующей лексемы */

   Number_Lexem++;

  else {

   /* Неверный оператор SWITCH.*/

   Code_Error = 25; return;

  }

  if (Tab_Lexems[Number_Lexem].Code == _CONSTANT_){

   /* y22: прочитать (без удаления) вершину стека StekCaseValue в переменную Ai (StekCaseValue -> Ai); значение прочитанной константы занести в Bi; сравнить Ai и Bi: Ai==Bi – движение по TRUE, иначе по FALSE;*/

   Ai=StekCaseValue.Peek();

   Bi=Tab_Constants[Tab_Lexems[Number_Lexem].Value];                        

    /* y4: чтение следующей лексемы */

   Number_Lexem++;

   if(Ai==Bi) {//обработка TRUE для ветки CASE

    /* y23: снять вершину стека StekDefaultValue в переменную Ai (StekDefaultValue -> Ai); отправить значение 0 в стек StekDefaultValue (0 -> StekDefaultValue) */

    Ai=StekDefaultValue.Pop();

    StekDefaultValue.Push(0);

    if (Tab_Lexems[Number_Lexem].Code == _COLON_)

     /* y4: чтение следующей лексемы */

     Number_Lexem++;

    }

    else {

     /* Неверный оператор SWITCH.*/

      Code_Error = 25; return;

    }

    /* <последовательность операторов> после : */

     ProcedureL();

    if (Code_Error != -1) return;

   }

   else { //обработка FALSE для ветки CASE

    if (Tab_Lexems[Number_Lexem].Code == _COLON_){

     /* y24: снять значение текущей лексемы в переменную Ai (Tab_Lexems[Number_Lexem].Value -> Ai); номеру текущей лексемы присвоить значение Ai */

     Ai = Tab_Lexems[Number_Lexem].Value;

     Number_Lexem = Ai;

    }

    else {

    /* Неверный оператор SWITCH.*/

     Code_Error = 25; return;

   }

  }

  /* Обработка конструкции <содержимое> после : */

  ProcedureZ();

  if (Code_Error != -1) return;

  if (Tab_Lexems[Number_Lexem].Code == _RBRACE_){

   /* y26: снять вершину стека StekCaseValue в перменную Ai (StekCaseValue -> Ai); */

   Ai = StekCaseValue.Pop();

   /* y4: чтение следующей лексемы */

   Number_Lexem++;

  }

  else {

   /* Неверный оператор SWITCH.*/

    Code_Error = 25; return;

  }

 }

 else {

  /* Неверный оператор SWITCH.*/

   Code_Error = 25; return;

 }

 break;

case _FOR_:

  /* y4: чтение следующей лексемы */

 Number_Lexem++;

if (Tab_Lexems[Number_Lexem].Code == _IDENTIFIER_){

  /* y13: добавить значение лексемы с номером Number_Lexem в стек StekIdent */

 StekIdent.Push(Tab_Lexems[Number_Lexem].Value);

 /* y4: чтение следующей лексемы */

 Number_Lexem++;

}

else {

 /*Конструкция <оператор>. Неверный оператор FOR*/

  Code_Error = 26; return;

 }

if (Tab_Lexems[Number_Lexem].Code == _ASSIGNMENT_)

  /* y4: чтение следующей лексемы */

 Number_Lexem++;  

else {

 /*Конструкция <оператор>. Неверный оператор FOR*/

   Code_Error = 26; return;

}

/* Обработка конструкции <выражение> после := */

ProcedureE();

if (Code_Error != -1) return;

/* y14: в переменную Ai снять элемент со стека StekRes (Ai <- StekRes), прочитать (без удаления) вершину стека StekIdent в переменную Bi (Bi <- StekIdent), идентификатору с номером Bi, присвоить значение Ai */

Ai = StekRes.Pop();

Bi = StekIdent.Peek();

ArrIdent[Bi] = Ai;

if (Tab_Lexems[Number_Lexem].Code == _TO_){

 /* y29: значение текущей лексемы занести в стек StekForExit [Tab_Lexems[Number_Lexem].Value -> StekForExit]*/

 StekForExit.Push(Tab_Lexems[Number_Lexem].Value);

 /* y4: чтение следующей лексемы */

 Number_Lexem++;

}

else {

 /*Конструкция <оператор>. Неверный оператор FOR*/

 Code_Error = 26; return;

}

/* Обработка конструкции <выражение> после TO */

ProcedureE();

if (Code_Error != -1) return;

/* y27: снять вершину стека StekRes в переменную Ai */

Ai = StekRes.Pop();

/* Обработка конструкции U=<шаг> после TO */

if (Tab_Lexems[Number_Lexem].Code == _STEP_){

 /* y4: чтение следующей лексемы */

 Number_Lexem++;

 /*Обработка конструкции <выражение> после STEP*/

 ProcedureE();

 if (Code_Error != -1) return;

 /* y37: снять вершину стека StekRes в переменную Ai*/

 Ai = StekRes.Pop();

}

else

 /* y38: В переменную Ai занести 1 */

 Ai = 1;

/* Обработка конструкции <последовательность операторов> - тела цикла FOR */

ProcedureL();

if (Code_Error != -1) return;

if (Tab_Lexems[Number_Lexem].Code == _ENDFOR_){

 /* y28: значение текущей лексемы занести в Ai (Tab_Lexems[Number_Lexem].Value -> Ai); номеру текущей лексемы присвоить значение переменной Ai */

 Ai = Tab_Lexems[Number_Lexem].Value;

 Number_Lexem = Ai;

}

else {

 /*Конструкция <оператор>. Неверный оператор FOR*/

 Code_Error = 26; return;

}

// выполнение тела цикла FOR

do {

 /* Обработка конструкции <выражение> после TO*/

 ProcedureE();

 if (Code_Error != -1) return;

/*y30:снять вершину стека StekRes в переменную ForAi*/

 ForAi = StekRes.Pop();

 /* Обработка конструкции U=<шаг> после TO */

 if (Tab_Lexems[Number_Lexem].Code == _STEP_){

  /* y4: чтение следующей лексемы */

  Number_Lexem++;

  /*Обработка конструкции <выражение> после STEP*/

  ProcedureE();

  if (Code_Error != -1) return;

  /*y37:снять вершину стека StekRes в переменную Ai*/

  Ai = StekRes.Pop();

 }

 else

  /* y38: В переменную Ai занести 1 */

  Ai = 1;

  /* y31: значение Ai занести в переменную ForBi (Ai-> ForBi); прочитать (без удаления)вершину стека StekIdent в переменную ForCi (StekIdent -> ForCi); занести в переменную ForDi значение идентификатора с номером ForCi (ForDi=ArrIdent[ForCi]); сравнить ForDi+ForBi и ForAi: ForDi+ForB<=ForAi – движение по ветке TRUE, иначе по FALSE */

  ForBi = Ai;

  ForCi = StekIdent.Peek();

  ForDi = ArrIdent[ForCi];

  if (ForDi + ForBi <= ForAi){                            

   //движение по TRUE - продолжение итерации цикла FOR

   /* y32: значение идентификатора с номером ForCi увеличить на значение переменной ForBi */

   ArrIdent[ForCi] += ForBi;

   /* Обработка конструкции <последовательность операторов>  - тела цикла FOR */

   ProcedureL();

   if (Code_Error != -1) return;

   /* y28: значение текущей лексемы занести в Ai (Tab_Lexems[Number_Lexem].Value -> Ai); номеру текущей лексемы присвоить значение переменной Ai */

   Ai = Tab_Lexems[Number_Lexem].Value;

   Number_Lexem = Ai;

  }

  else {

   //движение по ветке FALSE - завершение цикла FOR

   /* y33: снять вершину стека StekIdent в переменную Bi (StekIdent -> Bi); снять вершину стека StekForExit в Ai (StekForExit -> Ai); текущему номеру лексемы присвоить значение переменной Ai */

   Bi = StekIdent.Pop();

    Ai = StekForExit.Pop();

    Number_Lexem = Ai;

   }

  } while (ForDi + ForBi <= ForAi);

  break;

 }

 /* y36: пока в StekPostDec есть элементы выполнять: снять вершину StekPostDec в переменную Ai (StekPostDec -> Ai), идентификатор с номером Ai уменьшить на 1 */

for (int i = StekPostDec.Count; i > 0; i--){

 Ai = StekPostDec.Pop();

  ArrIdent[Ai]--;

 }

 return;

} /* End ProcdureS */

6.9 Метод обработки конструкции «содержимое»

/* <содержимое>::= CASE<константа> : <последовательность операторов> <содержимое> | DEFAULT:<последовательность операторов> | <пусто>  */

static void ProcedureZ()

{

int Ai, Bi;

if (Tab_Lexems[Number_Lexem].Code== _CASE_) {

 /*y4: чтение следующей лексемы */

 Number_Lexem++;

 if (Tab_Lexems[Number_Lexem].Code == _CONSTANT_){

  /* y22: прочитать (без удаления) вершину стека StekCaseValue в переменную Ai (StekCaseValue -> Ai); значение прочитанной константы занести в Bi (Tab_Constants[Tab_Lexems[Number_Lexem].Value] -> Bi); сравнить Ai и Bi: Ai==Bi – движение по TRUE, иначе по FALSE*/

  Ai=StekCaseValue.Peek();

  Bi=Tab_Constants[Tab_Lexems[Number_Lexem].Value];

   /* y4: чтение следующей лексемы */

  Number_Lexem++;

  if(Ai==Bi) {//обработка TRUE для ветки CASE

   /* y23: снять вершину стека StekDefaultValue в переменную Ai (StekDefaultValue -> Ai); отправить значение 0 в стек StekDefaultValue (0 -> StekDefaultValue) */

   Ai=StekDefaultValue.Pop();

    StekDefaultValue.Push(0);

    if (Tab_Lexems[Number_Lexem].Code == _COLON_)

    /* y4: чтение следующей лексемы */

    Number_Lexem++;

   else {

    /* Неверный оператор SWITCH.*/

    Code_Error = 25; return;

    }

   /* <последовательность операторов> после : */

   ProcedureL();

   if (Code_Error != -1) return;

  }

  else {//обработка FALSE для ветки CASE

   if (Tab_Lexems[Number_Lexem].Code == _COLON_){

    /* y24: снять значение текущей лексемы в переменную Ai (Tab_Lexems[Number_Lexem].Value -> Ai); номеру текущей лексемы присвоить значение Ai */

    Ai = Tab_Lexems[Number_Lexem].Value;

    Number_Lexem = Ai;

   }

   else {

    /* Неверный оператор SWITCH.*/

    Code_Error = 25; return;

    }

   }

  /* Обработка конструкции <содержимое> после :*/

   ProcedureZ();

    if (Code_Error != -1) return;

  }

   else {

   /* Неверный оператор SWITCH.*/

    Code_Error = 25; return;

   }

  }

  if (Tab_Lexems[Number_Lexem].Code == _DEFAULT_){

  /* y25: снять вершину стека StekDefaultValue в переменную Ai (StekDefaultValue -> Ai); сравнить Ai с 1: Ai==1 – движение по TRUE, иначе по FALSE*/

  Ai=StekDefaultValue.Pop();

   /* y4: чтение следующей лексемы */

  Number_Lexem++;

   if(Ai==1){//движение по TRUE для ветки DEFAULT

   if (Tab_Lexems[Number_Lexem].Code == _COLON_)

     /* y4: чтение следующей лексемы */

    Number_Lexem++;

   else {

    /* Неверный оператор SWITCH.*/

     Code_Error = 25; return;

    }

    /* <последовательность операторов> после : */

    ProcedureL();

    if (Code_Error != -1) return;

  }

   else {//обработка FALSE для ветки DEFAULT

   if (Tab_Lexems[Number_Lexem].Code == _COLON_){

    /* y24: снять значение текущей лексемы в переменную Ai (Tab_Lexems[Number_Lexem].Value -> Ai); номеру текущей лексемы присвоить значение Ai */

   Ai = Tab_Lexems[Number_Lexem].Value;

    Number_Lexem = Ai;

   }

   else {

   /* Неверный оператор SWITCH.*/

    Code_Error = 25; return;

   }

  }

}

}


7 ТЕСТИРОВАНИЕ ИНТЕРПРЕТАТОРА МОДИФИЦИРОВАННОГО ЯЗЫКА MILAN 

7.1 Тестовые примеры без ошибок

7.1.1 Тестовый пример №1.

BEGIN 

x:=0;

FOR n:=0 TO 100 STEP 10

z:=READ;

x:=x+z;

ENDFOR;

OUTPUT(x)

END

Рисунок 6 – Результат работы тестового примера №1

7.1.2 Тестовый пример №2.

BEGIN /*здесь находится начало программы*/

x:=10;

OUTPUT(x);

OUTPUT(x--);   /* постдекремент */

OUTPUT(--x);  /* преддекремент */

OUTPUT(x);

END

Рисунок 7 – Результат работы тестового примера №2

7.1.3 Тестовый пример №3.

BEGIN

x:=READ;

n:=READ;

SWITCH ( n ) {

CASE 1 : OUTPUT( x/10)  /* если n=1, то поделить */

CASE 2: OUTPUT(x*10)   /* если n=2, то умножить  */

DEFAULT : OUTPUT(0) }  /* иначе, 0 */

END

Рисунок 8 – Результат работы тестового примера №3

7.2 Тестовые примеры c ошибками

7.2.1 Тестовый пример №4.

BEGIN

FOR n:=0  TO

x:=x+1;

ENDFOR;

OUTPUT(x)

END

Рисунок 9 – Результат работы тестового примера №4

7.2.2 Тестовый пример №5.

BEGIN 

x:=READ;

n:=READ;

SWITCH(n){

CASE 1 : OUTPUT( x/10)  /* если n=1, то поделить */

CASE 2: OUTPUT(x*10)    /* если n=2, то умножить  */

DEFAULT : OUTPUT(0)     /* иначе, 0 */

END

Рисунок 10 – Результат работы тестового примера №5

7.2.3 Тестовый пример №6.

BEGIN

n:=56--;

OUTPUT(n);

END

Рисунок 11 – Результат работы тестового примера №6

7.2.4 Тестовый пример №7.

BEGIN

IF x/2 THEN

x:=2%x;

ENDIF;

OUTPUT(0)

END

Рисунок 12 – Результат работы тестового примера №7


ЗАКЛЮЧЕНИЕ 

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

Приобретены навыки написания лексического и синтаксического анализаторов языков, описываемых LL(1)-грамматикой.

Согласно заданию, в грамматику языка MILAN были добавлены новые конструкции и произведена разработка лексического и синтаксического анализаторов интерпретатора модифицированного языка.

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

Таким образом, был закреплён изученный курс по дисциплине «Основы трансляции».

 


СПИСОК ЛИТЕРАТУРЫ

1. Гагарина Л.Г., Кокорева Е.В. Введение в теорию алгоритмических языков и компиляторов: учеб. пособ. [Текст] / Л.Г. Гагарина, Е.В. Кокорева. – М.: ИД «ФОРУМ», 2011. – 176 с.

2. Мозговой М.В. Классика программирования: языки, автоматы, компиляторы. Практический подход [Текст] / М.В. Мозговой. – СПб.: «Наука и техника», 2006. – 320 с.

3. Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технолигии, инструменты [Текст]: пер. с англ. / А. Ахо, Р. Сети, Д. Ульман. – М.: Изд. дом «Вильямс», 2003. – 768 с.

4. Карпов Ю.Г. Основы построения трансляторов [Текст] / Ю.Г. Карпов. – СПб.: БХВ-Петербург, 2005. – 272 с.

КР 230100. 28 Д. ПЗ

Лист

Изм.

Лист

№ докум.

Подп.

Дата

39

35


 

А также другие работы, которые могут Вас заинтересовать

76856. Вены головы 186.78 KB
  Кровь из вен головы поступает в яремные вены шеи и внутреннее позвоночное сплетение. Поверхностные вены головного мозга впадают в венозные синусы твердой мозговой оболочки. cerebri superiores имеющих восходящее направление: вены пре и постцентральной извилин предлобные лобные теменные и затылочные которые впадают в верхний сагиттальный синус.
76857. Вены верхней конечности 179.85 KB
  В области надплечья и плеча они вливаются в глубокие вены. Вторые проходят вместе с артериями собирая кровь от костей мышц суставов и вливаясь в подключичные вены. Вены верхней конечности клапанные начинаясь от пальцев они формируют на кисти тыльные венозные сети и ладонные дуги с перфорантными ветвями на предплечье и плече поверхностные и глубокие вены с анастомозами между ними.
76858. Вены нижней конечности 182.02 KB
  Прободающие вены соединяют между собой многочисленные глубокие и поверхностные вены расположенные в разных плоскостях и уровнях. В области лодыжек перфорантные вены не имеют прямых связей с подкожной сетью. Поверхностные вены вливаются в глубокие в разных отделах ноги в подколенной ямке и под паховой связкой.
76859. Принципы строения лимфатической системы 182.88 KB
  Лимфатические капилляры отсутствуют в тех органах и тканях где кровеносные капилляры не имеют базальной мембраны: в головном и спинном мозге и их оболочках глазном яблоке внутреннем ухе эпителии кожи и слизистых оболочек в пульпе селезенки хрящах костном мозге и плаценте. Начиная с выносящих лимфатические сосуды располагают полулунными клапанами в виде складок эндотелия придающих сосуду снаружи четкообразный вид. Лимфатические сосуды подразделяются на висцеральные органные и париетальные поверхностные и глубокие. Внеорганные...
76860. Грудной проток 180.8 KB
  Образование протока явление многовариантное: слияние поясничных или кишечных или тех и других стволов правой и левой стороны; слияние только поясничных и кишечных стволов 25; образование стволами млечной цистерны cistern chyli в виде конусовидного ампулярного расширения 75; сетевидное начало в виде крупного петлистого сплетения из поясничных чревных брыжеечных стволов и выносящих сосудов. Проток возникает на уровне XII грудного II поясничного позвонков и располагается рядом с брюшной аортой. В грудном протоке от начала...
76861. Правый лимфатический проток 179.63 KB
  Он проходит рядом с подключичной веной имеет клапаны и сфинктер впадает либо в венозный угол и вены его образующие либо в правый лимфатический проток. Бронхомедиастинальный правый ствол truncus bronchomedistinlis собирается из выносящих лимфатических сосудов от средостенных трахеобронхиальных и бронхолегочных лимфатических узлов. Он имеет клапаны впадает в правый лимфатический проток или в правый яремный венозный угол или в вены его составляющие – внутреннюю яремную подключичную плечеголовную.
76862. Лимфатический узел 181.03 KB
  Лимфатические синусы в паренхиме узла делятся на краевой подкапсульный – sinus mrginlis seu subcpsulris корковые – sinus corticles мозговые – sinus medullres воротный – sinus chilris. По приносящим сосудам лимфа поступает в краевой синус из него в корковые из них – в мозговые синусы а потом – в воротный откуда начинаются выносящие лимфатические сосуды. Лимфатические узлы располагаются группами с вариабельным числом узлов в каждой 420 66404 всего образуется до 150 региональных групп. У висцеральных узлов наблюдается несколько...
76863. Лимфатические сосуды и узлы головы и шеи 182.17 KB
  Они формируются из однослойной сети кожных лимфатических капилляров и посткапилляров и впадают в поверхностные лимфатические узлы расположенные на границе головы и шеи. Поверхностные лимфатические узлы головы. Они принимают лимфу от лобной теменной височной областей наружного уха слуховой трубы верхней губы и от околоушной железы а направляют её в поверхностные и глубокие шейные узлы.
76864. Лимфатические сосуды и узлы руки 180.47 KB
  По поверхностным сосудам оттекает лимфа от кожи подкожной клетчатки поверхностной фасции поверхностных мышц используя крупные и длинные лимфатические сосуды трех групп латеральной медиальной и средней. Латеральные лимфатические сосуды 510 начинаются от кожи IIII пальцев латеральной поверхности кисти предплечья плеча проходят вместе с цефалической веной и впадают в подмышечные лимфатические узлы латеральную группу. Медиальные лимфатические сосуды 515 начинаются на IVV пальцах медиальной поверхности кисти предплечья...