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

Размещено на http://www.allbest.ru

Министерство образования и науки Российской Федерации

Волжский политехнический институт (филиал) федерального государственного бюджетного образовательного учреждения высшего профессионального образования

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

(ВПИ (филиал) ВолгГТУ)

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

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

по дисциплине «ОСНОВЫ ТРАНСЛЯЦИИ»

на тему «ИССЛЕДОВАНИЕ МЕТОДОВ И АЛГОРИТМОВ РАБОТЫ ТРАНСЛЯТОРОВ ПРЕДМЕТНО-ОРИЕНТИРОВАННЫХ ЯЗЫКОВ»

Студент: Наумчук Игорь Владимирович

Волжский 2014 г.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 Обзор методов и алгоритмов работы интерпретатора языка МИЛАН

1.2 Грамматика модифицированного языка МИЛАН в виде синтаксических диаграмм Вирта

1.3 Описание лексического анализатора модифицированного языка МИЛАН

1.4 Описание процесса расстановки ссылок модифицированного языка МИЛАН

1.5 Описание интерпретатора модифицированного языка МИЛАН

2. ИССЛЕДОВАТЕЛЬСКАЯ ЧАСТЬ

2.1 Программная реализация интерпретатора модифицированного языка МИЛАН

2.2 Разработка тестов и тестирование модифицированного языка МИЛАН

ЗАКЛЮЧЕНИЕ

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

ВВЕДЕНИЕ

Курсовая работа - заключительный этап изучения дисциплины.

Цель курсовой работы: разработка интерпретатора языка МИЛАН с незначительными модификациями.

Программная реализация интерпретатора выполнена на языке PHP. Входной язык интерпретатора удовлетворяет следующим требованиям:

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

- текст входной программы может содержать <оператор-переключатель>:

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

{

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

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

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

}

- текст входной программы может содержать <цикл-FОR>:

<цикл-REPEAT>::= REPEAT <последовательность операторов> UNTIL <условие>

- текст входной программы может содержать <оператор-инкремент>: ++

- текст входной программы может содержать комментарии любой длины, которые должны игнорироваться интерпретатором: комментарий в круглых скобках со звездочками. Пример: { раздел описания переменных }

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 Обзор методов и алгоритмов работы интерпретатора языка МИЛАН

Работа интерпретатора производится в два этапа: лексический и синтаксический анализ.

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

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

1.2 Грамматика модифицированного языка МИЛАН в виде синтаксических диаграмм Вирта

Грамматика в виде диаграмм Вирта представляет собой схематическое описание какого-либо нетерминального символа языка. В качестве начального нетерминального символа выбран нетерминал «программа». Каждая программа начинается со слова BEGIN и заканчивается словом END. Между этими словами расположены операторы, разделенные символом «;». Типов операторов в расширенной грамматике МИЛАНа пять: вывод, присваивание, инкремент, развилка, цикл. По принципу вложенности диаграммы Вирта описывают возможные конструкции языка и выражение их через терминальные и нетерминальные символы. Множество терминальных символов модифицированного языка представлено в таблице 1.

Таблица 1

Терминалы грамматики языка МИЛАН

Терминалы	Обозначения
Служебные слова	BEGIN, CASE, DEFAULT, DO, ELSE, END, ENDDO,ENDFOR, ENDIF,REPEAT, IF, OUTPUT, READ, STEP, SWITCH, THEN, TO, WHILE,UNTIL
знаки операций и отношений	+, ++, -, *, /, =, >, <, >=, <=, <>
латинские буквы в нижнем регистре	a, b, ..., z
цифры	0, 1, ..., 9
знак присваивания	:=
разделитель операторов	;
знаки комментария	{, }
знаки конструкций	(, ), {, }, :

Диаграммы Вирта для группы нетерминалов 1 («программа», «комментарий» и «последовательность операторов») представлены на рисунке 1.

Программа

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

Рисунок 1 - Группа нетерминалов 1

Блок комментария введен в грамматику формально, так как не будет вводиться на уровне лексем. Еще на этапе лексического анализа скобки комментария и любые заключенные в них символы будут игнорироваться. Таким образом, комментарий можно вставлять произвольно по тексту программы, нетерминал «текст комментария» подразумевает множество любых символов.

Диаграмма Вирта для нетерминала оператор представлена на рисунке 2.

Рисунок 2 - Нетерминал «оператор»

В качестве условия используется пара выражений, разделенных знаками отношения. Соответствующая диаграмма представлена на рисунке 3.

Рисунок 3 - Нетерминал «условие»

Группа нетерминалов 2 («выражение», «терм» и «множитель») позволяют составлять различные выражения в конструкциях, и представлены на рисунке 4.

