Описание модельного паскалеподобного языка (М-языка):
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
Условные обозначения:
d) запись вида {a} означает итерацию цепочки a, то есть в порождаемой цепочке в этом месте может находиться либо e, либо a, либо aa, либо aaa и так далее.
e) запись вида [ a | b ] означает, что в порождаемой цепочке в этом месте может находиться либо a, либо b.
f) P - цель грамматики; символ ^ - маркер конца текста программы.
Семантические условия:
- любой идентификатор обязательно описывается в программе и только один раз;
- в любом месте программы (кроме идентификаторов, служебных слов и чисел) может находиться произвольное число пробелов и комментариев вида { < любые символы, кроме ‘}’ и ‘^’ > };
- запрещается переопределять ключевые слова true, false, read и write ;
- сохраняется правило языка Паскаль о разделителях между идентификаторами, числами и служебными словами;
- в операторе присваивания типы левого и правого операндов должны совпадать;
- в условном операторе и в операторе цикла в качестве условия возможно только логическое выражение;
- операнды операции отношения должны быть целочисленными;
- тип выражения и совместимость типов операндов в выражении определяются по обычным правилам, старшинство операций задано синтаксисом;
Вход лексического анализатора: символы исходной программы на М-языке.
Выход лексического анализатора: исходная программа в виде последовательности лексем (их внутреннего представления).
Процесс построения лексического анализатора для М-языка включает в себя следующие этапы:
1) построение графа переходов конечного автомата, распознающего цепочки М-языка;
2) программная реализация лексического анализатора для М-языка.
Первый этап:разработка графа переходов конечного автомата.
Разделим на классы все лексемы М-языка, классы пронумеруем следующим образом:
- ключевые слова - 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=d*10+(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. Программная реализация конкретного лексического анализатора будет во многом определяться способом организации взаимодействия сканера с другими составляющими компилятора. От этого будет зависеть возвращаемое функцией-сканером значение, а также ее действия при обнаружении ошибки и при завершении распознавания лексемы.
В целом техника построения сканеров основывается на моделировании работы детерминированных и недетерминированных конечных автоматов с дополнением функций лексического анализатора вызовами функций обработки ошибок, а также заполнения таблиц лексем и таблиц и идентификаторов. Такая техника не требует реализации сложных алгоритмов обработки исходного текста и существенных преобразований входных грамматик. Единственным принципиально важным вопросом, который должны решить для себя разработчики сканера, является вопрос о том, где заканчиваются функции сканера и начинаются функции синтаксического анализатора, после чего процесс построения лексического анализатора легко поддается автоматизации.
