Реализация компилятора. Организация лексического блока

Реализация компилятора

Организация лексического блока

Назначение лексического блока

Как мы уже ранее говорили, основным назначением ЛБ является разбиение цепочки литер, представляющей программу на исходном языке, в цепочку символов языка, опознание этих цепочек, начальное заполнение таблиц, замена символов кодами. При этом, если в программе были комментарии, то ЛБ их должен удалить.

Т.о. ЛБ представляет собой программу, в которой:

1)  открывается на чтение файл с текстом программы на исходном языке программирования;

2)  открывается на запись файл, в который будем заносить версию программы на исходном языке программирования в виде кодов символов;

3)  читаем построчно файл с исходным текстом программы;

4)  обрабатываем строку:

·  удаляем комментарии;

·  выделяем очередную цепочку литер до ближайшего разделителя, распознаем ее и записываем в файл в виде кода;

·  все это продолжаем, пока не дойдем до конца считанной строки;

5)  пункты 3,4 повторяем до тех пор, пока не дойдем до конца файла.

Реализация лексического блока

Прежде чем рассматривать вопросы программной реализации ЛБ необходимо задать коды символов (лексем). Всего может быть 4 группы символов:

1)  служебные слова;

2)  разделители;

3)  идентификаторы;

4)  константы.

 Коды всех этих символов лучше всего задать символическими константами и потом использовать их в программе. Это можно сделать, например,  т.о.:

Для служебных слов:

#define            TTL        1

#define            END       2

#define            READ    3

#define            WRITE   4

#define            PBASE   5

#define            Int          6       //имя INT  C++Builder уже использует

#define            REAL     7

#define            POW      8

#define            ABS       9

#define            DIV      10

#define            OR       11

#define            AND     12

#define            NOT     13

или через перечисляемый тип:

enum Term {

  TTL=1,END,READ,WRITE,PBASE,Int, REAL,POW,ABS,DIV,OR,AND,NOT

};

Для разделителей:

#define            PLUS             16

#define            MINUS           17

#define            UMINUS        18

#define            MUL               19

#define            EQ                   20

#define            LT                   21

#define            GT                   22

#define            LE                    23

#define            GE                   24

#define            NE                   25

#define            LB                    26

#define            RB                   27

#define            COMMA        28

#define            SCOL               29

или:

enum Delim {

  PLUS=16,MINUS,UMINUS,MUL,EQ,LT,GT,LE,GE,NE,LB,RB,COMMA,SCOL

};

Для идентификаторов:

#define            BEGTBL        31

#define            ENDTBL        59

Для констант:

#define            BEGLIT          61

#define            ENDLIT         99

Разбиение цепочки входных литер на цепочки символов и их опознание может быть выполнено фрагментами программ вида:

Головная функция для ЛБ

. . .

out=fopen(lname, "w");

Form3->Memo1->Lines->Clear();

Memo2->Lines->Clear();

Memo2->Visible = false;

lerr=0;

for (int i = 0; i < Memo1->Lines->Count; i++){

Lex(Memo1->Lines->Strings[i].c_str(), i+1);

} 

if (lerr) Memo2->Visible =  true;

fclose(out);

Form3->ShowModal();

     . . .

Разбиение:

  .   .   .

void Lex(char *s, int ns){

  char ls[80], str[160], *pstr, *ps, errstr[80];

  ps=s;

  *str='\0'; pstr=str;

  while(*s!='\0'){

        s=NextLex(s,ls);  lcod=LexRecogn(ls);

        if (lcod>0) { sprintf(pstr,"%02d ",lcod); pstr += 3; }

/*можно: pos= sprintf(pstr,"%02d ",lcod); pstr += pos;

Где локальная переменная : int pos;*/

        else { lerr++; sprintf(errstr,"Неопознанная лексема %s в строке %d", ls, ns);

        Memo2->Lines->Add(errstr);

     }

   }

   sprintf(pstr,"00 %s",ps); //Чтобы вывести после кодов исходный текст

   Form3->Memo1->Lines->Add(str);

   fprintf(out,"%s\n",str);

}

