В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов, страница 8

, AN)и только в зависимости от того, что стоит после “)”, можно определить,является ли DECLARE ключевым словом или идентификатором. Длинатакой строки может быть сколь угодно большой и уже невозможно отделить фазу синтаксического анализа от фазы лексического анализа.Рассмотрим несколько подробнее вопросы программирования ЛА. Основная операция лексического анализатора, на которую уходит большаячасть времени его работы – это взятие очередного символа и проверка напринадлежность его некоторому диапазону. Например, основной циклпри выборке числа в простейшем случае может выглядеть следующимобразом:while (Insym<=’9’ && Insym>=’0’){ ... }Программу можно значительно улучшить следующим образом [4].Пусть LETTER, DIGIT, BLANK – элементы перечислимого типа.

Введем массив map, входами которого будут символы, значениями – типы символов. Инициализируем массив map следующим образом:map[’a’]=LETTER;........map[’z’]=LETTER;map[’0’]=DIGIT;........map[’9’]=DIGIT;map[’ ’]=BLANK;........Тогда приведенный выше цикл примет следующую форму:while (map[Insym]==DIGIT){ ... }Выделение ключевых слов может осуществляться после выделенияидентификаторов. ЛА работает быстрее, если ключевые слова выделяются непосредственно.Для этого строится конечный автомат, описывающий множество ключевых слов.

