Постановка задачи (обновлена 07/04/2008)

В рамках практикума вам предлагается разработать интерпретатор подмножества языка Модула-2. Реализуемое подмножество вы можете выбирать сами, но таким образом, чтобы были удовлетворены следующие минимальные требования.

В качестве эталонной реализации используется XDS Modula-2.

Грамматика языка. Это — грамматика для полного языка ISO Modula-2. Она содержит неоднозначности и конфликты и не может быть непосредственно использована. Грамматика должна быть упрощена (выброшены ненужные для модельной реализации конструкции), все конфликты в грамматике должны быть устранены. Кроме того, необходимо доопределить сложные лексемы, например, IDENT.

Входной язык

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

Поддержка программ из нескольких единиц компиляции не требуется.

Встроенные процедуры

Должны поддерживаться следующие встроенные процедуры. Для подробного описания обратитесь к описанию языка Модула-2.

ABS(x)

The function ABS can be used to obtain the absolute value of a value of a real number type or a whole number type.

A call of ABS shall have one actual parameter, which shall be an expression that is of a real number type or a whole number type, except that the expression shall not be of the unsigned type.

The type of a call of ABS shall be the same type as the expression.

ASH(x,n)арифметический сдвиг влево или вправо. При n > 0 сдвиг влево, при n < 0 сдвиг вправо. 
PROCEDURE ASH(x : SHORTINT; n : INTEGER) : LONGINT;
PROCEDURE ASH(x, n : INTEGER) : LONGINT;
PROCEDURE ASH(x : LONGINT; n : INTEGER) : LONGINT;
PROCEDURE ASH(x : SHORTCARD; n : INTEGER) : LONGCARD;
PROCEDURE ASH(x : CARDINAL; n : INTEGER) : LONGCARD;
PROCEDURE ASH(x : LONGCARD; n : INTEGER) : LONGCARD;
CHR(x)

The function CHR can be used to obtain the value of the character type that has a specified ordinal number.

A call of CHR shall have one actual parameter, which shall be an expression that is of a whole number type.

The type of a call of CHR shall be the character type.

DEC(x)x := x - 1 
PROCEDURE DEC(VAR x : SHORTINT);
PROCEDURE DEC(VAR x : INTEGER);
PROCEDURE DEC(VAR x : LONGINT);
PROCEDURE DEC(VAR x : SHORTCARD);
PROCEDURE DEC(VAR x : CARDINAL);
PROCEDURE DEC(VAR x : LONGCARD);
DEC(x,v)x := x - v 
PROCEDURE DEC(VAR x : SHORTINT; v : SHORTINT);
PROCEDURE DEC(VAR x : INTEGER; v : INTEGER);
PROCEDURE DEC(VAR x : LONGINT; v : LONGINT);
PROCEDURE DEC(VAR x : SHORTCARD; v : SHORTCARD);
PROCEDURE DEC(VAR x : CARDINAL; v : CARDINAL);
PROCEDURE DEC(VAR x : LONGCARD; v : LONGCARD);
ENTIER(x)наибольшее целое, не превосходящее x 
PROCEDURE ENTIER(x : REAL) : LONGINT;
PROCEDURE ENTIER(x : LONGREAL) : LONGINT;
INC(x)x := x + 1 
PROCEDURE INC(VAR x : SHORTINT);
PROCEDURE INC(VAR x : INTEGER);
PROCEDURE INC(VAR x : LONGINT);
PROCEDURE INC(VAR x : SHORTCARD);
PROCEDURE INC(VAR x : CARDINAL);
PROCEDURE INC(VAR x : LONGCARD);
INC(x,v)x := x + v 
PROCEDURE INC(VAR x : SHORTINT; v : SHORTINT);
PROCEDURE INC(VAR x : INTEGER; v : INTEGER);
PROCEDURE INC(VAR x : LONGINT; v : LONGINT);
PROCEDURE INC(VAR x : SHORTCARD; v : SHORTCARD);
PROCEDURE INC(VAR x : CARDINAL; v : CARDINAL);
PROCEDURE INC(VAR x : LONGCARD; v : LONGCARD);
HALTзавершение работы программы 
PROCEDURE HALT;
HALT(n)завершение работы программы. n - код завершения программы. 
PROCEDURE HALT(n : INTEGER);
LEN(x)длина массива или строки 
PROCEDURE LEN(VAR x : ARRAY OF T) : Z;
Результат имеет тип целочисленной константы, то есть совместим по присваиванию с любой целой переменной. Если размер массива известен на этапе компиляции, процедура может использоваться в константных выражениях.
LSH(x,n)логический сдвиг вправо или влево. При n > 0 сдвиг влево, при n < 0 сдвиг вправо. 
PROCEDURE LSH(x : SHORTINT; n : INTEGER) : LONGINT;
PROCEDURE LSH(x, n : INTEGER) : LONGINT;
PROCEDURE LSH(x : LONGINT; n : INTEGER) : LONGINT;
PROCEDURE LSH(x : SHORTCARD; n : INTEGER) : LONGCARD;
PROCEDURE LSH(x : CARDINAL; n : INTEGER) : LONGCARD;
PROCEDURE LSH(x : LONGCARD; n : INTEGER) : LONGCARD;
MAX(T)Максимальное значение типа T. T — целый тип. Может использоваться в константных выражениях.
MIN(T)Минимальное значение типа T. T — целый тип. Может использоваться в константных выражениях.
ODD(x)x - нечетное? 
PROCEDURE ODD(x : SHORTINT) : BOOLEAN;
PROCEDURE ODD(x : INTEGER) : BOOLEAN;
PROCEDURE ODD(x : LONGINT) : BOOLEAN;
PROCEDURE ODD(x : SHORTCARD) : BOOLEAN;
PROCEDURE ODD(x : CARDINAL) : BOOLEAN;
PROCEDURE ODD(x : LONGCARD) : BOOLEAN;
ORD(x)код по букве 
PROCEDURE ORD(x : CHAR) : INTEGER;