Рисунок 4 - Группа нетерминалов 2

Нетерминальные символы «идентификатор» и «константа» представлены на рисунке 5.

Рисунок 5 - Нетерминалы «идентификатор» и «константа»

Группа нетерминалов 3 замещаются терминальными символами и представляют собой минимальные единицы языка («операция отношения», «цифра», «буква», «операция умножения», «операция сложения») представлены на рисунке 6.

Рисунок 6 - Группа нетерминалов 6

1.3 Описание лексического анализатора модифицированного языка МИЛАН

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

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

Для расширенного языка МИЛАН используются определения лексем, представленные в таблице 2.

Таблица 2

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

Название лексемы	Код	Запись в языке	Обозначение	Значение
Служебные слова: BEGIN DO ELSE END ENDDO ENDIF IF OUTPUT READ THEN WHILE	1 2 3 4 5 6 7 8 9 10 11	BEGIN DO ELSE END ENDDO ENDIF IF OUTPUT READ THEN WHILE	BEGIN DO ELSE END ENDDO ENDIF IF OUTPUT READ THEN WHILE	0 Ссылка на лексему после ENDDO Ссылка на лексему после ENDIF 0 Ссылка на лексему после WHILE 0 0 0 0 Ссылка на лексему после ENDIF или ELSE 0
Точка с запятой	12	;	tz	0
Знак отношения: = <> > < >= <=	13	= <> > < >= <=	otn	k(=)=0 k(<>)=1 k(>)=2 k(<)=3 k(>=)=4 k(<=)=5
Операция типа сложения: + -	14	+ -	ots	k(+)=0 k(-)=1
Операция типа умножения: * /	15	* /	otu	k(*)=0 k(/)=1
Присваивание	16	:=	oprsv	0
Открывающаяся скобка	17	(	os	0
Закрывающаяся скобка	18	)	zs	0
Идентификатор	19	a, b23	id	Указатель на таблицу идентификаторов
Константа без знака	20	32, 0274	int	Указатель на таблицу констант
Добавлено
Служебные слова: CASE DEFAULT REPEAT SWITCH UNTIL	21 22 23 24 25	CASE DEFAULT REPEAT SWITCH UNTIL	CASE DEFAULT REPEAT SWITCH UNTIL	0 0 0 0 Ссылка на REPEAT+1
Инкремент	26	++	inc	0
Двоеточие	27	:	td	Ссылка на лексему CASE, DEFAULT или }
Начало SWITCH	28	{	bswch	0
Конец SWITCH	29	}	eswch	0
Открытие комментария	30	{	ocom	0
Закрытие комментария	31	}	zcom	0

Синтаксическая диаграмма (R-схема) расширенного лексического анализатора языка МИЛАН описывающая построение массива лексем, таблицы констант и идентификаторов представлена на рисунке 7.

Обозначение к R-схеме лексического анализатора:

$Position - текущая позиция в строке, просматриваемая ЛА;

$Number_String - текущая строка программы, просматриваемая ЛА;

* - любой символ).



Рисунок 7 - R-схема лексического анализатора

Семантические функции к R-схеме лексического анализатора:

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

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

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

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

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

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

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

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

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

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

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

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

Пример №1. Рассмотрим пример обработки лексическим анализатором программы на расширенном языке МИЛАН, содержащей все операторы языка и осуществляющей разбиение числа на единицы, сотни, десятки.

Листинг программы:

BEGIN

next:=1;

rng:=1;

c1:=READ;

c2:=c1;

WHILE next=1 DO

c1:=c1/10;

IF c1=0 THEN

next:=0

ELSE

rng++

ENDIF

ENDDO;

OUTPUT(rng);

k:=1;

REPEAT

SWITCH(k)

{

CASE 1 : rez:=c2-(c2/10)*10

CASE 2 : rez:=c2/10

CASE 3 : rez:=c2/100

DEFAULT: rez:=999

};

OUTPUT(rez);

k++;

UNTIL k<=rng

END

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

Таблица 3

Таблица лексем для листинга примера 1

номер	0	1	2	3	4	5	6	7	8	9
0	-	1,0	19,1	16,0	20,1	12,0	19,2	16,0	20,1	12,0
10	19,3	16,0	9,0	12,0	19,4	16,0	19,3	12,0	11,0	19,1
20	13,0	20,1	2,42	19,3	16,0	19,3	15,1	20,2	12,0	7,0
30	19,3	13,0	20,3	10,38	19,1	16,0	20,3	3,41	19,2	26,0
40	6,0	5,19	12,0	8,0	17,0	19,2	18,0	12,0	19, 5	16, 0
50	20,1	12,0	23,0	24,0	17,0	19,5	18,0	28,0	21, 0	20,1
60	27, 72	19,6	16,0	19,4	14,1	17,0	19,4	15,1	20,2	18,0
70	15,0	20,2	21,0	20,4	27,80	19,6	16,0	19,4	15,1	20,2
80	21,0	20,5	27,88	19,6	16,0	19,4	15,1	20,6	22,0	27,93
90	19,6	16,0	20,7	29,0	12,0	8,0	17,0	19,6	18,0	25,53
100	19,5	13,5	19,2	4,0

