* программу.
* Обратите внимание на то, что в
* этой Lex-программе отсутствуют
* активные правила. Это сделано
* в связи с тем, что нет
* необходимости иметь правила,
* которые всегда активны.
* Все цепочки символов входного
* потока, не распознанные в
* правилах, копируются в выходной
* поток символов.
*/
LETTER [A-ZА-Яa-zа-я_]
DIGIT [0-9]
IDENT {LETTER}({LETTER}|{DIGIT})*
INT {DIGIT}+
FIXED {INT}?.{INT}
WHISP [ 0*
%%
BEGIN Normal;
<Normal>"{" BEGIN IC1;
<IC1>[^}] ;
<IC1>"}" BEGIN Normal;
<Normal>"(*" BEGIN IC2;
<IC2>[^*]|[^)] ;
<IC2>>"*)" BEGIN Normal;
<Normal>'([^']|'')*' return( строка );
<Normal>"<>" return( не_равно );
<Normal>"=" return( равно );
<Normal>"<" return( меньше );
<Normal>">" return( больше );
<Normal>">=" return(больше_или_равно);
<Normal>"<=" return(меньше_или_равно);
<Normal>".." return( точка_точка );
<Normal>"+" return( плюс );
<Normal>"-" return( минус );
<Normal>":=" return( присвоить );
<Normal>"*" return( умножить );
<Normal>"/" return( разделить );
<Normal>mod return( t_mod );
24
<Normal>div return( t_div );
<Normal>and return( t_and );
<Normal>or return( t_or );
<Normal>not return( t_not );
<Normal>"(" return( lpar );
<Normal>")" return( rpar );
<Normal>"[" return( lbracket );
<Normal>"]" return( rbracket );
<Normal>"," return( comma );
<Normal>":" return( colon );
<Normal>"^" return( circumflex );
<Normal>";" return( semicolon );
<Normal>write return( Write );
<Normal>writeln return( Writeln );
<Normal>label return( t_label );
<Normal>program return( );
<Normal>const x( "константы" ) ;
<Normal>type x( "типы" ) ;
<Normal>var x( "перем" ) ;
<Normal>procedure x( "процедура" ) ;
<Normal>function x( "функция" ) ;
<Normal>begin x( "начало" ) ;
<Normal>end{WHISP}. x( "конец прогр" ) ;
<Normal>end x( "конец" ) ;
<Normal>array x( "массив" ) ;
<Normal>of x( "из" ) ;
<Normal>record x( "запись" ) ;
<Normal>case x( "выбор" ) ;
<Normal>in x( "в" ) ;
<Normal>file x( "файл" ) ;
<Normal>for x( "для" ) ;
<Normal>to x( "к" ) ;
<Normal>downto x( "вниз к" ) ;
<Normal>do x( "выполн" ) ;
<Normal>while x( "пока" ) ;
<Normal>repeat x( "повт" ) ;
<Normal>until x( "до" ) ;
<Normal>set x( "множество" ) ;
<Normal>with x( "с" );
<Normal>nil x( "nil" ) ;
<Normal>if x( "если" ) ;
<Normal>then x( "то" ) ;
<Normal>else x( "иначе" ) ;
<Normal>{FIXED} x( "float" ) ;
<Normal>{INT} x( "ц.б.з" ) ;
<Normal>{IDENT} x( "идент" ) ;
<Normal>[ 0] ;
%%
x( s )
char *s ;
{
25
printf("%-15.15s 177> %s <1770,
s, yytext ) ;
}
4. Структура файла lex.yy.c
lex строит программу - лексический анализатор на языке
Си, которая размещается в файле со стандартным именем
lex.yy.c. Эта программа содержит две основных функции и нес-
колько вспомогательных. Основные - это:
функция yylex()
Она содержит разделы действий всех правил, которые
определены пользователем;
функция yylook()
Она реализует детерминированный конечный автомат, кото-
рый осуществляет разбор входного потока символов в
соответствии с регулярными выражениями правил Lex-
программы.
Вспомогательные функции, которые являются подпрограм-
мами ввода-вывода. К ним относятся:
input()
читает и возвращает символ из входного потока символов;
unput(c)
возвращает символ обратно во входной поток для повтор-
ного чтения;
output(c)
выводит в выходной поток символ c.
Эти функции определены как макроподстановки следующим
образом:
input -
fprintf( fout, "%s%d%s0,
"#define input() (((yytchar=yysptr>yysbuf
ctable['0],
"?(yylineno++,yytchar):yytchar)==EOF?0:yyt
unput -
26
#define unput(c){
yytchar = (c);
if( yytchar == '\n' ) yylineno--;
*yysptr++ = yytchar;
}
output -
#define output(c) putc(c,yyout)
Эти функции можно изменить, указав им те же имена и
разместив в разделе программ пользователя.
При сборке программы лексического анализа редактор
связи ld по флагу -ll подключает головную функцию main, если
она не определена. Ниже приведен текст этой функции из биб-
лиотеки /usr/lib/libl.a
# include "stdio.h"
main(){
yylex();
exit(0);
}
5. Функция yywrap()
Функция yywrap используется для определения конца
файла, из которого лексический анализатор читает поток сим-
волов. Если yywrap возвращает 1, лексический анализатор
прекращает работу. Однако, иногда имеется необходимость
начать ввод данных из другого источника и продолжить работу.
В этом случае пользователь должен написать свою подпрограмму
yywrap, которая организует новый входной поток и возвращает
0, что служит сигналом к продолжению работы анализатора. По
умолчанию yywrap всегда возвращает 1 при завершении входного
потока символов.
В Lex-программе невозможно записать правило, которое
будет обнаруживать конец файла. Единственный способ это сде-
лать - использовать фунцию yywrap. Эта функция также удобна,
когда необходимо выполнить какие-либо действия по завершению
входного потока символов, определив в разделе программ поль-
зователя новый вариант функции yywrap. Пример:
27
%START AA BB CC
/*
* Строится лексический анализатор,
* который распознает наличие
* включений файлов в Си-программе,
* условных компиляций,
* макроопределений,
* меток и головной функции main.
* Анализатор ничего не выводит, пока
* осуществляется чтение входного
* потока, а по его завершении
* выводит статистику.
*/
БУКВА = [A-ZА-Яa-zа-я_]
ЦИФРА [0-9]
ИДЕНТИФИКАТОР {БУКВА}({БУКВА}|{ЦИФРА})*
int a1,a2,a3,b1,b2,c;
%%
{a1 = a2 = a3 = b1 = b2 = c = 0;}
^# BEGIN AA;
^[ \t]*main BEGIN BB;
^[ \t]*{ИДЕНТИФИКАТОР} BEGIN CC;
\t ;
\n BEGIN 0;
<AA>define { a1++; }
<AA>include { a2++; }
<AA>ifdef { a3++; }
<BB>[^\,]*","[^\,]*")" { b1++; }
<BB>[^\,]*")" { b2++; }
<CC>":"/[ \t] { c++; }
%%
yywrap(){
if( b1 == 0 && b2 == 0 )
printf("В программе\
отсутствует функция main.\n");
if( b1 >= 1 && b2 >= 1 ){
printf("Многократное\
определение функции main.\n");
} else {
if(b1 == 1 )
printf("Функция main\
28
с аргументами.\n");
if( b2 == 1 )
printf("Функция main\
без аргументов.\n");
}
printf("Включений файлов: %d.\n",a2);
printf("Условных компиляций: %d.\n",a3);
printf("Определений: %d.\n",a1);
printf("Меток: %d.\n",c);
return(1);
}
Оператор return(1) в функции yywrap указывает, что лек-
сический анализатор должен завершить работу. Если необходимо
продолжить работу анализатора для чтения данных из нового
файла, нужно указать return(0), предварительно осуществив
операции закрытия и открытия файлов и, в этом случае, анали-
затор продолжит чтение и обработку входного потока. Однако,
если yywrap не возвращает 1, то это приводит к бесконечному
циклу.
6. Функция REJECT
Обычно lex разделяет входной поток, не осуществляя
поиск всех возможных соответствий каждому выражению. Это
означает, что каждый символ рассматривается один и только
один раз. Предположим, что мы хотим подсчитать все вхождения
цепочек she и he во входном тексте. Для этого мы могли бы
записать следующие правила:
she s++;
he h++;
. |
\n ;
Так как she включает в себя he, анализатор не распознает те
вхождения he, которые включены в she, так как, прочитав один
раз she, эти символы он не вернет во входной поток.
Иногда желательно переопределить этот выбор. Действие
функции REJECT означает "выбрать следующую альтернативу".
Это приводит к тому, что каким бы ни было правило, после
него необходимо выполнить второй выбор. Соответственно изме-
нится и положение указателя во входном потоке:
29
she { s++; REJECT; }
he { h++; REJECT; }
. |
\n ;
Здесь после выполнения одного правила символы возвращаются
назад во входной поток, и выполняется другое правило.
Функция REJECT полезна в том случае, когда она применя-
ется для определения всех вхождений какого-либо объекта,
причем вхождения могут перекрываться или включать друг
друга. Предположим, необходимо получить из одного потока
таблицу всех двухбуквенных сочетаний, которые обычно перек-
рываются, например, слово the содержит как th, так и he.
Допустим, имеется двумерный массив digram, тогда:
%%
[a-z][a-z] {
digram[yytext[0]][yytext[1]]++;
REJECT;
}
\n ;
Здесь REJECT используется для выделения буквенных пар, начи-
нающихся на каждой букве, а не на каждой следующей.
7. Функции yyless и yymore
В обычной ситуации содержимое yytext обновляется всякий
раз, когда на входе появляется следующая строка. Напомним,
что в yytext всегда находятся символы распознанной последо-
вательности. Иногда возникает необходимость добавить к теку-
щему содержимому yytext следующую распознанную цепочку сим-
волов. Для этой цели используется функция yymore. Формат
вызова этой функции:
yymore()
В некоторых случаях возникает необходимость использовать не
все символы распознанной последовательности в yytext, а
только необходимое их число. Для этой цели используется
функция yyless. Формат ее вызова:
yyless(n)
где n указывает, что в данный момент необходимы только n
символов строки в yytext. Остальные найденные символы будут
возвращены во входной поток.
Пример использования фунцкии yymore:
30
.
.
.
\"[^"]* {
if( yytext[yyleng - 1] == '\\'){
yymore();
}else{
/*
* здесь должна быть часть
* программы, обрабатывающая
* закрывающую кавычку.
*/
}
}
.
.
.
В этом примере распознаются строки симвoлов, взятые в двой-
ные кавычки, причем символ двойная кавычка внутри этой
строки может изображаться с предшествующей косой чертой.
Анализатор должен распознавать кавычку, ограничивающую
строку, и кавычку, являющуюся частью строки, когда она изоб-
ражена как \".
Допустим, на вход поступает строка "абв\"где". Сначала
будет распознана цепочка "абв\ и, так как последним символом
в этой цепочке будет символ "\", выполнится вызов yymore().
В результате к цепочке "абв\ будет добавлено "где, и в
yytext мы получим: "абв\"где, что и требовалось.
Пример использования фунции yyless:
.
.
.
=-[A-ZА-Яa-zа-я] {
printf("Oператор (=-) двусмысленный.\n");
yyless(yyleng - 2);
/*
* здесь необходимо указать
* действия для случая "=-"
*/
}
.
.
.
В этом примере разрешается двусмысленность выражения "=-
31
буква" в языке Си. Это выражение можно рассматривать как
"=- буква" (равносильно "-=" )
или
"= -буква"
Предположим, что желательно эту ситуацию рассматривать как
"= -буква" и выводить пердупреждение. Указанное в примере
правило распознает эту ситуацию и выводит предупреждение.
Затем, в результате вызова "yyless(yyleng - 2);" два сим-
вола "-буква" будут возвращены во входной поток, а знак "="
останется в yytext для обработки, как в нормальной ситуации.
Таким образом, при продолжении чтения входного потока уже
будет обрабатываться цепочка "-буква", что и требовалось.
8. Совместное использование lex и yacc
yacc требует указание лексическому анализатору имени
yylex(). Именно поэтому эта функция так называется в lex.
Известно, что yacc строит выходной файл y.tab.c .
Основной в файле y.tab.c является функция yyparse, реализую-
щая алгоритм грамматического разбора. Функция yyparse содер-
жит многократное обращение к функции лексического анализа
yylex.
Для обеспечения корректной работы грамматического ана-
лизатора функция yylex должна быть согласована с конкретной
спецификацией грамматики и удовлетворять определенным требо-
ваниям.
Пользователь при описании грамматики решает, какие
конструкции целесообразнее непосредственно выделять из вход-
ного текста на этапе лексического анализа.
Сложность лексического анализатора зависит от того,
какие структурные единицы взяты за основу при описании грам-
матических правил. Детализовав грамматику до отдельных сим-
волов, можно обойтись простейшим лексическим анализатором.
Однако, в этом случае число правил растет, а грамматический
разбор оказывается менее эффективным. Поэтому пользователь
обычно должен найти некоторый компромисс при выборе набора
лексем.
Заметим, что ключевые слова описываемого входного языка
часто бывает удобно считать лексемами. Имена лексем могут
совпадать с этими ключевыми словами, недопустимым является
лишь совпадение имен лексем с зарезервированными словами
языка Си.
Основная задача функции yylex состоит во вводе из вход-
ного потока ряда очередных символов до выявления конструк-
ции, соответствующей одной из лексем, и возвращении номера
32
типа этой лексемы и, когда это необходимо, значения этой
лексемы.
Все виды лексем, кроме литералов, обозначаются некото-
рыми именами и под этими именами фигурируют в Yacc-
программе, где объявление имен лексем осуществляется дирек-
тивой token:
%token <список имен лексем>
Благодаря объявлению имен лексем в директиве token, yacc
отличает имена лексем от имен нетерминальных символов.
Пример объявления имен лексем в Yacc-программе:
%token IDENT CONST ЗНАК IF THEN GOTO
При первом появлении лексемы или литерала в секции объявле-
ний Yacc-программы за каждым из них может следовать неотри-
цательное целое число, рассматриваемое как номер_типа лек-
семы.
По умолчанию номера типов всех лексем определяются yacc
следующим образом:
- для литерала номером типа лексемы считается числовое
значение данного литерального символа, рассматривае-
мого как однобайтовое целое число;
- лексемы, обозначенные именами, в соответствии с оче-
редностью их объявления получают последовательные
номера, начиная с 257.
Для каждого имени лексемы независимо от того, переопре-
делен ли ее номер пользователем, yacc генерирует в выходном
файле y.tab.c оператор препроцессора:
#define <имя_лексемы> <номер_типа>
Значение, возвращаемое функцией yylex, является номером типа
лексемы. Таким образом, список лексем и номера их типов ука-
зываются в Yacc-программе, а определения этих лексем в Lex-
программе. Возникает проблема соответствия номеров типов
лексем в файлах y.tab.c и lex.yy.c, котороя разрешается сле-
дующим образом:
- при вызове yacc с флагом -d последовательность опера-
торов #define помещается в файл y.tab.h.;
- этот файл посредством оператора #include включается в
Lex-программу.
33
В процедуре лексического анализа кроме выделения лексем
можно предусмотреть некоторую обработку лексем определенных
типов, в частности, запоминание конкретных значений лексем.
Примером значения лексемы могут служить числовое значе-
ние символа - цифры, вычисленное значение константы, адрес
идентификатора в таблице имен (построение таблицы имен осу-
ществляет lex). Кроме того, эти значения обычно требуется
передать грамматическому анализатору. С этой целью нужное
значение должно быть присвоено внешней переменной целого
типа с именем yylval. Если функция yylex находится в отдель-
ном файле, то эта переменная должна быть объявлена:
extern int yylval;
Уточним, что значением_лексемы будем называть значение,
присвоенное при ее распознавании переменной yylval. Заметим,
что в yylval всегда должно находится значение последней
выделенной лексемы.
Допустим, мы располагаем Yacc-программой в файле
source.y и Lex-программой в файле source.l, которые необхо-
димо собрать в работающую программу. Существует два способа
сборки:
- сборка Lex- и Yacc-программы с созданием файла
y.tab.h;
- сборка Lex- и Yacc-программы без создания файла
y.tab.h.
Рассмотрим первый способ сборки.
Ниже приведен пример makefile для программы make, кото-
рая осуществляет последовательную обработку и сборку эих
программ и размещает результат в файле program:
34
program: y.tab.o lex.yy.o
cc y.tab.o lex.yy.o -ly -ll -o program
y.tab.o: y.tab.c
cc -c -O y.tab.c
lex.yy.o: lex.yy.c y.tab.h
cc -c -O lex.yy.c
y.tab.h:
y.tab.c: source.y
yacc -d source.y
lex.yy.c: source.l
lex -v source.l
clear:
rm -f yy.tab.? lex.yy.? program
В файле source.l размещена Yacc-программа, реализующая
небольшой настольный калькулятор. Калькулятор имеет 52
регистра, помеченных буквами от A до z, и разрешает исполь-
зовать арифметические выражения, содержащие операции +, -,
*, /, % (остаток от деления), & (побитовое и), | (побитовое
или) и присваивание. Как и в Си, целые числа, начинающиеся с
0, считаются восьмеричными, все остальные - десятичными.
Результат всегда выводится десятичными числами.
Калькулятор работает в интерактивном режиме с построч-
ным формированием выхода, может читать задание из файла и
выводить результат в файл.
Знак "=" используется для присваивания, а для выведения
результата достаточно нажать клавишу <ВК>. Распознаются ско-
бочные структуры, изменяющие порядок приоритетов при вычис-
лениях. Калькулятор работает только с целыми типа integer.
35
%token DIGIT LETTER
%left '|'
%left '&'
%left '+' '-'
%left '*' '/' '%'
%left UMINUS
%{
int base, regs[26];
%}
%%
list:
|
list stat '\n'
|list stat error '\n' { yyerrok; }
stat:
expr { printf( "%d\n",$1 ); }
|LETTER '=' expr { regs[$1]=$3; }
expr:
'(' expr ')' { $$=$2; }
|expr '+' expr { $$=$1+$3; }
|expr '-' expr { $$=$1-$3; }
|expr '*' expr { $$=$1*$3; }
|expr '/' expr { $$=$1/$3; }
|expr '%' expr { $$=$1%$3; }
|expr '&' expr { $$=$1&$3; }
|expr '|' expr { $$=$1|$3; }
|'-' expr %prec UMINUS { $$= -$2; }
| LETTER { $$=regs[$1]; }
| number;
number:
DIGIT { $$=$1;
base=10;
if($1==0) base=8; }
|number DIGIT { $$=base*$1+$2; }
В файле source.l размещена Lex-программа лексичского
анализатора для этого калькулятора:
36
%{
#include "y.tab.h"
extern int yylval;
%}
%%
^\n ;
[ \t]* ;
[A-Za-z] {
yylval = yytext[yyleng-1] - 'a';
return(LETTER);}
[0-9] {
yylval = yytext[yyleng-1] - '0';
return(DIGIT);}
Рассмотрим второй способ сборки. Makefile теперь
существенно проще:
program: y.tab.c lex.yy.c
cc -O y.tab.c -ly -ll -o program
y.tab.c: source.y
yacc source.y
lex.yy.c: source.l
lex -v source.l
clear:
rm -f y.tab.? lex.yy.? program
Но в файлах source.y и source.l произойдут следующие измене-
ния. В разделе входной информации для Yacc-программы необхо-
димо указать строку #include lex.yy.c, а из Lex-программы
необходимо убрать строку #include "y.tab.h". Теперь файл
source.y выглядит следующим образом:
37
%token DIGIT LETTER
%left '|'
%left '&'
%left '+' '-'
%left '*' '/' '%'
%left UMINUS
%{
#include "lex.yy.c"
int base, regs[26];
%}
%%
list:
|
list stat '\n'
|list stat error '\n' { yyerrok; }
stat:
expr { printf( "%d\n",$1 ); }
|LETTER '=' expr { regs[$1]=$3; }
expr:
'(' expr ')' { $$=$2; }
|expr '+' expr { $$=$1+$3; }
|expr '-' expr { $$=$1-$3; }
|expr '*' expr { $$=$1*$3; }
|expr '/' expr { $$=$1/$3; }
|expr '%' expr { $$=$1%$3; }
|expr '&' expr { $$=$1&$3; }
|expr '|' expr { $$=$1|$3; }
|'-' expr %prec UMINUS { $$= -$2; }
| LETTER { $$=regs[$1]; }
| number;
number:
DIGIT { $$=$1;
base=10;
if($1==0) base=8; }
|number DIGIT { $$=base*$1+$2; }
А файл source.l выглядит следующим образом:
38
%{
extern int yylval;
%}
%%
^\n ;
[ \t]* ;
[A-Za-z] {
yylval = yytext[yyleng-1] - 'a';
return(LETTER);}
[0-9] {
yylval = yytext[yyleng-1] - '0';
return(DIGIT);}
9. Использование Ратфора
lex можно использовать для генерации программ лексичес-
кого анализа на Ратфоре. Для этого в первой строке раздела
определений необходимо указать %R. Все сказанное выше об
использовании Си в качестве host-языка относится и к Рат-
фору. Необходимо учесть, что Ратфор имеет свою библиотеку
ввода-вывода. Однако, состав функций lex для Ратфора тот же,
что и для Си. Есть и функция, выделенная только для Ратфора
- lexshf. Функция lexshf переводит внутреннее представление
символа (младший байт) из Си во внутреннее представление
символа в Фортране (старший байт).
Дествия правил Lex-программы для Ратфора оформляются в
виде вычисляемых goto в выходном файле, который называется
lex.yy.r.
Допустим, имеется исходный файл source.l с Ратфором в
качестве host-языка, тогда для получения лексического анали-
затора необходимы следующие действия:
% lex source.l
% rc lex.yy.r -llr
Напомним, что в Ратфоре индексы массивов начинаются с 1,
поэтому, например, yytex[yyleng] - это последний полученный
из входного потока символ.
10. Флаги Lex
-t поместить результат в стандартный файл вывода, а не в
файл lex.yy.c;
-v вывести размеры внутренних таблиц;
-f ускорить работу, не упаковывая таблицы (только для
небольших программ);
39
-n не выводить размеры таблиц (устанавливается по умолча-
нию);
-d используется при отладке lex.
Имеется возможность собрать анализатор для диагностики.
Для этого необходимо компиляцию файла lex.yy.c осуществлять
с подключением разделов диагностики:
cc -d -DLEXDEBUG lex.yy.c
При работе полученного таким образом анализатора будет выво-
диться диагностика действий. Флаг -d, кроме того, позволяет
проверить текст программы lex.yy.c с помощью текстового
отладчика cdeb.
40
СОДЕРЖАНИЕ
. Аннотация ......................................... 2
1. Введение .......................................... 3
2. Регулярные выражения в Lex-правилах ............... 8
2.1. Обозначения символов в выражениях ............... 8
2.2. Операторы регулярных выражений .................. 9
2.3. Оператор выделения классов символов ............. 9
2.4. Повторители ..................................... 9
2.5. Операторы выбора ................................ 10
2.6. Оператор {} ..................................... 11
2.7. Оператор <>. Служебные слова START и BEGIN ...... 12
3. Структура Lex-программы ........................... 15
3.1. Раздел определений Lex-программы ................ 15
3.2. Раздел правил ................................... 18
3.2.1. Действия в правилах Lex-программы ............. 19
3.2.2. Порядок действия активных правил .............. 21
3.3. Раздел программ пользователя .................... 22
3.4. Комментарии Lex-программы ....................... 22
3.5. Примеры Lex-программ ............................ 22
4. Структура файла lex.yy.c .......................... 26
5. Функция yywrap() .................................. 27
6. Функция REJECT .................................... 29
7. Функции yyless и yymore ........................... 30
8. Совместное использование lex и yacc ............... 32
9. Использование Ратфора ............................. 39
10. Флаги Lex ......................................... 39
41