SIZE(T)размер типа T в байтах. Результат имеет тип
целочисленной константы, то есть совместим по присваиванию с любым целым типом.
Может использоваться в константных выражениях.




TRUNC(x)Отбрасывание дробной части числа

PROCEDURE TRUNC(VAR x : REAL) : LONGINT;
PROCEDURE TRUNC(VAR x : LONGREAL) : LONGINT;




  VAL(T, x)
  Преобразование значения x к типу T.
    В качестве типа T могут указываться целые и вещественные типы.
    Значение x также может быть произвольного целого или
    вещественного типа.






Стандартные функции ввода-вывода



Функции ввода-вывода находятся в стандартных модулях
STextIO, SWholeIO, SRealIO,
SLongIO.





STextIO.ReadChar(c)чтение одного символа со стандартного потока ввода


STextIO.SkipLineпропустить остаток строки


SWholeIO.ReadShortInt(x)чтение значения SHORTINT. Перед числом пропускаются все пробельные символы


SWholeIO.ReadInt(x)чтение значения INTEGER. Перед числом пропускаются все пробельные символы


SWholeIO.ReadLongInt(x)чтение значения LONGINT. Перед числом пропускаются все пробельные символы


SWholeIO.ReadShortCard(x)чтение значения SHORTCARD. Перед числом пропускаются все пробельные символы


SWholeIO.ReadCard(x)чтение значения CARDINAL. Перед числом пропускаются все пробельные символы


SWholeIO.ReadLongCard(x)чтение значения LONGCARD. Перед числом пропускаются все пробельные символы


SRealIO.ReadReal(x)чтение значения REAL. Перед числом пропускаются все пробельные символы


SLongIO.ReadReal(x)чтение значения LONGREAL. Перед числом пропускаются все пробельные символы




STextIO.WriteChar(c)вывод одного символа на стандартный поток вывода



SWholeIO.WriteShortInt(x,n)вывод значения SHORTINT

PROCEDURE WriteShortInt(x : SHORTINT; n : CARDINAL);



SWholeIO.WriteInt(x, n)вывод значения INTEGER

PROCEDURE WriteInt(x : INTEGER; n : CARDINAL);



SWholeIO.WriteLongInt(x,n)вывод значения LONGINT

PROCEDURE WriteLongInt(x : LONGINT; n : CARDINAL);


SWholeIO.WriteShortCard(x,n)вывод значения SHORTCARD

PROCEDURE WriteShortCard(x : SHORTCARD; n : CARDINAL);



SWholeIO.WriteCard(x, n)вывод значения CARDINAL

PROCEDURE WriteCard(x : CARDINAL; n : CARDINAL);



SWholeIO.WriteLongCard(x,n)вывод значения LONGCARD

PROCEDURE WriteLongCard(x : LONGCARD; n : CARDINAL);



SRealIO.WriteFloat(x,p,n)вывод значения REAL

PROCEDURE WriteFloat(x : REAL; p : CARDINAL; n : CARDINAL);


SRealIO.WriteEng(x,p,n)вывод значения REAL

PROCEDURE WriteEng(x : REAL; p : CARDINAL; n : CARDINAL);


SRealIO.WriteFixed(x,p,n)вывод значения REAL

PROCEDURE WriteFixed(x : REAL; p : CARDINAL; n : CARDINAL);


SLongIO.WriteFloat(x,p,n)вывод значения LONGREAL

PROCEDURE WriteFloat(x : LONGREAL; p : CARDINAL; n : CARDINAL);


SLongIO.WriteEng(x,p,n)вывод значения LONGREAL

