CodeNet / Языки программирования / C / C++ / Руководства и справочные материалы по C/C++ / C для профессиональных программистов
C для профессиональных программистов
ГЛАВА 7 -- 1 --
-------
ИНТЕРПРЕТАТОРЫ ЯЗЫКА.
-----------------------------------------------------------------
Вы когда-нибудь хотели создать свой язык программирования?
Большинство программистов призывают к поиску идеи создания,
управления и модификации своих языков программирования. Однако,
лишь немногие программисты могут легко и непринужденно создать
язык программирования. Создание полного компилятора является
многообязывающей задачей, но гораздо проще создать интерпретатор
языка. Методы, используемые для создания итерпретаторов языка,
изучаются редко или изучаются довольно абстрактно. В этой главе
на практических примерах вы будете изучать секреты интерпретации
языка и грамматического разбора выражений.
Интерпретаторы важны по трем очень важным причинам.
Во-первых, они могут обеспечивать удобную интерактивную среду
(как доказательство - интерпретатор стандартного языка BASIC,
которыми снабжаются большинство персональных компьтеров). Многие
пользователи-новички находят, что интерактивная среда более
удобна, чем компилятор. Во-вторых, интерпретаторы языка
обеспечивают превосходные интерактивные отладочные возможности.
Даже ветераны-программисты при отладке трудных программ прибегают
к помощи интерпретатора языка, потому что он позволяет динамично
устанавливать значения переменных и условий. В-третьих,
большинство языков запросов к базе данных работают в режиме
интерпретации.
В этой главе будет разработан интерпретатор для подмножества
языка BASIC, который еще называют "SMALL BASIC". BASIC выбран
вместо Cи, потому что BASIC легче интерпретируется, чем Cи или
другой структурный язык. Интерпретатор для структурного языка,
такого как Cи более труден, чем для BASIC из-за автономных
функций с локальными переменными, которые обеспечивают
интерпретатору многозначность. Принципы, используемые в
интерпретаторе BASIC, применимы и для других языков, и вы можете
использовать написанные программы в качестве отправной точки.
Прежде, чем начать работу, необходимо изучить сущность языковой
интерпретации, особенно перед тем, как браться за интерпетацию
такого сложного языка, как Cи. Если вы не знаете BASIC, не
беспокойтесь, команды используемые в SMALL BASIC очень легкие для
понимания.
Мы начинаем с сердца любого интерпретатора: синтаксического
анализатора выражений.
Глава VII -- 2 --
СИНТАКСИЧЕСКИЙ РАЗБОР ВЫРАЖЕНИЙ
-----------------------------------------------------------------
Наиболее важной частью интерпретатора языка является
синтактический анализатор выражений, который преобразует числовые
выражения, такие как (10-X)/23, в такую форму, чтобы компьютер
мог понять ее и вычислить. В книге по языку Cи: The Complete
Reference (Osborne/McGraw-uill, 1987) вступительная глава
посвящена синтаксическому анализу выражений. Подобного же рода
синтаксический анализ, основанный на принципах, изложенных в
вышеупомянутой книге, (правда, с небольшими изменениями) будет
использоваться для построения интерпретатора SMALL BASIC в данной
главе нашей книги. (Так как эта глава содержит только краткие
сведения о синтаксическом анализе выражений, то для более
детального изучения этой проблемы советуем вам обратиться к
источнику: The Compelete Reference.
Синтаксический анализ выражений является довольно сложной
задачей, однако в некоторых случаях она облегчается тем, что в
процессе синтаксического анализа используются довольно строгие
правила алгебры. Синтаксический анализатор, описанный в этой
главе, в общем может быть классифицирован как синтаксический
анализатор рекурсивного спуска.
Перед тем, как приступить к детальной разработке
синтаксического анализатора, вы должны иметь представление о
выражениях. Поэтому наш следующий параграф посвящен именно этому
вопросу.
Глава VII -- 3 --
ВЫРАЖЕНИЯ
-----------------------------------------------------------------
Хотя выражения могут быть составлены в принципе из любых
типов данных, в этой главе мы будем иметь дело только с числовыми
выражениями. Будем считать, что для наших целей числовые
выражения могут строится из следующих элементов:
- числа
- операторы + - / * ^ % = () <> ; ,
- скобки
- переменные
Символ '^' означает экспоненту, а символ '=' используется
как оператор присваивания, а также как знак равенства в операциях
сравнения. Элементы выражения можно комбинировать согласно
правилам алгебры.
Вот некоторые примеры выражений:
7-8 (100-5)*14/6
a+b-c
10^5
a=7-b
Символы '=', '>', '<', ',', ';' являются операторами, они не
могут использоватся в выражениях функций и конструкциях типа IF,
PRINT и операторах присваивания. (Заметим, что анализатор языка
Cи должен обрабатывать и эти операторы в различных их
комбинациях).
Что касается языка BASIC, старшинство операторов не
определено. В процессе работы синтаксический анализатор
присваивает операторам следующие приоритеты:
высший ()
^
* / %
+ -
низший =
Операторы равного приоритета выполняются слева направо.
Синтаксис языка SMALL BASIC предполагает, что все переменные
обозначаются одной буквой. Это позволяет оперировать в программе
двадцати шестью переменными (буквы от A до Z). Хотя
интерпретаторы языка BASIC поддерживают обычно большее число
символов в определении переменной, (например, переменные типа
Х27), но для простоты изложения основных принципов построения
интерпретаторов наш интерпретатор языка SMALL BASIC этого делать
не будет. Будем считать также, что переменные разных регистров не
отличаются друг от друга и, поэтому, переменные "a" и "A" будут
трактоваться как одна и та же переменная. Условимся, что все
числа являются целыми, хотя вы без особого труда можете написать
Глава VII -- 4 --
программы для манипулирования другими типами чисел. Хотя
символьные переменные в нашей версии языка и не поддерживаются,
будем считать, что возможен вывод ограниченных символьных
констант на экран в виде различных сообщений.
Итак, будем строить синтаксический анализатор исходя из
перечисленных выше допущений. Теперь давайте рассмотрим такое
базовое понятие теории синтаксического анализа как лексема.
Глава VII -- 5 --
ЛЕКСЕМЫ
-----------------------------------------------------------------
Перед тем, как построить синтаксический анализатор,
разбирающий значения выражений, вы должны иметь несколько
вариантов разбиения строки, содержащей выражение, на составляющие
части. Например, выражение
А*В-(W+10)
содержит компоненты "А", "*", "В", "-", "(", "W", "+", "10" и
")". Каждый компонент представляет собой неделимый элемент
выражения. Такой компонент или независимая часть выражения
называется лексемой. Функция, разбивающая выражение на составные
части, должна решать четыре задачи: (1) игнорировать пробелы и
символы табуляции, (2) извлекать каждую лексему из текста, (3)
если необходимо, преобразовывать лексему во внутренний формат,
(4) определять тип лексемы.
Каждая лексема имеет два формата: внешний и внутренний.
Внешний формат - это символьная строка, с помощью которой вы
пишите программы на каком-либо языке программирования. Например,
"PRINT" - это внешняя форма команды PRINT языка BASIC. Можно
построить интерпретатор из расчета, что каждая лексема
используется во внешнем формате, но это типичное решение проблемы
программистом-непрофессионалом, который лишь два часа назад
оторвался от материной юбки и час назад увидел настоящий
компьютер. Настоящие мужчины ориентируются на внутренний формат
лексемы, который является просто числом, и разрабатывают
интерпретаторы исходя из этой профессиональной точки зрения на
проблему. Поясним этот подход. Например, команда PRINT может
иметь порядковый внутренний номер 1, команда INPUT - 2 и т.д.
Преимущество внутреннего формата заключается в том, что
программы, обрабатывающие числа, более быстродействующие, чем
программы, обрабатывающие строки. Для реализации такого подхода
необходима функция, которая берет из входного потока данных
очередную лексему и преобразует ее из внешнего формата во
внутренний. Помните, что не все лексемы имеют разные форматы.
Например, операторы не подлежат преобразованию потому, что они
могут трактоваться как символы или числа в своих внешних
форматах.
Очень важно знать, какой тип лексемы возвращен. Например,
анализатору выражений необходимо знать, является ли следующая
лексема числом, оператором или переменной. Значение типа лексемы
для процесса анализа в целом станет очевидным, когда вы
приступите непосредственно к разработке интерпретатора.
Функция, которая возвращает следующую лексему в выражении,
называется get_token( ). Она работает из расчета того, что в
языке SMALL BASIC, программа хранится как одна строка,
ограниченная в конце символом завершения строки (\0). Функция
get_token() сканирует текст программы, анализируя по одному
символу, при этом глобальный указатель анализатора принимает
Глава VII -- 6 --
значение адреса очередной считаной лексемы. В версии get_token(),
приведенной ниже, этот указатель называется prog. Так как prog
является глобальной переменной, то его значение между вызовами
get_token сохраняется и позволяет другим функциям использовать
его.
Анализатор, разрабатываемый в этой главе, использует шесть
типов лексем: DELIMITER, VARIABLE, NUMBER, COMMAND, STRING и
QUOTE (разделитель, переменная, число, команда, строка и
кавычки). Тип VARIABLE приписывается переменным. Тип DELIMITER
приписывается операторам и скобкам. Тип NUMBER - для чисел. Тип
COMMAND - для команд языка SMALL BASIC. Тип STRING временно
используется внутри get_token() пока идет разбор лексемы. Тип
QUOTE используется при определении кавычек, ограничивающих
строку. Глобальная переменная token_type содержит тип лексемы.
Внутреннее представление лексемы помещается в глобальную
переменную tok.
Ниже приведена функция get_token(). Все остальные
необходимые вспомогательные функции для полного синтаксического
анилизатора будут приведены в этой главе немного позже.
#define DELIMITER 1
#define VARIABLE 2
#define NUMBER 3
#define COMMAND 4
#define STRING 5
#define QUOTE 6
#define FINISHED 10
#define EOL 9
extern char token[80];
extern int tok, token_type;
extern char *prog; /* Содержит анализируемое выражение */
/* Получить лексему */
get_token()
{
register char *temp;
token_type=0; tok=0;
temp=token;
if(*prog=='\0') { /* Конец файла */
*token=0;
tok=FINISHED;
return(token_type=DELIMITER);
}
while(iswhite(*prog)) ++prog; /* пропуск пробелов */
if(*prog=='\r') { /* crtl */
++prog; ++prog;
tok= EOL; *token='\r';
Глава VII -- 7 --
token[1]='\n';token[2]=0;
return (token_type = DELIMITER);
}
if(strchr("+-*^/%=;(),><", *prog)) { /* разделитель */
*temp=*prog;
prog++; /* переход на слкдующую позицию */
temp++;
*temp=0;
return (token_type=DELIMITER);
}
if(*prog=='"') { /* строка в кавычках */
prog++;
while(*prog != '"' && *prog!='\r') *temp++=*prog++;
if(*prog=='\r') serror(1);
prog++;*temp=0;
return(token_type=QUOTE);
}
if(isdigit(*prog)) { /* число */
while(!isdelim(*prog)) *temp++=*prog++;
*temp = '\0';
return(token_type = NUMBER);
}
if(isalpha(*prog)) { /* переменная или команда */
while(!isdelim(*prog)) *temp++=*prog++;
token_type=STRING;
}
*temp = '\0';
/* Просматривается, если строка есть команда или переменная */
if(token_type==STRING) {
tok=look_up(token); /* преобразование во внутренний
формат */
if(!tok) token_type = VARIABLE;
else token_type = COMMAND; /* это команда */
}
return token_type;
}
Посмотрите внимательно на get_token(). Многие программисты
любят помещать пробелы перед выражениями для улучшения
удобочитаемости и наглядности своей программы. Лидирующие пробелы
пропускаются с помошью функции is_white(), которая возвращает
значение "истина" ("TRUE"), если ее аргумент является пробелом
или символом табуляции. Псле пропуска пробелов, сканер,
реализуемый с помощью программы prog, указывает на каждое число,
переменную, команду, символ "возврат каретки" или ноль, если
достигнут конец выражения (программы). Если очередным
анализируемым символом является символ "возврат каретки" (\r), то
возвращается значение "конец строки программы" ("EOL"). Если
Глава VII -- 8 --
очередной символ является оператором, то в качестве значения
глобальной переменной token возвращается соответствующая строка,
при этом в переменную token_type помещается значение DELIMITER. В
противном случае проверяется наличие кавычек. Затем происходит
проверка является ли лексема числом. Если лексема является
символом, то она, следовательно, является или переменной или
командой. Функция look_up() сравнивает внешний формат лексемы с
таблицей лексем, определенной при разработке анализатора и, если
находит соответствующе значение в ней, возвращает внутреннее
представление лексемы (команды). В противном случае лексема
трактуется как переменная. И, наконец, если символ не
удовлетворяет ни одному из условий, приведенных выше, то он
трактуется как символ конца выражения. При этом значение token
обнуляется.
Для лучшего понимания работы get_token() изучите типы,
которые возвращает функция для каждой лексемы:
PRINT A+100-(B*C)/2
--------------------------------
Лексема Тип лексемы.
PRINT COMMAND
A VARIABLE
+ DELIMITER
100 NUMBER
- DELIMITER
( DELIMITER
B VARIABLE
* DELIMITER
C VARIABLE
) DELIMITER
/ DELIMITER
2 NUMBER
null DELIMITER
--------------------------------
Помните, что значение переменной token равно нулю, если
лексема состоит из одного символа.
Некоторые функции интерпретатора нуждаются в повторном
просмотре лексемы. В этом случае лексема должна быть возвращена
во входной поток. Функция putback() решает эту задачу.
/* Возвращает лексему обратно во входной поток */
void putback()
{
char *t;
t = token;
for(; *t; t++) prog--;
}
Глава VII -- 9 --
Глава VII -- 10 --
ПОРЯДОК ПОСТРОЕНИЯ ВЫРАЖЕНИЙ
-----------------------------------------------------------------
Имеется много вариантов анализа и вычисления выражений. Для
использования полного синтаксического анализатора рекурсивного
спуска мы должны представить выражение в виде рекурсивной
структуры данных. Это означает, что выражение определяется в
термах самого себя. Если выражение можно определить с
использованием только символов "+" ,"-" ,"*" ,"/" и скобок, то
все выражения могут быть определены с использованием следующих
правил:
Выражение = > Терм [+Терм][-Терм]
Терм = > Фактор [*Фактор][/Фактор]
Фактор = > Переменная, Число или (Выражение)
Очевидно, что некоторые части в выражении могут
отсутствовать вообще. Квадратные скобки означают именно такие
необязательные элементы выражения. Символ => имеет смысл
"продуцирует".
Фактически, выше перечислены правила, которые обычно
называют правилами вывода выражения. В соответствии с этими
правилами терм можно определить так: "Терм является
произведением или отношением факторов".
Вы вероятно заметили, что приоритет операторов безусловен в
описанных выражениях, то есть вложенные элементы включают
операторы с более высоким приоритетом.
В связи с этим рассмотрим ряд примеров. Выражение
10+5*B
содержит два терма: "10" и "5*B". Они, в свою очередь, состоят из
трех факторов: "10", "5" и "B", содержащих два числа и одну
переменную.
В другом случае выражение
14*(7-C)
содержит два фактора "14" и "(7-C)", которые, в свою очередь,
состоят из числа и выражения в скобках. Выражение в скобках
вычисляется как разность числа и переменной.
Можно преобразовать правила вывода выражений в множество
общих рекурсивных функций, что и является зачастую основной
формой синтаксического анализатора рекурсивного спуска. На каждом
шаге анализатор такого типа выполняет специфические операции в
соответствии с установленными алгебраическими правилами. Работу
этого процесса можно рассмотреть на примере анализа выражения и
выполнения арифметических операций.
Глава VII -- 11 --
Пусть на вход анализатора поступает следующее выражение:
9/3-(100+56)
Анализатор в этом случае будет работать по такой схеме:
1. Берем первый терм: "9/3".
2. Берем каждый фактор и выполняем деление чисел, получаем
результат "3".
3. Берем второй терм: "(100+56)". В этой точке стартует
рекурсивный анализ второго выражения.
4. Берем каждый фактор и суммируем их между собой, получаем
результат 156
5. Берем число, вернувшееся из рекурсии, и вычитаем его из
первого: 3-156. Получаем итоговый результат "-153".
Если вы немного смущены столь сложной схемой работы
анализатора, то уверяем вас, что это не так уж страшно. Гораздо
страшнее оказаться у телевизора, когда транслируют финальный
футбольный матч, не имея с собой достаточного запаса пива.
Поэтому не пугайтесь комплексного подхода.
Вы должны помнить две основные идеи рекурсивного разбора
выражений: (1) приоритет операторов является безусловным в
продукционных правилах и определен в них; (2) этот метод
синтаксического анализа и вычисления выражений очень похож на
тот, который вы сами используете для выполнения таких же
операций.
Глава VII -- 12 --
СИНТАКСИЧЕСКИЙ АНАЛИЗАТОР ВЫРАЖЕНИЙ
-----------------------------------------------------------------
Полный простой синтаксический анализатор рекурсивного спуска
для целых числовых выражений включает в себя ряд функций. Вы
должны взять тексты этих функций и сохранить их в своем файле
(когда тексты анализатора и интерпретатора объединятся получится
довольно большой файл, поэтому рекомендуется откомпилировать
файлы отдельно). Смысл использования глобальных переменных будет
кратко описан, в процессе обсуждения интерпретатора.
Исходный текст простейшего синтаксического анализатора
рекурсивного спуска для целочисленных выражений приведен ниже.
/* Синтаксический анализатор рекурсивного спуска
для целочисленных выражений, который содержит
ряд включаемых переменных
*/
#include "setjmp.h"
#include "math.h"
#include "ctype.h"
#include "stdlib.h"
#define DELIMITER 1
#define VARIABLE 2
#define NUMBER 3
#define COMMAND 4
#define STRING 5
#define QUOTE 6
#define EOL 9
#define FINISHED 10
extern char *prog; /* буфер анализируемого выражения */
extern jmp_buf e_buf; /* буфер среды функции longjmp() */
extern int variables[26]; /* переменные */
extern struct commands {
char command[20];
char tok;
} table[];
extern char token[80]; /* внешнее представление лексемы */
extern char token_type; /* тип лексемы */
extern char tok; /* внутреннее представление лексемы */
void get_exp(),level2(),level3(),level4(),level5();
void level6(),primitive(),arith(),unary();
void serror(), putback();
/* Точка входа в анализатор. */
void get_exp(result)
int *result;
{
get_token();
if(!*token) {
serror(2);
Глава VII -- 13 --
return;
}
level2(result);
putback(); /* возвращает последнюю считаную
лексему обратно во входной поток */
}
/* Сложение или вычитание двух термов */
void level2(result)
int *result;
{
register char op;
int hold;
level3(result);
while((op=*token) == '+' || op == '-') {
get_token();
level3(&hold);
arith(op,result,&hold);
}
}
/* Вычисление произведения или частного двух фвкторов */
void level3(result)
int *result;
{
register char op;
int hold;
level4(result);
while((op = *token) == '+' || op == '/' || op == '%') {
get_token();
level4(&hold);
arith(op,result,&hold);
}
}
/* Обработка степени числа (целочисленной) */
void level4(result)
int *result;
{
int hold;
level5(result);
if(*token== '^') {
get_token();
level4(&hold);
arith('^', result, &hold);
}
}
/* Унарный + или - */
void level5(result)
Глава VII -- 14 --
int *result;
{
register char op;
op = 0;
if((token_type==DELIMITER) && *token=='+' || *token=='-') {
op = *token;
get_token();
}
level6(result);
if(op)
unary(op, result);
}
/* Обработка выражения в круглых скобках */
void level6(result)
int *result;
{
if((*token == '(') && (token_type == DELIMITER)) {
get_token();
level2(result);
if(*token != ')')
serror(1);
get_token();
}
else
primitive(result);
}
/* Определение значения переменной по ее имени */
void primitive(result)
int *result;
{
switch(token_type) {
case VARIABLE:
*result = find_var(token);
get_token();
return;
case NUMBER:
*result = atoi(token);
get_token();
return;
default:
serror(0);
}
}
/* Выполнение специфицированной арифметики */
void arith(o, r, h)
char o;
int *r, *h;
{register int t, ex;
switch(o) {
Глава VII -- 15 --
case '-':
*r = *r-*h;
break;
case '+':
*r = *r+*h;
break;
case '*':
*r = *r * *h;
break;
case '/':
*r = (*r)/(*h);
break;
case '%':
t = (*r)/(*h);
*r = *r-(t*(*h));
break;
case '^':
ex =*r;
if(*h==0) {
*r = 1;
break;
}
for(t=*h-1; t>0; --t) *r = (*r) * ex;
break;
}
}
/* Изменение знака */
void unary(o, r)
char o;
int *r;
{
if(o=='-') *r = -(*r);
}
/* Поиск значения переменной */
int find_var(s)
char *s;
{
if(!isalpha(*s)){
serror(4); /* не переменная */
return 0;
}
return variables[toupper(*token)-'^'];
}
/* выдать сообщение об ошибке */
void serror(error)
int error;
{
static char *e[]= {
"Синтаксическая ошибка",
"Непарные круглые скобки",
"Это не выражениеt",
Глава VII -- 16 --
"Предполагается символ равенства",
"Не переменная",
"Таблица меток переполнена",
"Дублирование меток",
"Неопределенная метка",
"Необходим оператор THEN",
"Необходим оператор TO",
"Уровень вложенности цикла FOR слишком велик",
"NEXT не соответствует FOR",
"Уровень вложенности GOSUB слишком велик",
"RETURN не соответствует GOSUB"
};
printf("&4%s\n",e[error]);
longjmp(e_buf, 1); /* возврат в точку сохранения */
}
/* Чтение лексемы. */
get_token()
{
register char *temp;
token_type=0; tok=0;
temp=token;
if(*prog=='\0') { /* Конец файла */
*token=0;
tok = FINISHED;
return(token_type=DELIMITER);
}
while(iswhite(*prog)) ++prog; /* пропуск пробелов */
if(*prog=='\r') { /* коней строки программы */
++prog; ++prog;
tok = EOL; *token='\r';
token[1]='\n'; token[2]=0;
return (token_type = DELIMITER);
}
if(strchr("+-^/%=;(),><", *prog)){ /* разделитель */
*temp=*prog;
prog++; /* переход на следующую позицию */
temp++;
*temp=0;
return (token_type=DELIMITER);
}
if(*prog=='"') { /* строка кавычек */
prog++;
while(*prog != '"' && *prog!='\r') *temp++=*prog++;
if(*prog=='\r') serror(1);
prog++;*temp=0;
return(token_type=QUOTE);
}
if(isdigit(*prog)) { /* число */
Глава VII -- 17 --
while(!isdelim(*prog)) *temp++=*prog++;
*temp = '\0';
return(token_type = NUMBER);
}
if(isalpha(*prog)) { /* переменная или команда */
while(!isdelim(*prog)) *temp++=*prog++;
token_type=STRING;
}
*temp = '\0';
/* просматривается, если строка - переменная или команда */
if (token_type==STRING) {
tok=look_up(token); /* Преобразование во внутренний формат */
if (!tok) token_type = VARIABLE;
else token_type = COMMAND; /* это команда */
}
return token_type;
}
/* Возврат лексемы во входной поток */
void putback()
{
char *t;
t = token;
for(; *t; t++) prog--;
}
/* Поиск соответствия внутреннего формата для
текущей лексемы в таблице лексем.
*/
look_up(s)
char *s;
{
register int i,j;
char *p;
/* преобразование к нижнему регистру */
p = s;
while(*p){ *p = tolower(*p); p++; }
/* просматривается, если лексема обнаружена в
таблице */
for(i=0; *table[i].command; i++)
if(!strcmp(table[i].command, s)) return table[i].tok;
return 0; /* нераспознанная команда */
}
/* Возвращает "истину", если "c" разделитель */
isdelim(c)
char c;
Глава VII -- 18 --
{
if(strchr(" ;,+-<>/*%^=()",c) || c==9 || c=='\r' || c==0)
return 1;
return 0;
}
/* Возвращает 1, если "с" пробел или табуляция */
iswhite(c)
char c;
{
if(c==' ' || c=='\t') return 1;
else return 0;
}
Анализатор поддерживает следующие операторы: "+", "-", "*",
"/", "%", целочисленный показатель степени (^) и унарный минус.
Все эти операции могут использоваться в сочетании с круглыми
скобками. Вы, вероятно, заметили, что в программе имеются функции
шести уровней, которые работают точно также как функция
primitive(), вращающая значение числа. Помимо этих функций,
реализующих арифметические операции, в состав программы включены
функции arith() и unary(), а также get_token().
При вычислении выражения prog указывает на начало строки,
содержащей выражение, и вызывает get_exp() с адресом переменной,
в которую вы хотите поместить результат.
Обратите особое внимание на функцию serror(), которая
используется для выдачи сообщений об ошибках. При обнаружении
синтаксической ошибки serror() вызывается с номером этой ошибки в
качестве аргумента. Ошибка с кодом 0, которой соответствует
сообщение "синтаксическая ошибка", выдается в том случае, когда
тип ошибки нельзя определить более конкретно. В других случаях
ошибка уточняется. Заметьте, что serror() заканчивается вызовом
функции longjmp().
Функция logjmp() выполняет нелокальный переход, возвращаясь
в точку, определенную с помощью функции setjmp(). Функция
setjmp() включена в исходный текст интерпретатора. Первый
аргумент функции logjmp() является буфером среды, инициированной
с помощью setjmp(). Второй аргумент - это значение, которое
определяется при передаче управления из setjmp() обратно в точку
ее вызова. Как это делается вы, увидите позже.
Использование ljgjmp() упрощает обработку ошибок, так как
программы-анализаторы не должны аварийно завершаться при
обнаружении ошибки. Если ваш компилятор Си не поддерживает
функции setjmp() и logjmp(), то каждая функция при обнаружении
ошибок должна выполнять возврат в точку возникновения ошибки
самостоятельно.
Глава VII -- 19 --
КАК АНАЛИЗАТОР ОБРАБАТЫВАЕТ ПЕРЕМЕННЫЕ
-----------------------------------------------------------------
Как было сказано раньше, интерпретатор языка SMALL BASIC
распознает переменные с именами только от "A" до "Z". Каждой
переменной соответствует элемент массива variables, состоящего из
26 элементов. Этот массив определен в тексте интерпретатора, как
показано ниже, и инициализируется нулевыми значениями.
int variables[26]= { /* 26 переменных пользователя, A-Z */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0
};
Так как именами переменных являются буквы от "A" до "Z", то
индексирование массива variables можно легко осуществить путем
вычитания из соответствующих значений имен переменных в коде
ASCII кода символа 'A'. Функция find_var(), определяющая значение
переменной в зависимости от ее имени, представлена ниже.
/* Определение значения переменной по ее имени*/
int find_var(s)
char *s;
{
if(!isalpha(*s)){
serror(4); /* это не переменная */
return 0;
}
return variables[toupper(*token)-'A'];
}
Эта функция допускает использование более длинных имен, но
только первая буква имени переменной является значащей.
Глава VII -- 20 --
ИНТЕРПРЕТАТОР ЯЗЫКА SMALL BASIC
-----------------------------------------------------------------
Разрабатываемый интерпретатор будет распознавать следующие
ключевые слова языка программирования BASIC:
PRINT
INPUT
IF
THEN
FOR
NEXT
TO
GOTO
GOSUB
RETURN
END
Внутреннее представление этих команд (плюс значение EOL для
конца строки и FINISHED для сигнализации о конце программы)
определяется так:
#define PRINT 1
#define INPUT 2
#define IF 3
#define THEN 4
#define FOR 5
#define NEXT 6
#define TO 7
#define GOTO 8
#define EOL 9
#define FINISHED 10
#define GOSUB 11
#define RETURN 12
#define END 13
Для преобразования внешнего представления лексем во
внутренний формат используется вспомагательная структура table.
struct commands { /* Вспомогательная структура ключевых
слов анализатора */
char command[20];
char tok;
} table[] = { /* Таблица обрабатывает команды, введенные */
"print",PRINT, /* на нижнем регистре */
"input",INPUT,
"if",IF,
"then",THEN,
"goto",GOTO,
"for",FOR,
"next",NEXT,
"to",TO,
"gosub",GOSUB,
"return",RETURN,
Глава VII -- 21 --
"end",END,
"",END /* mark end of table */
};
Обратите внимание на то, что признак конца файла (нулевая
строка) помещен в конец таблицы.
Функция look_up() возвращает внутреннее представление каждой
лексемы или символа '\0', если таковая не обнаружена.
/* Преобразование каждой лексемы из таблицы лексем
во внутреннее представление.
*/
look_up(s)
char *s;
{
register int i,j;
char *p;
/* преобразование в символы нижнего регистра */
p =s;
while(*p){ *p = tolower(*p); p++; }
/* если лексема обнаружена в таблице */
for(i=0; *table[i].command; i++)
if(!strcmp(table[i].command, s)) return table[i].tok;
return 0; /* команда не распознана */
}
Интерпретатор языка SMALL BASIC не поддерживает редактор
текстов, поэтому вы должны создавать программы на языке BASIC,
используя стандартный текстовый редактор.
Каждая программа считывается и выполняется с помощью
интерпретатора. Функция, которая загружает программу, называется
load_program().
/* Загрузка программы */
load_program(p, fname)
char *p;
char *fname;
{
FILE *fp;
int i=0;
if(!(fp=fopen(fname, "rb"))) return 0;
i = 0;
do {
*p = getc(fp);
p++; i++;
} while(!feof(fp) && i<PROG_SIZE);
*(p-2) = '\0'; /* Символ конца загружаемой программы */
fclose(fp);
return 1;
Глава VII -- 22 --
}
Глава VII -- 23 --
ОСНОВНОЙ ЦИКЛ РАБОТЫ АНАЛИЗАТОРА
-----------------------------------------------------------------
Все интерпретаторы выполняют операции путем считывания
лексемы программы и выбора необходимой функции для ее выполнения.
Основной цикл работы для интерпретатора языка SMALL BASIC
выглядит следующим образом.
do {
token_type = get_token();
/* Проверка на соответствие оператору языка */
if (token_type == VARIABLE) {
putback(); /* возврат переменной во входной поток */
assignment(); /* длжен быть оператор присваивания */
}
else /* это команда */
switch(tok) {
case PRINT:
print();
break;
case GOTO:
exec_if();
break;
case FOR:
exec_for();
break;
case NEXT:
next();
break;
case INPUT:
input();
break;
case GOSUB:
gosub();
break;
case RETURN:
greturn();
break;
case END:
exit(0);
}
} while (tok != FINISHED);
Сначала лексема считывается из программы. Для удобства
анализа каждая лексема располагается на отдельной строке. Если
лексема является переменной, то, следуя синтаксису языка, за ней
должен следовать оператор присваивания (SMALL BASIC не
поддерживает старомодную команду LET). В противном случае,
лексема считается командой и с помощью оператора case в
зависимости от значения tok происходит выбор соответствующей
Глава VII -- 24 --
команды. Посмотрите, как работает каждая из них.
Глава VII -- 25 --
КОМАНДА ПРИСВАИВАНИЯ ЗНАЧЕНИЙ.
-----------------------------------------------------------------
В языке BASIC основной формой оператора присваивания
является следующая:
<имя переменной>=<выражение>
Функция assignment() поддерживает этот тип присваивания.
/* Присвоить значение переменной */
assignment()
{
int var, value;
/* получить имя переменной */
get_token();
if(!isalpha(*token)) {
serror(4); /* это не переменная */
return;
}
/* поиск индекса переменной в массиве */
var = toupper(*token)-'A';
/* считать символ равенства*/
get_token();
if(*token!='=') {}
serror(3);
return;
}
/* считать присваемое переменной значение */
get_exp(&value);
/* присвоить значение*/
variables[var] = value;
}
Сначала assignment() считывает лексему из программы. Это -
лексема-переменная, которой должна быть присвоена величина. Если
лексема не является переменной, то сообщается об ошибке. Затем
считывается знак равенства (очередная лексема). Далее вызывается
функция get_exp(), которая вычисляет значение переменной. Функция
получается удивительно простой потому, что анализатор выражений и
get_token делают большую часть рутинной работы.
Глава VII -- 26 --
КОМАНДА PRINT
-----------------------------------------------------------------
Команда PRINT стандарта языка BASIC достаточно мощная и
гибкая, особенно когда применяется ее формат PRINT USING. Хотя
создание функции, которая реализует все возможности этой команды,
выходит за рамки этой главы, разрабатываемая функция является
наиболее важной. Вот основная форма команды PRINT языка SMALL
BASIC:
PRINT <список аргумеентов>
где <список аргументов> представляет собой перечень переменных,
заключенных в кавычки и разделенных запятыми или точкой с
запятой. Функция print(), представленная ниже, является аналогом
команды PRINT языка BASIC. Обратите внимание, что печать
выполняется в теле цикла do-while, условием завершения которого
является вывод на печать всего списка аргументов команды.
/* Простейшая версия оператора PRINT */
void print()
{
int answer;
int len=0, spaces;
char last_delim;
do {
get_token(); /* получить следующий элемент списка */
if (tok == EOL || tok == FINISHED) break;
if (token_tipe == QUOTE) { /* это строка */
printf(token);
len += strlen(token);
get_token();
}
else { /* это выражение */
putback();
get_exp(&answer);
get_token();
len+= printf("%d", answer);
}
last_delim = *token;
if (*token == ';') {
/* Вычисление числа пробелов при переходе к следующей
табуляции */
spaces = 8-(len % 8);
len += spaces; /* смещение на одну табуляцию */
while (spaces) {
printf(" ");
spaces--;
}
}
else if (*token == ','); /* ничего не делать */;
else if (tok != EOL && tok != FINESHED) serror(0);
} while (*token == ';' || *token == ',');
Глава VII -- 27 --
if (tok == EOL || tok == FINESHED) {
if (last_delim != ';' && last_delim != ',')
printf("\n");
else serror(0); /* Отсутствует разделитель */
}
Команда PRINT может быть использована для вывода списка
переменных и строчных констант на экран. Если два элемента
разделены запятой, то их значения выводятся на печать без
пробелов (конкатенируются). Если же два элемента разделены точкой
с запятой, то второй элемент выводится начиная, со следующей
позиции табуляции. Если список элементов заканчивается запятой
или точкой с запятой, то переход на новую строку не выполняется.
Приведенные ниже примеры вызовут печать данных с новой
строки:
PRINT X; Y; "ЭТО СТРОКА"
PRINT 10 / 4
PRINT
Функция print() использует функцию putback() для возврата
лексемы во входной поток. Причиной этого является то, что прежде,
чем начать печать строки, заключенной в скобки, или числового
выражения, функция print() должна проанализировать следующий
элемент списка аргументов. Если следующий элемент является
выражением, то первый терм выражения должен быть помещен обратно
во входной поток, так как в противном случае анализатору не
удастся корректно обработать это выражение.
Глава VII -- 28 --
КОМАНДА INPUT.
-----------------------------------------------------------------
В языке BASIC команда INPUT используется для чтения
информации с клавиатуры и сохранения ее в переменных. Она имеет
два основных формата. Первый формат команды выводит маркер
ожидания ввода данных ('?') и переводит всю программу в ожидание
ввода данных:
INPUT <имя переменной>
Второй формат приводит к отображению на экране строки
символов, после чего ожидается ввод данных:
INPUT "<символьная строка>" <имя переменной>
Функция input (), приведенная ниже, реализует команду языка
BASIC INPUT.
/* Простейшая версия оператора INPUT */
void input()
{
char str[80], var;
int i;
get_token(); /*Анализ наличия символьной строки */
if (token_type == QUOTE) {
printf(token); /*Если строка есть, проверка запятой */
get_token();
if (*token != ',') serror(1);
get_token();
}
else printf("? "); /* В противном случае отображение "? "*/
var = toupper(*token)-'A'; /* Вычисление индекса массива имен */
scanf("%d",&i); /* Чтение входных данных */
variables[var] = i; /* Сохранение их */
}
Работа функции станет ясной и понятной после чтения
комментариев.
Глава VII -- 29 --
КОМАНДА GOTO
-----------------------------------------------------------------
Сейчас вы увидите реализацию одной из самых простых команд,
но в то же время довольно сложной для разработчика. В языке BASIC
основной формой программного управления является команда GOTO. В
стандарте языка BASIC объектом, на который должен указывать GOTO,
является номер строки. Этот традиционный подход сохраняется и в
языке SMALL BASIC. Однако, SMALL BASIC не требуется нумеровать
каждую строку. Номер строки необходим только в том случае, если
на нее ссылается команда GOTO. Основной формат команды GOTO
представлен ниже:
GOTO <номер строки>
Основной сложностью реализации оператора GOTO является то,
что он должен позволять совершать переходы как вниз, так и вверх
по программе. Для удовлетворения этого требования необходим
механизм, который бы просматривал программу, выбирал каждую метку
и помещал ее в таблицу, содержащую как имя метки так, и указатель
ее размещения в программе. Такая таблица определена ниже.
struct label {
char name[LAB_LEN]; /* имя метки */
char *p; /* указатель на место размещения в программе */
};
struct label label_table[NUM_LAB];
Функция, которая просматривает программу и выбирает каждую
метку для размещения ее в таблице, называется scan_labels(). Она
и основные поддерживающие ее функции приведены ниже.
/* Поиск всех меток */
void scan_labels()
{
register int loc;
char *temp;
label_init(); /* обнуление всех меток */
temp = prog; /* запись указателя на начало программы */
/* Если первая лексема файла является меткой */
get_token();
if(token_type==NUMBER) {
strcpy(label_table[0].name,token);
label_table[0].p=prog;
}
find_eol();
do {
get_token();
if(token_type==NUMBER) {
loc=get_next_label(token);
if(loc == -1 || loc == -2) {
(loc == -1) ? serror(5):serror(6);
Глава VII -- 30 --
}
strcpy(label_table[loc].name, token);
label_table[loc].p = prog; /* текущий указатель программы*/
}
/* Если строка не помечена, переход к следующей */
if(tok!=EOL) find_eol();
} while(tok != FINISHED);
prog = temp; /* восстановить начальное значение*/
}
/* Инициализация массива хранения меток.
По соглашению имя нулевой метки указывает, что
данная позиция массива не используется */
void label_init()
{
register int t;
for(t=0;t<NUM_LAB;++t) lable_table[t].name[0]='\0';
}
/* Поиск начала следующей строки */
void find_eol()
{
while (*prog!='\n' && *prog!='\0') ++prog;
if (*prog) prog++;
}
/* Возвращает индекс следующей свободной позиции в массиве
меток. Значение -1 указывает на переполнение массива.
Значение -2 указывает на дублирование имен меток */
get_next_label(s)
char *s;
{
register int t;
for (t=0;t<NUM_LAB;++t) {
if (label_table[t].name[0] == 0) return t;
if(!strcmp(label_table[t].name,s)) return -2; /* дубль */
}
return -1;
}
Функция scan_labels() сообщает о двух типах ошибок. Первый -
это дублирующие метки. В языке BASIC (как и в большинстве других
языков) не может быть двух одинаковых меток. Второй тип ошибки -
это переполнение таблицы меток. Размер таблицы определен с
помощью макроопределения NUM_LAB. Вы можете изменить его в ту или
иную сторону.
Таблица меток строится один раз, и выполнение перехода GOTO
выполняется с помощью функции exec_goto(), приведенной ниже.
/* Реализация оператора GOTO */
void exec_goto()
Глава VII -- 31 --
{
char *loc;
get_token(); /* получить метку перехода */
/* Поиск местоположения метки в программе*/
loc = find_label(token);
if (loc == '\0')
serror(7); /* Метка не найдена */
else prog=loc; /*Программа начала выполнятся не с начала*/
}
/* Поиск местоположения метки. Ноль возвращается, если метка
не найдена; в противном случае возвращается указатель на
место, где расположена метка */
char *find_label(s)
char *s;
{
register int t;
for (t=0;t<NUM_LAB;++t)
if (!strcmp(label_tabel[t].name,s)) return label_tabel[t].p;
return '\0';
}
Вспомогательная функция find_label(), получая метку, ищет ее
в таблице меток и возвращает указатель на нее. Если метка не
обнаружена, возвращает, значение null. Если адрес не null, то он
присваивается переменной prog, что вызывает выполнение той
строки, которая была помечена меткой. (Помните о том, что
указатель prog описывает путь выполнения считаной программы).
Если указатель не обнаружен, то выдается сообщение о том, что
метка неопределена.
Глава VII -- 32 --
ОПЕРАТОР IF
-----------------------------------------------------------------
Интерпретатор SMALL BASIC обрабатывает оператор IF в
соответствии со стандартом языка BASIC. В SMALL BASIC,
отсутствует ELSE и поддерживается только три условия: "больше",
"меньше" или "равно". (Это сделано для того, чтобы вы могли легко
понять работу этого оператора). Основной формат оператора:
IF <выражение><оператор><выражение> THEN <оператор>
Оператор, стоящий после THEN, выполняется только в том
случае, если значение сравнения является истинным. Функция
exec_if(), приведенная ниже, обеспечивает выполнение этой формы
оператора IF.
/* Простейшая реализация оператора IF */
void exec_if()
{
int x , y, cond;
char op;
get_exp(&x); /* получить левое выражение */
get_token(); /* получить оператор */
if (!strchr("=<>", *token)) {
serror(0); /* недопустимый оператор */
return;
}
op=*token;
get_exp(&y); /* получить правое выражение */
/* Определение результата */
cond=0;
switch(op) {
case '=':
if(x==y) cond=1;
break;
case '<':
if(x<y) cond=1;
break;
case '>':
if(x>y) cond=1;
break;
}
if(cond) { /* если истина, то поиск нужного IF */
get_token();
if(tok!=THEN) {
serror(8);
return;
} /* В противном случае программа продолжается со
следующей строки */
}
else find_eol(); /* поиск строки продолжения программы */
}
Функция exec_if() выполняется следующим образом:
Глава VII -- 33 --
1. Вычисляется значение левого выражения.
2. Считывается оператор сравнения.
3. Вычисляется величина правого выраженния.
4. Выполняется операция сравнения.
5. Если условие является истиной, то выполняется поиск THEN;
в противном случае, find_eol выполняет переход на начало
следующей строки.
Глава VII -- 34 --
ЦИКЛ FOR
-----------------------------------------------------------------
Проблема обработки интерпретатором оператора цикла FOR,
входящего в состав оператора BASIC, решена в нашем случае
довольно оригинально. Основной формат оператора цикла FOR
следующий:
FOR<имя управляющей переменной>=<нач. значение>TO<кон. значение>
.
.
.
последовательность операторов
.
.
.
NEXT
Версия оператора FOR, поддерживаемая интерпретатором SMALL
BASIC, реализует цикл с положительным проращением равным 1 на
каждую итерацию цикла. Параметр STEP не поддерживается.
В языке BASIC, точно также как и в Cи, допускается
вложенность цикла FOR. Основной изюминкой, при реализации этого
оператора, с точки зрения программиста-профессионала, является
сохранение информации о каждом вложенном цикле со ссылкой на
внешний цикл. Для реализации этой маленькой, но все-таки
заковырки (трудности всегда радуют настоящих
программистов-мужчин), используется стековая структура, которая
работает следующим образом: Начало цикла, информация о значении
управляющей переменной цикла и ее конечном значении, а также
место расположения цикла в теле программы заносятся в стек.
Каждый раз, при достижении оператора NEXT, из стека извлекается
информация о значении управляющей переменной, затем ее значение
пересчитывается и сравнивается с конечным значением цикла. Если
значение управляющей переменной цикла достигло своего конечного
значения, выполнение цикла прекращается и выполняется оператор
программы следующий за оператором NEXT. В противном случае, в
стек заносится новая информация и выполнение цикла начинается с
его начала. Таким же образом обеспечивается интерпретация и
выполнение вложенных циклов. В стекоподобной структуре вложенных
циклов каждый FOR должен быть закрыт соответствующим оператором
NEXT.
Для реализации оператора цикла FOR стек должен иметь
следующую структуру:
struct for_stack {
int var; /* счетчик цикла */
int target; /* конечное значение */
char *loc;
} fstack[FOR_NEST]; /* стек для цикла FOR/NEXT */
int ftos; /* индекс начала стека FOR */
Глава VII -- 35 --
Значение макроса FOR_NEST ограничивает уровень вложенности
цикла. (По умолчанию допускается 25 уровней вложенности).
Переменная ftos всегда имеет значение индекса начала стека.
Для обработки стека вам понадобятся две функции fpush() и
fpop(), которые приведены ниже.
/* Поместить элемент в стек */
void fpush(i)
struct for_stack i;
{
if (ftos > FOR_NEST)
serror(10);
fstack[ftos]=i;
ftos++;
}
struct for_stack fpop()
{
ftos--;
if (ftos < 0) serror(11);
return(fstack[ftos]);
}
Итак, после того, как вы получили возможность ознакомиться
со всеми необходимыми вспомогательными функцмями, приведем полный
текст функции, реализующей оператры FOR и NEXT.
/* Простейшая реализация оператора цикла FOR */
void exec_for()
{
struct for_stack i;
int value;
get_token(); /* чтение управляющей переменной */
if (!isalfa(*token)) {
serror(4);
return;
}
i.var=toupper(token) - 'A'; /* сохраним индекс */
get_token(); /* чтение символа равенства */
if (*token != '=') {
serror(3);
return;
}
get_exp(&value); /* получить начальное значение */
variables[i.var] = value;
Глава VII -- 36 --
get_token();
if (tok != TO) serror(9); /* чтение и анализ TO */
get_exp(&i.target); /* получить конечное значение */
/* Если цикл выполняется последний раз, поместить информацию
в стек*/
if (value >= variables[i.var]) {
i.loc = prog;
fpush(i);
}
else { /* пропустить весь цикл целиком */
while(tok != NEXT) get_token();
}
}
/* Выполнение оператора NEXT */
void next()
{
struct for_stack i;
i = fpop(); /* чтение информации о цикле */
variables[i.var]++; /* увеличение переменной цикла */
if (variables[i.var] > i.target) return; /* конец */
fpush(i); /* в противном случае запомнить информацию */
prog = i.loc; /* цикл */
}
Как именно работает эта подпрограмма, вполне ясно из
комментариев к ней. Следует заметить, что анализ на возможность
выхода из цикла по оператору GOTO в данном случае не
выполняется. Поэтому использование GOTO в теле цикла может
привести к искажению содержимого стека, что вобщем-то не
желательно.
Решение проблемы реализации цикла FOR с помощью применения
стековых структур является, в общем случае, типичным для
реализации циклических конструкций. Так как интерпретатор SMALL
BASIC не поддерживает другие типы циклических конструкций, то вы
можете самостоятельно разработать подпрограммы реализации циклов
WHILE и DO-WHILE. Как вы сможете увидеть в следующем параграфе,
стековые структуры ипользуются при реализации и других
конструкций программирования, допускающих вложенность.
Глава VII -- 37 --
ОПЕРАТОР GOSUB.
-----------------------------------------------------------------
Хотя BASIC не поддерживает отдельные подпрограммы, но
имеется возможность вызвать отдельные части программы с помощью
оператора GOSUB и вернутся из нее с помощью оператора RETURN.
Основной формой GOSUB-RETURN является следующая:
GOSUB <номер строки>
.
.
.
<номер строки>
.
тело подпрограммы
.
.
RETURN
Вызов подпрограммы требует использования стека. Очевидно,
что это реализовать в данном случае проще, чем для оператора FOR
потому, что каждому оператору RETURN соответствует свой GOSUB.
Описание стека GOSUB показано ниже.
char *gstack[SUB_NEST]; /* стек подпрограмм */
int gtos; /* индекс верхней части стека */
Функция gosub() и вспомогательные программы приведены ниже.
/* Простейшая реализация оператора GOSUB */
void gosub()
{
char *loc;
get_token();
/* поиск метки обращения */
loc = find_label(token);
if(loc=='\0')
serror(7); /* метка не найдена */
else {
gpush(prog); /* запомним место, куда надо вернуться */
prog = loc; /* старт программы с точки loc */
}
}
/* Возврат из подпрограммы */
void greturn()
{
prog = gpop();
}
/* Поместить элемент в стек операторов GOSUB (подпрограмм) */
void gpush(s)
char *s;
Глава VII -- 38 --
{
gtos++;
if(gtos == SUB_NEST) {
serror(12);
return;
}
gstack[gtos]=s;
}
/* Вытолкнуть элемент из стека операторов GOSUB (подпрограмм) */
char *gpop()
{
if(gtos==0) {
serror(13);
return;
}
return(gstack[gtos--]);
}
Команда GOSUB работает следующим образом. Текущее значение
prog помещается в стек GOSUB. Затем prog присваивается адрес
строки, с которой начинается подпрограмма, и начинается
выполнение подпрограммы. Когда встречается RETURN, из стека GOSUB
выталкивается очередное значение и присваивается prog. Далее
выполнение продолжается со следующей строки после оператора
GOSUB. Оператор GOSUB допускает вложенность.
Глава VII -- 39 --
ПОЛНЫЙ ФАЙЛ ИНТЕРПРЕТАТОРА.
-----------------------------------------------------------------
Все тексты SMALL BASIC, исключая тексты синтаксического
анализатора выражений, приведены ниже. Вам необходимо
откомпилировать файлы интерпретатора и анализатора, а затем
отредактировать их.
/* Минимальный BASIC-интепретатор */
#include "stdio.h"
#include "setjmp.h"
#include "math.h"
#include "ctype.h"
#include "stdlib.h"
#define NUM_LAB 100
#define LAB_LEN 10
#define FOR_NEST 25
#define SUB_NEST 25
#define PROG_SIZE 10000
#define DELIMITER 1
#define VARIABLE 2
#define NUMBER 3
#define COMMAND 4
#define STRING 5
#define QUOTE 6
#define PRINT 1
#define INPUT 2
#define IF 3
#define THEN 4
#define FOR 5
#define NEXT 6
#define TO 7
#define GOTO 8
#define EOL 9
#define FINISHED 10
#define GOSUB 11
#define RETURN 12
#define END 13
char *prog; /* содержит выражение для анализа */
jmp_buf e_buf; /* содержит сртеду для longjmp() */
int variables[26]= { /* 26 переменных пользователя A - Z */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0
};
struct commands { /* Просмотр таблицы ключевых слов */
char command[20];
char tok;
Глава VII -- 40 --
} table[] = { /* Команда должна вводится прописными */
"print",PRINT, /* буквами в эту таблицу */
"input",INPUT,
"if",IF,
"then",THEN,
"goto",GOTO,
"for",FOR,
"next",NEXT,
"to",TO,
"gosub",GOSUB,
"return",RETURN,
"end",END,
"",END /* Маркер конца таблицы */
};
char token[80];
char token_type, tok;
struct label {
char name[LAB_LEN];
char *p; /* */
};
struct label label_table[NUM_LAB];
char *find_label(), *gpop();
struct for_stack {
int var; /* переменная счетчика */
int target; /* конечное значение */
char *loc;
} fstack[FOR_NEST]; /* стек цикла FOR/NEXT */
struct for_stack fpop();
char *gstack[SUB_NEST]; /* стек оператора GOSUB */
int ftos; /* индекс начала стека FOR */
int gtos; /* индекс начала стека GOSUB */
void print(), scan_labels(), find_eol(),exec_goto();
void exec_if(), exec_for(), next(), fpush(), input();
void gosub(), greturn(), gpush(), label_init();
main(argc, argv)
int argc;
char *argv[];
{
char in[80];
int answer;
char *p_buf;
char *t;
if(argc!=2) {
printf("Используйте формат: run <filename>\n");
exit(1);
}
Глава VII -- 41 --
/* Выделение памяти для программы */
if (!(p_buf=(char *) malloc(PROG_SIZE))) {
printf("Ошибка при выделении памяти ");
exit(1);
}
/* Загрузка программы для выполнения */
if(!load_program(p_buf,argv[1])) exit(1);
if(setjmp(e_buf)) exit(1); /* инициализация буфера
нелокальных переходов */
prog = p_buf;
scan_labels(); /* поиск метки в программе */
ftos = 0; /* инициализация индеса стека FOR */
gtos = 0; /* инициализация индеса стека GOSUB */
do {
token_type = get_token();
/* проверка на оператор присваивания */
if(token_type==VARIABLE) {
putback(); /* возврат пер. обратно во входной поток */
assignment(); /* должен быть оператор присваивания */
}
else /* это команда */
switch(tok) {
case PRINT:
print();
break;
case GOTO:
exec_if();
break;
case FOR:
exec_for();
break;
case NEXT:
next();
break;
case INPUT:
input();
break;
case GOSUB:
gosub();
break;
case RETURN:
greturn();
break;
case END:
exit(0);
}
} while (tok != FINISHED);
}
/* Загрузка программы. */
load_program(p, fname)
char *p;
Глава VII -- 42 --
char *fname;
{
FILE *fp;
int i=0;
if(!(fp=fopen(fname, "rb"))) return 0;
i = 0;
do {
*p = getc(fp);
p++; i++;
} while(!feof(fp) && i<PROG_SIZE);
*(p-2) = '\0'; /* символ конца программы */
fclose(fp);
return 1;
}
/* Присваивание переменной значения */
assigment()
{
int var, value;
/* Получить имя переменной */
get_token();
if(!isalpha(*token)) {
serror(4); /* это не переменная */
return;
}
/* вычисление индекса переменной */
var = toupper(*token)-'A';
/* получить знак равенства */
get_token();
if(*token!='=') {
serror(3);
return;
}
/* получить значение, присваемое переменной */
get_exp(&value);
/* присвоить это значение */
variables[var] = value;
}
/* Простейшая реализация оператора PRINT */
void print()
{
int answer;
int len=0, spaces;
char last_delim;
do {
get_token(); /* получить следующий элемент списка */
if(tok==EOL || tok==FINISHED) break;
Глава VII -- 43 --
if(token_type==QUOTE) { /* это строка */
print(token);
len += strlen(token);
get_token();
}
else { /* это выражение */
putback();
get_exp(&answer);
get_token();
len +=printf("%d", answer);
}
last_delim = *token;
if(*token==';') {
/* вычисление числа пробелов при переходе к следующей табуляции*/
spaces= 8- (len % 8);
len += spaces; /* включая позицию табуляции */
while(spaces) {
print(" ");
spaces--;
}
}
else if(*token==','); /* ничего не делать */
else if(tok!=EOL && tok!=FINISHED) serror(0);
} while (*token == ';' || *token == ',');
if(tok==EOL || tok==FINISHED) {
if(last_delim != ';' && last_delim != ',') printf("\n");
}
else serror(0); /* отсутствует ',' или ';' */
}
/* Поиск всех меток */
void scan_labels()
{
int addr;
char *temp;
label_init(); /* обнуление всех меток */
temp = prog; /* сохраним указатель на начало программы*/
/* Если первая лексема файла есть метка */
get_token();
if(token_type==NUMBER) {
strcpy(label_table[0].name,token);
label_table[0].p=prog;
}
find_eol();
do {
get_token();
if(token_type==NUMBER) {
addr =get_next_label(token);
if(addr==-1 || addr==-2) {
(addr==-1) ?serror(5):serror(6);
}
Глава VII -- 44 --
strcpy(label_table[addr].name, token);
label_table[addr].p = prog; /* текущий указатель программы */
}
/* если строка не помечена, то поиск следующей */
if(tok!=EOL) find_eol();
} while(tok!=FINISHED);
prog = temp; /* сохраним оригинал */
}
/* Поиск начала следующей строки */
void find_eol()
{
while(*prog!='\n' && *prog!='\0') ++prog;
if(*prog) prog++;
}
/* Возвращает индекс ена следующую свободную позицию
массива меток. -1, если массив переполнен.
-2, если дублирование меток. */
get_next_label(s)
char *s;
{
register int t;
for(t=0;t<NUM_LAB;++t) {
if(label_table[t].name[0]==0) return t;
if(!strcmp(label_table[t].name,s)) return -2; /*дубль*/
}
return -1;
}
/* Поиск строки по известной метке. Значение 0 возвращается,
если метка не найдена; в противном случае возвращается
указатель на помеченную строку программы */
char *find_label(s)
char *s;
{
register int t;
for(t=0; t<NUM_LAB; ++t)
if(!strcmp(label_table[t].name,s)) return label_table[t].p;
return '\0'; /* состояние ошибки */
}
/* Реализация оператора GOTO */
void exec_goto()
{
char *loc;
get_token(); /* получить метку перехода */
Глава VII -- 45 --
/* Поиск местоположения метки */
loc = find_label(token);
if(loc=='\0')
serror(7); /* метка не обнаружена */
else prog=loc; /* старт программы с указанной точки */
}
/* Инициализация массива хранения меток. По договоренности
нулевое значение метки символизирует пустую ячейку массива *
void label_init()
{
register int t;
for(t=0; t<NUM_LAB; ++t) label_table[t].name[0]='\0';
}
/* Реализация оператора IF */
void exec_if()
{
int x , y, cond;
char op;
get_exp(&x); /* получить левое выражение */
get_token(); /* получить оператор */
if(!strchr("=<>", *token)) {
serror(0); /* недопустимый оператор */
return;
}
op=*token;
get_exp(&y); /* получить правое выражение */
/* Определение результата */
cond=0;
switch(op) {
case '=':
if(x==y) cond=1;
break;
case '<':
if(x<y) cond=1;
break;
case '>':
if(x>y) cond=1;
break;
}
if(cond) { /* если значение IF "истина" */
get_token();
if(tok!=THEN) {
serror(8);
return;
} /* иначе, программа выполняется со следующей строки */
}
else find_eol(); /* поиск точки старта программы */
}
/* Реализация цикла FOR */
void exec_for()
Глава VII -- 46 --
{
struct for_stack i;
int value;
get_token(); /* получить управляющую переменную */
if(!isalpha(*token)); {
serror(4);
return;
}
i.var=toupper(*token)-'A'; /* сохранить ее индекс */
get_token(); /* получить знак равенства */
if(*token!='=') {
serror(3);
return;
}
get_exp(&value); /* получить начальное значение */
variables[i.var]=value;
get_token();
if(tok!=TO) serror(9); /* если нее нашли TO */
get_exp(&i.target); /* получить конечное значение */
/* Если цикл выполняется последний раз, поместить
информацию в стек */
if(value>=variables[i.var]) {
i.loc = prog;
fpush(i);
}
else /* пропустить весь цикл */
while(tok!=NEXT) get_token();
}
/* Реализация оператора NEXT */
void next()
{
struct for_stack i;
i = fpop(); /* чтение информации о цикле */
variables[i.var]++; /* увеличение управляющей переменной*/
if(variables[i.var]>i.target) return; /* конец цикла */
fpush(i); /* иначе, сохранить информацию в стеке */
prog = i.loc; /* цикл */
}
/* Поместить информацию в стек FOR */
void fpush(i)
struct for_stack i;
{
if(ftos>FOR_NEST)
serror(10);
fstack[ftos]=i;
ftos++;
}
Глава VII -- 47 --
struct for_stack fpop()
{
ftos--;
if(ftos<0) serror(11);
return(fstack[ftos]);
}
/* Реализация оператора INPUT */
void input()
{
char str[80], var;
int i;
get_token(); /*просматривается если существует строка символов*/
if(token_type==QUOTE) {
printf(token); /* если да, то ее печать и контроль ',' */
get_token();
if(*token!=',') serror(1);
get_token();
}
else printf("? "); /* выдача строки по умолчанию */
var = toupper(*token)-'A'; /* получить индекс имени переменной*
scanf("%d",&i); /* чтение ввода данных */
variables[var] = i; /* сохранение данных */
}
/* Реализация оператора GOSUB */
void gosub()
{
char *loc;
get_token();
/* поиск метки вызова */
loc = find_label(token);
if(loc=='\0')
serror(7); /* метка не определена */
else {
gpush(prog); /* запомним место, куда вернемся */
prog = loc; /* старт программы с указанной точки */
}
}
/* Возврат из подпрограммы, вызвынной по GOSUB */
void greturn()
{
prog = gpop();
}
/* Помещает данные в стек GOSUB */
void gpush(s)
char *s;
{
gtos++;
if(gtos==SUB_NEST) {
Глава VII -- 48 --
serror(12);
return;
}
gstack[gtos]=s;
}
/* */
char *gpop()
{
if(gtos==0) {
serror(13);
return;
}
return(gstack[gtos--]);
}
Глава VII -- 49 --
ПРИМЕР ИСПОЛЬЗОВАНИЯ ИНТЕРПРЕТАТОРА SMALL BASIC
-----------------------------------------------------------------
Теперь вы можете запускать простейшие BASIC-программы.
PRINT "Эта программа демонстрирует все команды."
FOR X = 1 TO 100
PRINT X, X/2; X, X*X
NEXT
GOSUB 300
PRINT "Привет"
INPUT H
IF H<11 THEN GOTO 200
PRINT 12-4/2
PRINT 100
200 A = 100/2
IF A>10 THEN PRINT "Все нормально"
PRINT A
PRINT A+34
INPUT H
PRINT H
INPUT "Это тест",y
PRINT H+Y
END
300 PRINT "Это подпрограмма"
RETURN
PRINT "Эта подпрограмма демонстрирует вложенный GOSUB"
INPUT "Введите число: ", i
GOSUB 100
END
100 FOR T = 1 TO I
X = X+I
GOSUB 150
NEXT
RETURN
150 PRINT X;
RETURN
print "Эта подпрограмма вычисляет объем куба "
input "Введите длину парвой стороны: ", l
input "Введите длину второй стороны: ", w
input "Введите длину третей стороны: ", d
t = l * w * d
print "Обьем равен: ", t
Глава VII -- 50 --
PRINT "Эта программа демонстрирует вложенные циклы"
FOR X = 1 TO 100
FOR Y = 1 TO 10
PRINT X; Y; X*Y
NEXT
NEXT
Глава VII -- 51 --
РАСШИРЕНЕИЕ ВОЗМОЖНОСТЕЙ ИНТЕРПРЕТАТОРА
-----------------------------------------------------------------
Основным пунктом расширения функций интерпретатора и их
модификации является ограниченность его лишь возможностью
интерпретировать язык BASIC. Основная масса технических приемов,
описанных в этой главе, может использоватся при создании
интерпретаторов для различных процедурных языков
программирования. Потому вы, в принципе, можете разработать свой
язык, учитывающий ваш взгляд на программирование и ваш стиль
программирования.
Дополнительные команды и соответствуюшие им основные форматы
лексем описаны в этой главе. Для использования различных
дополнительных типов переменных вы должны использовать массивы
структур для хранения таких переменных; одно из полей этой
структуры должно индицировать тип переменной, а остальные поля
предназначены для хранения значений этих переменных. Для
использования строчных переменных вам необходимо установить
таблицу строк. Простейшим путем реализации строк фиксированной
длины является использование фиксированных участков памяти в 255
байт для размешения строк.
И последняя мысль: типы операторов, которые вы можете
интерпретировать, ограничены лишь вашей фантазией.