Таблицы идентификаторов и констант представлены соответствующими таблицами 4 и 5.

Таблица 4

Таблица идентификаторов для листинга примера 1

№	Идентификатор
1	next
2	rng
3	c1
4	c2
5	k
6	rez

Таблица 5

Таблица констант для листинга примера 1

№	Константа
1	1
2	10
3	0
4	2
5	3
6	100
7	999

1.4 Описание процесса расстановки ссылок модифицированного языка МИЛАН

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

Для оператора цикла WHILE на лексему DO необходимо поставить ссылку на номер лексемы, следующей за лексемой ENDDO (рис. 8, а) для выхода из цикла при невыполнении условия. А для возврата по циклу - ссылку с ENDDO на лексему, следующую за WHILE, т.е. проверка условия цикла.

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

Для оператора развилки SWITCH ссылки указываются следующим образом: каждая лексема «:» в строке выбора ссылается на нижележащую ветку выбора (CASE или DEFAULT) или на лексему завершения оператора «}»(рис. 8, г, д). Условия проверки выполнения ветки для CASE и DEFAULT различны. Для ветки CASE условие не выполняется - если константа не соответствует проверяемому значению, а для DEFAULT - если флаг прохождения ветви выставлен (который устанавливается в случае прохода в ветви CASE).

Для работы оператора цикла необходимо поставить ссылку возврата к лексеме REPEAT+1 на лексему UNTIL, по которой будет осуществляется переход при выполнении условия UNTIL, иначе - выход из цикла (рис 8,б).



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

Для независимой обработки вложенных структур используются отдельные стеки для циклов и развилок. Синтаксическая диаграмма (R-схема) расстановки ссылок представлена на рисунке 9.



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

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

- $Tab_Lexems[…]->Code - массив номеров лексем;

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

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

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

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

- $Stek_repeat - стек для циклов REPEAT;

- $Stek_switch - стек для развилок SWITCH.

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

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

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

y1: значение $Number_Lexem занести стек $Stek_do ($Number_Lexem>$Stek_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: Значение $Number_Lexem+1 занести в стек $Stek_repeat ($Number_Lexem+1>$Stek_repeat);

y7: Снять вершину стека $Stek_repeat в переменную $r ($r<$Stek_repeat). Лексеме с номером $Number_Lexem присвоить значение $r ($Tab_Lexems[$Number_Lexem]->Value=$r) [UNTIL>REPEAT+1].

y8: Значение $Number_Lexem занести в стек $Stek_switch ($Number_Lexem>$Stek_ switch);

y9: Снять вершину стека $Stek_switch в переменную $r ($r<$Stek_switch). Снять вершину стека $Stek_switch в переменную $s ($s < $Stek_switch). Значение $r присвоить лексеме с номером $s ($Tab_Lexems[$s]->Value=$r) [: >CASE, : >DEFAULT]. Значение $Number_Lexem занести в стек $Stek_switch ($Number_Lexem>$Stek_switch);

y10: Снять вершину стека $Stek_switch в переменную $r ($r<$Stek_switch). Присвоить значение $Number_Lexem лексеме с номером $r ($Tab_Lexems[$r]->Value=$Number_Lexem)[: >}];

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

y12: завершить работу.

1.5 Описание интерпретатора модифицированного язык МИЛАН

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

Уточненная грамматика расширенного языка МИЛАН:

1) W > BEGIN L END

2) L > S | S; L

3) S > I:=E | I++ | OUTPUT(E) | WHILE B DO L ENDDO | IF B THEN L ENDIF | IF B THEN L ELSE L ENDIF | REPEAT L UNTIL B | SWITCH(E){V} | SWITCH(E){VX}

4) V > F | FV

5) F > CASE K : L

6) X > DEFAULT : L

7) B > EOE

8) E > T | NT | T N T | N T N T

9) T > P | P M P

10) P > I | I++ | K | READ | (E)

11) I > id(0) | ... | id(i)

12) K > int(0) | ... | int(j)

13) O > otn(0) | ... | otn(5)

14) M > otu(0) | otu(1)

15) N > ots(0) | ots(1)

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