.   .   .

Здесь предполагается, что имелись глобальные описания и функции:

FILE *out;                     //выходной файл с кодами лексем

int  lcod;                         //содержит код лексемы ( норма >0)

int lerr=0;                      //количество ошибок лексического блока

int LexRecogn(char *);  //функция, распознающая лексему и возвращающая ее код >0

Form1->Memo2 – для вывода сообщений об ошибках, если они будут.

Опознание:

LexRecogn(char *s){

    int cod;      

    if((cod=TermRecogn (s)) = = 0)

        if((cod=IdRecogn (s)) = = 0)

            if((cod=LitRecogn (s)) = = 0)

                if((cod=DlmRecogn (s)) = = 0)

                     return(0);

                return(cod);

}

Прежде чем рассматривать вопросы распознавания символов, рассмотрим понятие конечного автомата.

Конечные автоматы

На практике вопросы организации лексического блока очень тесно связаны с понятием конечного автомата. Конечный автомат - это устройство для распознавания строк языка, имеющее конечное множество состояний. По мере считывания литер из входной строки, автомат меняет свое состояние в соответствии с заданным множеством переходов. Конечное состояние автомата после считывания последней литеры строки определяет результат распознавания.

Таким образом, на вход конечного автомата подается цепочка литер из алфавита нашего языка, а автомат либо принимает (распознает), либо отвергает эту цепочку. Грамматика, реализуемая конечным автоматом, должна быть линейной. Сам конечный автомат задается пятеркой множеств:

M=(K, T, d, S, F)

где  K - конечное множество состояний;

T - конечный входной алфавит;

d- множество переходов;

S - начальное состояние (S Î K);

F - множество конечных, допускающих состояний (F Ì K).

Рассмотрим пример реализации конечного автомата для распознавания идентификатора.

Грамматика для этого случая имеет вид:

G=(N, T, P, S)                    N={S, Z}                 T={l,  d}

P={ S àl | lZ

       Z à l | lZ |d | dZ

     }

Описание автомата имеет вид:

M=(K, T, d, S,F)       K={S, Z }     T={+, -, d}

	l	d	\0
S	Z		0
Z	Z	Z	1

         d  =

Здесь d означает понятие "цифра", а l – "буква".

Ниже представлен пример программной реализации этого автомата в предположении, что распознаваемая цепочка символов представлена отдельной строкой. В дальнейшем также будем предполагать, что на вход конечного автомата подается строка литер, полученная выделением из входной строки всех литер до первого символа-разделителя (см. лабораторную работу 2).

IsId (char *s){

if (isalpha(*s) { //перешли в состояние Z после появления 1-ой буквы

    s++;

    while (isdigit(*s) || isalpha(*s)) s++;

    /* проверка на допускающее состояние */

    if (*s== '\0') return(1); else return 0;

}else return(0);

}

или по-другому (хотя это и не совсем по таблице переходов) :

IsId (char *s){

if (!isalpha(*s++) return 0;

//перешли в состояние Z после появления 1-ой буквы

while (isdigit(*s) || isalpha(*s)) s++;

 /* проверка на допускающее состояние */

if (*s== '\0') return(1); else return 0;

}

Рассмотрим пример реализации конечного автомата для распознавания целого числа.

Грамматика для этого случая имеет вид:

G=(N, T, P, S)                    N={S, U}                 T={ d}

P={ S àU

       U à d | dU

     }

Описание автомата имеет вид:

M=(K, T, d, S,F)       K={S, U }     T={ d}

	D	\0
S	U	0
U	U	1

         d  =

Пример программной реализации этого автомата.

IsNumb (char *s){

if (isdigit(*s) { //перешли в состояние U после появления 1-ой цифры

    s++;

    while (isdigit(*s)) s++;

    /* проверка на допускающее состояние */