Страница:
k - упакованных классов символов 1000
o - выходных элементов 1500
Для того чтобы определить, каковы размеры таблиц и насколько
они заняты, можно использовать флаг -v, например:
% lex -v source.l
33/600 узлов(%e)
97/1500 позиций(%p)
17/300 состояний(%n)
2551 переходов
18/1000 упакованных классов символов(%k)
41/1500 упакованных переходов(%a)
68/1500 выходных элементов(%o)
%
Здесь показано сообщение, которое выводит lex по флагу -v.
Число перед символом "/" указывает сколько элементов массива
занято, а число за символом "/" указывает установленный раз-
мер массива.
КОММЕНТАРИИ в разделе определений задаются в форме
host-языка и должны начинаться не с первой колонки строки.
3.2. Раздел правил
Все, что указано после первой пары %% и до конца Lex-
программы или до второй пары %%, если она указана, относится
к разделу правил. Раздел правил может содержать правила и
фрагменты программ. Фрагменты программ, содержащиеся в раз-
деле правил, становятся частью функции yylex файла lex.yy.c,
в которой осуществляется выполнение действий активных пра-
вил. Фрагмент программы указывается следующим образом:
%{
строки
фрагмента
программы
%}
Например:
%%
%{
#include file.h
%}
.
.
.
18
Здесь строка "#include file.h" станет строкой функции
yylex().
Раздел правил может включать список активных и неактив-
ных (помеченных) правил. Активные и неактивные правила
могут быть указаны в любом порядке, в том числе быть "пере-
мешанными" в списке. Активные правила выполняются всегда,
неактивные только по ссылке на них оператором BEGIN.
Активное правило имеет вид:
ВЫРАЖЕНИЕ ДЕЙСТВИЕ
Неактивное правило имеет вид:
<МЕТКА>ВЫРАЖЕНИЕ ДЕЙСТВИЕ
или
<СПИСОК_МЕТОК>ВЫРАЖЕНИЕ ДЕЙСТВИЕ
где СПИСОК_МЕТОК имеет вид:
метка1,метка2,...
В качестве первого правила раздела правил может быть правило
вида:
BEGIN МЕТКА;
В этом правиле отсутствует ВЫРАЖЕНИЕ, и первым действием в
разделе правил будет активизация помеченных правил. Для
возвращения автомата в исходное состояние можно использовать
действие:
BEGIN 0;
Важно отметить следующее. Если Lex-программа содержит актив-
ные и неактивные правила, то активные правила работают
всегда. Оператор "BEGIN МЕТКА;" просто расширяет список
активных правил, активируя помеченные меткой МЕТКА. А опера-
тор "BEGIN 0;" удаляет из списка активных правил все поме-
ченные правила, которые до этого были активированы. Кроме
того, если из помеченного и активного в данный момент вре-
мени правила осуществляется действие BEGIN МЕТКА, то из
помеченных правил активными останутся только те, которые
помечены меткой МЕТКА.
3.2.1. Действия в правилах Lex-программы
Действие можно представлять либо как оператор lex, нап-
ример, "BEGIN МЕТКА;", либо как оператор Си. Если имеется
необходимость выполнить достаточно большой набор преобразо-
ваний, то действие оформляют как блок Си-программы (он
19
начинается открывающей фигурной скобкой и завершается закры-
вающей фигурной скобкой), содержащий необходимые фрагменты.
Действие в правиле указывается через не менее, чем один
пробел или табуляцию после выражения (обязательно в той же
строке, где и выражение), а его продолжение может быть ука-
зано в следующих строках только в том случае, если действие
оформлено как блок Си-программы.
Область действия переменных, объявленных внутри блока,
распространяется только на этот блок. Внешними переменными
для всех действий будут являться только те переменные, кото-
рые объявлены в разделе определений Lex-программы.
Действия в правилах Lex-программы выполняются, если
правило активно, и если автомат распознает цепочку символов
из входного потока как соответствующую регулярному выражению
данного правила. Однако, одно действие выполняется всегда -
оно заключается в копировании входного потока символов в
выходной. Это копирование осуществляется для всех входных
строк, которые не соответствуют правилам, преобразующим эти
строки. Комбинация символов, не учтенная в правилах и поя-
вившаяся на входе, будет напечатана на выходе. Можно ска-
зать, что действие - это то, что делается вместо копирования
входного потока символов на выход. Часто бывает необходимо
не копировать на выход некоторую цепочку символов, которая
удовлетворяет некоторому регулярному выражению. Для этой
цели используется пустой оператор Си, например:
[ 0 ;
Это правило игнорирует (запрещает) вывод пробелов, табуляций
и символа новая строка. Запрет выражается в том, что на
указанныe символы во входном потоке осуществляется действие
";" - пустой оператор Си, и эти символы не копируются в
выводной поток символов.
Существует возможность для нескольких регулярных выра-
жений указывать одно действие. Для этого используется символ
"|", который указывает, что действие данного правила совпа-
дает с действием для следующего, например:
" " |
|
;
Результат будет тот же, что и в примере, указанном выше.
Когда необходимо вывести или преобразовать текст, соот-
ветствующий некоторому регулярному выражению, используется
внешний массив символов, который формирует lex. Называется
он yytext и доступен в действиях правил. Например:
20
[A-Z]+ printf("%s",yytext);
По этому правилу распознается слово, содержащее прописные
латинские буквы и выводится с помощью printf, если оно выде-
лено. Операция вывода распознанного выражения используется
очень часто, поэтому имеется сокращенная форма записи этого
действия:
[A-Z]+ ECHO;
Результат действия этого правила будет аналогичен результату
предыдущего примера. В выходном файле lex.yy.c ECHO опреде-
лено как макроподстановка:
#define ECHO fprintf(yyout, "%s",yytext);
Когда необходимо знать длину обнаруженной последовательности
символов, используется счетчик найденных символов yyleng,
который также доступен в действиях. Например:
[A-Z]+ printf("%c",yytext[yyleng-1]);
В этом примере будет выводится последний символ слова, соот-
ветствующего регулярному выражению [A-Z]+. Рассмотрим еще
один пример:
[A-Z]+ {число_слов++;число_букв += yyleng;}
Здесь ведется подсчет числа распознанных слов и количества
символов во всех словах.
3.2.2. Порядок действия активных правил
Список правил Lex-программы может содержать активные и
неактивные правила, размещенные в любом порядке в разделе
правил. В процессе работы лексического анализатора список
активных правил может видоизменяться за счет действий опера-
тора BEGIN. В процессе распознавания символов входного
потока может оказаться так, что одна цепочка символов будет
удовлетворять нескольким правилам и, следовательно, возни-
кает проблема: действие какого правила должно выполняться?
Для разрешения этого противоречия можно использовать
квантование (разбиение) регулярных выражений этих правил
Lex-программы на такие новые регулярные выражения, которые
дадут, по возможности, однозначное распознавание лексемы.
Однако, когда это не сделано, lex использует определенный
детерминированный механизм разрешения такого противоречия:
- выбирается действие того правила, которое распознает
наиболее длинную последовательность символов из вход-
ного потока;
21
- если несколько правил распознают последовательности
символов одной длины, то выполняется действие того
правила, которое записано первым в списке раздела
правил Lex-программы.
Рассмотрим пример:
.
.
.
[Мм][Аа][Йй] ECHO;
[А-Яа-я]+ ECHO;
.
.
.
Слово "Май" распознают оба правила, однако, выполнится пер-
вое из них, так как и первое, и второе правило распознали
лексему одинакового размера (3 символа). Если во входном
потоке будет, допустим, слово "майский", то первые 3 символа
удовлетворяют первому правилу, а все 7 символов удовлетво-
ряют второму правилу, следовательно, выполнится второе пра-
вило, так как ему удовлетворяет более длинная последователь-
ность символов.
3.3. Раздел программ пользователя
Все, что размещено за вторым набором %%, относится к
разделу программ пользователя. Содержимое этого раздела
копируется в выходной файл lex.yy.c без каких-либо измене-
ний. В файле lex.yy.c строки этого раздела рассматриваются
как функции в смысле Си. Эти функции могут вызываться в
действиях правил и, как обычно, передавать и возвращать зна-
чения аргументов.
3.4. Комментарии Lex-программы
Комментарии можно указывать во всех разделах Lex-
программы. Формат комментариев должен соответствовать фор-
мату комментариев host-языка. Однако, в каждом разделе Lex-
программы комментарии указываются по разному. В разделе
определений комментарии должны начинаться не с первой пози-
ции строки. В разделе правил комментарии можно указывать
только внутри блоков, принадлежащих действиям. В разделе
программ пользователя комментарии указываются как и в host-
языке.
3.5. Примеры Lex-программ
Пример1.
22
%Start KOMMENT
/*
* Программа записывает в
* стандартный файл вывода
* комментарии Си-программы.
* Обратите внимание на то, что
* здесь строки комментариев указаны
* не с первой позиции строки!
*/
КОММ_НАЧАЛО "/*"
КОММ_КОНЕЦ "*/"
%%
{КОММ_НАЧАЛО} { ECHO;
BEGIN KOMMENT;}
[0* ;
<KOMMENT>[^*]* ECHO;
<KOMMENT>[^/] ECHO;
<KOMMENT>{КОММ_КОНЕЦ} {
ECHO;
printf("0);
/*
* Здесь приведен пример
* использования комментариев в
* разделе правил Lex-программы.
* Обратите внимание на то, что
* комментрий указан внутри блока,
* определяющего действие правила.
*/
BEGIN 0;}
%%
/*
* Здесь приведен пример комментариев
* в разделе программ пользователя.
*/
Пример 2.
23
%Start IC1 IC2 Normal
/*
* Отладочный фрагмент
* Lex-программы, которая строит
* лексический анализатор для
* компилятора языка Паскаль.
* Действие return(...)
* возвращает тип лексемы в
* в вызывающую анализатор
* программу.
* Обратите внимание на то, что в
* этой 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
следующим образом:
- для литерала номером типа лексемы считается числовое
значение данного литерального символа, рассматривае-
мого как однобайтовое целое число;
- лексемы, обозначенные именами, в соответствии с оче-
редностью их объявления получают последовательные
o - выходных элементов 1500
Для того чтобы определить, каковы размеры таблиц и насколько
они заняты, можно использовать флаг -v, например:
% lex -v source.l
33/600 узлов(%e)
97/1500 позиций(%p)
17/300 состояний(%n)
2551 переходов
18/1000 упакованных классов символов(%k)
41/1500 упакованных переходов(%a)
68/1500 выходных элементов(%o)
%
Здесь показано сообщение, которое выводит lex по флагу -v.
Число перед символом "/" указывает сколько элементов массива
занято, а число за символом "/" указывает установленный раз-
мер массива.
КОММЕНТАРИИ в разделе определений задаются в форме
host-языка и должны начинаться не с первой колонки строки.
3.2. Раздел правил
Все, что указано после первой пары %% и до конца Lex-
программы или до второй пары %%, если она указана, относится
к разделу правил. Раздел правил может содержать правила и
фрагменты программ. Фрагменты программ, содержащиеся в раз-
деле правил, становятся частью функции yylex файла lex.yy.c,
в которой осуществляется выполнение действий активных пра-
вил. Фрагмент программы указывается следующим образом:
%{
строки
фрагмента
программы
%}
Например:
%%
%{
#include file.h
%}
.
.
.
18
Здесь строка "#include file.h" станет строкой функции
yylex().
Раздел правил может включать список активных и неактив-
ных (помеченных) правил. Активные и неактивные правила
могут быть указаны в любом порядке, в том числе быть "пере-
мешанными" в списке. Активные правила выполняются всегда,
неактивные только по ссылке на них оператором BEGIN.
Активное правило имеет вид:
ВЫРАЖЕНИЕ ДЕЙСТВИЕ
Неактивное правило имеет вид:
<МЕТКА>ВЫРАЖЕНИЕ ДЕЙСТВИЕ
или
<СПИСОК_МЕТОК>ВЫРАЖЕНИЕ ДЕЙСТВИЕ
где СПИСОК_МЕТОК имеет вид:
метка1,метка2,...
В качестве первого правила раздела правил может быть правило
вида:
BEGIN МЕТКА;
В этом правиле отсутствует ВЫРАЖЕНИЕ, и первым действием в
разделе правил будет активизация помеченных правил. Для
возвращения автомата в исходное состояние можно использовать
действие:
BEGIN 0;
Важно отметить следующее. Если Lex-программа содержит актив-
ные и неактивные правила, то активные правила работают
всегда. Оператор "BEGIN МЕТКА;" просто расширяет список
активных правил, активируя помеченные меткой МЕТКА. А опера-
тор "BEGIN 0;" удаляет из списка активных правил все поме-
ченные правила, которые до этого были активированы. Кроме
того, если из помеченного и активного в данный момент вре-
мени правила осуществляется действие BEGIN МЕТКА, то из
помеченных правил активными останутся только те, которые
помечены меткой МЕТКА.
3.2.1. Действия в правилах Lex-программы
Действие можно представлять либо как оператор lex, нап-
ример, "BEGIN МЕТКА;", либо как оператор Си. Если имеется
необходимость выполнить достаточно большой набор преобразо-
ваний, то действие оформляют как блок Си-программы (он
19
начинается открывающей фигурной скобкой и завершается закры-
вающей фигурной скобкой), содержащий необходимые фрагменты.
Действие в правиле указывается через не менее, чем один
пробел или табуляцию после выражения (обязательно в той же
строке, где и выражение), а его продолжение может быть ука-
зано в следующих строках только в том случае, если действие
оформлено как блок Си-программы.
Область действия переменных, объявленных внутри блока,
распространяется только на этот блок. Внешними переменными
для всех действий будут являться только те переменные, кото-
рые объявлены в разделе определений Lex-программы.
Действия в правилах Lex-программы выполняются, если
правило активно, и если автомат распознает цепочку символов
из входного потока как соответствующую регулярному выражению
данного правила. Однако, одно действие выполняется всегда -
оно заключается в копировании входного потока символов в
выходной. Это копирование осуществляется для всех входных
строк, которые не соответствуют правилам, преобразующим эти
строки. Комбинация символов, не учтенная в правилах и поя-
вившаяся на входе, будет напечатана на выходе. Можно ска-
зать, что действие - это то, что делается вместо копирования
входного потока символов на выход. Часто бывает необходимо
не копировать на выход некоторую цепочку символов, которая
удовлетворяет некоторому регулярному выражению. Для этой
цели используется пустой оператор Си, например:
[ 0 ;
Это правило игнорирует (запрещает) вывод пробелов, табуляций
и символа новая строка. Запрет выражается в том, что на
указанныe символы во входном потоке осуществляется действие
";" - пустой оператор Си, и эти символы не копируются в
выводной поток символов.
Существует возможность для нескольких регулярных выра-
жений указывать одно действие. Для этого используется символ
"|", который указывает, что действие данного правила совпа-
дает с действием для следующего, например:
" " |
|
;
Результат будет тот же, что и в примере, указанном выше.
Когда необходимо вывести или преобразовать текст, соот-
ветствующий некоторому регулярному выражению, используется
внешний массив символов, который формирует lex. Называется
он yytext и доступен в действиях правил. Например:
20
[A-Z]+ printf("%s",yytext);
По этому правилу распознается слово, содержащее прописные
латинские буквы и выводится с помощью printf, если оно выде-
лено. Операция вывода распознанного выражения используется
очень часто, поэтому имеется сокращенная форма записи этого
действия:
[A-Z]+ ECHO;
Результат действия этого правила будет аналогичен результату
предыдущего примера. В выходном файле lex.yy.c ECHO опреде-
лено как макроподстановка:
#define ECHO fprintf(yyout, "%s",yytext);
Когда необходимо знать длину обнаруженной последовательности
символов, используется счетчик найденных символов yyleng,
который также доступен в действиях. Например:
[A-Z]+ printf("%c",yytext[yyleng-1]);
В этом примере будет выводится последний символ слова, соот-
ветствующего регулярному выражению [A-Z]+. Рассмотрим еще
один пример:
[A-Z]+ {число_слов++;число_букв += yyleng;}
Здесь ведется подсчет числа распознанных слов и количества
символов во всех словах.
3.2.2. Порядок действия активных правил
Список правил Lex-программы может содержать активные и
неактивные правила, размещенные в любом порядке в разделе
правил. В процессе работы лексического анализатора список
активных правил может видоизменяться за счет действий опера-
тора BEGIN. В процессе распознавания символов входного
потока может оказаться так, что одна цепочка символов будет
удовлетворять нескольким правилам и, следовательно, возни-
кает проблема: действие какого правила должно выполняться?
Для разрешения этого противоречия можно использовать
квантование (разбиение) регулярных выражений этих правил
Lex-программы на такие новые регулярные выражения, которые
дадут, по возможности, однозначное распознавание лексемы.
Однако, когда это не сделано, lex использует определенный
детерминированный механизм разрешения такого противоречия:
- выбирается действие того правила, которое распознает
наиболее длинную последовательность символов из вход-
ного потока;
21
- если несколько правил распознают последовательности
символов одной длины, то выполняется действие того
правила, которое записано первым в списке раздела
правил Lex-программы.
Рассмотрим пример:
.
.
.
[Мм][Аа][Йй] ECHO;
[А-Яа-я]+ ECHO;
.
.
.
Слово "Май" распознают оба правила, однако, выполнится пер-
вое из них, так как и первое, и второе правило распознали
лексему одинакового размера (3 символа). Если во входном
потоке будет, допустим, слово "майский", то первые 3 символа
удовлетворяют первому правилу, а все 7 символов удовлетво-
ряют второму правилу, следовательно, выполнится второе пра-
вило, так как ему удовлетворяет более длинная последователь-
ность символов.
3.3. Раздел программ пользователя
Все, что размещено за вторым набором %%, относится к
разделу программ пользователя. Содержимое этого раздела
копируется в выходной файл lex.yy.c без каких-либо измене-
ний. В файле lex.yy.c строки этого раздела рассматриваются
как функции в смысле Си. Эти функции могут вызываться в
действиях правил и, как обычно, передавать и возвращать зна-
чения аргументов.
3.4. Комментарии Lex-программы
Комментарии можно указывать во всех разделах Lex-
программы. Формат комментариев должен соответствовать фор-
мату комментариев host-языка. Однако, в каждом разделе Lex-
программы комментарии указываются по разному. В разделе
определений комментарии должны начинаться не с первой пози-
ции строки. В разделе правил комментарии можно указывать
только внутри блоков, принадлежащих действиям. В разделе
программ пользователя комментарии указываются как и в host-
языке.
3.5. Примеры Lex-программ
Пример1.
22
%Start KOMMENT
/*
* Программа записывает в
* стандартный файл вывода
* комментарии Си-программы.
* Обратите внимание на то, что
* здесь строки комментариев указаны
* не с первой позиции строки!
*/
КОММ_НАЧАЛО "/*"
КОММ_КОНЕЦ "*/"
%%
{КОММ_НАЧАЛО} { ECHO;
BEGIN KOMMENT;}
[0* ;
<KOMMENT>[^*]* ECHO;
<KOMMENT>[^/] ECHO;
<KOMMENT>{КОММ_КОНЕЦ} {
ECHO;
printf("0);
/*
* Здесь приведен пример
* использования комментариев в
* разделе правил Lex-программы.
* Обратите внимание на то, что
* комментрий указан внутри блока,
* определяющего действие правила.
*/
BEGIN 0;}
%%
/*
* Здесь приведен пример комментариев
* в разделе программ пользователя.
*/
Пример 2.
23
%Start IC1 IC2 Normal
/*
* Отладочный фрагмент
* Lex-программы, которая строит
* лексический анализатор для
* компилятора языка Паскаль.
* Действие return(...)
* возвращает тип лексемы в
* в вызывающую анализатор
* программу.
* Обратите внимание на то, что в
* этой 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
следующим образом:
- для литерала номером типа лексемы считается числовое
значение данного литерального символа, рассматривае-
мого как однобайтовое целое число;
- лексемы, обозначенные именами, в соответствии с оче-
редностью их объявления получают последовательные