На рис. 3.17 приведен фрагмент такого автомата. Рассмотрим пример программирования этого конечного автомата на языке Си,приведенный в [14]:3.5. ПРОГРАММИРОВАНИЕ ЛЕКСИЧЕСКОГОLIQG_[md\Zb g_pbnjZ;md\ZbebpbnjZG_I b g_QАНАЛИЗА43Dexq_\h_keh\h LIB^_glbnbdZlhjG_WW;md\ZbebpbnjZG_[md\Zb g_pbnjZDexq_\h_keh\hLQWРис. 3.17:........case ’i’:if (cp[0]==’f’ &&!(map[cp] & (DIGIT | LETTER))){cp++; return IF;}if (cp[0]==’n’ && cp==’t’&&!(map[cp] & (DIGIT | LETTER))){cp+=2; return INT;}{ обработка идентификатора }........Здесь cp – указатель текущего символа. В массиве map классы символов кодируются битами.Поскольку ЛА анализирует каждый символ входного потока, его скорость существенно зависит от скорости выборки очередного символа входного потока.

В свою очередь, эта скорость во многом определяется схемой буферизации. Рассмотрим возможные эффективные схемы буферизации.Будем использовать буфер, состоящий из двух одинаковых частейдлины N (рис. 3.18, а), где N – размер блока обмена (например, 1024,2048 и т.д.).Чтобы не читать каждый символ отдельно, в каждую из половин буфера поочередно одной командой чтения считывается N символов.

Еслина входе осталось меньше N символов, в буфер помещается специальный символ (eof). На буфер указывают два указателя: продвижение и начало. Между указателями размещается текущая лексема. Вначале ониоба указывают на первый символ выделяемой лексемы. Один из них,продвижение, продвигается вперед, пока не будет выделена лексема, иГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ44111Ijh^\b`_gb_GZqZehHRI1Ijh^\b`_gb_GZqZehZ[Рис. 3.18:устанавливается на ее конец.

После обработки лексемы оба указателяустанавливаются на символ, следующий за лексемой. Если указательпродвижение переходит середину буфера, правая половина заполняетсяновыми N символами. Если указатель продвижение переходит правуюграницу буфера, левая половина заполняется N символами и указательпродвижение устанавливается на начало буфера.При каждом продвижении указателя необходимо проверять, не достигли ли мы границы одной из половин буфера. Для всех символов,кроме лежащих в конце половин буфера, требуются две проверки.

Число проверок можно свести к одной, если в конце каждой половины поместить дополнительный “сторожевой” символ, в качестве которого логично взять eof (рис. 3.18, б).В этом случае почти для всех символов делается единственная проверка на совпадение с eof и только в случае совпадения нужно дополнительно проверить, достигли ли мы середины или правого конца.3.6Конструктор лексических анализаторов LEXДля автоматизации разработки лексических анализаторов было разработано довольно много средств.

Как правило, входным языком для нихслужат либо праволинейные грамматики, либо язык регулярных выражений. Одной из наиболее распространенных систем является LEX, работающий с расширенными регулярными выражениями. LEX-программасостоит из трех частей:Объявления%%Правила трансляции%%Вспомогательные подпрограммы3.6. КОНСТРУКТОР ЛЕКСИЧЕСКИХ АНАЛИЗАТОРОВ LEX45Секция объявлений включает объявления переменных, констант иопределения регулярных выражений. При определении регулярных выражений могут использоваться следующие конструкции:[abc]– либо a, либо b, либо c;[a-z]– диапазон символов;R*– 0 или более повторений регулярного выражения R;R+– 1 или более повторений регулярного выражения R;R1/R2 – R1 , если за ним следует R2 ;R1|R2 – либо R1 , либо R2 ;R?– если есть R, выбрать его;R$– выбрать R, если оно последнее в строке;^R– выбрать R, если оно первое в строке;[^R]– дополнение к R;R{n,m} – повторение R от n до m раз;{имя} – именованное регулярное выражение;(R)– группировка.Правила трансляции LEX программ имеют видp_1 { действие_1 }p_2 { действие_2 }................p_n { действие_n }где каждое p_i – регулярное выражение, а каждое действие_i – фрагментпрограммы, описывающий, какое действие должен сделать лексическийанализатор, когда образец p_i сопоставляется лексеме.

В LEX действиязаписываются на Си.Третья секция содержит вспомогательные процедуры, необходимыедля действий. Эти процедуры могут транслироваться раздельно и загружаться с лексическим анализатором.Лексический анализатор, сгенерированный LEX, взаимодействует ссинтаксическим анализатором следующим образом. При вызове его синтаксическим анализатором лексический анализатор посимвольно читает остаток входа, пока не находит самый длинный префикс, которыйможет быть сопоставлен одному из регулярных выражений p_i.

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

Синтаксическому анализатору лексический анализатор возвращает единственное значение – тип лексемы. Дляпередачи информации о типе лексемы используется глобальная переменная yylval. Текстовое представление выделенной лексемы хранитсяв переменной yytext, а ее длина в переменной yylen.46ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗПример 3.11. LEX-программа для ЛА, обрабатывающего идентификаторы,числа, ключевые слова if, then, else и знаки логических операций.%{ /*определения констант LT,LE,EQ,NE,GT,GE,IF,THEN,ELSE,ID,NUMBER,RELOP, например,через DEFINE или скалярный тип*/ %}/*регулярные определения*/delim [ \t\n]ws{delim}+letter [A-Za-z]digit [0-9]id{letter}({letter}|{digit})*number {digit}+(\.{digit}+)?(E[+\-]?{digit}+)?%%{ws} {/* действий и возврата нет */}if{return(IF);}then {return(THEN);}else {return(ELSE);}{id} {yylval=install_id(); return(ID);}{number} {yylval=install_num(); return(NUMBER);}"<" {yylval=LT; return(RELOP);}"<=" {yylval=LE; return(RELOP);}"=" {yylval=EQ; return(RELOP);}"<>" {yylval=NE; return(RELOP);}">" {yylval=GT; return(RELOP);}">=" {yylval=GE; return(RELOP);}%%install_id(){/*подпрограмма, которая помещает лексему,на первый символ которой указывает yytext,длина которой равна yylen, в таблицусимволов и возвращает указатель на нее*/}install_num(){/*аналогичная подпрограмма для размещениялексемы числа*/}В разделе объявлений, заключенном в скобки %{ и %}, перечислены константы, используемые правилами трансляции.

Все, что заключено в эти скобки, непосредственно копируется в программу лексического анализатора lex.yy.cи не рассматривается как часть регулярных определений или правил трансляции. То же касается и вспомогательных подпрограмм третьей секции. В данномпримере это подпрограммы install_id и install_num.В секцию определений входят также некоторые регулярные определения.Каждое такое определение состоит из имени и регулярного выражения, обозначаемого этим именем.

Например, первое определенное имя – это delim. Оно обозначает класс символов { \t\n\}, т.е. любой из трех символов: пробел, табуляция или новая строка. Второе определение – разделитель, обозначаемый именем ws. Разделитель – это любая последовательность одного или более символов-3.6. КОНСТРУКТОР ЛЕКСИЧЕСКИХ АНАЛИЗАТОРОВ LEX47разделителей. Слово delim должно быть заключено в скобки, чтобы отличить егоот образца, состоящего из пяти символов delim.В определении letter используется класс символов.

Сокращение[A-Za-z] означает любую из прописных букв от A до Z или строчных букв от a до z.В пятом определении для id для группировки используются скобки, являющиеся метасимволами LEX. Аналогично, вертикальная черта – метасимвол LEX,обозначающий объединение.В последнем регулярном определении number символ “+” используется какметасимвол “одно или более вхождений”, символ “?” как метасимвол “ноль илиодно вхождение”. Обратная черта используется для того, чтобы придать обычный смысл символу, использующемуся в LEX как метасимвол. В частности, десятичная точка в определении number обозначается как “\.”, поскольку точкасама по себе представляет класс, состоящий из всех символов, за исключением символа новой строки.

В классe символов [+\] обратная черта перед минусомстоит потому, что знак минус используется как символ диапазона, как в [A-Z].Если символ имеет смысл метасимвола, то придать ему обычный смысл можно и по-другому, заключив его в кавычки. Так, в секции правил трансляциишесть операций отношения заключены в кавычки.Рассмотрим правила трансляции, следующие за первым %%.