Полный код анализатора выражений для интерпретатора Mini С++ приведен в листинге 9.1. Его нужно поместить в файл parser.cpp. Функционирование синтаксического анализатора описано в последующих разделах.
Листинг 9.1. Рекурсивно-нисходящий анализатор для целочисленных выражений
#include <iostream> #include <cstring> #include <cstdlib> #include <cctype> #include "mccommon.h"
using namespace std;
II Таблица поиска ключевых слов.
// Ключевые слова должны быть набраны строчными буквами, struct commands {
char command[20];
token_ireps tok; } com_table[] = (
"if", IF,
"else", ELSE,
"for", FOR.
"do", DO,
"while", WHILE,
"char", CHAR,
"int", INT,
"return", RETURN,
"switch", SWITCH,
"break", BREAK,
"case", CASE,
"cout", COUT,
"cin", CIN,
"", END // помечает конец-таблицы
};
// Эта структура связывает имя библиотечной функции // с указателем на эту функцию, struct intern_func_type {
char *f_name; // имя функции
int (*р)(); // указатель на функцию } intern_func[] = {
"getchar", call^getchar,
"putchar", call_putchar, . "abs", call_abs,
"rand", call_rand,
"", 0 // нуль-завершение перечня
};
// Точка входа в анализатор, void eval_exp(int fcvalue) {
get_token();
if(!*token) {
throw InterpExc(NO_EXP);
}
if(*token == ';') {
value =0; // пустое выражение return;
}
eval_exp0(value);
putbackO; // возвращает последнюю прочитанную лексему // во входной поток
}
// Обрабатывает выражение присваивания.
void eval_expO(inc &value)
{
// temp содержит имя var, получающей присваивание, char temp[MAX_ID_LEN+1];
tok_types temp_tok;
if(token_type == IDENTIFIER) {
if(is_var(token)) { // если переменная, то не присваивание ли? strcpy(temp, token); temp_tok = token_type; get_token();
if(*token ==•=•) { // присваивание get_token();
eval_exp0(value); // получает значение для присваивания assign_var(temp, value); // присваивает значение return;
}
else { //не присваивание putbackO; // возвращает исходную лексему во входной поток strcpy(token, temp);
token_type = temp_tok;
>
}
eval_expl(value);
}
// Обрабатывает операции отношения, void eval_expl(int &value)
int partial_value; char op;
char relopsf] = {
LT, LE, GT, GE, TEQ, NE, 0
>;
eval_exp2 (value) ; op = *token;
if(strchr(reldps, op)) { get_token();
eval_exp2(partial_value);
switch(op) { // выполняет операцию отношения case LT:
value = value < partial_value;
break; case LE:
value = value <= partial_value;
break; case GT:
value = value > parcial_value;
break; case GE:
value = value >= partial_value; break; case EQ:
value = value == partial_value; break;
}
case NE:
value = value != partial_value; break;
J
J
}
// Складывает или вычитает два терма.
void eval_exp2(int &value)
{
char op;
int partial_value; char okops[] = {
'(', INC, DEC, •+', 0
};
eval_exp3(value);
while((op = *token) == '+' || op == '-') { get_token();
if(token_type == DELIMITER && !strchr(okops, * token)) throw InterpExc(SYNTAX);
eval_exp3(partial_value);
switch(op) { // добавляет или вычитает case
value = value - partial_value; break; case '+':
value = value + partial_value; break;
}
}
}
// Умножает или делит два фактора.
void eval_exp3(int fcvalue) {
char op;
int partial_value, t; char okopsf] = {
' (', INC, DEC, '-' , 4-', 0
};
eval_exp4(value);
while((op = * token) == '*' || op == '/' || op == '%') { get_token();
if(token_type == DELIMITER && !strchr(okops, * token)) throw InterpExc(SYNTAX);
eval_exp4(partial_value);
switch(op) { // умножение, деление нацело или остаток от деления // нацело
case '*':
value = value * partial_value;
break; case '/':
if(partial_value == 0)
throw InterpExc(DIV_BY_ZERO);
value = (value) / partial_value;
break; case 1 %':
t = (value) / partial_value;
value = value - (t * partial_value);
break;
}
}
}
// Унарные +, -, ++, или —.
void eval_exp4(int fcvalue) {
char op; ,
char temp;
op = '\0';
if(*token == •+• || *token == '-' || ¦token == INC || *token == DEC)
{
temp = * token; op = *token; get_token(); if(temp == INC)
assign_var(token, find_var(token) +1); if(temp == DEC)
ass ign_var(token, find_var(token) -1);
}
eval_exp5(value);
if(op == '-') value = -(value);
}
// Обрабатывает выражение со скобками.
void eval_exp5(int fcvalue)
{
if((*token == ' (')) { get_token();
eval_expO(value); // получает подвыражение
if(*token != ')')
throw InterpExc(PAREN_EXPECTED); get_token();
}
else
acorn(value);
}
// Находит значение числа, переменной или функции.
void atom (int fcvalue) {
int i;
char temp[MAX_ID_LEN+1];
i
swi tch(token_type) { case IDENTIFIER:
i = internal_func(token); if(i != -1) {
// Вызывает функцию стандартной библиотеки ("standard library").
value = (*intern_func[i].p)(); } *
else if(find_func(token)) {
// Вызывает функцию, созданную программистом.
call();
value = ret_value;
}
else {
value = find_var(token); // получает значение переменной strcpy(temp, token); // сохраняет имя переменной
// Проверяет операции ++ или —. get_token();
if(*token == INC || *token == DEC) { if(*token == INC)
assign_var(temp, find_var(temp)+1); else
assign_var(temp, find_var(temp)-1); } else putback();
}
get_token(); return;
case NUMBER: // числовая константа value = atoi(token); get_token();
return;
case DELIMITER: // проверяет, не символьная ли константа
if(*token == ' \" ') { value = *prog; prog++;
if(*prog! = "\'1)
throw InterpExc(QUOTE_EXPECTED); prog++; get_token();
return ;
}
if(*token==')') return; // обрабатывает пустое выражение else throw InterpExc(SYNTAX); // иначе синтаксическая ошибка default:
throw InterpExc(SYNTAX); // синтаксическая ошибка
}
}
// Отображает сообщение об ошибке, void sntx_err(error_msg error) {
char *p, *temp; int linecount = 0;
static char *e[]= { "Syntax error", "No expression present", "Not a variable", "Duplicate variable name", "Duplicate function name", "Semicolon expected", "Unbalanced braces", "Function undefined", "Type specifier expected", "Return without call", "Parentheses expected", "While expected", "Closing quote expected", "Division by zero",
"{ expected (control statements must use blocks)".
"Colon expected"
// Выводит ошибку и номер строки, cout « "\n" « е[error]; р - p_buf;
while(р != prog) { // находит номер строки с ошибкой P++;
if(*р == '\г') { linecount++;
}
}
cout « " in line " « linecount « endl; temp = p;
while(p > p_buf && *p != '\n') p—;
// Отображает ошибочную строку, while(p <= temp) cout « *p++;
cout « endl;
>
// Получает лексему. tok_types get_token() {
char *temp;
token_type = UNDEFTT; tok = UNDEFTOK;
temp = token; *temp = '\0';
// Пропускает пробелы.
while(isspace(*prog) && *prog) ++prog;
// Пропускает переход на новую строку, while(*prog == '\r') {
};
++prog; ++prog;
// Снова пропускает пробелы.
while(isspace(*prog) && *prog) ++prog;
// Проверяет, не конец ли программы. if(*prog == 'NO') {
¦token = ' \0';
tok = END;
return (token_type = DELIMITER) ;
// Проверяет ограничители блока, if(strchr("", *prog)) {
¦temp = ¦prog;
temp++;
¦temp = '\0';
prog++;
return (token_type = BLOCK) ;
}
// Ищет комментарии, if(*prog == •/')
if(Mprog+l) =»'*') { // знак комментария /* prog += 2;
do { // находит конец комментария
while(*prog != •*') prog++; . prog++;
} while (¦prog != "/'); prog++;
П return (token_type = DELIMITER);
} else if(*(prog+l) == '/') { // знак комментария // prog += 2;
// Находит конец комментария.
while(^prog != '\r' && ^prog != '\0') prog++;
if(*prog == '\r1) prog +=2;
return (token_type = DELIMITER);
II Проверяет двойные знаки операций, if(strchr("!<>=+-", *prog)) { switch(*prog) { case 1=1:
. if(*(prog+1) == '=') { prog++; prog++; ¦temp = EQ;
temp++; *temp = EQ; temp++; ¦temp = '\0';
}
break; case •!•:
if (Mprog+1) == ' = ') { prog++; prog++; ¦temp = NE;
temp++; ¦temp = NE; temp++; ¦temp = '\0';
}
break; case •<':
if(*(prog+1) == •=') { prog++; prog++;
¦temp = LE; temp++; ¦temp = LE;
}
else if(¦(prog+1) == •<•) { prog++; prog++;
¦temp = LS; temp++; ¦temp = LSr
}
else { prog++; ¦temp = LT;
}
temp++; ¦temp = '\0'; break; case '>':
if(¦(prog+1) == '=') { prog++; prog++;
¦temp = GE; temp++; *temp = GE; } else if(*(prog+1) == ">') { prog++; prog++;
*temp = RS; temp++; *temp = RS;
}
else { prog++; *temp = GT;
}
temp++; *terop = '\0'; break; case '+':
if(*(prog+l) == '+') { prog++; prog++;
*temp = INC; terap++; *temp = INC;
terap++;
*temp = '\0';
}
break; case * - ':
if(*(prog+1) == '-') { prog++; prog++;
¦temp = DEC; temp++; ¦temp = DEC;
temp++;
¦temp = '\0*;
}
break;
}
if(¦token) return(token_type = DELIMITER);
}
// Проверяет другие ограничители, if(strchr("+-*Л/%=;:(),¦", ¦prog)) {
¦temp = ¦prog;
prog++;
temp++;
¦temp = '\0';
return (token_type = DELIMITER) ;
// Читает строку в кавычках, if(*prog == "") { prog++;
while(*prog != '"' && *prog != '\r' && *prog) { // Ищет escape-последовательность \n. if(*prog == 'W') { if(*(prog+l) == 'n') { prog++;
*temp++ = ' \n';
}
}
else if((temp - token) < MAX_T_LEN) *temp++ = *prog;
prog++;
}
if(*prog == '\r" || *prog == 0)
throw InterpExc(SYNTAX); prog++; *temp = ' \0'; return (token_type = STRING);
}
// Читает целое число, if(isdigit(*prog)) {
while (! isdel im (*prog)) {
if ((temp - token) < MAX_ID_LEN)
*temp++ = *prog; prog++;
}
*temp = *\0';
return (token_type = NUMBER);
}
// Читает идентификатор или ключевое слово, i f(isalpha(*prog)) {
while(!isdelim(*prog)) {
}
if((temp - token) < MAX_ID_LEN)
*temp++ = *prog; prog++;
}
token_type = TEMP;
}
*temp = '\0';
// Определяет, является ли лексема ключевым словом
// или идентификатором.
if(token_type == TEMP) {
tok = look_up(token); // преобразует во внутреннюю форму if(tok) token_type = KEYWORD; // ключевое слово else token_type = IDENTIFIER;
}
// Проверяет неидентифицированный символ в файле, if(token_type == UNDEFTT) throw InterpExc(SYNTAX);
return token_type;
}
// Возвращает лексему во входной поток.
void putback()
{
char *t; t = token;
for(; *t; t++) prog—;
}
// Ищет внутреннее представление лексемы //в таблице лексем. token_ireps look_up(char *s) {
int i; char *p;
// Преобразует в нижний регистр, р = s;
while(*p) { *р = tolower(*p); р++; }
// Проверяет, есть ли лексема в таблице. for(i=0; *cam_table[i].command; i++) { if(!strcmp(com_table[i].command, s)) return com_table[i].tok;
}
return UNDEFTOK; // неизвестная команда
}
// Возвращает индекс внутренней библиотечной функции // или -1, если она не найдена, int internal_func(char *s) {
int i;
for(i=0; intern_func[i].f_name[0]; i++) {
if(!strcmp(intern_func[i].f_name, s)) return i;
}
return -1;
}
// Возвращает true, если с — ограничитель.
bool isdelim(char с)
{
if(strchr(" !:;,+-<>'/*%Л=()с) || с == 9 ||
с == '\r' II с == 0) return true; return false;
}
Анализатор использует следующие глобальные переменные и перечислимые типы (они объявлены в заголовочном файле mccommon.h, который будет приведен далее в этой главе).
const int MAX_T_LEN = 128; // максимальная длина лексемы
const int MAX_ID_LEN = 31; // максимальная длина идентификатора
// Перечислимый тип для типов лексем.
enum tok_types { UNDEFTT, DELIMITER, IDENTIFIER,
NUMBER, KEYWORD. TEMP. STRING, BLOCK };
// Перечислимый тип внутреннего представления лексем, enum token_ireps { UNDEFTOK, ARG, CHAR, INT, SWITCH,
CASE, IF, ELSE, FOR, DO, WHILE, BREAK,
RETURN, COUT, CIN, END };
// Перечислимый тип для двухсимвольных операций, таких как <=. enum double_Ops { LT=1, LE, GT, GE, EQ, NE, LS, RS, INC, DEC };
// Константы, используемые для генерации
// исключения при наличии синтаксических ошибок.
//
// Замечание: SYNTAX — общее сообщение об ошибке, используемое, когда // нет более подходящего, enum error_msg
{ SYNTAX, NO_EXP, NOT_VAR, DUP_VAR, DUP_FUNC,
SEMI_EXPECTED, UNBAL_BRACES, FUNC_UNDEF,
TYPE_EXPECTED, RET_NOCALL, PAREN_EXPECTED,
WHILE_EXPECTED, QUOTE_EXPECTED, DIV_BY_ZERO,
BRACE_EXPECTED, COLON_EXPECTED };
extern char *prog; // текущая позиция в исходном коде extern char *p_buf; // указывает на начало буфера программы
extern char token[MAX_T_LEN+1]; // строковая версия лексемы extern tok_types token_type; // содержит тип лексемы extern token_ireps tok; // внутреннее представление лексемы
extern int ret_value; // значение, возвращаемое функцией
// Класс-исключение для Mini С++, class InterpExc {
error_msg err; public:
InterpExc(error_msg e) { err = e; } error_msg get_err() { return err; }
};
В переменной prog указывается текущая позиция в исходном коде, на которой находится выполняющаяся программа в данный момент. Таким образом, в ней содержится адрес, начиная с которого будет читаться интерпретатором следующий фрагмент программы. Указатель p_buf не меняется интерпретатором и всегда указывает на начало интерпретируемой программы Текущая лексема (token) хранится в переменной token (лексема — это неделимая часть кода программы). Тип лексемы содержится в переменной token_type. Переменная tok хранит внутренний формат лексемы, если она представляет собой ключевое слово.
В перечислимом типе (enumeration) tok_types объявлены типы лексем, распознаваемые интерпретатором Mini С++. Перечислимый тип token_ireps описывает внутренний формат лексем, представляющих собой ключевые слова. Константы, обозначающие двухсимвольные знаки операций, такие как <=, заданы в перечислимом типе doubie_ops. Различные коды ошибок перечислены в типе error_msg. Наконец, класс-исключение InterpExc предназначен для сообщения об ошибках.
|
