Вход лексического анализатора - символы исходной программы на М-языке; результат работы - исходная программа в виде последовательности лексем (их внутреннего представления).
Лексический анализатор для модельного языка будем писать в два этапа: сначала построим диаграмму состояний с действиями для распознавания и формирования внутреннего представления лексем, а затем по ней напишем программу - лексический анализатор.
Первый этап:разработка диаграммы состояний.
Все лексемы М-языка разделим на несколько классов. Классы перенумеруем следующим образом:
- служебные слова - 1,
- ограничители - 2,
- константы (целые числа) - 3,
- идентификаторы - 4.
Внутреннее представление лексем - это пара (номер_класса, номер_в_классе). Номер_в_классе - это номер строки в таблице лексем соответствующего класса.
Список принятых обозначений (на диаграмме состояний и в программе).
- Переменные:
buf- буфер для накопления символов лексемы;
c - очередной входной символ;
d - переменная для формирования числового значения константы;
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.4.
Второй этап: основываясь на разработанной диаграмме состояний, осуществим программную реализацию лексического анализатора: функция void scan (void);.
#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); /* очистка буфера buf */
void add(void); /* добавление символа с в конец буфера buf*/
int look(ptabl); /* поиск в таблице лексемы из buf;
результат: номер строки таблицы либо 0 */
int putl(ptabl); /* запись в таблицу лексемы из buf,
если ее там не было; результат:
номер строки таблицы */
int putnum(); /* запись в TNUM константы из d, если ее там не было; результат: номер строки таблицы TNUM */
Рис. 3.4. Диаграмма состояний для лексического анализатора
int j; /* номер строки в таблице, где находится лексема, найденная функцией look */
void makelex(int,int); /* формирование и вывод внутреннего представления лексемы */
void scan (void)
{enum state {H,ID,NUM,COM,ASS,DLM,ER,FIN};
state TC; /* текущее состояние */
FILE* fp;
TC = H;
fp = fopen("prog","r"); /* в файле "prog" находится
текст исходной программы */
c = fgetc(fp);
do {switch (TC) {
case H:
if (c == ' ') c = fgetc(fp);
else 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:
if (isalpha(c) || isdigit(c)) {add(); c=fgetc(fp);}
