Загрузка...
Учебная работа. Реферат: Интерпретатор 2
ОМСКИЙ ГОСУДАРСТВЕННЫЙ технический УНИВЕРСИТЕТ
Кафедра информатики и вычислительной техники
Объяснительная записка
к курсовому проекту
по дисциплине СПО
Выполнил:
студент гр. ИВТ-425
Елизов В. В.
Проверил:
к.т.н., доцент
Флоренсов А. Н.
Омск 2009
Содержание
Задание. 3
Описание разработанного языка. 4
Описание модулей. 7
main.c. 8
init.c. 9
lexer.c. 10
parser.c. 12
symbol.c. 19
emitter.c. 21
errors.c. 24
Перечень использованной литературы.. 25
Задание
№4
Создать на базе предиктивного анализатора интерпретатор программ для языка программирования, который описательно задается последующими определениями:
1. язык обеспечивает вычисления на базе типов double и int языка Си (применяемого компилятором компиляторов), предполагается внедрение директив определения типа;
2. арифметические выражения могут употребляться сколь угодно сложной структуры, но не должны содержать воззваний к функциям;
3. язык содержит операторы цикла, задаваемые главным словом while, и условные операторы if — else; допускаются операторы break;
4. условия задаются в виде
5. для выдачи результатов служат операторы
printn
при этом оператор printn выдает округлые целые значения переменных, а для ввода оператор
input
где
представляет собой перечисление через запятую;
6. другие синтаксические элементы языка выбираются разрабом без помощи других (скобки, средства указания конца оператора, блока операторов, знак присваивания, обозначения операций сопоставления и т.п.);
7. Имена программных объектов должны формироваться по общеупотребительному правилу: первым эмблемой обязана быть случайная латинская буковка, следующими знаками могут быть числа либо латинские буковкы.
Главным результатом работы компилятора должен быть исполняемый файл интерпретатора; в качестве доп файла, выдаваемого компилятором при указании функции запроса для него, должен формироваться файл таблицы символических имен.
Представляемые результаты разработки должны включать объяснительную записку и начальный файл на языке Си, детально прокомментированный, с текстами подключаемых файлов, сделанных разрабом. Рекомендуется проводить разработку равномерно, реализую до получения результирующего файла поначалу 1-ые пункты его задания, потом добавляя к ним группу последующих и т.д.
Описание разработанного языка
Разработанный интерпретатор работает с особенным языком программирования, который, для упрощения, дальше в тексте будет называться NL.
Алфавит языка можно поделить на 6 групп:
1.
.
2.
— это строчные и строчные буковкы латинского алфавита.
3.
— это числа от 0 до 9.
4. Разделители и ограничители: , ; ( ) {}
5. Знаки операций + — * / := != == > < <= >=
6. Зарезервированныеслова: if, else, while, input, print, printn
Для записи программки не требуется какого-нибудь специального формата файла. Можно применять хоть какое расширение.
Неважно какая программка обязана начинаться знака { и заканчиваться эмблемой }. Они именуются операторные скобки и указывают на начало и конец процедуры.
К тому же неважно какая операция обязана заканчиваться эмблемой ; (точка с запятой).
Простая программка может смотреться последующим образом:
{
print 5.3;
}
При выполнении данной для нас программки на дисплее покажется число 5.3. Можно увидеть, что оператор print выводит на экран число (
Также существует оператор printn, который делает те же самые функции, что и print, лишь на экран выведется только целочисленное
{
printn 5.3;
}
То на дисплее покажется округлый итог – число 5.
Для того чтоб применять переменную нужно или ввести ее
{
a:=5.3;
input b;
print a,b;
printna,b;
}
В вышеперечисленном примере употребляется две переменных, a и b. 1-ая воспринимает
Для ввода нескольких переменных, как и для вывода можно применять последовательность имен, перечисленных через запятую.
язык NL дозволяет делать простые операции (над числами и переменными) такие как: сложение, вычитание, умножение и деление. Которые записываются так же, как и в арифметике: +, -, *, /. порядок выполнения этих операций также соответствует обычному. Для конфигурации приоритета необходимо применять скобки.
{
input a,b,c;
d:=(a*(a+b*b)+c)*c;
print d;
}
Для выполнения наиболее сложных операций употребляется оператор условного перехода if-else – когда последовательность действий зависит от какого-нибудь условия. структура условного оператора в полной форме имеет последующий вид:
if (условие) {действия1} else { деяния 2};
Условие — это выражение логического типа, которое может принимать два значения: правда либо ересь. Для записи условия употребляются операции сопоставления:
· == — равно
· != — неравно
· > — больше
· < — меньше
· >= — меньше-равно
· <= — больше-равно
Разглядим на примере работу условного оператора:
{
input a,b;
if(a==b)
{
print 10;
}
else
{
print 0;
};
}
Сначала программки вводятся два числа a и b. Потом они сравниваются на равенство. Если a равно b, то будут производиться деяния, находящиеся в операторных скобках конкретно за словом if. Другими словами, на экран выведется 10. Потом программка «перепрыгнет» через операторные скобки опосля слова else, на чем выполнение завершится. Если же условие окажется неверным (a не равно b), то пропустится 1-ая последовательность действий и выполнится 2-ая, находящаяся в операторных скобках опосля слова else. А конкретно, выведется 0.
Для выполнения циклических действий употребляется оператор цикла while. структура этого оператора имеет вид:
while (условие) {последовательность действий};, где условие — это хоть какое логическое выражение, истинность которого проверяется сначала каждой итерации (условие выполнения тела цикла). При истинности условия выполнится последовательность действий, находящаяся в операторных скобках и снова проверится условие. Так будет длиться до того времени, пока итог логического выражения не окажется неверным. Тогда последовательность действий не станет производиться и программка перейдет к последующему за операторными скобками действию. Следует увидеть, что если условие постоянно будет производиться, то программка зациклится – никогда не остановится. Ее необходимо будет окончить принудительно.
{
i:=10;
while(i>=1)
{
i:=i-1;
print i;
};
}
Выполнение данной программки приведет к тому, что на экран выведется 10 цифр – от 9 до 0.
Необходимо подчеркнуть, что операторы цикла, как и условные могут быть вложенными:
{
i:=10;
while(i>=1)
{
i:=i-1;
print i;
j:=i;
while(j<10)
{
j:=j+1;
print j;
};
};
}
Таковым образом, язык NL дозволяет воплотить достаточно большие вычисления и методы с ветвящейся структурой.
Описание модулей
Разработанная программка состоит из 7 модулей:
1. main.c – особая функция, которая открывает файл и делает пуск процедур обработки.
2. init.c – инициализация, делает деяния, которые необходимо произвести до начала анализа (занесение в таблицу знаков зарезервированных главных слов).
3. lexer.c – лексический анализатор. Выделяет из входной последовательности слово (токен).
4. parser.c – синтаксический анализатор. Обрабатывает слово, выделенное ранее лексическим анализатором.
5. symbol.c – модуль реализует взаимодействие с таблицей знаков и кодов (добавить запись, отыскать номер строчки)
6. emitter.c – выполнение программки, по таблице кодов, с внедрением таблицы знаков.
7. errors.c – обработка ошибок.
Для описания общих переменных и наружных функций употребляется заголовочный файл global.h
Дальше будут приведены начальные коды обрисованных выше файлов.
main.c
#include «global.h»
FILE* Open;
int main(int argc,char *argv[])
{
char *name=argv[1]; // Считать 1-ый аргумент (опосля имени исполняемого файла) из командной строчки
char *a1=argv[2]; // Считать 2-ой аргумент
char *a2=argv[3]; // Считать 3-ий аргумент
if((Open=fopen(name,»r»))==NULL) // Если не удалось открыть файл, то
{
printf(«Can’t open file test.txtn»); // Вывод сообщения о ошибке
getch(); // Ожидать нажатия на всякую клавишу
exit(1); // Выход
}
init(); // Иницализация
parse(); // Разбор
emit(); // Выполнение
fclose(Open); //Закрыть файл
if (a1) // Если 2-ой аргумент есть, то
{
printf(«nsymtable:n»); // Вывод таблицы знаков
get_symtable();
}
if (a2) // Если 3-ий аргумент есть, то
{
printf(«ncodetable:n»); // Вывод таблицы кодов
get_codetable();
}
printf(«nPress any key to exit.n»);
getch(); // Ожидать нажатия на кнопку
return(0);
}
init.c
#include «global.h»
struct entry keywords[]=
{
«if»,IF,0,
«else»,ELSE,0,
«while»,WHILE,0,
«input»,INPUT,0,
«print»,PRINT,0,
«printn»,PRINTN,0,
0,0,0,
};
void init(void)/* Загрузкаключевыхсловвтаблицусимволов */
{
struct entry *i;
for(i=keywords;i->token;i++)
insert(i->lexptr,i->token);
}
lexer.c
#include «global.h»
int CmpNextSym(int,int,int);
char lexbuf[BSIZE];
int lineno = 1;
double tokenval = NONE;
int lexan(void) /* Лексическийанализатор */
{
int t;
while (1)
{
t = fgetc(Open);// Считать в t знак из ранее открытого файла
if (t == ‘ ‘ || t == ‘t’); /* Отбрасываем разделители-пробелы */
else if (t == ‘n’)// Если знак перевода строчки, то
lineno++;// Прирастить счетчик линий
else if (isdigit(t)) /* t — цифра */
{
ungetc(t, Open);// Возвратить t во входной поток
fscanf(Open,»%lf»,&tokenval);// Занести занчение числа (1 либо > знаков) в tokenval
return NUM;// Возвратить идентификатор числа
}
else if (isalpha(t)) /* t — буковка */
{
int p, b = 0;
while (isalnum(t)) /* Пока t — букваилицифра */
{
lexbuf[b++] = t;// Добавить в буффер t
t=fgetc(Open);// Считать очередной знак
if (b >= BSIZE)// если превышен рзмер буффера
error(«compiler error»);// Вызов процедуры выхода с сообщением о ошибке
}
lexbuf[b] = EOS;// Добавить в буффер признак окончания последовательности знаков (слова)
if (t != EOF)// Если t — не признак конца файла, то
ungetc(t, Open);// Возвратить t
p = lookup(lexbuf);// p = положение считанного слова в таблце знаков
if (p == 0)// Если слово повстречалось в первый раз
p = insert(lexbuf, ID);// Добавить в таблицу знаков новейшую переменную
tokenval = p;
return symtable[p].token;// Возвратить соответственный считанному слову идентификатор
}
else if (t == EOF) return DONE;// Если в t признак окончания файла — возвратить идентификатор конца программки
else switch(t)// По другому, если t один из знаков:
{
case ‘>’:
return CmpNextSymactiveXJG,JGE);// Если за t следует =, то возвратить инедтификатор условия JGE (больше-равно), по другому — JG (больше)
case ‘<‘:
return CmpNextSymactiveXJL,JLE);// Меньше-равно, либо меньше
case ‘!’:
return CmpNextSymactiveXJNE,’!’);// Не равно, либо знак !
case ‘=’:
return CmpNextSymactiveXJE,’=’);// Равно (условие) либо знак =
case ‘:’:
return CmpNextSymactiveXEQUAL,’:’);// Прсвоитьилисимвол :
case ‘{‘:
return BEGIN;// Вернутьидентификатор BEGIN
case ‘}’:
return END;// Вернутьидентификатор END
default:// Если что-либо другое, то
tokenval=NONE;
return t;// Возвратить t
}
}
}
int CmpNextSym(int ch,int good,int bad)
{
int nc=fgetc(Open);// считать последующий знак
if(nc==ch) return good;//если последующий знак = ch — возвратить good
ungetc(nc,Open);//по другому, возврат знака во входной поток
return bad;// возвратить bad
}
parser.c
#include «global.h»
int FillCode(void);
int FC(void);
int expr(void);
int term(void);
int factor(void);
int IdIn(void);
void LabelPush(int);
int LabelPop(void);
int match(int);
int lookahead;//текущий сканируемый входной токен
int LabelStack[100],LabelCnt=0;
double tv;
int parse(void)/* Разбор и трансляция перечня выражений */
{
lookahead=lexan();// Чтение слова
while(lookahead!=DONE)// До того времени, пока не будет получен идентификатор окончания программки
{
FillCode();// Наполнение таблицы кодов
}
return 0;// Возврат
}
int FillCode()
{
int t;
FC();// Обработкаслова
while(1)// Нескончаемо повторять
{
switch(lookahead)
{
case ‘;’://Если текущее слово — знак «;», то
match(‘;’);// Перейти к последующему слову
insertcode(0,»;»,0);// Добавить в таблицу клдлв «;»
FC();// Обработка слова
break;
default:
return;
}
}
}
int FC(void)
{
while(1)
{
switch(lookahead)
{
case ID:
match(ID);
tv=tokenval;
match(EQUAL);
expr();// Обработкавыражения
insertcode(EQUAL,symtable[tv].lexptr,0);// Добавить в таблицу кодов присваивание переменной
break;
case PRINTN:
match(PRINTN);
expr();// Обработка выражения
insertcode(PRINTN,»printn»,0);// Добавить строку в таблицу кодов
while(1)
{
switch(lookahead)
{
case ‘,’:// Обработкааргументов, введенных через запятую
match(‘,’);
expr();
insertcode(PRINTN,»printn»,0);
break;
default:
return;
}
}
case INPUT:
match(INPUT);
IdIn();// Добваить в таблицу кодов строку получения заначения переменной
break;
case PRINT:
match(PRINT);
expr();
insertcode(PRINT,»print»,0);
while(1)
{
switch(lookahead)
{
case ‘,’:
match(‘,’);
expr();
insertcode(PRINT,»print»,0);
break;
default:
return;
}
}
case BEGIN:
match(BEGIN);
FillCode();// Вызов процедуры обработки слов (сначала проверится слово, потом «;»)
match(END);
break;
case IF:
match(IF);
match(‘(‘);
expr();
insertcode(THEN,»then»,0);
LabelPush(lastcode);// Добавитьметку
match(‘)’);
FC();
codetable[LabelPop()].value=lastcode+1;// Поменять занчение в строке метки, для указания на подходящую строку
insertcode(GOTO,»else»,0);
LabelPush(lastcode);// Добавитьметку
match(ELSE);
FC();
codetable[LabelPop()].value=lastcode;// Поменять занчение в строке метки, для указания на подходящую строку
break;
case WHILE:
insertcode(WHILE,»while»,0);
LabelPush(lastcode);
match(WHILE);
match(‘(‘);
expr();
match(‘)’);
insertcode(DO,»do»,0);
LabelPush(lastcode);
FC();
codetable[LabelPop()].value=lastcode+1;
insertcode(GOTO,»goto»,LabelPop());
break;
default:
return;
}
}
}
int expr(void)
{
term();// Ввызов вспомогательной процедуры разбора
while(1)
{
switch(lookahead)// Обработка операций + — и логических уловий
{
case ‘+’:
match(lookahead);// Перейти к последующему слову
term();
insertcodeactiveXquot;+»,0);
break;
case ‘-‘:
match(lookahead);
term();
insertcodeactiveXquot;-«,0);
break;
case JNE:
match(lookahead);
term();
insertcode(JE,»!=»,0);
break;
case JE:
match(lookahead);
term();
insertcode(JNE,»==»,0);
break;
case JL:
match(lookahead);
term();
insertcode(JL,»<«,0);
break;
case JLE:
match(lookahead);
term();
insertcode(JLE,»<=»,0);
break;
case JG:
match(lookahead);
term();
insertcode(JG,»>»,0);
break;
case JGE:
match(lookahead);
term();
insertcode(JGE,»>=»,0);
break;
default:
return;
}
}
}
int term()
{
factor();// Ввызов вспомогательной процедуры разбора
while(1)
{
switch(lookahead)// Обработка матемтических операций типа *, /
{
case ‘*’:
match(lookahead);
factor();
insertcodeactiveXquot;*»,0);
break;
case ‘/’:
match(lookahead);
factor();
insertcode(‘/’,»/»,0);
break;
default:
return;
}
}
}
int factor(void)
{
switch(lookahead)
{
case NUM:
insertcode(NUM,»num»,tokenval);
match(NUM);
break;
case ID:
insertcode(ID,symtable[tokenval].lexptr,0);
match(ID);
break;
case ‘(‘:
match(‘(‘);
expr();
match(‘)’);
break;
default:
error(«syntax error»);
}
return 0;
}
int IdIn()
{
insertcode(INPUT,symtable[tokenval].lexptr,0);
match(ID);
while(1)
{
switch(lookahead)
{
case ‘,’:
match(‘,’);
insertcode(INPUT,symtable[tokenval].lexptr,0);
match(ID);
break;
default:
return;
}
}
}
void LabelPush(int n)// Добавить метку в стек
{
LabelStack[LabelCnt++]=n;
}
int LabelPop(void)// Извлечь метку из стека
{
LabelCnt—;
return LabelStack[LabelCnt];
}
int match(int t)//процедура перебегает к последующему входному токену, если ее аргумент t совпадает со сканируемым эмблемой.
{
if(lookahead==t)// Если t совпадает со сканируемым словом, то
lookahead=lexan();// Считать последующее слово
else error(«syntax error»);// По другому — вывод ошибки, выход
return 0;
}
symbol.c
#include «global.h»
#defineSTRMAX 1000 /* Размер массива лексем */
#define SYMMAX 1000 /* Размер таблицы знаков */
#define CODEMAX 1000/* Размер таблицы кодов */
char lexemes[STRMAX];
int lastchar = -1; /* Крайняя использованная позиция в lexemes */
struct entry symtable[SYMMAX];
int lastentry = 0; // Крайняя использованная позиция в таблице знаков
char lexgen[STRMAX];
int lastlexgen = -1;
struct code codetable[CODEMAX];
int lastcode = 0; /* Последняяиспользованнаяпозициявтаблицекодов */
int lookup(char s[]) /* Возвращает положение в таблице знаков для s */
{
int i;
for(i = lastentry; i > 0; i—)
if (strcmp(symtable[i].lexptr, s) == 0)
return i;
return 0;
}
int insert(char s[], int tok) /* Добавитьстрочкувтаблицусимволов */
{
int len;
len = strlen(s); /* strlen вычисляетдлинустроки */
if (lastentry + 1 >= SYMMAX)
error(«symbol table full»);
if (lastchar + len + 1 >= STRMAX)
error(«lexemes array full»);
lastentry++;
symtable[lastentry].token = tok;
symtable[lastentry].lexptr = &lexemes[lastchar + 1];
lastchar += len + 1;
strcpy(symtable[lastentry].lexptr, s);
return lastentry;
}
int insertcode(int tok,char s[],double value){ //Добавлениевтаблицукодов
int len;
len=strlen(s);
if(lastcode+1>=CODEMAX)
error(«code table full»);
if(lastlexgen+len+1>=STRMAX)
error(«lexemes array full»);
lastcode++;
codetable[lastcode].value = value;
codetable[lastcode].token = tok;
codetable[lastcode].lexptr = &lexgen[lastlexgen+1];
lastlexgen+=len +1;
strcpy(codetable[lastcode].lexptr,s);
return lastcode;
}
int get_codetable()// Вывеститаблицукодов
{
int i;
for(i=1;i<=lastcode;i++)
printf(«%d %d %s %gn»,i,codetable[i].token,codetable[i].lexptr,codetable[i].value);
return 0;
}
int get_symtable()// Вывеститаблицусимволов
{
int i;
for(i=1;i<=lastentry;i++)
printf(«%d %d %s %gn»,i,symtable[i].token,symtable[i].lexptr,symtable[i].value);
return 0;
}
emitter.c
#include «global.h»
double stack[1000];
int j=0;
int a;
double pop(void);
void push(double n);
double x,y,z;
int emit(void) //Выполнениепрограммы
{
int i=0;
while(i<lastcode)// делать, пока не достигнут конец таблицы кодов
{
switch(codetable[i].token)// Выполнить действие, в согласовании с прочитанным словом из таблицы кодов
{
case NUM:
push(codetable[i].value);
break;
case ID:
push(symtable[lookup(codetable[i].lexptr)].value);
break;
case ‘+’:
y=pop();
z=pop();
push(z+y);
break;
case ‘-‘:
y=pop();
z=pop();
push(z-y);
break;
case ‘*’:
y=pop();
z=pop();
push(z*y);
break;
case ‘/’:
y=pop();
z=pop();
push(z/y);
break;
case EQUAL:
symtable[lookup(codetable[i].lexptr)].value=pop();
break;
case JE:
y=pop();
z=pop();
push(y==z);
break;
case JNE:
y=pop();
z=pop();
push(y!=z);
break;
case JL:
y=pop();
z=pop();
push(y<z);
break;
case JLE:
y=pop();
z=pop();
push(y<=z);
break;
case JG:
y=pop();
z=pop();
push(y>z);
break;
case JGE:
y=pop();
z=pop();
push(y>=z);
break;
case DO:
if(pop()==1)i=codetable[i].value;// Если условие выполнено — перейти в подобающую строчку
break;
case GOTO:
i=codetable[i].value;
break;
case THEN:
if(pop()==1)i=codetable[i].value;
break;
case PRINT:
printf(«%g n»,pop());
break;
case PRINTN:
a = pop();
printf(«%d n»,a);
break;
case INPUT:
scanf(«%lf,»,&symtable[lookup(codetable[i].lexptr)].value);
break;
}
i++;
}
return 0;
}
void push(double n)//Положитьвстек
{
stack[j++]=n;
}
double pop()//Извлечьизстека
{
j—;
return stack[j];
}
errors.c
#include»global.h»
int error(char *s)
{
printf(«%s in line %dn»,s,lineno); // вывод сообщения о ошибке в определенной строке
getch();
exit(1); // выход
return 0;
}
Перечень использованной литературы
1. А. Ахо, Р. Сети, Д. Ульман Компиляторы: принципы, технологии и инструменты.: Пер. с англ. — М.: Издательский дом «Вильяме», 2003. — 768 с.
2. Липпман C++ для начинающих. – 1194 с.
3. Флоренсов А.Н. Операционные системы: Учеб. пос. — Омск: Издательство ОмГТУ, 2005. – 160 с.
]]>