Обозначения для описания семантических функций синтаксической диаграммы интерпретатора: $Tab_Lexems[…]->Code - массив номеров лексем; $Tab_Lexems[…]->Value - массив значений лексем; $Number_Lexem - номер очередной рассматриваемой лексемы в массиве лексем; $StekRes - стек результатов вычислений; $StekIdent - стек идентификаторов; $StekMul - стек для операций типа умножения; $StekSum - стек для операций типа сложения; $StekRel - стек для операции отношения; $ArrIdent - стек текущих значений идентификаторов; $StekRep - стек для циклов REPEAT; $StekSw - стек для развилок switch.

Синтаксическая диаграмма интерпретатора нетерминальных символов W, L, S представлена на рисунке 12, для символов P, B, E, T на рисунке 10 и для символов V, F, X на рисунке 12 соответственно.

Рисунок 10 - R-схема интерпретатора: нетерминальные символы P, B, E, T.

Рисунок 11 - R-схема интерпретатора: нетерминальные символы V, F, X. 

Рисунок 12 - R-схема интерпретатора: нетерминальные символы W, L, S.

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

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

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

y2: удалить вершину стека $StekRes, снять значение лексемы $Number_Lexem-1 в переменную $Ai ($Tab_Lexems[Number_Lexem-1]->Value>$Ai), увеличить значение идентификатора с номером $Ai на 1 ($ArrIdent[$Ai]++); Обновить вершину стека $StekRes новым значением $ArrIdent[$Ai];

y2p: снять значение лексемы $Number_Lexem-1 в переменную $Ai ($Tab_Lexems[Number_Lexem-1]->Value>$Ai), увеличить значение идентификатора с номером $Ai на 1 ($ArrIdent[$Ai]++). Удалить вершину стека $StekIdent;

y3: занесение в стек $StekRes константы $Tab_Lexems[$Number_Lexem]->Value;

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

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

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

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

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

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

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]->Value>$StekIdent);