PROCEDURE WriteEng(x : LONGREAL; p : CARDINAL; n : CARDINAL);


SLongIO.WriteFixed(x,p,n)вывод значения LONGREAL

PROCEDURE WriteFixed(x : LONGREAL; p : CARDINAL; n : CARDINAL);




STextIO.WriteString(x)вывод строки

PROCEDURE WriteString(x : ARRAY OF CHAR);


STextIO.WriteLnпереход на новую строку





Модули RealMath и LongMath







RealMath.piконстанта π типа REAL


LongMath.piконстанта π типа LONGREAL


RealMath.exp1константа e типа REAL


LongMath.exp1константа e типа LONGREAL


RealMath.sqrt(x)x0.5

PROCEDURE sqrt(x : REAL) : REAL;


LongMath.sqrt(x)x0.5

PROCEDURE sqrt(x : LONGREAL) : LONGREAL;


RealMath.exp(x)ex

PROCEDURE exp(x : REAL) : REAL;


LongMath.exp(x)ex

PROCEDURE exp(x : LONGREAL) : LONGREAL;


RealMath.ln(x)ln x

PROCEDURE ln(x : REAL) : REAL;


LongMath.ln(x)ln x

PROCEDURE ln(x : LONGREAL) : LONGREAL;


RealMath.sin(x)sin x

PROCEDURE sin(x : REAL) : REAL;


LongMath.sin(x)sin x

PROCEDURE sin(x : LONGREAL) : LONGREAL;


RealMath.cos(x)cos x

PROCEDURE cos(x : REAL) : REAL;


LongMath.cos(x)cos x

PROCEDURE cos(x : LONGREAL) : LONGREAL;


RealMath.arctan(x)arctg x. Возвращает результат в диапазоне (-pi/2,pi/2].

PROCEDURE arctan(x : REAL) : REAL;


LongMath.arctan(x)arctg x

PROCEDURE arctan(x : LONGREAL) : LONGREAL;



RealMath.round(x)Возвращает ближайшее целое.

PROCEDURE round(x : REAL) : LONGINT;


LongMath.round(x)Ближайшее целое.

PROCEDURE round(x : LONGREAL) : LONGINT;





Совместимость типов по присваиванию



Поскольку стандарт не определяет типы SHORTINT и т. п., понятие
совместимости типов для арифметических (то есть вещественных и целых) типов
нуждается в уточнении.



Рассмотрим присваивание v := e. Пусть Tv
— это тип переменной v,
Te — тип выражения e.
Если Tv — LONGREAL, то Te
может быть любого типа.





Если Tv — REAL, то Te
может быть любого типа, кроме LONGREAL.





Если e — это константа целого типа, она совместима по
присваиванию с любым целым типом при условии, что попадает в диапазон
этого целого типа.





Если Tv — LONGINT, то Te
может быть типа SHORTINT, SHORTCARD, INTEGER, CARDINAL, LONGINT.





Если Tv — LONGCARD, то Te
может быть типа SHORTCARD, CARDINAL, LONGCARD.





Если Tv — INTEGER, то Te
может быть типа SHORTINT, SHORTCARD, INTEGER.





Если Tv — CARDINAL, то Te
может быть типа SHORTCARD, CARDINAL.





Если Tv — SHORTINT, то Te
может быть типа SHORTINT.





Если Tv — SHORTCARD, то Te
может быть типа SHORTCARD.




Совместимость типов в выражениях




Рассмотрим выражение e1 OP e2.
Здесь OP — некоторая бинарная операция.
В зависимости от типов операндов результат будет иметь следующий тип.




Если один из типов аргументов LONGREAL, то тип другого аргумента
должен быть REAL или LONGREAL. Тип результата —
LONGREAL.




Иначе если тип обоих аргументов — REAL, то и тип
результата — REAL.




Выражения, в которых один из аргументов целого типа, а другой —
вещественного, недопустимы.



Иначе, если оба аргумента — целые константы, то выбирается минимальный
тип в последовательности SHORTINT, SHORTCARD, INTEGER, CARDINAL, LONGINT, LONGCARD, что обе константы
представимы значениями этого типа. Это будет тип результата.




Иначе, если один из типов аргументов — LONGINT, 
то другой аргумент должен быть типа 
SHORTINT, SHORTCARD, INTEGER, CARDINAL, LONGINT или целой константой, представимой типом LONGINT.
Тип результата — LONGINT.
Пара LONGINT, LONGCARD недопустима.




Иначе, если один из аргументов — константа, представимая типом
LONGINT, но не представимая типами INTEGER или CARDINAL,
тогда другой аргумент должен быть типа
SHORTINT, SHORTCARD, INTEGER, CARDINAL.
Тип результата — LONGINT.




