3.5 Разработка лексического анализатора для модельного языка Описание модельного паскалеподобного языка (м-языка):
P program D1; B
D1 var D {;D}
D I {,I}: [ int | bool ]
B begin S {;S} end
S I := E | if E then S else S | while E do S | B | read (I) | write (E)
E E1 [ = | < | > | != ] E1
E1 T {[ + | - | or ] T}
T F {[ | / | and ] F}
F I | N | L | not F | (E)
L true | false
I C | IC | IR
N R | NR
C a | b | ... | z | A | B | ... |Z
R 0 | 1 | 2 | ... | 9
Условные обозначения:
запись вида {} означает итерацию цепочки , то есть в порождаемой цепочке в этом месте может находиться либо , либо , либо , либо и так далее.
запись вида [ | ] означает, что в порождаемой цепочке в этом месте может находиться либо , либо .
P - цель грамматики; символ - маркер конца текста программы.
Семантические условия:
любой идентификатор обязательно описывается в программе и только один раз;
в любом месте программы (кроме идентификаторов, служебных слов и чисел) может находиться произвольное число пробелов и комментариев вида { < любые символы, кроме ‘}’ и ‘’ > };
запрещается переопределять ключевые слова true, false, read и write ;
сохраняется правило языка Паскаль о разделителях между идентификаторами, числами и служебными словами;
в операторе присваивания типы левого и правого операндов должны совпадать;
в условном операторе и в операторе цикла в качестве условия возможно только логическое выражение;
операнды операции отношения должны быть целочисленными;
тип выражения и совместимость типов операндов в выражении определяются по обычным правилам, старшинство операций задано синтаксисом;
Вход лексического анализатора: символы исходной программы на М-языке.
Выход лексического анализатора: исходная программа в виде последовательности лексем (их внутреннего представления).
Процесс построения лексического анализатора для М-языка включает в себя следующие этапы:
построение графа переходов конечного автомата, распознающего цепочки М-языка;
программная реализация лексического анализатора для М-языка.
Первый этап: разработка графа переходов конечного автомата.
Разделим на классы все лексемы М-языка, классы пронумеруем следующим образом:
ключевые слова - 1,
ограничители - 2,
константы (целые числа) - 3,
идентификаторы - 4.
Внутреннее представление лексем - это пара (номер_класса, номер_в_классе). Номер_в_классе - это номер строки в таблице лексем соответствующего класса.
Список принятых обозначений (на диаграмме состояний и в программе).
Переменные:
buf - буфер для накопления символов лексемы;
c - очередной входной символ;
d - переменная для формирования числового значения константы;
TW - таблица ключевых слов М-языка;
TD - таблица ограничителей М-языка;
TID - таблица идентификаторов анализируемой программы;
TNUM - таблица чисел-констант, используемых в программе.
Таблицы ключевых слов (TW) и ограничителей (TD) заполнены заранее, так как их содержимое не зависит от исходной программы. Таблицы идентификаторов (TID) и числовых констант (TNUM) формируются в процессе лексического анализа.
Для простоты будем считать, что все таблицы TW, TD, TID, TNUM одного типа tabl, ptabl - указатель на tabl.
Символом Nx в диаграмме (и в тексте программы) обозначим номер лексемы x в ее классе.
Функции:
void clear (void); - очистка буфера buf;
void add (void); - добавление символа с в конец буфера buf;
int look (ptabl Т); - поиск в таблице Т лексемы из буфера buf; результат: номер строки таблицы с информацией о лексеме или 0, если такой лексемы в таблице Т нет;
int putl (ptabl Т); - запись в таблицу Т лексемы из буфера buf, если ее там не было; результат: номер строки таблицы с информацией о лексеме;
int putnum (); - запись в TNUM константы из d, если ее там не было; результат: номер строки таблицы TNUM с информацией о константе-лексеме;
void makelex (int k, int i); - формирование и вывод внутреннего представления лексемы; k - номер класса, i - номер в классе;
void gc (void); - функция, читающая из входного потока очередной символ исходной программы и заносящая его в переменную с.
Граф переходов конечного автомата, распознающего цепочки М-языка, представлен на рис.3.13. Дуги графа, обозначающие переходы автомата из одного состояния в другое, помечены вызовами соответствующих функций распознавания и формирования внутреннего представления лексем. Очевидно, что построенный автомат является детерминированным конечным автоматом, приведенным к полностью определенному виду, поэтому в дальнейших преобразованиях он не нуждается.
Второй этап: основываясь на построенном графе переходов конечного автомата, распознающего цепочки М-языка, напишем программу, моделирующую работу указанного автомата.
В листинге 3.2 приводится текст функции int scan (void) на языке С, реализующей данный распознаватель. В случае успешного окончания разбора функция-сканер возвращает 0, в противном случае – 1. Исходный анализируемый текст располагается в файле prog.txt. В ходе разбора функция scan() заполняет таблицу числовых констант и таблицу идентификаторов, а также преобразует исходный текст в последовательность внутренних представлений лексем. Текст, представляющий собой результат разбора, выводится на экран дисплея или в файл (в зависимости от реализации функции makelex()).
Листинг 3.2
#include <stdio.h>
#include <ctype.h>
#define BUFSIZE 80
typedef struct tabl* ptabl;
extern ptabl TW, TID, TD, TNUM;
char buf[BUFSIZE]; // Буфер для накопления символов лексемы
int c; // Переменная для хранения текущего символа
int d; // Переменная для формирования числового значения константы
void clear(void); // Очистка буфера
void add(void); // Добавление текущего символа в конец буфера
int look(ptabl); // Поиск в таблице лексемы из buf;
// результат: номер строки таблицы либо 0
int putl(ptabl); // Запись в таблицу лексемы из buf, если ее там не было;
// результат: номер строки таблицы
Рис. 3.11. Граф
переходов конечного автомата для
распознавания цепочек М-языка
int putnum(); //Запись в TNUM константы из d, если ее там не было;
// результат: номер строки таблицы TNUM
int j; // Номер строки в таблице, где находится лексема, найденная функцией look()
void makelex(int,int); //Формирование и вывод внутреннего представления лексемы
// Функция – лексический анализатор М-языка
int scan(void){
// Множество состояний конечного автомата
enum state {H,ID,NUM,COM,ASS,DLM,ER,FIN};
state TC; // Текущее состояние
FILE fp;
TC=H; // В качестве текущего состояния устанавливается начальное состояние Н
// Открываем для чтения файл "prog.txt", в котором находится текст исходной программы
fp=fopen("prog.txt","r");
c=fgetc(fp); // Считывание символа из файла
// Основной цикл: распознавание лексемы
do {switch (TC) {
case H:
while (c==' ') c=fgetc(fp);
if (isalpha(c))
{clear(); add(); c=fgetc(fp); TC=ID;}
else
if (isdigit (c))
{d=c-'0'; c=fgetc(fp); TC=NUM;}
else
if (c=='{')
{c=fgetc(fp); TC=COM;}
else
if (c==':')
{c=fgetc(fp); TC=ASS;}
else
if (c=='')
{makelex(2,N); TC=FIN;}
else TC=DLM;
break;
case ID:
while (isalpha(c)||isdigit(c))
{add(); c=fgetc(fp);}
if (j=look(TW))
makelex(1,j);
else
{j=putl(TID); makelex(4,j);};
TC=H;};
break;
case NUM:
while(isdigit(c))
{d=d10+(c-'0'); c=fgetc(fp);}
makelex(3,putnum());
TC=H;
break;
case COM:
while((c!='}')&& (c!=''))
c=fgetc(fp);
if (c=='}')
{c=fgetc(fp); TC=H;}
else
TC=ER;
break;
case ASS:
if (c=='=')
{c=fgetc(fp); makelex(2,N:=); TC=H;}
else
{makelex(2,N:); TC=H;}
break;
case DLM:
clear();
add();
if (j=look(TD))
{makelex(2,j); c=fgetc(fp); TC=H;}
else
TC=ER;
break;
}
// Выход из цикла по достижению заключительного состояния FIN или состояния ER
} while ((TC!=FIN)&&(TC!=ER));
if (TC==ER) return 0;
else return 1;
}
Конечно, рассмотренная программа является всего лишь примером моделирования такого рода автомата. Она построена так, чтобы можно было четко отследить соответствие между этой программой и построенным конечным автоматом, граф переходов которого изображен на рис. 3.11. Программная реализация конкретного лексического анализатора будет во многом определяться способом организации взаимодействия сканера с другими составляющими компилятора. От этого будет зависеть возвращаемое функцией-сканером значение, а также ее действия при обнаружении ошибки и при завершении распознавания лексемы.
В целом техника построения сканеров основывается на моделировании работы детерминированных и недетерминированных конечных автоматов с дополнением функций лексического анализатора вызовами функций обработки ошибок, а также заполнения таблиц лексем и таблиц и идентификаторов. Такая техника не требует реализации сложных алгоритмов обработки исходного текста и существенных преобразований входных грамматик. Единственным принципиально важным вопросом, который должны решить для себя разработчики сканера, является вопрос о том, где заканчиваются функции сканера и начинаются функции синтаксического анализатора, после чего процесс построения лексического анализатора легко поддается автоматизации.