<![CDATA[
Инструментальные средства для построения компиляторов
Реализация компилятора для настоящего языка программирования
всегда является весьма трудоемкой задачей, и поэтому давно
предпринимались попытки автоматизировать этот процесс. Чаще
всего объектом приложения таких усилий служили лучше всего
изученные (и наиболее простые) части компилятора - сканер и
парсер. Мы рассмотрим два инструментальных средства: LEX -
предназначен для реализации сканера, YACC - для построения
парсера. Эти программы разработаны в Белловской лаборатории и
получили широкую известность благодаря системе UNIX, в состав
которой они включены.
В отличие от некоторых систем подобного типа, по-крайней мере
одна из этих двух программ не является всего лишь забавной
игрушкой. YACC использован для реализации переносимого
C-компилятора системы UNIX. Говорят, что первоначально сканер
этого компилятора был реализован с помощью LEX'а, но
впоследствии (по-видимому по соображениям эффективности)
заменен сканером, написанным вручную. Эти программы расчитаны
на совместное использование.
LEX и YACC относятся к системам, которые иногда называют
компиляторами компиляторов. (Название YACC есть сокращение от
yet another compiler compiler - еще один компилятор
компиляторов). Они компилируют описания сканера и парсера
соответственно, записанные на специальных языках, в
C-программы, реализующие эти компоненты компилятора.
LEX
В общем, LEX воспринимает описания регулярных выражений и
строит детерминированный конечный автомат для их распознавания.
Регулярные выражения и их описания
Рассмотрим метаязык, используемый для описания регулярных
выражений LEX'a. Алфавит языка совпадает с алфавитом метаязыка
и содержит набор символов, имеющийся на данной машине. (Скорее
всего это множество включает код ASCII).
1. Обычный символ и строка символов, заключенная в кавычки,
описывают регулярное выражение, задающее их самих. Для того,
чтобы включить в выражение символы имеющие специальное значение
в метаязыке ( + - * ? ( ) [ ] { } | / \ ^ $ . < > ), следует
предварять их знаком \ или употреблять внутри кавычек.
Непечатные символы можно задавать как в C.
a "a" \a - три способа задать выражение, состоящее
\n \t \007 "continue" | из символа a
2. Регулярное выражение, состоящее из одного символа,
принадлежащего определенному классу, описывается следующим
образом:
. - любой символ кроме \n (Разделителя строк)
[A-Za-z_] - большая или маленькая латинская буква или _
[^0-9A-Fa-f]- что угодно кроме шестнадцатиричных цифр
3. Итераторы. Далее мы вынуждены прибегнуть к еще одному
метаязыку (НФБН) для продолжения описания метаязыка LEXа,
служащего для описания регулярных выражений. Нетерминал r
следует произносить как "описатель регулярного выражения".
Правила грамматики указаны в порядке уменьшения приоритетов
операций.
r : r+ - повторение один или более раз выражения r
| r* - повторение ноль или более раз выражения r
| r? - необязательное вхождение r
[0-9]+ - последовательность цифр любой длины
4. r : r r - Конкатенация двух цепочек
[A-Za-z][A-Za-z0-9]* - последовательность букв или
цифр, начинающаяся с буквы.
5. r : r{m,n} - повторение r от m до n раз
r{m} - повторение r ровно m раз
r{m,} - повторение r m или более раз
[A-Za-z] ([A-Za-z0-9]){0,5} - идентификатор фортрана
6. r : ^r - выражение r в начале строки
| r$ - выражение r в конце строки
^#" "*define - оператор препроцессора C
7. r : r|r - или первое выражение, или второе
(+|-)?[0-9]+ - целая константа с знаком
8. r : r/r - первое выражение, если за ним следует второе
9. r : (r) - для указания порядка вычисления можно ис╬
пользовать обычные круглые скобки.
Структура LEX-программы
Вначале приведем пример простейшей программы. Эта программа
считает число строк, слов и символов в входном файле и
распечатывает результат.
/********************* Программа wc.lex **********************/
/***************** Секция определений *********************/
/* NODELIM означает любой символ, кроме разделителей слов */
NODELIM [^" "\t\n]
int l, w, c; /* Число строк, слов, символов */
%% /******************** Секция правил ***********************/
{ l=w=c=0; /* Инициализация */ }
{NODELIM}+ { w++; c+=yyleng; /* Слово */ }
\n { l++; /* Перевод строки */ }
. { c++; /* Остальные символы */ }
%% /******************* Секция программ **********************/
int main() { yylex(); return 0; }
int yywrap() { /* Вызывается при достижении конца входного файла */
printf( " Lines - %d Words - %d Chars - %d\n", l, w, c );
return( 1 );
}
/****************** Конец программы wc.lex *******************/
Можно заметить, что LEX-программа состоит из трех секций,
отделяемых друг от друга символом %%.
Первая из них содержит определения макросимволов (или, если
угодно, нетерминалов грамматики регулярных выражений). Каждое
описание начинается с первой позиции строки и имеет вид
"имя_макросимвола строка". Вместо последовательности
{имя_макросимвола}, встреченной после его определения, будет
подставлена соответствующая ему строка. Макро полезны для
задания сложных выражений, например:
letter [a-zA-Z_#]
digit [0-9]
ident {letter}({letter}|{digit})*
iconst (\+|\-)?{iuconst}
Строки, содержащие в первой позиции пробел или заключенные в
скобки %{ и %} просто копируются в C-программу, являющуюся
результатом работы LEX'a. Они могут содержать описания
переменных, реализацию функций и т.д. В нашем примере секция
определений содержит макро NODELIM и описания трех
переменных-счетчиков.
Вторая секция содержит правила, которые имеют вид "регулярное
выражение { действие }". Действие представляют собой
последовательность операторов языка C, выполняемые при успешном
распознавании регулярного выражения. Выражение записывается с
начала строки. Фигурная скобка, начинающая действие, должна
находится в той же строке, что и регулярное выражение, действие
может быть продолжаться на нескольких строках.
Текст, содержащийся в последней секции, просто копируется в
выходной файл.
Принцип работы сканера
Файл, полученный в результате работы LEX'a, является
C-программой, которая содержит таблицы, описывающие построенный
конечный автомат, функции, реализующие интерпретатор автомата,
описания структур данных, использующиеся интерпретатором, и
пользовательские программы.
Для запуска автомата надо вызвать функцию yylex(), содержащей
все действия, описанные в секции правил LEX-программы. Она, в
свою очередь вызывает функцию yylook, реализующую собственно
конечный автомат. В процессе работы автомат читает символ за
символом из потока yyin, назначенного по умолчанию на
стандартный ввод. После успешного распознавания одного из
выражений происходит возврат в функцию yylex и выполнение
соответствующего ему действия. При этом, переменная char
yytext[YYLMAX] содержит терминированную нулем строку считанных
символов, соответствующую данному регулярному выражению.
Переменная int yyleng содержит длину этой строки. Действие
может завершаться оператором return, который возвратит код
лексемы, вызвавшей yylex функции (например, парсеру).
Если сканер встречает цепочку, не отвечающую ни одному из
правил, то он просто копирует ее в поток yyout, по умолчанию
назначенный на стандартный вывод и пытается разобрать
следующую. Если такие действия нежелательны, то следует
предусмотреть правило для таких цепочек, например
[\n.] { /* Ничего не делать */ }
Если возникает неоднозначность при выделении цепочки символов,
то она разрешается стандартным образом. Предпочтение отдается
правилу, порождающему наиболее длинную цепочку. Если два
правила соответствуют одной и той же цепочке, то применяется
правило, описанное раньше в секции правил. Например, если
заданы следующие правила
[0-9]+ { printf( "Без знака <%s>", yytext ); }
(\+|\-)?[0-9]+ { printf( "Целое <%s>", yytext ); }
(\+|\-)?[0-9]+"."[0-9]* { printf( "Плавающее <%s>", yytext ); }
то цепочка "123", удовлетворяющая первым двум правилам будет
разобрана по первому а цепочка 3.14, первый символ которой
удовлетворяет первым двум правилам, - по третьему правилу.
Условные правила
Многие языки программирования состоят из частей, синтаксис
которых настолько различается друг от друга, что эти части
требуют различных лексических анализаторов. В качестве примера
можно привести оператор формат фортрана, набор лексем которого
отличается от применяемого в других операторах. Для реализации
этой возможности в LEX'e предусмотрены так называемые условные
правила.
Сканер может находится в нескольких состояниях, имена которых
перечисляются в операторе %Start в секции определений. В
начальном состоянии действуют только обычные безусловные
правила. Условные правила действуют, если только текущее
состояние сканера содержится в их списке допустимых состояний.
Переключение сканера из одного состояния в другое
осуществляется оператором BEGIN имя_состояния; возвращение в
исходное осуществляется оператором BEGIN 0.
Условные правила могут применяться и для оптимизации сканера.
Например, сканер C-компилятора должен игнорировать комментарии.
Выделение комментария в отдельное правило потребовало бы буфера
yytext, достаточного для размещения самого длинного
комментария. В качестве примера использования состояний
рассмотрим программу, выделяющую и выводящую на стандартный
вывод комментарии из C-программы, каждый с новой строки.
%Start out_com in_com
%%
{ BEGIN out_com; }
<out_com>"/*" { putchar( '\n' ); ECHO; BEGIN in_com;}
<out_com>.|\n { }
<in_com>"*/" { ECHO; BEGIN out_com; }
<in_com>.|\n { ECHO; }
%%
int main() { yylex(); return 0; }
int yywrap() { putchar( '\n' ); return( 1 ); }
Построенный сканер содержит два состояния: out_com - вне
комментария и in_com - внутри комментария. В первом состоянии
он игнорирует все символы, кроме начала комментария "/*".
Встретив его, сканер переводит строчку, выводит начало
комментария и переключается во второе состояние. Оно отличается
от первого тем, что "остальные" символы копируются в
стандартный вывод до тех пор пока не встретится конец
комментария "*/". В операторе ECHO, который выводит
распознанную лексему в поток yout нет ничего мистического. Он
реализован с помощью обычной макроподстановки "#define ECHO
fprintf(yyout, "%s",yytext)".
Дополнительные возможности LEX
При достижении конца входного файла вызывается функция yywrap,
которую должен реализовать пользователь. Для завершения работы
сканера, эта функция должна возвратить 1. В этом случае
происходит возврат из yylex с значением 0. Для продолжения
работы сканера функция yywrap может переназначить поток yyin на
другой файл и возвратить 0. Это позволяет обрабатывать
несколько файлов как один поток символов, например,
обрабатывать операторы #include в языке C. Также эта функция
может быть использована для выполнения завершающих действий,
как в рассмотренных выше примерах программ.
Оператор REJECT.
Вызов функции yyless( n ) укорачивает лексему в буфере yytext
до n первых символов, возвращая ее отрубленный хвост обратно в
входной поток.
Вызов функции yymore() приведет к тому, что следующая
разобранная лексема будет помещена не в начало буфера yytext, a
дописана в конец его текущего содержимого.
Использование LEX'a в нашей системе или какие кнопки надо
нажимать.
YACC
YACC предназначен для построения парсера (синтаксического
анализатора). Он воспринимает описание контекстно-свободной
грамматики языка в виде, близком форме Бэкуса-Наура (НФБН) и
строит восходящий LALR(1) распознаватель для данного языка.
Структура YACC-программы
YACC-программа состоит из трех секций, разделенных символом %%
- секции описаний, в которой описываются лексемы, секции
правил, в которой описывается грамматика и секции программ,
содержимое которой просто копируется в выходной файл. Пример
простейшей программы на языке YACC'а:
%token name
%start e
%%
e : e '+' m | e '-' m | m ;
m : m '*' t | m '/' t | t ;
t : name | '(' e ')' ;
%%
Секция правил содержит информации о том, что символ name
является лексемой, т.е. терминалом данной грамматики (вместо
ключевого слова %token можно писать %term), а символ e - ее
начальным нетерминалом. (В нашем случае предложение %start e
можно было опустить - по умолчанию в качестве начального
берется левая часть первого правила грамматики).
Грамматика записана обычным образом - идентификаторы означают
терминалы и нетерминалы, символьные константы типа '+' '-' -
терминалы, символы : | ; - понятия "есть по определению", "или"
и "конец правила" соответственно.
Разрешение конфликтов
Написанная грамматика (очевидно она обладает свойством LALR(1))
задает язык арифметических формул, в которых приоритет '*' и
'/' выше приоритета '+' и '-', a все операции левоассоциативны.
Для указания этих свойств в грамматику введены дополнительные
нетерминалы m, и t. Другая грамматика этого языка
e : e '+' e | e '-' e | e '*' e | e '/' e | '(' e ')' | name ;
не является однозначной, и попытка создать LALR(1) анализатор
для этой грамматики приведет к многочисленным (16)
неразрешенным конфликтам типа сдвиг-свертка (shift-reduce) в
построенном автомате. Однако при внимательном исследовании этих
конфликтов выясняется, что в каждом случае можно однозначно
выбрать между сдвигом или сверткой, основываясь на приоритетах
операций и порядке выполнения равноприоритетных операций слева
направо. Эту грамматику можно дополнить этой информацией и
получить ее бесконфликтный распознаватель.
%token name
%left '+' '-'
%left '*' '/'
%%
e : e '+' e | e '-' e | e '*' e | e '/' e | '(' e ')' | name ;
%%
Рассмотрим механизм приоритетов, реализованный в YACC'е, более
подробно. Для приписывания приоритета лексемам (терминалам)
служат предложения %left, %right и %nonassoc, употребляемые в
секции описаний. Они приписывают всем перечисленным за ними
лексемам одинаковый приоритет и соответствующее значение
ассоциативности. (Отсутствие ассоциативности означает
ошибочность выражений типа a @ b @ c в языке). Приоритет
возрастат сверху вниз.
Приоритет сдвига равен приоритету считываемой лексемы.
Приоритет свертки равен приоритету самой правой лексемы в
правиле, по которому свертка проводится. Можно явно приписать
приоритет данному правилу, написав "%prec <лексема>" справа от
него. Это может потребоваться, например, если правило не
содержит лексем или в случаях подобных следующему.
Если мы захотим добавить в язык арифметических формул унарный
минус, то его приоритет должен быть выше приоритета бинарных
операций. Добиться этого можно, введя фиктивную лексему с
высоким приоритетом,
%left UMIN
и добавив правило с приоритетом этой лексемы.
e : - e %prec UMIN
Итак, сформулируем правила, по которым YACC разрешает
конфликты.
- если приоритеты альтернативных действий различны, то вы╬
полняется действие с б'ольшим приоритетом.
- если приоритеты действий одинаковы, то в случае их левой
ассоциативности выбирается свертка, в случае правой ассоци╬
ативности - сдвиг. Если они неассоциативны - возбуждается оши╬
бочная ситуация.
- если какой-нибудь из приоритетов не указан, то в случае
конфликта сдвиг/свертка выполняется сдвиг, а в случае конфликта
свертка/свертка - свертка по правилу, определенному раньше в
описании грамматики.
Отметим, что для конфликтной грамматики с правилами
s : if '(' e ')' s | if '(' e ')' s else s ;
предпочтение сдвига "правильно" разрешает конфликт при разборе
выражения "if( e ) if( e ) s _ else s" в месте, отмеченном
знаком "_". Else будет отнесено к ближайшему if'у, как и
принято в алголоподобных языках. В случае конфликтной
грамматики арифметических формул, это правило приведет к
вычислению справа-налево без учета приоритетов операций.
Семантические действия
С каждым правилом грамматики может быть связано действие,
которое будет выполнено при свертке по данному правилу. Оно
записывается в виде заключенной в фигурные скобки
последовательности операторов языка C, расположенной после
правой части соответствующего правила.
statement : IF '(' expr ')' statement { if_ctr++; }
| WHILE '(' expr ')' statement { while_ctr++; }
| assign_st { ass_ctr++; }
;
В этом примере действие if_ctr++ будет выполнено после
считывания всего оператора if. Если необходимо выполнить
семантические действия, например, после вычисления выражения
expr, надо поместить их сразу после соответствующего символа.
statement: IF '(' expr {action_1;} ')' statement {action_2;}
В таких случаях YACC автоматически, вводя дополнительные
нетерминалы, разбивает одно правило грамматики на несколько.
Действия будут выполнены при свертке промежуточных правил.
Семантический стек
Для естественного обмена данными между действиями, каждый
терминал или нетерминал может иметь значение. Для доступа к
нему в действиях используются псевопеременные $$ - значение
левого символа правила, $<i> - значение i-ого символа правой
части правила. Другими словами, кроме обычного стека состояний
построенный YACC'ом анализатор содержит "семантический" стек,
содержащий значения символов. Значения имеют тип YYSTYPE,
который по умолчанию определяется как int. Действие
expr : expr '+' expr { $$ = $1 + $3; } ;
может быть использовано в интерпретаторе формул, в котором
значение нетерминала "выражение" есть его вычисленное значение.
Если для правила не указано никакого действия, или действие не
содержит упоминания псевдопеременной $$, то значение левой
части правила становится равным значению первого символа правой
части, т.е. неявно выполняется действие { $$ = $1; }. Значение
очередной лексемы копируерся из переменной int yylval, в
которую его заносит сканер.
Естественно, что различные символы грамматики могут иметь
значения разных типов. Для этого следует определить тип YYSTYPE
как union и специфицировать тип терминалов и нетерминалов в
разделе описаний. Например:
%{
#define YYSTYPE yys
typedef union {
int intval;
long longval;
nodeptr *ptrval;
} yys;
%
%token ICONST LCONST
%type <intval> ICONST
%type <longval> LCONST
%type <ptrval> expr
В этом примере символ грамматики может иметь значение одного из
трех типов: intval, longval и ptrval, имена которых совпадают с
именами полей типа YYSTYPE. При обращении к значению символа,
тип которого объявлен в операторе %type, в порожденной YACC'ом
C-програме будет обращение к соответствующему полю объединения
yys.
Если в качестве внутреннего представления программы
используется дерево, естественно иметь в качестве значения
нетерминала указатель на соответствующий ему узел дерева.
Кодировка лексем и интерфейс
Файл, порожденный YACC'ом в процессе работы, содержит таблицы
разбора и функцию yyparse, содержащую интерпретатор таблиц и
семантические действия. Для запуска парсера достаточно вызвать
эту функцию. В случае успешного разбора она возвращает 0, в
случае ошибки - 1.
Для получения очередной лексемы парсер вызывает функцию yylex.
Она должна возвратить код лексемы и поместить ее значение в
переменную yylval, которая имеет тип YYSTYPE. Код лексемы -
положительное целое число. Лексемам, заданных в виде символьных
констант, соответствует их код в наборе символов ЭВМ, лежащий в
диапазоне 0..255. Код 256 зарезервирован для специальной
лексемы error, которая служит для обработки ошибок. Лексемам,
имеющим имена, присваиваются коды начиная с 257.
Файл содержит операторы #define, определяющие имена лексем как
их коды. Если имена лексем требуются в других файлах, следует
указать ключ -d при запуске YACC'а, и он продублирует эти
определения в файле y.tab.h (или ytab.h). Этот файл следует
включить в LEX-текст сканера, если YACC и LEX используются
совместно.
Обработка ошибок
Если разбираемое предложение не соответствует языку, то в
некоторый момент при получении очередной лексемы возникнет
ошибочная ситуация, т.е. в текущем состоянии парсера не
предусмотрено ни сдвига, ни свертки для полученной ошибочной
лексемы. Обычная реакция парсера - вызов функции yyerror с
аргументом ( "Syntax error" ) и завершение работы - возврат из
функции yyparse с значением 1. Реализация функции yyerror
возлагается на пользователя, и он может организовать в ней
выдачу более вразумительной диагностики.
Во многих случаях желательно как-нибудь продолжить разбор. Для
восстановления после ошибки YACC содержит следующие средства.
Имеется специальная лексема с именем error, которая может
употребляться в грамматике. При возникновении ошибки
устанавливается флаг ошибки, вызывается функция yyerror, а
затем из стека состояний удаляются элементы, пока не встретится
состояние, допускающее лексему error. При обнаружении такого
состояния выполняются действия, соответствующие лексеме error в
этом состоянии и разбор продолжается. Если при установленном
флаге ошибки снова возникает ошибочная ситуация, то yyerror не
вызывается, а ошибочная лексема удаляется. Флаг ошибки
сбрасывается после трех успешно считанных лексем.
Специальными действиями в правилах, обрабатываюших ошибочные
ситуации можно более активно вмешиваться в этот процесс.
yyerrok() - сбрасывает флаг ошибки
yyclearin() - удаляет просмотренную вперед ошибочную лексему
Пример
statement : ....
| error ';'
при возникновении ошибки внутри statement восстановление
возможно только с ';' - будет пропущены все лексемы до точки с
запятой.
Выдача y.out и ее формат и кнопки
Пример простейшего интерпретатора формул
%token NAME
%left '+' '-'
%left '*' '/'
%%
s : e { printf( "%d\n", $1 ); }
e : e '+' e { $$ = $1 + $3; }
| e '-' e { $$ = $1 - $3; }
| e '*' e { $$ = $1 * $3; }
| e '/' e { $$ = $1 / $3; }
| '(' e ')'{ $$ = $2; }
| NAME ;
%%
#include <stdio.h>
#include <ctype.h>
int yylex() {
register int c, v;
while ((c = getchar()) == ' ');
if (isdigit(c)) {
for( v=c-'0'; isdigit( c=getchar() ); ) v=v*10+c-'0';
ungetc( c, stdin );
yylval = v;
return( NAME );
} else if( c=='\n' ) {
return( 0 );
} else {
yylval = c;
return( yylval=c );
}
}
int main() { for(;;) yyparse(); return 0; }
int yyerror(char *mes) { printf( "%s\n", mes ); return 0; }
]]>