Материал: LabWork2
Генератор лексических анализаторов Flex
Существуют различные программные средства для решения задачи построения лексических анализаторов. Наиболее известным из них является Lex (в более поздних версиях –
Flex).
Программный инструментарий Flex позволяет определить лексический анализатор с помощью регулярных выражений для описания шаблонов токенов. Входные обозначения для Flex обычно называют языком Flex, а сам инструмент – компилятором Flex. Компилятор Flex преобразует входные шаблоны в конечный автомат и генерирует код (в файле с именем lex.yy.c), имитирующий данный автомат.
Рисунок 3. Схема использования Flex
На рисунке 3 показаны схема использования Flex и команды, соответствующие каждому этапу генерирования лексического анализатора. Входной файл input.l написан на языке Flex и описывает генерируемый лексический анализатор. Компилятор Flex преобразует input.l в программу на языке программирования Си (файл с именем lex.yy.c). При компиляции lex.yy.c необходимо прилинковать библиотеку Flex (-lfl). Этот файл компилируется в файл с именем а.out как обычно. Выход компилятора Си представляет собой работающий лексический анализатор, который на основе потока входных символов выдаёт поток токенов.
Обычно полученный лексический анализатор, используется в качестве подпрограммы синтаксического анализатора.
Структура программы на языке Flex имеет следующий вид:
Объявления
%%
Правила трансляции
%%
Вспомогательные функции
Обязательным является наличие правил трансляции, а, следовательно, и символов %% перед ними. Правила могут и отсутствовать в файле, но %% должны присутствовать всё равно.
Пример самого короткого файла на языке Flex:
%%
11
В этом случае входной поток просто посимвольно копируется в выходной. По умолчанию, входным является стандартный входной поток (stdin), а выходным – стандартный выходной
(stdout).
Раздел объявлений может включать объявления переменных, именованные константы и регулярные определения (например, digit [0-9] – регулярное выражение, описывающее множество цифр от 0 до 9). Кроме того, в разделе объявлений может помещаться символьный блок, содержащий определения на Си. Символьный блок всегда начинается с %{ и заканчивается %}. Весь код символьного блока полностью копируется в начало генерируемого файла исходного кода лексического анализатора.
Второй раздел содержит правила трансляции вида
Шаблон { Действие }
Каждый шаблон является регулярным выражением, которое может использовать регулярные определения из раздела объявлений. Действия представляют собой фрагменты кода, обычно написанные на языке программирования Си, хотя существуют и разновидности Flex для других языков программирования.
Третий раздел содержит различные дополнительные функции на Си, используемые в действиях. Flex копирует эту часть кода в конец генерируемого файла.
Листинг 2. Пример программы для подсчёта символов, слов и строк во введённом тексте
%{
int chars = 0; int words = 0; int lines = 0; %}
%%
[a-zA-Z]+ { words++; chars += strlen(yytext); }
\n |
{ chars++; |
lines++; } |
. |
{ chars++; |
} |
%% |
|
|
int main(int argc, char **argv)
{
yylex();
printf("%8d%8d%8d\n", lines, words, chars); return 0;
}
Влистинге 2 определены все три раздела программы на Flex.
Впервом разделе объявлены три переменных-счётчика для символов, слов и строк,
соответственно. Эта часть кода будет полностью скопирована в файл lex.yy.c.
Во втором разделе определены шаблоны токенов и действия, которые нужно выполнить при соответствии входного потока тому либо иному шаблону. Перед шаблоном не должно
быть пробелов, табуляций и т.п., поскольку Flex рассматривает любую строку, начинающуюся с пробела, как код, который нужно скопировать в файл lex.yy.c.
В данном примере определены три шаблона:
1)[a-zA-Z]+ соответствует слову текста. В соответствии с этим шаблоном слово может содержать прописные и заглавные буквы латинского алфавита. А знак + означает, что слово может состоять из одного или нескольких символов, описанных перед +. В случае
12
совпадения входной последовательности и этого шаблона, увеличиваются счётчики для слов и символов. Массив символов yytext всегда содержит текст, соответствующий данному шаблону. В нашем случае он используется для расчёта длины слова;
2)\n соответствует символу перевода строки. В случае совпадения входного потока с данным шаблоном происходит увеличение счётчиков для символов и строк на 1;
3). является шаблоном для любого входного символа.
|
В функции main вызывается yylex() – функция, непосредственно выполняющая |
||
лексический анализ входного текста. |
|||
|
Ниже приведены команды для компиляции и запуска программы на языке Flex для |
||
подсчёта символов, слов и строк в тексте, введённом с клавиатуры. |
|||
$ |
flex words.l |
|
|
$ |
gcc lex.yy.c -lfl |
|
|
$ |
./a.out |
|
|
To be, or not to be: that is the question |
|||
|
1 |
10 |
42 |
В таблице 4 перечислены специальные символы, использующиеся в регулярных выражениях (шаблонах) Flex.
Таблица 4. Специальные символы, использующиеся в регулярных выражениях
Flex
Символ шаблона |
|
|
Значение |
|
|
|
|
|
|
||
. |
Соответствует любому символу, кроме \n |
|
|
||
|
|
||||
[] |
Класс символов, соответствующий любому из символов, описанных |
||||
|
внутри скобок. Знак '-' указывает на диапазон символов. Например, |
||||
|
[0-9] означает то же самое, что и [0123456789], [a-z] – любая |
||||
|
прописная буква латинского алфавита, [A-z] – все заглавные и |
||||
|
прописные буквы латинского алфавита, а также 6 знаков пунктуации, |
||||
|
находящихся между Z и a в таблице ASCII. Если символ '-' или ']' |
||||
|
указан в качестве первого символа после открывающейся квадратной |
||||
|
скобки, значит он включается в описываемый класс символов. |
||||
|
Управляющие (escape) последовательности языка Си также могут |
||||
|
указываться внутри квадратных скобок, например, \t. |
|
|||
^ |
Внутри квадратных скобок используется как отрицание, например, |
||||
|
регулярное |
выражение |
[^\t\n] |
соответствует |
любой |
|
последовательности символов, не содержащей табуляций и |
||||
|
переводов строки. |
|
|
|
|
|
Если просто используется в начале шаблона, то означает начало |
||||
|
строки. |
|
|
|
|
$ |
При использовании в конце регулярного выражения означает конец |
||||
|
строки. |
|
|
|
|
{} |
Если в фигурных скобках указаны два числа, то они |
||||
|
интерпретируются как минимальное и максимальное количество |
||||
|
повторений шаблона, предшествующего скобкам. Например, A{1,3} |
||||
13
Таблица 4. Специальные символы, использующиеся в регулярных выражениях
Flex
Символ шаблона |
|
|
Значение |
|
|
|
|
||||
|
соответствует повторению буквы А от одного до трёх раз, а 0{5} – |
||||
|
00000. Если внутри скобок находится имя регулярного определения, |
||||
|
то это просто обращение к данному определению по его имени. |
||||
\ |
Используется в escape-последовательностях языка Си и для задания |
||||
|
метасимволов, например, \* – символ ‘*’ в отличие от * (см. ниже). |
||||
* |
Повторение регулярного выражения, указанного до *, 0 или более |
||||
|
раз. Например, [ \t]* соответствует регулярному выражению для |
||||
|
пробелов и/или табуляций, отсутствующих или повторяющихся |
||||
|
несколько раз. |
|
|
|
|
+ |
Повторение регулярного выражения, указанного до +, один или более |
||||
|
раз. Например, [0-9]+ соответствует строкам 1, 111 или 123456. |
||||
? |
Соответствует повторению регулярного выражения, указанного до ?, |
||||
|
0 или 1 раз. Например, -?[0-9]+ соответствует знаковым числам с |
||||
|
необязательным минусом перед числом. |
|
|
||
| |
Оператор «или». Например, true|false соответствует любой из |
||||
|
двух строк. |
|
|
|
|
() |
Используются для группировки нескольких регулярных выражений в |
||||
|
одно. |
Например, |
a(bc|de) |
соответствует |
входным |
|
последовательностям: abc или ade. |
|
|
||
/ |
Так называемый присоединенный контекст. Например, регулярное |
||||
|
выражение 0/1 соответствует 0 во входной строке 01, но не |
||||
|
соответствует ничему в строках 0 или 02. |
|
|||
“ ” |
Любое символы в кавычках рассматриваются как строка символов. |
||||
|
Метасимволы, такие как \*, теряют своё значение и |
||||
|
интерпретируются как два символа: \ и *. |
|
|||
Лексический анализатор на языке Flex для грамматики из предыдущего раздела представлен в листинге 3.
В первой строке данной программы указаны опции, которые должны быть учтены при построении лексического анализатора. Для этого используется формат
%option имя_опции
Те же самые опции можно было бы указать при компиляции в командной строке как
--имя_опции
Для отключения опции перед её именем следует указать «no», как в случае с noyywrap. Полный список допустимых опций можно найти в документации по Flex [6, 8].
Первые версии генератора лексических анализаторов Lex вызывали функцию yywrap() при достижении конца входного потока yyin. В случае, если нужно было продолжить анализ входного текста из другого файла, yywrap возвращала 0 для продолжения сканирования. В противном случае возвращалась 1.
14
Листинг 3. Лексический анализатор на языке Flex
%option noyywrap yylineno %{
#include <stdio.h> int ch;
%}
digit[0-9] letter[a-zA-Z] delim[();] oper[<>=]
ws[ \t\n]
%%
for { printf("KEYWORD (%d, %d): %s\n", yylineno, ch, yytext); ch += yyleng;
}
do { printf("KEYWORD (%d, %d): %s\n", yylineno, ch, yytext); ch += yyleng;
}
("_"|{letter})("_"|{letter}|{digit})* {
printf("IDENTIFIER (%d, %d): %s\n", yylineno, ch, yytext); ch += yyleng;
}
[-+]?({digit}*\.{digit}+|{digit}+\.|{digit}+) ([eE][-+]?{digit}+)?[flFL]? {
printf("NUMBER (%d, %d): %s\n", yylineno, ch, yytext); ch += yyleng;
}
{oper} { printf("OPERATION (%d, %d): %s\n", yylineno, ch, yytext); ch += yyleng;
}
":=" { printf("OPERATION (%d, %d): %s\n", yylineno, ch, yytext); ch += yyleng;
}
{delim} { printf("DELIMITER (%d, %d): %s\n", yylineno, ch, yytext); ch += yyleng;
}
{ws}+ { ch += yyleng; }
. { printf("Unknown character (%d, %d): %s\n", yylineno, ch, yytext); ch += yyleng;
}
%%
int main(int argc, char **argv)
{
if(argc < 2)
15