В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 14
Текст из файла (страница 14)
Программирование лексического анализа65{cp+=2; return INT;}{ обработка идентификатора }........Здесь cp — указатель текущего символа. В массиве map классы символовкодируются битами.Поскольку ЛА анализирует каждый символ входного потока, его скоростьсущественно зависит от скорости выборки очередного символа входного потока. В свою очередь, эта скорость во многом определяется схемой буферизации.
Рассмотрим возможные эффективные схемы буферизации.Рис. 3.19Будем использовать буфер, состоящий из двух одинаковых частей длинойN (рис. 3.19, а), где N — размер блока обмена (например, 1024, 2048 и т. п.).Чтобы не читать каждый символ отдельно, в каждую из половин буферапоочередно одной командой чтения считывается N символов.
Если на входеосталось меньше N символов, то в буфер помещается специальный символeof. Буфер снабжен двумя указателями: продвижение и начало. Между указателями размещается текущая лексема. Вначале они оба указывают на первый символ выделяемой лексемы. Один из них, продвижение, продвигаетсявперед, пока не будет выделена лексема, и устанавливается на ее конец.После обработки лексемы оба указателя устанавливаются на символ, следующий за лексемой. Если указатель продвижение переходит середину буфера,то правая половина заполняется новыми N символами. Если указатель продвижение переходит правую границу буфера, то левая половина заполняетсяN символами и указатель продвижение устанавливается на начало буфера.При каждом продвижении указателя необходимо проверять, не достиглили мы границы одной из половин буфера.
Для всех символов, кроме лежащихв концах половин буфера, требуются две проверки. Число проверок можносвести к одной, если в конце каждой половины поместить дополнительный«сторожевой» символ, в качестве которого логично взять eof (рис. 3.19, б).В этом случае почти для всех символов делается единственная проверкана совпадение с eof, и только при совпадении нужно дополнительно проверить, достигли ли мы середины или правого конца.3 В.А. Серебряков66Глава 3. Лексический анализ3.7. Конструктор лексических анализаторов LEXДля автоматизации разработки ЛА было создано довольно много средств.Как правило, входными языками для них служат или праволинейные грамматики, или языки регулярных выражений. Одной из наиболее распространенных систем является LEX, работающий с расширенными регулярнымивыражениями.
LEX-программа состоит из трех частей:Объявления%%Правила трансляции%%Вспомогательные подпрограммыСекция объявлений включает объявления переменных, констант и определения регулярных выражений. При определении регулярных выражениймогут использоваться следующие конструкции:[abc][a-z]R*R+R1/R2R1|R2R?R$^R[^R]R{n,m}{имя}(R)—————————————либо a, либо b, либо c;диапазон символов;0 или более повторений регулярного выражения R;1 или более повторений регулярного выражения R;R1 , если за ним следует R2 ;либо R1 , либо R2 ;если есть R, выбрать его;выбрать R, если оно последнее в строке;выбрать R, если оно первое в строке;дополнение к R;повторение R от n до m раз;именованное регулярное выражение;группировка.Правила трансляции LEX-программ имеют следующий вид:p_1 { действие_1 }p_2 { действие_2 }................p_n { действие_n }где p_i — регулярное выражение, а действие_i — фрагмент программы,описывающий, какое действие должен сделать ЛА, когда образец p_i сопоставляется лексеме.
В LEX действия записываются на Си.Третья секция содержит вспомогательные процедуры, необходимые длядействий. Эти процедуры могут транслироваться раздельно и загружатьсяс ЛА.3.7. Конструктор лексических анализаторов LEX67ЛА, сгенерированный LEX, взаимодействует с синтаксическим анализатором следующим образом. При вызове ЛА синтаксическим анализаторомон посимвольно читает остаток входа, пока не находит самый длинныйпрефикс, который может быть сопоставлен одному из регулярных выраженийp_i. Затем он выполняет действие_i.
Как правило, действие_i возвращаетуправление синтаксическому анализатору. Если это не так, т. е. в соответствующем действии нет возврата, то ЛА продолжает поиск лексем до техпор, пока действие не вернет управление синтаксическому анализатору. Повторный поиск лексем вплоть до явной передачи управления позволяет ЛАправильно обрабатывать пробелы и комментарии. Синтаксическому анализатору ЛА возвращает единственное значение — тип лексемы. Для передачиинформации о типе лексемы используется глобальная переменная yylval.Текстовое представление выделенной лексемы хранится в переменной yytext,а ее длина в переменной yylen.Пример 3.13. 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,3*68Глава 3.
Лексический анализдлина которой равна yylen, в таблицусимволов и возвращает указатель на нее*/}install_num(){/*аналогичная подпрограмма для размещениялексемы числа*/}В разделе объявлений, заключенном в скобки %{ и %}, перечислены константы,используемые правилами трансляции. Все, что заключено в эти скобки, непосредственно копируется в программу ЛА lex.yy.c и не рассматривается как частьрегулярных определений или правил трансляции. То же касается и вспомогательныхподпрограмм третьей секции.
В данном примере это подпрограммы install_idи install_num.В секцию определений входят также некоторые регулярные определения. Каждоетакое определение состоит из имени и регулярного выражения, обозначаемого этимименем. Например, первое определенное имя — это delim. Оно обозначает класссимволов { \t\n\}, т. е. любой из трех символов: пробел, табуляция или новаястрока. Второе определение — разделитель, обозначаемый именем ws.
Разделитель— это любая последовательность одного или более символов-разделителей. Словоdelim должно быть заключено в скобки, чтобы отличить его от образца, состоящегоиз пяти символов delim.В определении letter используется класс символов. Сокращение [A-Za-z]обозначает любую из прописных букв от A до Z или строчных букв от a до z. В пятомопределении id для группировки используются скобки, являющиеся метасимволамиLEX. Аналогично, вертикальная черта — метасимвол LEX, обозначающий объединение.В последнем регулярном определении number символ «+» используется какметасимвол «одно или более вхождений», символ «?» как метасимвол «ноль илиодно вхождение».
Обратная черта используется для того, чтобы придать обычныйсмысл символу, использующемуся в LEX как метасимвол. В частности, десятичнаяточка в определении number обозначается как «\.», поскольку точка сама по себепредставляет класс, состоящий из всех символов, за исключением символа новойстроки. В классe символов [+\] обратная черта перед минусом стоит потому, чтознак минус используется как символ диапазона, как в [A-Z].Если символ имеет смысл метасимвола, то придать ему обычный смысл можнои по-другому, заключив его в кавычки. Так, в секции правил трансляции шестьопераций отношения заключены в кавычки.Рассмотрим правила трансляции, следующие за первым %%.
Согласно первомуправилу, если обнаружено ws, т. е. максимальная последовательность пробелов, табуляций и новых строк, никаких действий не производится. В частности, не осуществляется возврат в синтаксический анализатор.Согласно второму правилу, если обнаружена последовательность букв if, нужно вернуть значение IF, которое определено как целая константа, понимаемаясинтаксическим анализатором как лексема if.
Аналогично обрабатываются ключевые слова then и else в двух следующих правилах.3.7. Конструктор лексических анализаторов LEX69В действии, связанном с правилом для id, два оператора. Переменной yylvalприсваивается значение, возвращаемое процедурой install_id. Переменнаяyylval определена в программе lex.yy.c, выходе LEX и доступна синтаксическому анализатору. Она хранит возвращаемое лексическое значение, поскольку второйоператор в действии, return(ID), может только возвратить код класса лексем.Функция install_id заносит идентификаторы в таблицу символов.Аналогично обрабатываются числа в следующем правиле.
В последних шестиправилах yylval используется для возврата кода операции отношения, возвращаемое же функцией значение — это код лексемы relop.Если, например, в текущий момент ЛА обрабатывает лексему if, то этойлексеме соответствуют два образца: if и {id}, причем более длинной строки,соответствующей образцу, нет. Поскольку образец if предшествует образцу дляидентификатора, конфликт разрешается в пользу ключевого слова. Такая стратегияразрешения конфликтов позволяет легко резервировать ключевые слова.Если на входе встречается «<=», то первому символу соответствует образец «<»,но это не самый длинный образец, который соответствует префиксу входа. Стратегиявыбора самого длинного префикса легко разрешает такого рода конфликты.Глава 4СИНТАКСИЧЕСКИЙ АНАЛИЗ4.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