Иначе, если один из типов аргументов — LONGCARD, 
то другой аргумент должен быть типа 
SHORTINT, SHORTCARD, INTEGER, CARDINAL, LONGCARD или целой константой, представимой типом LONGCARD.
Тип результата — LONGCARD.




Иначе, если один из аргументов — константа, представимая типом
LONGCARD, но не представимая типами INTEGER или CARDINAL,
тогда другой аргумент должен быть типа
SHORTINT, SHORTCARD, INTEGER, CARDINAL.
Тип результата — LONGCARD.




Иначе, если один из типов аргументов — INTEGER, 
то другой аргумент должен быть типа 
SHORTINT, SHORTCARD, INTEGER или целой константой,
представимой типом INTEGER.
Тип результата — INTEGER.




Иначе, если один из аргументов — константа, представимая типом
INTEGER, но не представимая типами SHORTINT или SHORTCARD,
тогда другой аргумент должен быть типа
SHORTINT, SHORTCARD.
Тип результата — INTEGER.




Иначе, если один из типов аргументов — CARDINAL, 
то другой аргумент должен быть типа 
SHORTINT, SHORTCARD, CARDINAL или целой константой, представимой типом CARDINAL.
Тип результата — CARDINAL.




Иначе, если один из аргументов — константа, представимая типом
CARDINAL, но не представимая типами SHORTINT или SHORTCARD,
тогда другой аргумент должен быть типа
SHORTINT, SHORTCARD.
Тип результата — CARDINAL.




Иначе, если один из типов аргументов — SHORTINT, 
то другой аргумент должен быть типа 
SHORTINT или целой константой, представимой типом SHORTINT.
Тип результата — SHORTINT.




Иначе, если один из типов аргументов — SHORTCARD, 
то другой аргумент должен быть типа 
SHORTCARD или целой константой, представимой типом SHORTCARD.
Тип результата — SHORTCARD.




Работа интерпретатора



При запуске интерпретатора указывается имя файла программы на Модуле-2
и дополнительные опции выполнения.


Modula2 [OPTIONS]... PROGRAM


Должны поддерживаться следующие опции:



--check-onlyПровести только синтаксический и семантический анализ, не выполнять программу.


--defsНа стандартный поток вывода напечатать список всех определённых в программе переменных и процедур в порядке возрастания их позиции в следующем формате:
LINE:COL:NAME:KIND:USAGES
 где KIND — либо V для переменных, либо P для процедур, а USAGES — число использований данной переменной или процедуры в программе.


--uses [LINE:[COL:]]NAMEНа стандартный поток вывода напечатать все точки использования указанной переменной или процедуры. Параметры LINE и COL позволяют задать точку определения переменной или процедуры NAME и, таким образом, устранить неоднозначность, если NAME определяется в программе более одного раза. Если переменных, отвечающих параметру запроса не существует, программа не должна ничего выдавать. В качестве NAME можно указывать имена стандартных процедур и переменных. В этом случае для устранения неоднозначности используется запись 0:0:NAME.





Интерпретатор проводит лексический,
синтаксический и семантический анализ программы и строит ее
внутреннее представление. Если при анализе программы были выявлены
ошибки, то на стандартный поток ошибок выводятся диагностические
сообщения, а сам интерпретатор завершает работу с кодом возврата 100.
Если ошибок выявлено не было, ничего ни на стандартный поток вывода,
ни на стандартный поток ошибок выводиться не должно.




Ошибки анализа программы должны выводиться в следующем виде:

FILE:LINE:COLUMN:Description

например

a.mod:2:10:Undefined identifier `x'

Обратите внимание, что строки программы нумеруются с 1, а столбцы —
с нуля.


Если при выполнении программы возникает ошибка выполнения,
то на стандартный поток ошибок должно быть напечатано диагностическое
сообщение стандартного вида, например

a.mod:15:10:Division by 0

и интерпретатор должен завершить работу с соответствующим кодом возврата,
как приведено в таблице ниже.





101Input format errorпроизошла ошибка при вводе числа


102Division by 0целочисленное деление на 0


103Integer overflowцелочисленное переполнение


104Domain errorнедопустимый аргумент для CHR, RealMath.ln и т. п.


105Index out of boundsвыход за пределы массива







Исходные коды интерпретатора


Исходный код вашего интерпретатора должен находиться в пакете
ru.msu.cmc.sp.modula2. Результатом сборки вашего интерпретатора
должен являться один файл modula2.jar. Главный класс
интерпретатора должен называться Modula2. Таким образом,
интерпретатор должен запускаться на выполнение командой

java -cp antlr.jar:modula2.jar ru.msu.cmc.sp.modula2.Modula2

(в Unix) или

java -cp antlr.jar;modula2.jar ru.msu.cmc.sp.modula2.Modula2

(в Windows).