Лабораторная работа 1
Цель работы
Целью данной лабораторной работы является применение на практике алгоритма рекурсивного спуска на основе библиотеки обработки входной строки.
Инструменты
Для выполнения данной лабораторной работы Вам потребу-ется любой компилятор языка С, способный генерировать 32-раз-рядные программы для той ОС, с которой Вы работаете. Для ОС Windows рекомендуется использовать бесплатную среду разра-ботки Microsoft Visual C++ Express.
Основная Ваша работа будет заключаться в формировании программы перевода выражения в постфиксную запись, которая была разобрана на лекции. Для первичной обработки строк пред-лагается использовать модуль match.
Процедура рекурсивного спуска
prim()
{
int s;
if (match("(")) {
if (expr()==0) return 0;
if (!match(")")) { cerror(E_RIGHT_BRACKET); return 0; }
}
else if (a=numb(&s)) {
printf("%d ", s);
} else { cerror(E_EXPRESS_SINTAX); return 0; }
return 1;
}
mult()
{
if (prim()==0) return 0;
while (1) {
if (match("*")) {
if (prim()==0) return 0;
printf("* ");
} else if (match("/")) {
if (prim()==0) return 0;
printf("/ ");
} else break;
}
return 1;
}
add()
{
if (mult()==0) return 0;
while (1) {
if (match("+")) {
if (mult()==0) return 0;
printf("+ ");
} else if (match("-")) {
if (mult()==0) return 0;
printf("- ");
} else break;
}
return 1; }
Модуль match
Данный модуль предназначен для первичной обработки строк и позволяет выделять из строки лексемы. Здесь описаны ин-терфейсные функции модуля match.
void match_init(char* line);
Процедура инициализации. Разбор строки всегда начинается с вызова этой функции. В качестве параметра передается входная строка.
void match_done(void);
Процедура деинициализации. После разбора строки необхо-димо вызвать данную функцию.
int match(char *lit);
Поиск указанной подстроки в начале входной строки. Если есть, то найденная подстрока удаляется и функция возвращает 1.
int amatch(char *lit, int len);
Аналогично предыдущему, но дополнительно указывается длина подстроки. Это используется для того, чтобы различать вы-ражения типа 'for' и 'formula', где первое, это ключевое слова, а второе - идентификатор.
int symname(char *sname);
Ищет идентификатор (метку) во входной строке. Метка начи-нается с подчеркивания или буквы, далее следуют буквы, подчер-кивание или цифры.
int number(int val[]);
Ищет целое знаковое число во входной строке
void skipblanks(void);
Пропускает последовательность пробельных символов (про-бел, табуляция) во входной строке.
skipchars(void);
Пропускает лексемы и следующие пустые символы. Исполь-зуется для обработки ошибок.
Задание
1. Реализовать программу рекурсивного спуска выражения и перевода в постфиксный вид.
2. Реализовать главную программу, считывающую строки из входного потока и выдающую в конце сообщения "OK" в случае успешного разбора или "FAIL" в случае неуспешного разбора.
3. Добавить в процедуру разбора задание по номеру вариан-та.
4. (Дополнительное.) Изучить разработку make файлов и раз-работать make файл для сборки проекта из двух модулей.
5. (Дополнительное.) Функция разбора вещественного числа в инженерной форме.
Список вариантов
1. Комплексные числа
Обеспечить поддержку вещественных и комплексных чисел. Числа вводить в нижеследующем формате
<вещ.число>::=<число>
<вещ.число>::=<число>.<число>
<комплксн.число>::=i
<комплксн.число>::=i+<вещ.число>
<комплксн.число>::=<вещ.число>i
<комплксн.число>::=<вещ.число>i+<вещ.число>
На выходе комплексные числа представлять в следующем виде:
complex(<комплексн.часть>,<реальн.часть>)
где комплексн.часть и реальн.часть - вещественные числа. Веще-ственные числа выводить без изменений.
Например
5.6i+4.9 на выходе complex(5.6,4.9)
0.6i на выходе complex(0.6,0)
i+7 на выходе complex(1,7)
2. Матрицы
Обеспечить поддержку матриц, состоящих из целых чисел. Матрицы вводить в нижеследующем формате:
<матрица>::=[<строки>]
<строки>::=<строка> | <строка> ; <строки>
<строка>::=<число> | <число> , <строка>
Например:
Матрица будет записана в виде [1,2,3;4,5,6]
вектор-столбец (матрица) будет записан в виде [1;4;5]
запись вида [1,2,3;5,6] будет считаться ошибочной.
На выходе матрицы предствлять в виде:
matrix(<строк>,<столбцов>,<значения>)
где <строк> и <столбцов> это целые числа - количество строк и столбцов соответственно, а значения, это перечисленные через за-пятую слева направо и сверху вниз, значения элементов матрицы - целые числа.
3. Строки
Обеспечить поддержку строки. Строки записываются в ка-вычках. Дополнительно необходимо обеспечить ввод кавычки в виде последовательности из двух кавычек. На выходе строки вы-давать в следующем формате:
string("<строка>")
где строка есть последовательность символов. Кавычка, если она была в исходной строке, должна быть заменена последовательно-стью символов \".
Например
"Hello World!" на выходе string("Hello World!")
"Hello ""World""!" на выходе string("Hello \"World!\"")
"""" на выходе string("\"")
4. Массивы
Обеспечить поддержку массивов чисел. Массивы вводить в нижеследующем формате:
<массив>::=( <числа> )
<числа>::=<число> , <числа> | <число>
На выходе массивы записывать в следующем виде:
array(<размер>, <числа>)
где, размер - это целое число - размер массива, числа - это элементы массива, перечисленные через запятую.
Например
(1, 2, 3, 4, 5) на выходе array(5,1,2,3,4,5)
5. Диапазоны
Обеспечить поддержку диапазонов (аналогично MathCAD). Диапазоны записывать в следующем формате:
<диапазон>::=<старт> ... <финиш>
<диапазон>::=<старт>, <приращение> ... <финиш>
где старт - целое число - начало диапазона, финиш - целое число - конец диапазона, приращение - целое число - прира-щение (по умолчанию 1 или -1, в зависимости от того, что больше старт или финиш). Приращение может быть отрицательным. Обес-печить контроль существования диапазона.
На выходе диапазоны записывать в следующем виде:
range(<старт>, <приращение>, <финиш>)
Например
5...10 на выходе range(5,1,10)
5...0 на выходе range(5,-1,0)
5,2...10 на выходе range(5,2,10)
5,-2...10 выдает ошибку "Неправильно задан диапазон"
6. Функции многих переменных
Обеспечить поддержку функций с любым количеством пара-метров (от 0).
<функция>::=<имя>(<параметры>)
<параметры>::=<выражение> | <выражение> < параметры > | e
На выходе функцию необходимо записывать в следующем виде:
Перечислить ее параметры слева направо (выражения долж-ны вычисляться), а затем имя функции.
Например
pow(3,5) на выходе 3 5 pow
pow(4+1,2) на выходе 4 1 + 2 pow
Дополнительно после обработки всех строк вывести список всех функций, использованных в строках.
Лабораторная работа 2
Цель работы
Изучение принципов построения виртуальных машин (ВМ) на основе реальных процессоров.
Исходные данные
Введем следующие обозначения абстракций ВМ.
данные (value) вещественное число (float или double)
адреса (addr) целое 16-битное число
В связи с тем, что ОУ принимает на вход вещественные числа, нам необходимо в нашей виртуальной машине сделать поддержку вещественных чисел. Однако полностью отказываться от под-держки целочисленных операций тоже нельзя. Она потребуется, по крайней мере, для вычисления адресов. Поэтому фактически приходится в виртуальной машине делать 2 блока арифметики - целочисленный и вещественный.
Самый простой способ, как можно поступить в этой ситуа-ции, заключается в выделении вещественной арифметики в про-блемно-ориентированный блок виртуальной машины. А в систем-ном блоке оставить только целочисленную арифметику. Так по-ступали практически во всех реальных вычислительных системах, так поступают обычно и при разработке ВМ.
Структура части ВМ, отвечающая за вещественную арифме-тику (назовем ее блок вещественной арифметики (БВА)), может выглядеть по-разному. Но в любом случае она включает некото-рое вещественное арифметико-логическое устройство (ВАЛУ). Главный вопрос, который нужно решить проектировщику, - откуда ВАЛУ должно брать операнды. В зависимости от типа виртуальной машины вообще и желания проектировщика в частности, это могут быть внутренний стек данных БВА, пара (тройка) внутренних регистров БВА или заданный адрес в основной памяти виртуальной машины.
Набор проблемно-ориентированных команд у разных типов виртуальных машин принципиально различаться не будет и обыч-но сводится к следующим группам:
- вещественные арифметические операции (сложение, вычи-тание, умножение, деление);
- функции (корень квадратный, тригонометрия и так далее);
- команды управления ОУ.
Набор системных команд по группам обычно выглядит так:
- целочисленные арифметические операции (целочисленные операции сложения, вычитания, умножения, иногда деления);
- управление логикой (переходы условные и безусловные, вызовы подпрограмм, возвраты из подпрограмм);
- операции со стеком (загрузка значения (целочисленного!), запись значения с вершины стека в указанный адрес).
Задание
Разработать стековую машину.
Системная часть:
- память команд - 64 килобайта;
- стек адресов в основной памяти, обычно в конце блока;
- регистры:
- SP - указатель стека,
- PC - указатель команд.
Проблемно-ориентированная часть:
память данных - в основной памяти, обычно после кода;
стек данных - 256 ячеек данных;
регистры:
SPF - указатель стека (8 бит),
PSW - слово состояния.
Разработка стековой виртуальной машины - одно из самых простых заданий. Все арифметические команды работают со сте-ком, то есть не имеют операндов. Целочисленные арифметические команды работают со стеком адресов. Вещественные арифметиче-ские команды работают со стеком данных. Команд, обладающих операндами, минимум:
Load <addr> Команда укладывает значение параметра в стек адресов.
Push <addr> Команда укладывает значение по адресу addr в стек адресов.
Pull <addr> Команда вытаскивает из стека адресов значение и записывает его по указанному в качестве параметра адресу.
Лабораторная работа 3
Цель работы
Целью данной лабораторной работы является разработка программы рекурсивного спуска с использованием генератора лексических анализаторов - Lex.
Общие сведения
Lex - программа для генерации сканеров (лексических ана-лизаторов). Входной язык содержит описания лексем в терминах регулярных выражений. Результатом работы LEX'a является про-грамма на языке Си, которая читает файл yyin (обычно это стан-дартный ввод) и выделяет из него последовательности символов (лексемы), соответствующие регулярным выражениям.
Рассмотрим способы записи регулярных выражений во вход-ном языке Lex'а. Алфавит Lex'а совпадает с алфавитом используе-мой ЭВМ. Символ из алфавита, естественно, представляет регу-лярное выражение из одного символа. Специальные символы (в том числе +-*?()[]{}|/\^$.<> ) записываются после специального префикса \. Кроме того, применимы все традиционные способы кодирования символа в языке C. Символы и цепочки можно брать в кавычки:
Например:
а "а" \а - три способа кодирования символа а
\n \t \007 "continue"
Имеется возможность задания класса символов:
[0-9] или [0123456789] - любая цифра
[A-Za-z] - любая буква
[^0-7] - любой символ, кроме восьмиричных цифр
. - любой символ, кроме \n
Грамматика для записи регулярных выражений (в порядке убывания приоритета):
<р> : <р>* повторение 0 или более раз
<р> : <р>+ повторение 1 или более раз
<р> : <р>? необязательный фрагмент
<р> : <р><р> конкатенация
<р> : <р>{m,n} повторение от m до n раз
<р> : <р>{m} повторение m раз
<р> : <р>{m,} повторение m или более раз
<р> : ^<р> фрагмент в начале строки
<р> : <р>$ фрагмент в конце строки
<р> : <р>|<р> любое из выражений
<р> : <р>/<р> первое выражение, если за ним следует второе
<р> : (р) скобки, используются для группировки
Примеры:
[A-Za-z]([A-Za-z0-9]{0,7}) - идентификатор (имя) в языке C до 8 символов.
^#" "*define - начало #define в языке C
Программа на входном языке Lex состоит из трех частей, раз-деленных символами %%:
Описания
%%
Правила
%%
Программы
Раздел описаний содержит определения макросимволов (ме-тасимволов) в виде:
ИМЯ ВЫРАЖЕНИЕ
Если в последующем тексте в регулярном выражении встре-чается {ИМЯ}, то оно заменяется на ВЫРАЖЕНИЕ. Если строка описаний начинается с пробелов или заключена в скобки %{ ... }%, то она просто копируется в выходной файл.
Раздел правил содержит строки вида
ВЫРАЖЕНИЕ {ДЕЙСТВИЕ}
ДЕЙСТВИЕ - это фрагмент программы на C, который вы-полняется тогда, когда обнаружена цепочка, соответствующая ВЫРАЖЕНИЮ. Действие, указанное в начале раздела без выраже-ния, выполняется до начала разбора. Lex делает попытку выделить наиболее длинную цепочку из входного потока. Если несколько правил дают цепочку одинаковой длины, применяется первое пра-вило. Так, при разборе по следующим правилам для цепочки "123" будет применено первое правило, а для цепочки "123." - третье:
[0-9]+
(\+|\-)?[0-9]+
(\+|\-)?[0-9]+"."[0-9]+
Если ни одно из правил не удастся применить, входной сим-вол будет скопирован в yyout. Если это нежелательно, в конец правил можно добавить, например, строки:
. {/* Ничего не делать */}
\n { }
Раздел программ может содержать произвольные тексты на C и целиком копируется в выходной файл. Обычно здесь записыва-ется функция yywrap(), которая определяет, что делать при дости-жении автоматом конца входного файла. Ненулевое возвращаемое значение приводит к завершению разбора, нулевое - к продолже-нию (перед продолжением, естественно, надо открыть какой-нибудь файл как yyin).
Интерпретатор таблиц КА имеет имя yylex(). Автомат пре-кращает работу (происходит возврат из функции yylex()), если в одном из действий выполнен оператор return (результат yylex() будет совпадать с указанным в операторе) или достигнут конец файла и значение yywrap() отлично от 0 (результат yylex() будет равен 0).
Традиционный пример входной программы для Lex'а - под-счет числа слов и строк в файле (обратите внимание на пробелы, этот текст нормально компилируется Lex'ом):
/********** Раздел определений ***********/
/* NODELIM означает любой символ, кроме разделителей слов */
NODELIM [^" "\t\n]
int l, w, c; /* Число строк, слов, символов */
%% /******************** Раздел правил **************/
{ l=w=c=0; /* Инициализация */ }
{NODELIM}+ { w++; c+=yyleng; /* Слово */ }
\n { l++; /* Перевод строки */ }
. { c++; /* Остальные символы */ }
%% /*************** Раздел программ *************/
main() { yylex(); }
yywrap() {
printf( " Lines - %d Words - %d Chars - %d\n", l, w, c );
return( 1 );
}
Внутри действий в правилах можно использовать некоторые специальные конструкции и функции Lex'а:
char* yytext - указатель на отождествленную цепочку сим-волов, терминированную нулем;
int yyleng - длина этой цепочки
void yyless(int n) - вернуть последние n символов цепочки обратно во входной поток;
void yymore() - считать следующие символы в буфер yytext после текущей цепочки
void yyunput(char c) - поместить байт c во входной поток
ECHO - копировать текущую цепочку в yyout
В некоторых случаях бывает удобно описать необходимые действия в терминах нескольких разных состояний (т.е. разных ко-нечных автоматов) с явным переключением с одного на другое. В этом случае набор имен состояний следует перечислить в специ-альной строке %Start, а перед выражениями записывать имя соот-ветствующего состояния в угловых скобках. Переключение в но-вое состояние выполняется с помощью оператора BEGIN. Напри-мер, следующая программа удаляет комментарии из программ на C (out - вне комментария, in - внутри):
%Start out in
%%
{ BEGIN out; }
<out>"/*" { BEGIN in; }
<out>.|\n { printf("%s",yytext); }
<in> "*/" { BEGIN out; }
<in> .|\n { }
%%
yywrap() { return(1); }
main() { yylex(); }
Обычным приемом при разработке трансляторов с использо-ванием Lex является следующий способ. Записываются правила для поиска нужных лексем, в действиях этих правил ставят опера-тор return для выхода из функции yylex(). Данный оператор дол-жен вернуть одно из предопределенных значений. Функция или функции, организующие разбор входной строки для получения очередной лексемы, пользуются функцией yylex(), если результат этой функции (идентификатор лексемы) совпадает с ожидаемой в данной точке лексемой, то считается, что лексема получена, иначе нет. В этой технологии есть две тонкости. 1. При обработке лексе-мы (в действии) зачастую требуется запомнить значение получен-ной лексемы, для того чтобы передать её в вызывающую функ-цию. 2. Всегда требуется помнить текущую лексему, так как если ее значение не совпало с требуемым, то это еще не значит, что вы-явлена ошибка. Вполне вероятно, что в другом месте программы (в другой функции по иерархии или в следующей проверке в этой же функции) полученное значение лексемы окажется именно ис-комым.
В данной лабораторной работе необходимо пользоваться именно этим механизмом.
Для вызова программы Lex следует ввести команду "lex имя_исходного_файла". Выходной файл по умолчанию имеет имя "lex.yy.c".
Задание
Ваша задача сформировать регулярную грамматику для язы-ка из лабораторной работы №1, записать ее в виде исходного тек-ста для lex и сгенерировать программу, на вход (входной поток) которой подается последовательность строк, предположительно принадлежащих данной грамматике. Каждая строка заканчивается символом \n. Программа должна выдать результат в виде числа (0 или 1) для каждой строки о ее принадлежности к грамматике.
Лабораторная работа 4
Цель работы
Целью данной лабораторной работы является разработка калькулятора на базе алгоритма рекурсивного спуска с использо-ванием генератора лексических анализаторов - Lex.
Общие сведения
Существует два вида трансляторов - интерпретаторы и ком-пиляторы. Первые из них выполняют программу сразу же в про-цессе ее разбора. Соответственно, если в программе есть какая-то синтаксическая или другая ошибка, интерпретатор обнаружит ее, только дойдя до этой строчки. Это одновременно и плюс, и минус. Плюс в том, что теоретически можно предложить пользователю тут же исправить ошибку и продолжить дальше (многие интерпре-таторы, снабженные средой разработки, так и поступают, например старые версии языка Basic). Компилятор, напротив, сперва перево-дит весь текст программы в последовательность команд некоторой реальной или виртуальной машины, а затем процессор или вирту-альная машина (программа) исполняет эту последовательность.
В данной работе Вам предстоит разработать калькулятор - это такая программа, которая позволяет производить вычисления арифметических выражений. Всего есть два варианта реализации калькулятора - интерпретатор и компилятор. В первом случае код, отвечающий за вычисления, должен находиться непосред-ственно в алгоритме рекурсивного спуска. Например, так:
add()
{
double op1,op2;
if (mult()==0) return 0;
while (1) {
if (match("+")) {
if (mult()==0) return 0;
op1 = pull();
op2 = pull();
push(op2+op1);
} else if (match("-")) {
if (mult()==0) return 0;
op1 = pull();
op2 = pull();
push(op2-op1);
} else break;
}
return 1;
}
Для компилятора все чуть-чуть сложнее. Вместо вычислений нужно генерировать некоторый исполняемый код. Будем считать, что генерируем код для некоторой виртуальной машины, поддер-живающей некоторый небольшой набор операций.
add()
{
double op1,op2;
if (mult()==0) return 0;
while (1) {
if (match("+")) {
if (mult()==0) return 0;
put_commd(&ptr, CADD);
} else if (match("-")) {
if (mult()==0) return 0;
put_commd(&ptr, CSUB);
} else break;
}
return 1;
}
где функция put_cmd размещает в буфере или выводит во внешний (бинарный) файл код этой команды. Примеры системы команд, ре-ализации виртуальной машины, а также пример функций кодоге-нератора приведены в архиве lab3vm.rar. Эта виртуальная машина поддерживает работу с вещественными числами, строками и пере-менными. А также команды ввода и вывода. Поддерживаются 4 стандартные математические операции.
Задания
1. Разработать калькулятор-интерпретатор. Поддерживаемые операции - из предыдущей лабораторной работы + (обязательно для всех) обеспечить работу с переменными, добавить операцию (или оператор) присваивания. Те, у кого был вариант №4, поддер-живаемые функции берут из варианта № 3. Обеспечить консоль-ный ввод и вывод переменных. Текст разбираемой программы те-перь многострочный. Необходимо также обеспечить возможность записи комментариев языка Си /* … */.
2. Разработать калькулятор-компилятор. Поддерживаемые операции - из предыдущей лабораторной работы. Те, у кого был вариант №4, поддерживаемые функции берут из варианта №3. Обеспечить консольный ввод и вывод переменных. Текст разбира-емой программы теперь многострочный. Если в виртуальной ма-шине нет какой-то необходимой вам операции (например, возведе-ние в степень) - добавьте ее. Необходимо также обеспечить воз-можность записи комментариев языка С++ (от // … и до конца строки). Обратите внимание, что виртуальная машина - это дру-гая исполняемая программа. И передача информации от вашего компилятора к виртуальной машине осуществляется через внеш-ний двоичный файл.
КУРСОВОЙ ПРОЕКТ
Заданием на курсовой проект является разработка транслято-ра одного из семи языков. Все задания на курсовой проект разде-ляются на четыре группы:
Тип транслятора:
1. Интерпретатор.
2. Компилятор и виртуальная машина.
Способ реализации транслятора:
" Рекурсивный спуск
" Генератор лексического и синтаксического анализатора (lex+yacc или какой-либо другой генератор, который Вам больше нравится).
Ниже приведена таблица, по которой Вы можете узнать тип языка, тип транслятора и способ реализации Вашего транслятора по номеру варианта. А далее описаны семь вариантов языка, один из которых Вам необходимо реализовать.
Результатом Вашей работы, которую Вы пришлете на про-верку, должны быть:
" Исходный текст Вашего транслятора: все *.c, *.cpp, *.h файлы, исходные тексты на lex и yacc (если Вы реализуете данный вариант) и виртуальной машины, если Вы реализу-ете компилятор и виртуальную машину.
" Не менее трех примеров корректного исходного текста, то есть такого текста, который обрабатывается Вашим транс-лятором как правильный.
" Не менее трех примеров некорректного исходного текста, то есть такого текста, который корректно обрабатывается Вашим транслятором как неправильный, то есть выдает ошибки.
" Makefile или пакетный файл, при помощи которого проис-ходит сборка вашего проекта и прогон тестовых примеров.
" Сопровождающий readme.txt, в котором описано назначе-ние каждого файла, а также для каждого тестового приме-ра описан результат, который выдает Ваш транслятор. Обязательно необходимо указать, какими компиляторами (C/C++, а также lex и yacc) и какой версии Вы пользова-лись для сборки Вашего проекта.
" Документ, оформленный обычным образом, как курсовой проект. Данный документ должен включать:
" описание грамматики;
" описание семантики операторов и операций Вашего языка.
Варианты курсовых проектов
№
варианта Вариант синтаксиса Тип транслятора Способ реализации
1 1 Интерпретатор Рекурсивный спуск
2 2 Компилятор Генератор анализаторов
3 3 Интерпретатор Рекурсивный спуск
4 4 Компилятор Генератор анализаторов
5 5 Интерпретатор Рекурсивный спуск
6 7 Интерпретатор Рекурсивный спуск
7 1 Компилятор Генератор анализаторов
8 2 Интерпретатор Рекурсивный спуск
9 3 Компилятор Генератор анализаторов
10 4 Интерпретатор Рекурсивный спуск
11 5 Компилятор Генератор анализаторов
12 6 Интерпретатор Рекурсивный спуск
13 7 Компилятор Генератор анализаторов
14 1 Интерпретатор Генератор анализаторов
15 2 Компилятор Рекурсивный спуск
16 3 Интерпретатор Генератор анализаторов
17 4 Компилятор Рекурсивный спуск
18 5 Интерпретатор Генератор анализаторов
19 7 Интерпретатор Генератор анализаторов
20 1 Компилятор Рекурсивный спуск
21 2 Интерпретатор Генератор анализаторов
22 3 Компилятор Рекурсивный спуск
23 4 Интерпретатор Генератор анализаторов
24 5 Компилятор Рекурсивный спуск
25 6 Интерпретатор Генератор анализаторов
26 7 Компилятор Рекурсивный спуск
Варианты синтаксиса
Вариант № 1. Pascal-подобный алгоритмический язык
В данном задании необходимо реализовать относительно простой язык программирования. За основу возьмите синтаксис языка Паскаль. Вам необходимо реализовать поддержку нижесле-дующих элементов:
" Стандартная структура программы языка Pascal (program name; переменные, подпрограммы, begin … end).
" Типы данных real, boolean.
" Подпрограммы: процедуры, функции. Можно не делать поддержку вложенных процедур и функций, достаточно будет обеспечить поддержку процедур и функций на верхнем уровне (уровне программы). Обязательно необ-ходимо обеспечить поддержку локальных переменных в подпрограммах. Для проверки реализуйте на Вашем языке рекурсивный алгоритм вычисления чисел Фибоначчи, он должен работать корректно.
" Операторы:
" for … to … [step …] do
" if … then … [else …]
" Системные процедуры:
" write, writeln: достаточно будет, если эти процедуры бу-дут принимать на вход ровно два параметра - строку и вещественное выражение для печати.
" read, readln: эти процедуры должны принимать ровно один параметр: переменную для ввода значения.
" Оператор присваивания. Слева от символа :=, а справа выражение с операциями, которые описаны ниже.
" Операции:
" Арифметические (для вещественных чисел): +, -, *, /.
" Сравнения (операнды могут быть вещественного типа, а результат операции булев): <, >, <>, ><, <=, =<, >=, =>, =
" Логические (операнды булевы, результат булев): and, or, xor
Примечание: Ваш транслятор должен быть реализован как консольное приложение, принимающее на вход (не в качестве входного потока, а как параметр приложения) исходный текст Ва-шей программы. Процедуры read/readln и write/writeln должны ра-ботать соответственно с входным и выходным потоками, что поз-волит делать автоматическое тестирование на основе заранее заго-товленных примеров. Сообщения об ошибках должны попадать в поток stderr (для языка C) или cerr (для C++). В случае если была хотя бы одна ошибка, программа должна возвращать значение -1, а если ошибок не было, то 0.
Вариант № 2. Экранный калькулятор выражений
В данном задании Вам необходимо реализовать простой калькулятор выражений, аналогичный тому, что Вы делали в рам-ках лабораторных работ. Однако ввод выражения может осу-ществляться при помощи экранной клавиатуры, похожей на ту, что можно увидеть у обычного калькулятора. Также необходимо обеспечить:
1) возможность загрузки готового выражения из файла;
2) выгрузки результата вычисления в файл;
3) копирование в буфер обмена и из буфера обмена;
4) возможность ввода многострочного выражения;
5) операции +, -, *, /, возведение в степень;
6) нахождение корня квадратного и корня любой степени;
7) основные тригонометрические функции, sin, cos, tg, ctg, arcsin, arcos, arctg, arcctg;
8) гиперболические функции;
9) скобки;
10) поддержку работы с переменными: для этого нужно обеспечить операцию присваивания, все переменные с их значени-ями должны отображаться в виде таблицы в калькуляторе, коли-чество переменных может быть ограничено.
Примечание: если Вам необходимо реализовать данный калькулятор на основе lex+yacc, то необходимо подменить в lex функции ввода символа. Сделать это можно, например, следую-щим образом:
int get_next_simbols(char* buf,int max_size)
{
if (max_size == 0) return 0;
if (*bufptr == 0) return 0;
*buf = *bufptr++;
return 1;
}
#define YY_INPUT(buf,result,max_size) \
{ \
result = get_next_simbols(buf,max_size); \
}
Данный текст, вставленный в секцию определений в скобки %{ … %}, позволит подменить ввод символов из входного потока на ввод символов из буфера bufptr, в который Вы должны загру-зить буфер с символами до начала разбора.
Вариант № 3. Консольный текстовый процессор
Задача данного текстового процессора - обработка строк входного файла. Проблемной частью команд виртуальной маши-ны, встроенной в интерпретатор или внешней (для компилятора), будут являться команды навигации по тексту и обработки текста, как это обычно происходит в обычном текстовом редакторе, одна-ко в отличие от обычного текстового редактора никакого графи-ческого или даже консольного отображения данного текста не требуется. Вся обработка должна происходить в оперативной па-мяти. Ближайший аналог такого текстового процессора - sed.
Команды навигации:
" перейти в начало файла, в конец файла, в начало строки, в конец сроки;
" перейти на строку N (по возможности сохранив теку-щую позицию);
" перейти на позицию N в текущей строке;
" перейти на N строк ниже, на N строк выше;
" перейти на N символов влево, на N символов вправо;
" перейти на N слов влево, на N слов вправо.
Команды работы с блоками:
" начать выделение (затем после нескольких команд пере-хода), закончить выделение;
" выделить текущий символ;
" выделить текущее слово;
" выделить текущую строку;
" выделить текущую строку от начала до текущей пози-ции;
" выделить текущую строку от текущей позиции до кон-ца;
" запомнить блок (аналогично копированию в буфер об-мена);
" вставить блок в текущую позицию (аналогично вставке из буфера обмена).
Команды редактирования:
" удалить текущий символ или выделенный блок;
" вставить заданную последовательность символов.
Поиск:
" найти заданную строку от начала файла;
" найти заданную строку от текущей позиции до конца документа;
" найти заданную строку от текущей позиции до начала документа;
" найди следующее вхождение.
Примечание 1:
" не важно, как эти команды будут называться - приду-майте разумные, понятные Вам названия;
" если блок уже выделен (то есть закончено выделение блока), то любая операция навигации сбрасывает выде-ленный блок (разумеется, это не касается блока, скопи-рованного в буфер;
" было бы неплохо сделать поддержку нескольких бло-ков, но это на Ваше усмотрение;
" в качестве дополнительного параметра для команд по-иска можно указать - требуется ли найденную строку выделить как блок;
" каждая команда возвращает значение - удалось ли ей выполнить задачу, это значение может быть использо-вано в команде if или проигонорировано.
Общие команды:
" Команда if - проверяет, успешно ли завершилась предыдущая команда, и позволяет выполнить какой-то блок действий в случае успеха. Конкретный синтаксис команды остается на Ваше усмотрение.
" Цикл пока. По синтаксису данная команда должна быть похожа на команду if, но все команды, включенные в блок, выполняются пока выполняется условие (по же-ланию).
Примечание 2: Ваш транслятор должен быть реализован как консольное приложение, исходный текст на Вашем языке переда-ется в качестве параметра транслятора (см. примечание для вари-анта №1). Обрабатываемый текстовый файл подается на входной поток, а обработанный файл, который получается после работы Вашей программы, выдается на выходной поток.
Вариант № 4. Графический язык
В данном варианте Вашей задачей является создание языка, который описывает в виде алгоритмов и графических примитивов векторный рисунок (приблизительно на таких принципах строится, например, отображение TTF шрифтов). Входным файлом для дан-ного транслятора будет являться исходный текст на описанном здесь языке, а выходным - либо окно с нарисованным рисунком, либо графический файл одного из популярных форматов (BMP, PNG etc). См. Примечание к варианту языка № 2.
Графические команды:
" задать параметры вывода:
- пера (толщина, цвет);
- кисти (тип, цвет);
- вывода текста (шрифт, размер);
" сохранить параметры вывода (в стек);
" восстановить параметры вывода (из стека);
" переместить перо в заданную позицию (x, y);
" переместить перо на заданную позицию (дельта x, дель-та y);
" нарисовать линию от текущей позиции до указанной (перо перемещается в эту позицию);
" нарисовать линию от текущей позиции до позиции в ви-де смещения от текущей позиции (перо перемещается в эту позицию);
" нарисовать прямоугольник с заданными координатами;
" нарисовать прямоугольник от текущей позиции до по-зиции, заданной в виде смещения;
" нарисовать эллипс с заданными координатами;
" нарисовать эллипс от текущей позиции до позиции, за-данной в виде смещения;
" нарисовать ломанную линию (каждая узловая точка ло-манной задается в виде смещения предыдущей точки).
Команды и конструкции общего назначения:
" задать глобальную переменную;
" вычислить выражение (стандартный минимум арифме-тических операций);
" повторить блок N раз (аналог цикла for);
" оператор if (конкретный синтаксис остается на Ваше усмотрение);
" оператор while (конкретный синтаксис остается на Ваше усмотрение);
" процедура (подпрограмма);
" обеспечить работу с локальными переменными.
Примечания:
" все замкнутые фигуры, такие, как прямоугольник, эл-липс и т.д., рисуются с учетом текущей кисти, но она может иметь тип "нет заливки", тогда фигура должна рисоваться без заливки;
" в качестве любого параметра проблемно-ориентиро-ванных команд могут использоваться выражения.
Вариант № 5. Язык управления "черепахой"
Данный язык является вариацией на тему известного языка для обучения программированию Лого. Рисовать "черепашку" можно в виде простого треугольничка. См. Примечание к варианту языка № 2.
Для данного варианта Ваш интерпретатор или виртуальная машина для компилятора должны представлять собой GUI-приложение, в котором требуется обеспечить как минимум коман-ду открытия файла (бинарного для компилятора и текстового для интерпретатора). Также требуется обспечить возможность указа-ния параметра задержки в миллисекундах, который будет исполь-зоваться для отображения после выполнения каждой команды, а также требуется отобразить и дать возможность изменить любой параметр - азимут "черепашки", ее текущие координаты. На вы-ходе Вы должны получить, в отличие от всех остальных вариан-тов, не файл, а процесс движения "черепашки".
Команды "черепашки":
" опусти хвост (после этого в процессе движения "чере-пашки" за хвостом остается линия), параметры - цвет и толщина линия;
" подними хвост (линия не остается);
" повернись на заданный азимут (азимут задается в граду-сах от севера, север - направление вверх);
" повернись на заданный угол (то есть к текущему азиму-ту нужно прибавить указанный);
" подвинься на заданное число шагов вперед (в ту сторо-ну, куда она смотрит);
" функция "впереди след хвоста".
Команды и конструкции общего назначения:
" создать переменную;
" вычислить выражение (стандартный минимум арифме-тических операций);
" условный оператор;
" цикл "пока";
" подпрограмма (желательно, но не обязательно, обеспе-чить работу с локальными переменными).
Примечание: в качестве относительно простого примера Вы можете реализовать построение какого-то лабиринта, а в качестве более сложного примера - выход из любого лабиринта, с любой позиции.
Вариант № 6. Интерпретатор командной строки
Основным назначением данного языка должна стать замена привычного Вам cmd.exe. сommand.com или shell. Соответственно, основными абстракциями, с которыми работает данный интерпре-татор, являются внешние программы, которые он может выпол-нять, передавая им параметры командной строки, и получать от них результат в виде кода завершения. Для примера можете изу-чить работу csh. Настоятельно рекомендую Вам реализовать сбо-рочный скрипт на Вашем языке, вместо использования обычных BAT или CMD файлов.
Необходимо обеспечить:
" запуск произвольного приложения со всеми его пара-метрами;
" работу перенаправления ввода-вывода для входного по-тока, выходного потока и потока вывода ошибок, в том числе работу канала передачи выхода одного приложе-ния входу другого при помощи "|";
" сохранение результата работы программы (кода завер-шения) в переменную;
" операции над переменными:
- конкатенацию переменных (то есть работу с ними как со строками);
- арифметические и логические операции над перемен-ными (то есть работу с ними, как с числами, стандарт-ный минимум арифметических операций);
" печать на экране (echo);
" поддержку параметров скриптового файла (то есть воз-можность передачи внешних параметров при запуске Вашего интерпретатора) и использование этих парамет-ров внутри скрипта как переменных;
" работу подпрограмм и локальных переменных;
" условный оператор;
" цикл "пока".
Вариант № 7. C-подобный алгоритмический язык
Требуется создать алгоритмический язык программирования, с синтаксисом, аналогичным языку C. Вам необходимо реализо-вать поддержку нижеследующих элементов.
" Стандартная структура программы языка C (глобальные переменные, функции, главная функция с именем main).
" Типы данных int и указатель на int.
" Функции. Обязательно необходимо обеспечить поддержку локальных переменных в функциях. Для проверки реали-зуйте на Вашем языке рекурсивный алгоритм вычисления чисел Фибоначчи, он должен работать корректно.
" Операторы:
" for
" if … [else …]
" Системные процедуры:
" print: достаточно, если эта функция будет принимать на вход ровно два параметра - строку и целочисленное выражение для печати;
" scanf: эта функция должна принимать ровно один пара-метр: переменную для ввода значения.
" Операции:
" Арифметические: +, -, *, /, %.
" Сравнения (операнды могут быть целого типа, результат целого типа): <, >, !=, <=, >=, ==
" Бинарные: &, |, ^, ~
" Логические (операнды булевы, результат булев): &&, ||, ^^, !
" Операции c указателем: *, &
Примечание:
" поддержка препроцессора и заголовочных файлов не требуется.
Сейчас на сайте
+79374242235
+79374242235
kursovikcom
kursovikcom