Лексемы
Перед тем, как построить синтаксический анализатор, разбирающий значения выражений, вы должны иметь несколько вариантов разбиения строки, содержащей выражение, на составляющие части. Например, выражение
А*В-(W+10)
содержит компоненты "А", "*", "В", "-", "(", "W", "+", "10" и
")". Каждый компонент представляет собой неделимый элемент
выражения. Такой компонент или независимая часть выражения
называется лексемой. Функция, разбивающая выражение на составные
части, должна решать четыре задачи: (1) игнорировать пробелы и
символы табуляции, (2) извлекать каждую лексему из текста, (3)
если необходимо, преобразовывать лексему во внутренний формат,
(4) определять тип лексемы.
Каждая лексема имеет два формата: внешний и внутренний. Внешний формат - это символьная строка, с помощью которой вы пишите программы на каком-либо языке программирования. Например, "PRINT" - это внешняя форма команды PRINT языка BASIC. Можно построить интерпретатор из расчета, что каждая лексема используется во внешнем формате, но это типичное решение проблемы программистом-непрофессионалом, который лишь два часа назад оторвался от материной юбки и час назад увидел настоящий компьютер. Настоящие мужчины ориентируются на внутренний формат лексемы, который является просто числом, и разрабатывают интерпретаторы исходя из этой профессиональной точки зрения на проблему. Поясним этот подход. Например, команда PRINT может иметь порядковый внутренний номер 1, команда INPUT - 2 и т.д. Преимущество внутреннего формата заключается в том, что программы, обрабатывающие числа, более быстродействующие, чем программы, обрабатывающие строки. Для реализации такого подхода необходима функция, которая берет из входного потока данных очередную лексему и преобразует ее из внешнего формата во внутренний. Помните, что не все лексемы имеют разные форматы. Например, операторы не подлежат преобразованию потому, что они могут трактоваться как символы или числа в своих внешних форматах.
Очень важно знать, какой тип лексемы возвращен. Например, анализатору выражений необходимо знать, является ли следующая лексема числом, оператором или переменной. Значение типа лексемы для процесса анализа в целом станет очевидным, когда вы приступите непосредственно к разработке интерпретатора.
Функция, которая возвращает следующую лексему в выражении, называется get_token( ). Она работает из расчета того, что в языке SMALL BASIC, программа хранится как одна строка, ограниченная в конце символом завершения строки (\0). Функция 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=='\0') /* Конец файла */
*token=0;
tok=FINISHED;
return(token_type=DELIMITER);
while(iswhite(*prog)) ++prog; /* пропуск пробелов */
if(*prog=='\r') /* crtl */
++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)) /* число */
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"). Если
очередной символ является оператором, то в качестве значения
глобальной переменной 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--;
