Интерпретатор 2
Федеральное агентство по образованию
ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра информатики и вычислительной техники
Пояснительная записка
к курсовому проекту
по дисциплине СПО
Выполнил:
студент гр. ИВТ-425
к. т. н., доцент
Флоренсов А. Н.
Омск 2009
Содержание
Задание. 3
Описание разработанного языка. 4
Описание модулей. 7
main. c. 8
init. c. 9
symbol. c. 19
emitter. c. 21
errors. c. 24
Разработать на основе предиктивного анализатора интерпретатор программ для языка программирования, который описательно задается следующими определениями:
1. язык обеспечивает вычисления на основе типов double и int языка Си (используемого компилятором компиляторов), предполагается использование директив определения типа;
2. арифметические выражения могут использоваться сколь угодно сложной структуры, но не должны содержать обращений к функциям;
4. условия задаются в виде
print
printnсписок имен переменных
inputсписок имен переменных
где список имен переменных
п.);
7. Имена программных объектов должны формироваться по общеупотребительному правилу: первым символом должна быть произвольная латинская буква, последующими символами могут быть цифры или латинские буквы.
Основным результатом работы компилятора должен быть исполняемый файл интерпретатора; в качестве дополнительного файла, выдаваемого компилятором при указании опции запроса для него, должен формироваться файл таблицы символических имен.
Представляемые результаты разработки должны включать пояснительную записку и исходный файл на языке Си, детально прокомментированный, с текстами подключаемых файлов, созданных разработчиком. Рекомендуется проводить разработку постепенно, реализую до получения результирующего файла сначала первые пункты его задания, затем добавляя к ним группу следующих и т. д.
Описание разработанного языка
Разработанный интерпретатор работает с особым языком программирования, который, для упрощения, далее в тексте будет называться NL.
Алфавит языка можно разделить на 6 групп:
1.
.
2. Буквы
- это прописные и строчные буквы латинского алфавита.
3.
- это цифры от 0 до 9.
4. Разделители и ограничители: , ; ( ) {}
5. Знаки операций + - * / := != == > < <= >=
Для записи программы не требуется какого-либо специального формата файла. Можно использовать любое расширение.
Любая программа должна начинаться символа { и заканчиваться символом }. Они называются операторные скобки и указывают на начало и конец процедуры.
К тому же любая операция должна заканчиваться символом ; (точка с запятой).
Простейшая программа может выглядеть следующим образом:
{
print 5. 3;
}
необходимо указать через запятую.
Также существует оператор printn, который выполняет те же самые функции, что и print, только на экран выведется лишь целочисленное значение. Например, если выполнить программу:
{
printn 5. 3;
}
Для того чтобы использовать переменную необходимо либо ввести ее значение при помощи оператора input, либо использовать присваивание (оператор :=). Переменная описывается последовательностью латинских букв, цифр и знака подчеркивания, начинающейся с буквы.
{
a:=5. 3;
print a,b;
printna,b;
}
В вышеописанном примере используется две переменных, a и b. Первая принимает значение 5. 3, значение же второй необходимо ввести вручную и нажать клавишу ввода. Результатом выполнения этой программы будет 4 числа: 5. 3, значение переменной b, 5 и округленное до целого значение второй переменной. Причем, каждое число будет выведено в новой строке.
Для ввода нескольких переменных, как и для вывода можно использовать последовательность имен, перечисленных через запятую.
Язык NL позволяет выполнять простейшие операции (над числами и переменными) такие как: сложение, вычитание, умножение и деление. Которые записываются так же, как и в математике: +, -, *, /. Порядок выполнения этих операций также соответствует привычному. Для изменения приоритета нужно использовать скобки.
{
d:=(a*(a+b*b)+c)*c;
print d;
}
Для выполнения более сложных операций используется оператор условного перехода if-else – когда последовательность действий зависит от какого-либо условия. Структура условного оператора в полной форме имеет следующий вид:
if (условие) {действия1} else { действия 2};
Условие - это выражение логического типа, которое может принимать два значения: истина или ложь. Для записи условия используются операции сравнения:
· != - неравно
> - больше
· < - меньше
· >= - меньше-равно
· <= - больше-равно
{
input a,b;
if(a==b)
{
}
else
{
};
}
В начале программы вводятся два числа a и b. Затем они сравниваются на равенство. Если a равно b, то будут выполняться действия, находящиеся в операторных скобках непосредственно за словом if. То есть, на экран выведется 10. Затем программа «перепрыгнет» через операторные скобки после слова else, на чем выполнение закончится. Если же условие окажется ложным (a не равно b), то пропустится первая последовательность действий и выполнится вторая, находящаяся в операторных скобках после слова else. А именно, выведется 0.
выполнится последовательность действий, находящаяся в операторных скобках и опять проверится условие. Так будет продолжаться до тех пор, пока результат логического выражения не окажется ложным. Тогда последовательность действий перестанет выполняться и программа перейдет к следующему за операторными скобками действию. Следует заметить, что если условие всегда будет выполняться, то программа зациклится – никогда не остановится. Ее нужно будет завершить принудительно.
{
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 позволяет реализовать довольно объемные вычисления и алгоритмы с ветвящейся структурой.
Описание модулей
Разработанная программа состоит из семи модулей:
1. main. c – специальная функция, которая открывает файл и выполняет запуск процедур обработки.
2. init. c – инициализация, выполняет действия, которые нужно произвести до начала анализа (занесение в таблицу символов зарезервированных ключевых слов).
3. lexer. c – лексический анализатор. Выделяет из входной последовательности слово (токен).
4. parser. c – синтаксический анализатор. Обрабатывает слово, выделенное ранее лексическим анализатором.
5. symbol. c – модуль реализует взаимодействие с таблицей символов и кодов (добавить запись, найти номер строки)
7. errors. c – обработка ошибок.
Для описания общих переменных и внешних функций используется заголовочный файл global. h
Далее будут приведены исходные коды описанных выше файлов.
main. c
"global. h"
FILE* Open;
{
char *name=argv[1]; // Считать первый аргумент (после имени исполняемого файла) из командной строки
char *a2=argv[3]; // Считать третий аргумент
if((Open=fopen(name,"r"))==NULL) // Если не удалось открыть файл, то
{
printf("Can't open file test.txt\n"); // Вывод сообщения об ошибке
getch(); // Ждать нажатия на любую кнопку
exit(1); // Выход
}
init(); // Иницализация
parse(); // Разбор
emit(); // Выполнение
fclose(Open); //Закрыть файл
if (a1) // Если второй аргумент есть, то
{
printf("\nsymtable:\n"); // Вывод таблицы символов
getsymtable();
}
if (a2) // Если третий аргумент есть, то
{
printf("\ncodetable:\n"); // Вывод таблицы кодов
getcodetable();
}
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,
};
void init(void)/* Загрузкаключевыхсловвтаблицусимволов */
{
struct entry *i;
>token;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)
{
if (t == ' ' t == '\t'); /* Отбрасываем разделители-пробелы */
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);// Считать очередной символ
>= 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;
}
else switch(t)// Иначе, если t один из символов:
{
case '>':
return CmpNextSym('=',JG,JGE);// Если за t следует =, то вернуть инедтификатор условия JGE (больше-равно), иначе - JG (больше)
case '<':
return CmpNextSym('=',JL,JLE);// Меньше-равно, или меньше
case '!':
case ':':
return CmpNextSym('=',EQUAL,':');// Прсвоитьилисимвол :
case '{':
return BEGIN;// Вернутьидентификатор BEGIN
case '}':
return END;// Вернутьидентификатор END
default:// Если что-либо другое, то
tokenval=NONE;
}
}
}
{
int nc=fgetc(Open);// считать следующий символ
if(nc==ch) return good;//если следующий символ = ch - вернуть good
return bad;// вернуть bad
}
"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;
int parse(void)/* Разбор и трансляция списка выражений */
{
lookahead=lexan();// Чтение слова
while(lookahead!=DONE)// До тех пор, пока не будет получен идентификатор завершения программы
{
FillCode();// Заполнение таблицы кодов
}
return 0;// Возврат
}
{
int t;
while(1)// Бесконечно повторять
{
switch(lookahead)
{
case ';'://Если текущее слово - символ ";", то
";",0);// Добавить в таблицу клдлв ";"
FC();// Обработка слова
break;
default:
return;
}
}
}
{
while(1)
{
{
case ID:
tv=tokenval;
expr();// Обработкавыражения
insertcode(EQUAL,symtable[tv]. lexptr,0);// Добавить в таблицу кодов присваивание переменной
break;
expr();// Обработка выражения
insertcode(PRINTN,"printn",0);// Добавить строчку в таблицу кодов
while(1)
{
switch(lookahead)
{
case ',':// Обработкааргументов, введенных через запятую
expr();
insertcode(PRINTN,"printn",0);
break;
default:
}
}
IdIn();// Добваить в таблицу кодов строчку получения заначения переменной
case PRINT:
match(PRINT);
expr();
insertcode(PRINT,"print",0);
{
switch(lookahead)
{
case ',':
match(',');
expr();
insertcode(PRINT,"print",0);
default:
return;
}
}
case BEGIN:
match(BEGIN);
FillCode();// Вызов процедуры обработки слов (вначале проверится слово, затем ";")
match(END);
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;
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());
default:
}
}
}
int expr(void)
{
term();// Ввызов вспомогательной процедуры разбора
while(1)
{
switch(lookahead)// Обработка операций + - и логических уловий
{
case '+':
term();
insertcode('+',"+",0);
break;
case '-':
match(lookahead);
term();
insertcode('-',"-",0);
case JNE:
match(lookahead);
term();
insertcode(JE,"!=",0);
case JE:
match(lookahead);
term();
insertcode(JNE,"==",0);
break;
match(lookahead);
insertcode(JL,"<",0);
break;
case JLE:
match(lookahead);
term();
insertcode(JLE,"<=",0);
case JG:
match(lookahead);
term();
insertcode(JG,">",0);
case JGE:
term();
insertcode(JGE,">=",0);
break;
default:
return;
}
}
}
int term()
{
factor();// Ввызов вспомогательной процедуры разбора
while(1)
{
switch(lookahead)// Обработка матемтических операций типа *, /
{
match(lookahead);
factor();
"*",0);
break;
case '/':
match(lookahead);
factor();
"/",0);
default:
return;
}
}
}
int factor(void)
{
switch(lookahead)
{
case NUM:
"num",tokenval);
break;
insertcode(ID,symtable[tokenval]. lexptr,0);
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();// Считать следующее слово
"syntax error");// Иначе - вывод ошибки, выход
}
symbol. c
#include "global. h"
#define CODEMAX 1000/* Размер таблицы кодов */
char lexemes[STRMAX];
int lastchar = -1; /* Последняя использованная позиция в lexemes */
struct entry symtable[SYMMAX];
int lastentry = 0; // Последняя использованная позиция в таблице символов
int lastlexgen = -1;
struct code codetable[CODEMAX];
int lastcode = 0; /* Последняяиспользованнаяпозициявтаблицекодов */
{
int i;
for(i = lastentry; i > 0; i--)
if (strcmp(symtable[i]. lexptr, s) == 0)
return i;
}
{
int len;
if (lastentry + 1 >= SYMMAX)
"symbol table full");
>= STRMAX)
"lexemes array full");
lastentry++;
symtable[lastentry]. lexptr = &lexemes[lastchar + 1];
lastchar += len + 1;
strcpy(symtable[lastentry]. lexptr, s);
return lastentry;
}
int len;
len=strlen(s);
>=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;
return lastcode;
}
int getcodetable()// Вывеститаблицукодов
{
int i;
for(i=1;i<=lastcode;i++)
"%d %d %s %g\n",i,codetable[i]. token,codetable[i]. lexptr,codetable[i]. value);
return 0;
}
int getsymtable()// Вывеститаблицусимволов
{
int i;
for(i=1;i<=lastentry;i++)
printf("%d %d %s %g\n",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) //Выполнениепрограммы
{
while(i<lastcode)// Выполнять, пока не достигнут конец таблицы кодов
{
{
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);
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();
push(y==z);
break;
case JNE:
z=pop();
push(y!=z);
break;
case JL:
y=pop();
z=pop();
push(y<z);
break;
y=pop();
z=pop();
<=z);
break;
case JG:
z=pop();
push(y>z);
case JGE:
y=pop();
z=pop();
push(y>=z);
break;
if(pop()==1)i=codetable[i]. value;// Если условие выполнено - перейти в соответствующую строку
break;
case GOTO:
break;
if(pop()==1)i=codetable[i]. value;
break;
case PRINT:
printf("%g \n",pop());
break;
case PRINTN:
printf("%d \n",a);
break;
case INPUT:
scanf("%lf,",&symtable[lookup(codetable[i]. lexptr)]. value);
break;
}
i++;
}
}
void push(double n)//Положитьвстек
{
stack[j++]=n;
}
{
j--;
return stack[j];
}
errors. c
#include"global. h"
int error(char *s)
{
printf("%s in line %d\n",s,lineno); // вывод сообщения об ошибке в конкретной строке
getch();
exit(1); // выход
}
Список использованной литературы
1. А. Ахо, Р. Сети, Д. Ульман Компиляторы: принципы, технологии и инструменты.: Пер. с англ. — М.: Издательский дом "Вильяме", 2003. — 768 с.
2. Липпман C++ для начинающих. – 1194 с.
3. Флоренсов А. Н. Операционные системы: Учеб. пос. - Омск: Издательство ОмГТУ, 2005. – 160 с.
| 