y14: в переменную $Ai снять элемент со стека $StekRes ($Ai<$StekRes), в переменную $Bi снять со стека $StekIdent значение лексемы ident ($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: перейти на лексему номер $Tab_Lexems[$Number_Lexem]->Value-1;

y19: занести в стек $StekRep значение лексемы $Number_Lexem ($StekRep<--$Tab_Lexems[$Number_Lexem]->Value);

y20: удалить вершину стека $StekRep, выйти из цикла;

y21: снять вершину стека $StekRep в переменную $Ai ($Ai<$StekRes), перейти на лексему с номером $Ai ($Number_Lexem <$Ai);

y24: снять вершину стека $StekRes в переменную $Ai ($Ai<$StekRes), занести в стек $StekSw значение 0 ($StekSw<0), занести значение $Ai в стек $StekSw ($StekSw<$Ai);

y25: снять со стека $StekSw вершину (удалить) 2 раза

y26: снять значение текущей константы в переменную $Ai, скопировать вершину стека $StekSw (без удаления) в переменную $Bi ($Bi<$StekSw), выполнить операцию сравнения между переменной $Ai и $Bi ($Ai = $Bi), если равенство выполняется, то истина, иначе - ложь;

у27: снять вершину стека $StekSw в переменную $Ai ($Ai<$StekSw), удалить вершину стека $StekSw, поместить в стек $StekSw значение 1 ($StekSw<1), поместить в стек $StekSw значение $Ai ($StekSw<$Ai);

у28: снять вершину стека $StekSw в переменную $Ai ($Ai<$StekSw), скопировать в переменную $Bi (без удаления) значение со стека $StekSw ($Bi<$StekSw), если $Bi=0, то истина, иначе - ложно, поместить в стек $StekSw переменную $Ai обратно ($StekSw<$Ai);

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



2. ИССЛЕДОВАТЕЛЬСКАЯ ЧАСТЬ

2.1 Программная реализация интерпретатора модифицированного языка МИЛАН

<?php

//Описание классов

/* элемент массива лексем */

class Element_Lexems

{

/* код лексемы */

public $Code = 0 ;

/* значение лексемы */

public $Value = 0 ;

}

/* Элемент таблицы ключевых [зарезервированных] слов */

class Element_Key_Words

{

/* Ключевое слово */

public $Key_Word = '';

/* Код ключевого слова */

public $Code_Key_Word = 0;

}

//Описание констант

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

//ADD

define("MAX_KEY_WORDS",16);

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

define("_BEGIN_", 1);

define("_DO_", 2);

define("_ELSE_", 3);

define("_END_", 4);

define("_ENDDO_", 5);

define("_ENDIF_", 6);

define("_IF_", 7);

define("_OUTPUT_", 8);

define("_READ_", 9);

define("_THEN_", 10);

define("_WHILE_", 11);

//ADD

define("_CASE_", 21);

define("_DEFAULT_", 22);

define("_REPEAT_", 23);

define("_SWITCH_", 24);

define("_UNTIL_", 25);

/* Кода лексем языка МИЛАН */

define("_SEMICOLON_",12); /* ; */

define("_RELATION_",13); // операция типа отношение

/* значения операции типа отношение */

define("_EQUAL_", 0); /* = */

define("_NOTEQUAL_", 1); /* <> */

define("_GT_", 2); /* > */

define("_LT_", 3); /* < */

define("_GE_", 4); /* >= */

define("_LE_", 5); /* <= */

define("_SUMM_", 14); /* операция типа сложение */

/* значения операции типа сложение */

define("_PLUS_", 0); /* + */

define("_MINUS_", 1); /* - */

define("_MUL_", 15); /* операция типа умножение */

/* значения операции типа сложение */

define("_STAR_", 0); /* * */

define("_SLASH_", 1); /* / */

define("_ASSIGNMENT_", 16); /* присваивание */

define("_LPAREN_", 17); /* ( */

define("_RPAREN_", 18); /* ) */

define("_IDENTIFIER_", 19); /* идентификатор */

define("_CONSTANT_", 20); /* константа */

//ADD

define("_INC_", 26); /* ++ */

define("_TD_", 27); /* : */

define("_BSWCH_", 28); /* { */

define("_ESWCH_", 29); /* } */

define("_OCOM_", 30); /* {* */

define("_ZCOM_", 31); /* *} */

/* Таблица ключевых [зарезервированных] слов языка МИЛАН */

/* Ключевые слова в массиве должны быть упорядочены, т.к. */

/* поиск в массиве осуществляется методом "бинарного поиска" */

$Table_Key_Words = Array();

/* Функция возвращает экземпляр элемента лексем */

function ct_AddElement($Key_Word, $Code_Key_Word)

{

$ct_Element = new Element_Key_Words;

$ct_Element->Key_Word = $Key_Word;

$ct_Element->Code_Key_Word = $Code_Key_Word;

return $ct_Element;

}

//создаём новый массив

//ADD

$Table_Key_Words[1] = ct_AddElement('BEGIN', _BEGIN_);

$Table_Key_Words[2] = ct_AddElement('CASE', _CASE_);

$Table_Key_Words[3] = ct_AddElement('DEFAULT', _DEFAULT_);

$Table_Key_Words[4] = ct_AddElement('DO', _DO_);

$Table_Key_Words[5] = ct_AddElement('ELSE', _ELSE_);

$Table_Key_Words[6] = ct_AddElement('END', _END_);

$Table_Key_Words[7] = ct_AddElement('ENDDO', _ENDDO_);

$Table_Key_Words[8] = ct_AddElement('ENDIF', _ENDIF_);

$Table_Key_Words[9] = ct_AddElement('IF', _IF_);

$Table_Key_Words[10] = ct_AddElement('OUTPUT', _OUTPUT_);

$Table_Key_Words[11] = ct_AddElement('READ', _READ_);

$Table_Key_Words[12] = ct_AddElement('REPEAT', _REPEAT_);

$Table_Key_Words[13] = ct_AddElement('SWITCH', _SWITCH_);

$Table_Key_Words[14] = ct_AddElement('THEN', _THEN_);

$Table_Key_Words[15] = ct_AddElement('UNTIL', _UNTIL_);

$Table_Key_Words[16] = ct_AddElement('WHILE', _WHILE_);

/* максимально допустимое количество идентификаторов в программе */

define("MAX_IDENTIFIERS", 15);

/* максимально допустимое количество констант в программе */

define("MAX_CONSTANTS", 15);

/* максимально допустимое количество лексем в программе */

define("MAX_LEXEMS", 500);

/* массив сообщений об ошибках в программе на МИЛАНе */

$Error_Message = Array(

/* 1 */ 'Неизвестный символ в программе.',

/* 2 */ 'Превышение максимального количества идентификаторов.',

/* 3 */ 'Превышение максимального количества констант.',

/* 4 */ 'Переполнение массива лексем.',

/* 5 */ 'Переполнение стека Stek_do.',

/* 6 */ 'Нехватка элементов в стеке Stek_do.',

/* 7 */ 'Неправильное обращение к функции для работы со стеком Stek_do.',

/* 8 */ 'Переполнение стека Stek_if.',

/* 9 */ 'Нехватка элементов в стеке Stek_if.',

/* 10 */ 'Неправильное обращение к функции для работы со стеком Stek_if.',

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

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

/* 13 */ 'Конструкция <программа>. Нет BEGIN.',

/* 14 */ 'Конструкция <программа>. Нет END.',

/* 15 */ 'Переполнение стека StekIdent.',

/* 16 */ 'Конструкция <оператор>. Неверное присваивание.',

/* 17 */ 'Нехватка элементов в стеке StekRes.',

/* 18 */ 'Нехватка элементов в стеке StekIdent.',

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

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

/* 21 */ 'Конструкция <оператор>. Отсутствует THEN в операторе IF.',

/* 22 */ 'Конструкция <оператор>. Отсутствует ENDIF в операторе IF.',

/*23*/'Конструкция<оператор>.Отсутствует ELSE или ENDIF в операторе IF.',

/* 24 */ 'Конструкция <условие>. Неверная операция отношения.',

/* 25 */ 'Переполнение стека StekRel.',

/* 26 */ 'Нехватка элементов в стеке StekRel.',

/* 27 */ 'Переполнение стека StekRes.',

/* 28 */ 'Нехватка элементов в стеке StekMul.',

/* 29 */ 'Переполнение стека StekMul.',

/* 30 */ 'Деление на ноль.',

/* 31 */ 'Конструкция <множитель>. Нет закрывающей скобки.',

/* 32 */ 'Переполнение стека StekSum.',

/* 33 */ 'Нехватка элементов в стеке StekSum.',

/* 34 */ 'Незакрытый комментарий в программе.',

/* 35 */ 'Несоответствие в операторах REPEAT-UNTIL.',

/* 36 */ 'Переполнение стека Stek_repeat.',

/* 37 */ 'Нехватка элементов в стеке Stek_repeat.',

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

/* 39 */ 'Переполнение стека Stek_switch.',

/* 40 */ 'Нехватка элементов в стеке Stek_switch.',

/* 41 */ 'Конструкция <оператор>. Неверная конструкция инкремента.',

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

/* 43 */ 'Переполнение стека $StekRep.',

/* 44 */ 'Нехватка элементов в стеке $StekRep.',

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

/* 46 */ 'Переполнение стека $StekSw.',

/* 47 */ 'Нехватка элементов в стеке $StekSw.',

/* 48 */ 'Оператор SWITCH. Некорректная конструкция CASE.',

/* 49 */ 'Оператор SWITCH. Некорректная конструкция DEFAULT.',

/* 50 */ 'Конструкция <множитель>. Неверный оператор инкремента.',

/* 51 */ 'Конструкция <выражение>. Неверный оператор инкремента.');

/* массив лексем */

$Tab_Lexems = Array ();

/* массив идентификаторов */

$Tab_Identifiers = Array ();

/* массив констант */

$Tab_Constants = Array ();

/* Имя программы на языке МИЛАН */

$Input_Programm = '';

/* Входной файл программы на языке МИЛАН */

/* Входной символ программы на языке МИЛАН */

$Input_Letter = '';

/* Номер очередного символа в программе */

$Number_Letter = 0;

/* Код ошибки */

$Code_Error = -1 ;

/* Номер строки и позиции в которой ошибка */

$Number_String = 0;

$Position = 0;

/* Номер очередной лексемы в программе */

$Number_Lexem = 0;

/* Сформированная Лексическим Анализатором лексема */

$Current_Lexem = new Element_Lexems

/* Количество лексем в программе */

$Number_Lexems_Programm = 0;

/* Номер очередного идентификатора в программе */

$Number_Identifiers = 0;

/* Номер очередной константы в программе */

$Number_Constants = 0;

/*********************************************************************/

/* Stek_Integer(...) */

/* Функция для работы со стеками типа Integer. */

/* Аргументы: */

/* Operation - код операции ( 0 - инициализация стека; */

/* 1 - извлечение элемента из стека */

/* в Element; */

/* 2 - добавление элемента */

/* в стек Element; */

/* $Current_Stek - массив из 50 элементов ; */

/* $Top - вершина стека ; */

/* $Element - элемент который кладется в стек или в который */

/* возвращается вершина стека. */

/* Функция возвращает значение TRUE, если операция работы со стеком */

/* выполнена успешно, FALSE - в противном случае. */

/*********************************************************************/

function Stek_Integer( $Operation ,

&$Current_Stek,

&$Top,

&$Element)

{

global $Code_Error;

switch ($Operation):

/* Инициализация стека */

Case 0 :

$Top=0;

for ($i=1;$i<=50;$i++)

{

$Current_Stek[$i]=0;

}

break;

/* Извлечение элемента со стека */

Case 1 :

if ($Top<=0)

{

return FALSE;

}

else

{

$Element=$Current_Stek[$Top];

$Top--;

}

break;

/* Добавление элемента в стек */

Case 2 :

if ($Top>=50)

{

return FALSE;

}

else

{

$Top++;

$Current_Stek[$Top]=$Element;

}

break;

/* Сообщение об ошибке */

default:

$Code_Error=4;

return FALSE;

endswitch;

return TRUE;

} /* End Stek_Integer*/

/*********************************************************************/

/* Replicate(<ВырC>,<ВырN>) */

/* Аргументы: <ВырC>, <ВырN>. */

/* Результат: Функция возвращает символьную строку, полученную */

/* повторением <ВырN> раз строки <ВырC>. */

/*********************************************************************/

Function Replicate($String_Letter, $Num)

{

$Word='';

for($i=1; $i<=$Num; $i++)

$Word = $Word . $String_Letter;

return $Word;

} /* End Replicate */

/*********************************************************************/

/* Space(<ВырN>) */

/* Аргументы: <ВырN>. */

/* Функция возвращает строку, состоящую из <ВырN> пробелов.

*/

/*********************************************************************/

Function Space($Num)

{

return Replicate(' ',$Num);

} /* End Space */

/*********************************************************************/

/* Print_Error */

/* Процедура вывода на экран сообщения об ошибке для */

/* Лексического Анализатора */

/* Расстановки ссылок */

/* Интерпретатора */

/*********************************************************************/

function Print_Error($Variant)

{

global $Number_String;

global $Position;

global $Number_Lexem;

global $Code_Error;

global $Error_Message;

global $Tab_Lexems;

global $ct_buf;

switch ($Variant)

{

Case 1 :

print ('<html><head><title>РЕЗУЛЬТАТ РАБОТЫ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА</title></head><body><br><H2 align="center">РЕЗУЛЬТАТ РАБОТЫ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА</H2><br><hr><br>

<table cellspacing="3" cellpadding="3" align="center"><tr><td >НАЙДЕНА ОШИБКА: </td><td align="center"><font color="red"> ' . $Error_Message[$Code_Error] . '</font></td></tr>

<tr><td> СТРОКА: </td><td align="left"><font color="blue">' . $Number_String . '</font></td></tr>

<tr><td> ПОЗИЦИЯ:</td><td align="left"><font color="blue">' . $Position . '</font></td></tr></table>

<br><hr><br><div align="center">

<form method="post" action="INTERFACE.php">

<input type="submit" value=" ОК " >

<input name="source" type="hidden" value="'.$ct_buf.'">

</form></div></body></html> ');

break;

Case 2 :

print ('<html><head><title>РЕЗУЛЬТАТ РАБОТЫ СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА</title></head><body><br><H2 align="center">РЕЗУЛЬТАТ РАБОТЫ СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА</H2><br><hr><br>

<table cellspacing="3" cellpadding="3" align="center"><tr><td >НАЙДЕНА ОШИБКА: </td><td align="center"><font color="red"> ' . $Error_Message[$Code_Error] . '</font></td></tr>

<tr><td> ЛЕКСЕМА: </td><td align="left"><font color="blue">' . $Number_Lexem . '</font></td></tr></table>

<br><hr><br><div align="center">

<form method="post" action="INTERFACE.php">

<input type="submit" value=" ОК ">

<input name="source" type="hidden" value="'.$ct_buf.'">

</form></div></body></html> ');

break;

}

} /* End Print_Error */

/*********************************************************************/

/* Isdigit(<ВырC>) */

/* Функция возвращает значение TRUE, если <вырC> начинается с цифры. */

/*********************************************************************/

Function Isdigit($Figure)

{

$ct_res=preg_match("/[0-9]/i", $Figure{0});

return $ct_res;

} /* End Isdigit */

/*********************************************************************/

/* Isalpha(<ВырC>) */

/* Функция возвращает значение TRUE, если <вырC> начинается с буквы. */

/*********************************************************************/

Function Isalpha($Letter)

{

$ct_res=preg_match("/[A-Za-zА-Яа-я]/i", $Letter{0});

return $ct_res;

} /* End Isalpha */

/*----------------------------------------------------------------------------------------- НАЧАЛО ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА*/

/*********************************************************************/

/* Lexical_Analyzer */

/* Лексический анализатор: Выполняет первую стадию транслятора - */

/* лексический анализ. Осуществляет просмотр исходного текста */

/* программы на МИЛАНе, распознавание и классификацию лексем. */

/* Строит: */

/* массив лексем; */

/* массив идентификаторов; */

/* массив констант; */

/* Производит расстановку ссылок для передачи управления. */

/* Входные данные: текст с программой на МИЛАНе. */

/* Результат: массив лексем, массив идентификаторов и констант. */

/*********************************************************************/

function Lexical_Analyzer()

{ /*********************************************************************/

/* Found_in_Table_Key_Words */

/* Функция бинарного поиска в таблице ключевых слов */

/* Вход: Word - выражение символьного типа, Code - код найденного */

/* ключевого слова */

/* Выход: Функция возвращает значение TRUE, если Word ключевое слово, и */

/* FALSE - в противном случае. В переменной Code содержится код */

/* ключевого слова, или 0 в противном случае. */

/*********************************************************************/

Function Found_in_Table_Key_Words($Word, &$Code)

{

global $Table_Key_Words;

$k=0;

$m=1;

$n=MAX_KEY_WORDS;

while ($m<=$n):

$k=intval($m+($n-$m) / 2);

if ($Word==$Table_Key_Words[$k]->Key_Word)

{

$Code=$Table_Key_Words[$k]->Code_Key_Word;

return TRUE;

}

elseif ($Word>$Table_Key_Words[$k]->Key_Word)

{

$m=$k+1;

}

else

$n=$k-1;

endwhile;

return FALSE;

}

/*********************************************************************/

/* Found_in_Table_Identifiers(<ВырC>) */

/* Функция для проверки идентификатора в таблице идентификаторов. */

/* Аргументы: <вырC>, содержащее имя идентификатора. */

/* Результат: номер идентификатора в таблице идентификаторов */

/* ( 0 - если идентификатор <ВырC> отсутствует в */

/* таблице идентификаторов). */

/*********************************************************************/

Function Found_in_Table_Identifiers($Identifier)

{

global $Tab_Identifiers;

global $Number_Identifiers;

for( $i=1;$i<=$Number_Identifiers;$i++)

{

if ($Tab_Identifiers[$i]==$Identifier)

return $i;

}

return 0;

} /* End Found_in_Table_Identifiers */

/*Функция Вывода сообщения об ошибке */

function Print_Error_Message()

{

global $Code_Error;

if ($Code_Error>-1)

{

Print_Error(1);

return 0;

}

//Если ошибок нет, то нормальное завершение лексического анализа

End_Lexical_Analyzer();

}

//Функция выхода из Лексического Анализатора

function End_Lexical_Analyzer()

{

global $Number_Lexems_Programm;

global $Number_Lexem;

global $Code_Error;

$Number_Lexems_Programm=$Number_Lexem;

/* Расстановка ссылок для операторов цикла и развилки */

Setup_Refference();

/* Проверка на ошибки, появившиеся в процессе расстановки ссылок */

if ($Code_Error>-1)

{

Print_Error(2);

return 0;

}

/* Печать таблицы массива лексем */

global $ct_milanMode;

global $ct_buf;

if($ct_milanMode==0)

{

Print_Tab_Lexems();

/* Печать таблицы массивов идентификаторов и констант */

Print_Tab_Identifiers_Constants();

/* Закрытие файла с программой на языке МИЛАН */

/* функция y10: нормальное завершение работы лексического анализатора */

global $Tab_Identifiers;

global $Tab_Constants;

global $ct_TabLEX_Value_str;

global $ct_TabLEX_Code_str;

//поля типа hidden используются для сохранения данных полученных в результате работы лексического анализатора $Tab_Constants, $Tab_Identifiers

print (

"<br><hr><br><div align=\"center\"><font color=\"blue\"> НОРМАЛЬНОЕ ЗАВЕРШЕНИЕ РАБОТЫ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА</font><br><br>

<form id=\"sourceform\" name=\"sourceform\" action='MILAN.PHP' method=\"post\" >

<input name=\"source\" type=\"hidden\" value='".$ct_buf."'> <!--поле хранит исходный код программы -->

<input name=\"lex_code\" type=\"hidden\" value='".$ct_TabLEX_Code_str."'> <!--поле хранит значения CODE таблицы лексем -->

<input name=\"lex_value\" type=\"hidden\" value='".$ct_TabLEX_Value_str."'> <!--поле хранит значения VALUE таблицы лексем -->

<input name=\"tab_ident\" type=\"hidden\" value='" .join('%',$Tab_Identifiers). "'> <!--поле хранит данные таблицы идентификаторов -->

<input name=\"tab_const\" type=\"hidden\" value='" .join('%',$Tab_Constants). "'> <!--поле хранит данные таблицы констант -->

<input name=\"next\" type=\"submit\" value=\"Далее\" align=\"center\" size=\"40\">

<input name=\"mode\" type=\"hidden\" value=\"1\"> <!--поле хранит текущий режим работы скрипта -->

</form></div> "

);

}

return 0;

}

/*******************************************************************/

/* Letter; */

/* Процедура для выделения символов ключевого слова или */

/* идентифика...