Страница:
номера, начиная с 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
Для каждого имени лексемы независимо от того, переопре-
делен ли ее номер пользователем, 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