Вы когда-нибудь хотели создать свой язык программирования? Большинство программистов призывают к поиску идеи создания, управления и модификации своих языков программирования. Однако, лишь немногие программисты могут легко и непринужденно создать язык программирования. Создание полного компилятора является многообязывающей задачей, но гораздо проще создать интерпретатор языка. Методы, используемые для создания итерпретаторов языка, изучаются редко или изучаются довольно абстрактно. В этой главе на практических примерах вы будете изучать секреты интерпретации языка и грамматического разбора выражений.
Интерпретаторы важны по трем очень важным причинам. Во-первых, они могут обеспечивать удобную интерактивную среду (как доказательство - интерпретатор стандартного языка BASIC, которыми снабжаются большинство персональных компьтеров). Многие пользователи-новички находят, что интерактивная среда более удобна, чем компилятор. Во-вторых, интерпретаторы языка обеспечивают превосходные интерактивные отладочные возможности. Даже ветераны-программисты при отладке трудных программ прибегают к помощи интерпретатора языка, потому что он позволяет динамично устанавливать значения переменных и условий. В-третьих, большинство языков запросов к базе данных работают в режиме интерпретации.
В этой главе будет разработан интерпретатор для подмножества языка BASIC, который еще называют "SMALL BASIC". BASIC выбран вместо Cи, потому что BASIC легче интерпретируется, чем Cи или другой структурный язык. Интерпретатор для структурного языка, такого как Cи более труден, чем для BASIC из-за автономных функций с локальными переменными, которые обеспечивают интерпретатору многозначность. Принципы, используемые в интерпретаторе BASIC, применимы и для других языков, и вы можете использовать написанные программы в качестве отправной точки. Прежде, чем начать работу, необходимо изучить сущность языковой интерпретации, особенно перед тем, как браться за интерпетацию такого сложного языка, как Cи. Если вы не знаете BASIC, не беспокойтесь, команды используемые в SMALL BASIC очень легкие для понимания.
Мы начинаем с сердца любого интерпретатора: синтаксического анализатора выражений.
Синтаксический разбор выраженийНаиболее важной частью интерпретатора языка является синтактический анализатор выражений, который преобразует числовые выражения, такие как (10-X)/23, в такую форму, чтобы компьютер мог понять ее и вычислить. В книге по языку Cи: The Complete Reference (Osborne/McGraw-uill, 1987) вступительная глава посвящена синтаксическому анализу выражений. Подобного же рода синтаксический анализ, основанный на принципах, изложенных в вышеупомянутой книге, (правда, с небольшими изменениями) будет использоваться для построения интерпретатора SMALL BASIC в данной главе нашей книги. (Так как эта глава содержит только краткие сведения о синтаксическом анализе выражений, то для более детального изучения этой проблемы советуем вам обратиться к источнику: The Compelete Reference.
Синтаксический анализ выражений является довольно сложной задачей, однако в некоторых случаях она облегчается тем, что в процессе синтаксического анализа используются довольно строгие правила алгебры. Синтаксический анализатор, описанный в этой главе, в общем может быть классифицирован как синтаксический анализатор рекурсивного спуска.
Перед тем, как приступить к детальной разработке синтаксического анализатора, вы должны иметь представление о выражениях. Поэтому наш следующий параграф посвящен именно этому вопросу.
ВыраженияХотя выражения могут быть составлены в принципе из любых типов данных, в этой главе мы будем иметь дело только с числовыми выражениями. Будем считать, что для наших целей числовые выражения могут строится из следующих элементов:
- числа
- операторы + - / * ^ % = () <> ; ,
- скобки
- переменные
Символ '^' означает экспоненту, а символ '=' используется как оператор присваивания, а также как знак равенства в операциях сравнения. Элементы выражения можно комбинировать согласно правилам алгебры.
Вот некоторые примеры выражений:
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" будут трактоваться как одна и та же переменная. Условимся, что все числа являются целыми, хотя вы без особого труда можете написать
программы для манипулирования другими типами чисел. Хотя
символьные переменные в нашей версии языка и не поддерживаются,
будем считать, что возможен вывод ограниченных символьных
констант на экран в виде различных сообщений.
Итак, будем строить синтаксический анализатор исходя из перечисленных выше допущений. Теперь давайте рассмотрим такое базовое понятие теории синтаксического анализа как лексема.
ЛексемыПеред тем, как построить синтаксический анализатор, разбирающий значения выражений, вы должны иметь несколько вариантов разбиения строки, содержащей выражение, на составляющие части. Например, выражение
А*В-(W+10)
содержит компоненты "А", "*", "В", "-", "(", "W", "+", "10" и
")". Каждый компонент представляет собой неделимый элемент
выражения. Такой компонент или независимая часть выражения
называется лексемой. Функция, разбивающая выражение на составные
части, должна решать четыре задачи: (1) игнорировать пробелы и
символы табуляции, (2) извлекать каждую лексему из текста, (3)
если необходимо, преобразовывать лексему во внутренний формат,
(4) определять тип лексемы.
Каждая лексема имеет два формата: внешний и внутренний. Внешний формат - это символьная строка, с помощью которой вы пишите программы на каком-либо языке программирования. Например, "PRINT" - это внешняя форма команды PRINT языка BASIC. Можно построить интерпретатор из расчета, что каждая лексема используется во внешнем формате, но это типичное решение проблемы программистом-непрофессионалом, который лишь два часа назад оторвался от материной юбки и час назад увидел настоящий компьютер. Настоящие мужчины ориентируются на внутренний формат лексемы, который является просто числом, и разрабатывают интерпретаторы исходя из этой профессиональной точки зрения на проблему. Поясним этот подход. Например, команда PRINT может иметь порядковый внутренний номер 1, команда INPUT - 2 и т.д. Преимущество внутреннего формата заключается в том, что программы, обрабатывающие числа, более быстродействующие, чем программы, обрабатывающие строки. Для реализации такого подхода необходима функция, которая берет из входного потока данных очередную лексему и преобразует ее из внешнего формата во внутренний. Помните, что не все лексемы имеют разные форматы. Например, операторы не подлежат преобразованию потому, что они могут трактоваться как символы или числа в своих внешних форматах.
Очень важно знать, какой тип лексемы возвращен. Например, анализатору выражений необходимо знать, является ли следующая лексема числом, оператором или переменной. Значение типа лексемы для процесса анализа в целом станет очевидным, когда вы приступите непосредственно к разработке интерпретатора.
Функция, которая возвращает следующую лексему в выражении, называется get_token( ). Она работает из расчета того, что в языке SMALL BASIC, программа хранится как одна строка, ограниченная в конце символом завершения строки ( ). Функция get_token() сканирует текст программы, анализируя по одному символу, при этом глобальный указатель анализатора принимает
значение адреса очередной считаной лексемы. В версии 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==' ') /* Конец файла */
*token=0;
tok=FINISHED;
return(token_type=DELIMITER);
while(iswhite(*prog)) ++prog; /* пропуск пробелов */
if(*prog==' ') /* crtl */
++prog; ++prog;
tok= EOL; *token=' ';
token[1]=' ';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!=' ') *temp++=*prog++;
if(*prog==' ') serror(1);
prog++;*temp=0;
return(token_type=QUOTE);
if(isdigit(*prog)) /* число */
while(!isdelim(*prog)) *temp++=*prog++;
*temp = ' ';
return(token_type = NUMBER);
if(isalpha(*prog)) /* переменная или команда */
while(!isdelim(*prog)) *temp++=*prog++;
token_type=STRING;
*temp = ' ';
/* Просматривается, если строка есть команда или переменная */
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, указывает на каждое число, переменную, команду, символ "возврат каретки" или ноль, если достигнут конец выражения (программы). Если очередным анализируемым символом является символ "возврат каретки" ( ), то возвращается значение "конец строки программы" ("EOL"). Если
очередной символ является оператором, то в качестве значения
глобальной переменной 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--;
Порядок построения выражений
Имеется много вариантов анализа и вычисления выражений. Для использования полного синтаксического анализатора рекурсивного спуска мы должны представить выражение в виде рекурсивной структуры данных. Это означает, что выражение определяется в термах самого себя. Если выражение можно определить с использованием только символов "+" ,"-" ,"*" ,"/" и скобок, то все выражения могут быть определены с использованием следующих правил:
Выражение = > Терм [+Терм][-Терм]
Терм = > Фактор [*Фактор][/Фактор]
Фактор = > Переменная, Число или (Выражение)
Очевидно, что некоторые части в выражении могут отсутствовать вообще. Квадратные скобки означают именно такие необязательные элементы выражения. Символ => имеет смысл "продуцирует".
Фактически, выше перечислены правила, которые обычно называют правилами вывода выражения. В соответствии с этими правилами терм можно определить так: "Терм является произведением или отношением факторов".
Вы вероятно заметили, что приоритет операторов безусловен в описанных выражениях, то есть вложенные элементы включают операторы с более высоким приоритетом.
В связи с этим рассмотрим ряд примеров. Выражение
10+5*B
содержит два терма: "10" и "5*B". Они, в свою очередь, состоят из
трех факторов: "10", "5" и "B", содержащих два числа и одну
переменную.
В другом случае выражение
14*(7-C)
содержит два фактора "14" и "(7-C)", которые, в свою очередь,
состоят из числа и выражения в скобках. Выражение в скобках
вычисляется как разность числа и переменной.
Можно преобразовать правила вывода выражений в множество общих рекурсивных функций, что и является зачастую основной формой синтаксического анализатора рекурсивного спуска. На каждом шаге анализатор такого типа выполняет специфические операции в соответствии с установленными алгебраическими правилами. Работу этого процесса можно рассмотреть на примере анализа выражения и выполнения арифметических операций.
Пусть на вход анализатора поступает следующее выражение:
9/3-(100+56)
Анализатор в этом случае будет работать по такой схеме:
1. Берем первый терм: "9/3".
2. Берем каждый фактор и выполняем деление чисел, получаем результат "3".
3. Берем второй терм: "(100+56)". В этой точке стартует рекурсивный анализ второго выражения.
4. Берем каждый фактор и суммируем их между собой, получаем результат 156
5. Берем число, вернувшееся из рекурсии, и вычитаем его из первого: 3-156. Получаем итоговый результат "-153".
Если вы немного смущены столь сложной схемой работы анализатора, то уверяем вас, что это не так уж страшно. Гораздо страшнее оказаться у телевизора, когда транслируют финальный футбольный матч, не имея с собой достаточного запаса пива. Поэтому не пугайтесь комплексного подхода.
Вы должны помнить две основные идеи рекурсивного разбора выражений: (1) приоритет операторов является безусловным в продукционных правилах и определен в них; (2) этот метод синтаксического анализа и вычисления выражений очень похож на тот, который вы сами используете для выполнения таких же операций.
Синтаксический анализатор выраженийПолный простой синтаксический анализатор рекурсивного спуска для целых числовых выражений включает в себя ряд функций. Вы должны взять тексты этих функций и сохранить их в своем файле (когда тексты анализатора и интерпретатора объединятся получится довольно большой файл, поэтому рекомендуется откомпилировать файлы отдельно). Смысл использования глобальных переменных будет кратко описан, в процессе обсуждения интерпретатора.
Исходный текст простейшего синтаксического анализатора рекурсивного спуска для целочисленных выражений приведен ниже.
/* Синтаксический анализатор рекурсивного спуска
для целочисленных выражений, который содержит
ряд включаемых переменных
*/
#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);
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)
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)
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",
"Предполагается символ равенства",
"Не переменная",
"Таблица меток переполнена",
"Дублирование меток",
"Неопределенная метка",
"Необходим оператор THEN",
"Необходим оператор TO",
"Уровень вложенности цикла FOR слишком велик",
"NEXT не соответствует FOR",
"Уровень вложенности GOSUB слишком велик",
"RETURN не соответствует GOSUB"
;
printf("&4%s ",e[error]);
longjmp(e_buf, 1); /* возврат в точку сохранения */
/* Чтение лексемы. */
get_token()
register char *temp;
token_type=0; tok=0;
temp=token;
if(*prog==' ') /* Конец файла */
*token=0;
tok = FINISHED;
return(token_type=DELIMITER);
while(iswhite(*prog)) ++prog; /* пропуск пробелов */
if(*prog==' ') /* коней строки программы */
++prog; ++prog;
tok = EOL; *token=' ';
token[1]=' '; 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!=' ') *temp++=*prog++;
if(*prog==' ') serror(1);
prog++;*temp=0;
return(token_type=QUOTE);
if(isdigit(*prog)) /* число */
while(!isdelim(*prog)) *temp++=*prog++;
*temp = ' ';
return(token_type = NUMBER);
if(isalpha(*prog)) /* переменная или команда */
while(!isdelim(*prog)) *temp++=*prog++;
token_type=STRING;
*temp = ' ';
/* просматривается, если строка - переменная или команда */
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;
if(strchr(" ;,+-<>/*%^=()",c) || c==9 || c==' ' || c==0)
return 1;
return 0;
/* Возвращает 1, если "с" пробел или табуляция */
iswhite(c)
char c;
if(c==' ' || c==' ') 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(), то каждая функция при обнаружении ошибок должна выполнять возврат в точку возникновения ошибки самостоятельно.
Как анализатор обрабатывает переменныеКак было сказано раньше, интерпретатор языка 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'];
Эта функция допускает использование более длинных имен, но только первая буква имени переменной является значащей.
Интерпретатор языка Small BasicРазрабатываемый интерпретатор будет распознавать следующие ключевые слова языка программирования BASIC:
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,
"end",END,
"",END /* mark end of table */
;
Обратите внимание на то, что признак конца файла (нулевая строка) помещен в конец таблицы.
Функция look_up() возвращает внутреннее представление каждой лексемы или символа ' ', если таковая не обнаружена.
/* Преобразование каждой лексемы из таблицы лексем
во внутреннее представление.
*/
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
*(p-2) = ' '; /* Символ конца загружаемой программы */ fclose(fp);
return 1;
Основной цикл работы анализатораВсе интерпретаторы выполняют операции путем считывания лексемы программы и выбора необходимой функции для ее выполнения. Основной цикл работы для интерпретатора языка 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 происходит выбор соответствующей
команды. Посмотрите, как работает каждая из них.
Команда присваивания значенийВ языке 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;