Библиотека сайта rus-linux.net
Ошибка базы данных: Table 'a111530_forumnew.rlf1_users' doesn't exist
Lex и YACC в примерах
PowerDNS BV (bert hubert <bert@powerdns.com>)
v0.8 $Date: 2004/09/20 07:14:23 $Оригинал: http://ds9a.nl/lex-yacc/cvs/lex-yacc-howto.html
Перевод: Александр Тарасов aka oioki
Дата перевода: 07.04.2009
Этот документ поможет вам освоить основы Lex и YACC
1. Введение
Здравствуй, дорогой читатель.
Если вы имели опыт программирования в окружении UNIX, то наверняка уже сталкивались с мистическими программами Lex и YACC, или как они известны пользователям GNU/Linux - Flex и Bison. Flex - это реализация программы Lex, написанная Верном Паксоном (Vern Paxson), а Bison - это GNU-версия программы YACC. Но все равно будем называть эти программы Lex и YACC - их новые версии обратно совместимы, и они сгодятся для примеров из этой статьи.
Эти программы чрезвычайно полезны, но как и для компилятора C, в их man-страницах не объясняется ни как ими пользоваться, ни описания языка использования. YACC удивительно полезен в сочетании с Lex, однако man-страница Bison не описывает, как интегрировать сгенерированный с помощью Lex код с вашей Bison-программой.
1.1. Чего НЕТ в этом документе
Есть множество замечательных книг по Lex и YACC. Если хотите знать об этих программах больше - не поленитесь пролистать их. В них написано куда больше, чем в этой статье. В самом конце статьи находится список "Дополнительные материалы". Этот же документ нацелен на быстрое ознакомление с Lex и YACC, чтобы вы как можно скорее смогли создать собственные программы.
Документация, которая идет с Flex и BISON великолепна, но не является средством обучения. Однако хорошо дополняет мое HOW-TO. Эта документация также указана в конце статьи.
Стоит сказать, что я не эксперт по YACC/Lex. Когда я начинал писать эту статью, у меня было всего два опыта работы с этими программами. Хотелось бы, чтобы с помощью моей статьи ваши первые два дня прошли полегче.
Не смотрите на примеры из этого HOW-TO как на примеры для подражания. Данные примеры намеренно упрощены, их можно написать куда лучше. Если знаете, как, пожалуйста, напишите мне.
1.2. Что нужно скачать
Все примеры, приведенные в статье, можно скачать с моей домашней страницы.
1.3. Лицензия
Copyright (c) 2001 by bert hubert. This material may be distributed only subject to the terms and conditions set forth in the Open Publication License, vX.Y or later (the latest version is presently available at http://www.opencontent.org/openpub/).
2. Чем Lex и YACC могут помочь
При правильном использовании с помощью этих программ вы с легкостью можете анализировать сложные языки. Эти программы - отличное подспорье, когда вам нужно прочитать конфигурационный файл, либо если у вас стоит задача написать компилятор для какого-нибудь своего языка.
Чтобы быстро научиться пользоваться этими программами, нужно совсем немного. Прочтя эту статью, вы никогда больше не станете писать парсер вручную - Lex и YACC сделают это за вас.
2.1. Чем занимается каждая программа
Хотя эти программы замечательно работают в связке, они тем не менее имеют различное предназначение. В следующей главе мы рассмотрим более подробно, что они делают.
3. Lex
Программа Lex генерирует лексические анализаторы (lexer). Lexer принимает на входе поток символов, а когда встречает группу символов, совпадающих с некоторым шаблоном (ключом), выполняет определенное действие. Вот простейший пример:
%{
#include <stdio.h>
%}
%%
stop printf("Получена команда stop\n");
start printf("Получена команда start\n");
%%
В первой секции между парой скобок %{ и %} мы включили текст, который напрямую попадет в итоговую программу. Это включение необходимо, потому что впоследствии мы используем подпрограмму printf, которая определена в заголовочном файле stdio.h
Секции разделяются комбинацией символов '%%'. Второй раздел начинается с ключа 'stop'. Как только во входном потоке обнаружится ключ 'stop', будет выполнено то, что находится в правой части строки второго раздела. В нашем случае будет вызвана функция printf().
Помимо 'stop' мы также определили ключ 'start'. Он делает почти то же самое.
Секция кода также заканчивается комбинацией '%%'.
Чтобы откомпилировать Пример 1, отдайте команды:
lex example1.l cc lex.yy.c -o example1 -ll
ЗАМЕЧАНИЕ. Если вы пользуетесь flex, а не lex, тогда возможно вам придется поменять параметр '-ll' на '-lfl', даже если вы вызываете 'flex' как 'lex'. Так требуется в некоторых дистрибутивах.
Будет создан файл 'example1'. Если теперь вы его запустите, программа будет ожидать ввода данных. Если введете что-либо, не совпадающее с определенными нами ключами ('stop' и 'start'), то эти символы будут отображены еще раз. Если введете 'stop', будет выведено сообщение 'Получена команда stop'.
Завершить работу с программой можно путем ввода EOF (^D).
Вы можете удивиться, как же программа работает, не имея функции main(). Однако эта функция определена за вас в библиотеке libl (liblex), которая подключается с помощью параметра -ll.
3.1. Регулярные выражения в шаблонах
Первый пример сам по себе не очень полезен, и следующий будет такой же. Однако он покажет вам, как пользоваться регулярными выражениями в Lex - они очень пригодятся вам в дальнейшем.
Пример 2:
%{
#include <stdio.h>
%}
%%
[0123456789]+ printf("NUMBER\n");
[a-zA-Z][a-zA-Z0-9]* printf("WORD\n");
%%
Этот Lex-файл описывает два типа последовательностей символов (так называемых токенов): числа и слова (NUMBER и WORD). Регулярные выражения могут показаться страшными, но это только на первый взгляд. Совсем немного умственных усилий - и все станет понятно. Давайте рассмотрим шаблон NUMBER:
[0123456789]+
Это означает: ищем последовательность из одного или более символов, имеющихся в группе 0123456789. Можно записать это регулярное выражение короче:
[0-9]+
Шаблон WORD немного более сложное:
[a-zA-Z][a-zA-Z0-9]*
Первая часть описывает совпадение в одном и только одном символе - это должен быть символ от 'a' до 'z', или от 'A' до 'Z'. Другими словами, буквы латинского алфавита. После этой начальной буквы должно идти 0 или более символов - букв или цифр. Почему здесь используется звездочка? Символ '+' означает 1 или более совпадений, но слово ведь может состоять и из одного символа, и это совпадение мы уже описали ранее. Поэтому вторая часть выражения может иметь 0 совпадений, поэтому пишем '*'.
Таким образом, мы имитируем логику многих языков программирования, требованием которых является то, что имя переменной обязательно начинается с буквы, но может содержать и цифры. Другими словами, последовательность символов 'temperature1' является словом, а '1temperature' - нет.
Откомпилируйте пример 2, аналогично примеру 1. С вашей новой программой может состояться вот такой диалог:
$ ./example2 foo WORD bar WORD 123 NUMBER bar123 WORD 123bar NUMBER WORD
Вы можете спросить, почему после каждого ввода данных появляется пустая строка? Причина проста - она была во входном потоке, однако для нее мы не нашли совпадения, поэтому она выводится еще раз.
Man-страница по Flex подробно описывает работу с регулярными выражениями. Некоторые считают, что man-страница по регулярным выражениям Perl (man perlre) весьма полезна, хотя Flex не может реализовать все, что подвластно Perl.
Стоит сразу уведомить пользователя, чтобы он не создавал пустых совпадений типа '[0-9]*' - лексический анализатор может войти в вечный цикл.
3.2. Более сложный пример, синтаксис наподобие C
Допустим, нам нужно проанализировать файл следующего вида:
logging {
category lame-servers { null; };
category cname { null; };
};
zone "." {
type hint;
file "/etc/bind/db.root";
};
Ясно видим, что здесь встречаются следующие категории (токены):
- Слова (WORD), например 'zone' и 'type'
- Имена файлов (FILENAME), например '/etc/bind/db.root'
- Кавычки (QUOTE), к примеру, те, которые окружают имя файла
- Открывающие фигурные скобки (OBRACE) - {
- Закрывающие фигурные скобки (EBRACEs) - }
- Точка с запятой (SEMICOLON) - ;
Соответствующий Lex-файл приведен в примере 3:
%{
#include <stdio.h>
%}
%%
[a-zA-Z][a-zA-Z0-9]* printf("WORD ");
[a-zA-Z0-9\/.-]+ printf("FILENAME ");
\" printf("QUOTE ");
\{ printf("OBRACE ");
\} printf("EBRACE ");
; printf("SEMICOLON ");
\n printf("\n");
[ \t]+ /* игнорируем пробелы и знаки табуляции */;
%%
Когда отдадим наш файл сгенерированной Lex-ом программе (с помощью скрипта example3.compile), мы получим:
WORD OBRACE WORD FILENAME OBRACE WORD SEMICOLON EBRACE SEMICOLON WORD WORD OBRACE WORD SEMICOLON EBRACE SEMICOLON EBRACE SEMICOLON WORD QUOTE FILENAME QUOTE OBRACE WORD WORD SEMICOLON WORD QUOTE FILENAME QUOTE SEMICOLON EBRACE SEMICOLON
Если взглянуть еще раз на исходный конфигурационный файл, становится ясно, что мы провели лексический разбор. Каждая составляющая конфигурационного файла была разобрана, конфигурационный файл разбит на токены.
На данном этапе нам здорово пригодится YACC.
3.3. Что мы увидели
Мы увидели, что Lex способен считывать символы из входного потока и группировать их в токены. Иначе это называется лексическим разбором.
4. YACC
YACC может проводить синтаксический анализ потока токенов с определенными значениями (атрибутами). Здесь явно видна связь между YACC и Lex. YACC совершенно не догадывается о том, что же такое "входной поток", ему требуются токены. Конечно, можно написать собственный лексический анализатор, но мы оставим эту задачу для Lex.
Небольшое замечание о грамматиках и парсерах. Когда YACC появился, им пользовались для обработки входных файлов для компиляторов - это были исходные тексты программ. Как правило, компьютерные программы являются однозначными - и не допускают двоякого толкования. Поэтому YACC не борется с неоднозначностью и попросту будет предупреждать пользователя о конфликтах типа shift/reduce и reduce/reduce. Подробнее об этом прочитаете в разделе 'Конфликты'.
4.1. Простой контроллер термостата
К примеру, у нас есть термостат, которым мы хотим управлять с помощью специального языка. Процесс работы с термостатом может выглядеть следующим образом:
heat on
Обогреватель включен!
heat off
Обогреватель выключен!
target temperature 22
Установлена новая температура!
Необходимо распознавать следующие токены: heat, on/off (состояние STATE), target, temperature и числа (NUMBER).
Lex-анализатор выглядит следующим образом (пример 4):
%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+ return NUMBER;
heat return TOKHEAT;
on|off return STATE;
target return TOKTARGET;
temperature return TOKTEMPERATURE;
\n /* игнорируем символ конца строки */;
[ \t]+ /* игнорируем пробелы и символы табуляции */;
%%
Отметим два важных изменения. Во-первых, мы подключили файл 'y.tab.h', во-вторых, мы больше ничего не печатаем, а лишь возвращаем имена токенов. Это изменение нужно потому, что мы будем отдавать поток токенов на вход YACC, которому неважно, что мы выводим на экран. В файле y.tab.h как раз находятся определения этих токенов.
Но откуда же берется файл y.tab.h? Он генерируется самим YACC из файла грамматики, который мы сейчас напишем. Наш язык очень прост, такой же простой будет и его грамматика:
commands: /* empty */
| commands command
;
command:
heat_switch
|
target_set
;
heat_switch:
TOKHEAT STATE
{
printf("\tОбогреватель включен или выключен\n");
}
;
target_set:
TOKTARGET TOKTEMPERATURE NUMBER
{
printf("\tТемпература установлена\n");
}
;
Первая часть, я называю ее "корень". Она означает, что мы имеем "команды" (commands), и эти команды состоят из отдельных "команд" (command). Как нетрудно заметить, это определение рекурсивно, ведь оно содержит в себе само себя. Благодаря рекурсии, программа способна постепенно сокращать набор команд одну за одной. В разделе "Внутреннее устройство Lex и YACC" есть существенные замечания по рекурсии.
Второе правило определяет, что из себя представляет команда. Мы задумываем лишь два типа команд - heat_switch (вкл/выкл обогревателя) и target_set (установка температуры). Здесь используется знак ИЛИ - | . В целом правило означает: "command может быть heat_switch или target_set".
Правило heat_switch состоит из токена HEAT (это просто слово "heat"), после которого идет состояние (оно определено в Lex-файле как "on" или "off").
Немного более сложным является последнее правило target_set, состоящее из токена TARGET (слово "target"), токена TEMPERATURE (слово "temperature") и числа.
Полный YACC-файл
В предыдущем разделе приведена лишь грамматическая часть YACC-файла, но это еще не все. Мы намеренно опустили этот заголовок:
%{
#include <stdio.h>
#include <string.h>
void yyerror(const char *str)
{
fprintf(stderr,"ошибка: %s\n",str);
}
int yywrap()
{
return 1;
}
main()
{
yyparse();
}
%}
%token NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE
Функция yyerror() вызывается YACC, когда он обнаруживает ошибку. Здесь мы просто выводим сообщение, что ошибка найдена, но можно выполнять и куда более умные вещи - смотрите раздел "Дополнительные материалы" в конце статьи.
Функция yywrap() может быть использована для продолжения чтения из другого файла. Она вызывается при получении символа EOF, здесь вы можете открыть другой файл, и вернуть 0. Либо можете вернуть значение 1 - это означает, что действительно достигнут конец. Более подробные сведения смотрите в разделе "Внутреннее устройство Lex и YACC".
Далее, есть функция main(), которая не делает ничего, только запускает наш механизм.
В последней строке определены используемые токены. На основе этой строки генерируется файл y.tab.h, если YACC вызван с ключом '-d'.
Компилируем и запускаем контроллер термостата
Кое-что изменилось. Теперь мы вызываем YACC для компиляции нашей грамматики, при этом создаются файлы y.tab.c и y.tab.h. Затем мы можем вызвать Lex, как обычно. При компиляции нужно убрать флаг "-ll": теперь у нас есть своя функция main(), и стандартная функция main из библиотеки libl нам не нужна.yacc -d example4.y lex example4.l cc lex.yy.c y.tab.c -o example4
ЗАМЕЧАНИЕ. Если при компиляции получите ошибку, что переменная "yylval" не найдена, просто добавьте эту строку в example4.l, сразу за #include <y.tab.h>:extern YYSTYPE yylval;Почему это так важно - объяснено в разделе "Внутреннее устройство Lex и YACC".
Пример диалога:
$ ./example4
heat on
Обогреватель включен или выключен
heat off
Обогреватель включен или выключен
target temperature 10
Температура установлена
target humidity 20
ошибка: parse error
$
Это не совсем то, чего мы хотели достичь, но в интересах понятности объяснения и легкости обучения нельзя показывать все и сразу.
4.2. Обработка параметров термостата
Итак, теперь мы корректно обрабатываем команды термостата, и даже отмечаем ошибки. Однако связь не очень хороша - программа поняла, что нужно что-то сделать, но не поняла, что именно. Так происходит, потому что мы еще не передавали параметры.
Давайте добавим возможность считывать новую температуру. Для этого нужно заставить Lex переводить строковую запись числа в целочисленное значение, которое потом можно отдать YACC.
Всякий раз, когда Lex распознает токен, текст этого токена помещается в строку "yytext". С другой стороны, YACC ожидает, что значение токена хранится в переменной "yylval". Пример 5 показывает очевидное решение этой проблемы:
%{ #include <stdio.h> #include "y.tab.h" %} %% [0-9]+ yylval=atoi(yytext); return NUMBER; heat return TOKHEAT; on|off yylval=!strcmp(yytext,"on"); return STATE; target return TOKTARGET; temperature return TOKTEMPERATURE; \n /* пропускаем символы конца строки */; [ \t]+ /* пропускаем пробелы и символы табуляции */; %%
Очевидно, мы обрабатываем yytext с помощью функции atoi(), и помещаем результат в yylval, где его и желает видеть YACC. Почти то же самое делаем при совпадении токена STATE - здесь лишь сравниваем yytext с "on", и если строки совпадают, то присваиваем переменной yylval значение 1. Обратите внимание, что если реализовать в Lex-файле отдельные правила "on" и "off", тогда это будет работать быстрее, но мне хотелось показать чуть более сложное правило и действие, зависящее от параметра.
Теперь нужно заставить YACC работать с этими переменными. То, что называется "yylval" в Lex, в YACC имеет совсем другое название. Давайте взглянем на новое правило для задания температуры:
target_set:
TOKTARGET TOKTEMPERATURE NUMBER
{
printf("\tТемпература установлена на %d градусов\n",$3);
}
;
Чтобы получить доступ к значению из третьей части правила (т.е. NUMBER), нужно воспользоваться записью $3. Когда программе возвращается управление после отработки функции yylex(), содержимое yylval соединяется с терминалом, и его значение можно получить через конструкцию вида $число.
Возможно, все станет ясно, когда вы увидите новое правило heat_switch:
heat_switch:
TOKHEAT STATE
{
if($2)
printf("\tОбогреватель включен\n");
else
printf("\tОбогреватель выключен\n");
}
;
Если теперь запустите example5, можно будет провести именно тот диалог, который мы приводили в качестве примера.
4.3. Обрабатываем конфигурационный файл
Давайте повторим часть конфигурационного файла, упомянутого ранее:
zone "." {
type hint;
file "/etc/bind/db.root";
};
Не забывайте, что лексический анализатор для этого файла у нас уже написан. Теперь нам надо составить YACC-грамматику, и модифицировать Lexer так, чтобы он возвращал значения в формате, понятном YACC.
Lex-файл примера 6 имеет следующий вид:
%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
zone return ZONETOK;
file return FILETOK;
[a-zA-Z][a-zA-Z0-9]* yylval=strdup(yytext); return WORD;
[a-zA-Z0-9\/.-]+ yylval=strdup(yytext); return FILENAME;
\" return QUOTE;
\{ return OBRACE;
\} return EBRACE;
; return SEMICOLON;
\n /* пропускаем концы строк */;
[ \t]+ /* пропускаем пробелы */;
%%
Если посмотрите внимательно, увидите, что порядок работы с yylval изменился. Теперь он является не целым числом, а строкой (указателем на char). В целях упрощения примера мы вызываем процедуру копирования строки strdup, и таким образом расходуется много памяти (память выделяется каждый раз при появлении токена типа WORD или FILENAME). Однако во многих случаях (особенно когда входные файлы маленькие) это не является острой проблемой, и можно обойтись этим примитивным решением.
Нужно хранить строки символов по той причине, что в основном сейчас будем работать с именами - именами файлов и именами зон. В последнем разделе мы поговорим о том, как работать с несколькими типами данных.
Чтобы объяснить YACC о новом типе yylval, нужно добавить эту строку в заголовок нашей YACC-грамматики:
#define YYSTYPE char *
Сама грамматика, опять же, куда сложнее. Чтобы было проще ее понять, я разбил ее на части.
commands:
|
commands command SEMICOLON
;
command:
zone_set
;
zone_set:
ZONETOK quotedname zonecontent
{
printf("Найдена полная зона для '%s'\n",$2);
}
;
Это лишь начало, которое включает в себя и уже упомянутый "корень". Обратите внимание, что команды заканчиваются точкой с запятой. Здесь определим команду лишь одного типа - zone_set. Она состоит из токена ZONE (просто слово "zone"), после чего идет имя зоны в кавычках и "содержимое зоны" (zonecontent). Содержимое зоны определяется достаточно просто:
zonecontent:
OBRACE zonestatements EBRACE
Содержимое зоны начинается с открывающей фигурной скобки (OBRACE), затем идут определения зоны, затем блок закрывается фигурной скобкой (EBRACE)
quotedname:
QUOTE FILENAME QUOTE
{
$$=$2;
}
В этом правиле определено, что такое "quotedname" - это имя файла (FILENAME) в кавычках (QUOTE). Далее идет кое-что интересное: значением токена quotedname становится значение FILENAME. Таким образом, значение quotedname - это имя файла без кавычек.
Вот что делает эта магическая команда "$$=$2;". Она как бы говорит нам: мое значение - это значение моей второй части. Теперь, когда токен quotedname будет упоминаться в других правилах, он уже будет обладать значением, которое вызывается аналогичным образом "$-число".
ВНИМАНИЕ. Грамматика не будет работать, если имя файла не содержит хотя бы одного символа '.' или '/'.zonestatements: | zonestatements zonestatement SEMICOLON ; zonestatement: statements | FILETOK quotedname { printf("Обнаружено имя файла зоны '%s'\n", $2); } ;
Это обычное утверждение, обобщающее все утверждения, которые могут встретиться в блоке "zone". Опять же, видим рекурсию.
block:
OBRACE zonestatements EBRACE SEMICOLON
;
statements:
| statements statement
;
statement: WORD | block | quotedname
Здесь определяется блок, и внутри него утверждения (statements).
Результат выполнения полученной программы может выглядеть так:
$ ./example6
zone "." {
type hint;
file "/etc/bind/db.root";
type hint;
};
Обнаружено имя файла зоны '/etc/bind/db.root'
Найдена полная зона для '.'
5. Написание парсера на C++
Хотя Lex и YACC появились раньше C++, тем не менее возможно создать парсер на языке C++. У Flex есть опция, позволяющая генерировать код лексического анализатора на C++, но мы не будем этим пользоваться, так как YACC не знает, как с ним напрямую работать.
Я предлагаю другой вариант, а именно пусть Lex сгенерирует обычный C-файл, а YACC генерирует код на C++. Затем при связывании двух своих программ возможны ошибки, так как код C++ не знает, где находятся определения функций C, до тех пор, пока вы не напишете объявление extern "C".
В общем, нужно добавить в заголовок YACC-файла следующие строки:
extern "C"
{
int yyparse(void);
int yylex(void);
int yywrap()
{
return 1;
}
}
Если хотите подсунуть модифицированную версию yydebug, нужно написать что-то вроде:
extern int yydebug;
main()
{
yydebug=1;
yyparse();
}
C++ запрещает несколько определений функции, поэтому мы так тут и пишем.
Возможно, придется повторить #define YYSTYPE в вашем Lex-файле, так как в C++ проверка типов данных более строгая.
Для компиляции программы введите:
lex bindconfig2.l yacc --verbose --debug -d bindconfig2.y -o bindconfig2.cc cc -c lex.yy.c -o lex.yy.o c++ lex.yy.o bindconfig2.cc -o bindconfig2
Из-за использования опции -o, файл y.tab.h теперь будет называться bindconfig2.cc.h, обратите на это внимание.
В целом: не утруждайте себя созданием лексического анализатора на C++, оставьте его написанным на обычном C. Вместо этого пусть синтаксический анализатор будет на C++, а связку с C-функциями проделывайте с помощью конструкций extern "C".
6. Внутреннее устройство Lex и YACC
В YACC-файле можно указать свою собственную функцию main(), которая вызывает функцию yyparse(). Функция yyparse() создается автоматически с помощью YACC, и определяется в файле y.tab.c.
Функция yyparse() считывает поток токенов с атрибутами из yylex(), которую также нужно указать. Можно написать эту функцию самому вручную, или сгенерировать автоматически с помощью Lex. В наших примерах мы решаем задачу с помощью Lex.
yylex(), созданный Lex считывает символы из файла, которому соответствует файловый дескриптор FILE * yyin. Если yyin не установлен, тогда считывается стандартный ввод (stdin). Вывод программы производится в файл с дескриптором yyout, по умолчанию это стандартный вывод (stdout). Можно также модифицировать yyin в функции yywrap(), которая вызывается по достижении конца файла. Здесь можно открыть другой файл, и продолжить анализ.
Если это ваш случай, ваша реализация функции yywrap() должна вернуть 0. Если же вы действительно завершаете анализ, без открытия дополнительных файлов, возвращайте значение 1.
Каждый вызов функции yylex() возвращает целое значение, представляющее из себя тип токена. Таким образом YACC понимает, какого типа токен был считан. Этот токен может обладать значением (атрибутом), которое помещается в переменную yylval.
По умолчанию переменная yylval имеет тип int, но это можно переопределить (#define YYSTYPE) в одном из файлов, созданных YACC.
Лексический анализатор должен иметь доступ к переменной yylval. Для этого он должен быть объявлен в области видимости lexer как extern-переменная. Оригинальный YACC не дает сделать это через его средства, но вы сами можете сделать переопределение, добавив строку следом за #include <y.tab.h>:
extern YYSTYPE yylval;
Bison, которым пользуется большинство людей, делает это для вас автоматически.
6.1. Атрибуты токенов
Как уже было сказано, функция yylex() возвращает тип полученного токена, и помещает его значение в yylval. Всем токенам, перечисленным в строке с %token, назначаются численные номера, начиная с 256.
Поэтому все символы из стандартной таблицы ASCII (их коды 0-255) могут быть использованы в качестве токенов. Предположим, в процессе разработки программы-калькулятора, вы написали следующий лексический анализатор:
[0-9]+ yylval=atoi(yytext); return NUMBER; [ \n]+ /* пропускаем пробелы */; - return MINUS; \* return MULT; \+ return PLUS; ...
Соответствующая YACC-грамматика выглядит так:
exp: NUMBER
|
exp PLUS exp
|
exp MINUS exp
|
exp MULT exp
Этот вариант чрезмерно сложен. Используя символы в качестве замены численных идентификаторов токенов, можно переписать наш лексический анализатор следующим образом:
[0-9]+ yylval=atoi(yytext); return NUMBER; [ \n]+ /* пропускаем пробелы */; . return (int) yytext[0];
Последняя точка соответствует всем символам, которые до сих пор не попали ни под одно правило.
Наша YACC-грамматика тогда будет выглядеть следующим образом:
exp: NUMBER
|
exp '+' exp
|
exp '-' exp
|
exp '*' exp
Это намного короче и куда очевиднее. Нет необходимости объявлять эти ASCII-токены в заголовке %token, они заработают автоматически.
Еще одним плюсом подобного подхода является распознавание абсолютно всех остающихся символов - никакая комбинация символов не будет скопирована в выходной поток. К примеру, если пользователь калькулятора введет операцию ^, тогда синтаксический анализатор выдаст ошибку, а сам символ ^ не будет выведен на экран.
6.2. Рекурсия: "правая - это неправильно"
Рекурсия - ключевой аспект работы YACC. Без нее было бы невозможно составление последовательностей из отдельных выражений или команд. Первой точкой входа в рекурсивные правила является первое правило, либо то, которое вы обозначаете как первое, с помощью символа "%start".
Рекурсия в YACC (да и вообще) бывает двух видов: правая и левая. Левая рекурсия, которой можно пользоваться в большинстве случаев, выглядит примерно так:
commands: /* пусто */
|
commands command
Это означает: команды (commands) либо пусты, либо состоит из нескольких команд (commands), за которыми следует еще одна команда (command). Таким образом, YACC может отцеплять от групп команд отдельные команды, и обрабатывать одна по одной.
Сравните такой подход с правой рекурсией, который почему-то на взгляд многих людей выглядит привлекательнее:
commands: /* пусто */
|
command commands
Однако этот вариант дороже обходится. Если это первое правило (с меткой %start), тогда YACC приходится держать все ваши команды на стеке, что занимает большой объем памяти. Поэтому для анализа больших выражений, например целых файлов, следует использовать левую рекурсию. Иногда трудно устранить правую рекурсию, но если ваши выражения малы по размеру, то можно обойтись и ею.
Если какой-либо символ завершает (и поэтому разделяет) список ваших команд, правая рекурсия на первый взгляд может выглядеть естественной, но она все такая же дорогая:
commands: /* пусто */
|
command SEMICOLON commands
Верным решением будет использование левой рекурсии (не я это изобрел):
commands: /* пусто */
|
commands command SEMICOLON
В ранних версиях этого HOW-TO ошибочно использовалась правая рекурсия. Маркус Триска (Markus Triska) любезно проинформировал меня об этом.
6.3. Продвинутый yylval: %union
На данный момент нам нужно определять тип переменной yylval. Однако это не всегда приемлемо. Бывают случаи, когда нужно работать с несколькими типами данных. Но вернемся к нашему гипотетическому термостату. Допустим, пользователь хочет выбирать, каким обогревателем он будет управлять, например так:
heater mainbuiling
Выбран обогреватель 'mainbuilding'
target temperature 23
Температура обогревателя 'mainbuilding' установлена в 25 градусов
Необходимо, чтобы yylval представлял собой тип данных union - объединение, которое может хранить как строки, так и целые числа - но не одновременно.
Запомните, что раньше мы указывали тип yylval, определяя YYSTYPE. Мы могли бы объявить YYSTYPE как тип union, но YACC предлагает куда более удобное решение - а именно символ %union.
Пример 7 основан на примере 4. Начнем написание YACC-грамматики:
%token TOKHEATER TOKHEAT TOKTARGET TOKTEMPERATURE
%union
{
int number;
char *string;
}
%token <number> STATE
%token <number> NUMBER
%token <string> WORD
Мы определяем наш тип union, состоящий лишь из чисел и строк. Затем с помощью расширенного синтаксиса %token, мы объясняем YACC, к какой части union'а каждый токен должен иметь доступ.
В нашем случае токен STATE использует целый тип данных, как и обычно. То же самое относится и к токену NUMBER, который используется для задания температур.
Однако здесь появляется новый токен WORD, которому нужен тип данных "строка".
Lex-файл также слегка изменяется:
%{
#include <stdio.h>
#include <string.h>
#include "y.tab.h"
%}
%%
[0-9]+ yylval.number=atoi(yytext); return NUMBER;
heater return TOKHEATER;
heat return TOKHEAT;
on|off yylval.number=!strcmp(yytext,"on"); return STATE;
target return TOKTARGET;
temperature return TOKTEMPERATURE;
[a-z0-9]+ yylval.string=strdup(yytext);return WORD;
\n /* пропускаем конец строки */;
[ \t]+ /* пропускаем пробелы */;
%%
Как видно из этого примера, мы больше не обращаемся к yylval напрямую, а вместо этого указываем суффикс, обозначающий тип, к которому хотим получить доступ. И не нужно думать об этом в YACC-грамматике, ведь YACC делает все за нас:
heater_select:
TOKHEATER WORD
{
printf("\tВыбран обогреватель '%s'\n",$2);
heater=$2;
}
;
Из-за определения %token, данного выше, YACC автоматически выбирает поле "строка" из нашего union'а. Обратите внимание, что мы храним копию $2, которая далее будет использована нами для определения обогревателя, температурой которого будем управлять:
target_set:
TOKTARGET TOKTEMPERATURE NUMBER
{
printf("\Температура обогревателя '%s' установлена в %d градусов\n",heater,$3);
}
;
В файле example7.y вы найдете более подробное описание.
7. Отладка
Отладочные средства всегда полезны, особенно в учебе. К счастью, YACC может дать кое-какую обратную связь в виде отладочной информации. Она, естественно, стоит определенных затрат ресурсов, и по умолчанию эта функция отключена. Чтобы включить, надо вызвать YACC с определенными опциями.
При компиляции вашей грамматики, добавьте ключи --debug и --verbose. Также в заголовок вашей программы добавьте следующую строчку:
int yydebug=1;
Это приведет к созданию файла "y.output", содержащего сведения о том, как именно автомат парсера был создан.
Когда вы запустите полученный бинарный файл, он выведет очень много сведений о том, что в данный момент происходит, в том числе текущие состояния автомата и какие токены были распознаны из потока символов.
Питер Джинкс (Peter Jinks) написал статью об отладке, в ней описаны часто допускаемые ошибки и методы их исправления.
7.1. Автомат
Внутри себя парсер YACC запускает так называемый "автомат". Автомат может находиться в нескольких состояниях. Также есть правила, при выполнении которых автомат переходит из одного состояния в другое. Начальным состоянием автомата является "корень", о котором я говорил раньше.
Рассмотрим часть файла y.output из примера 7:
состояние 0
ZONETOK , и переход в состояние 1
$default вывод с использованием правила 1 (commands)
commands переход в состояние 29
command переход в состояние 2
zone_set переход в состояние 3
По умолчанию, это состояние изменяется по правилу "commands". Как уже сказано выше, это рекурсивное правило определяет, что "commands" состоит из отдельных "command", после которых идет точка с запятой и, возможно, другие команды.
Это состояние повторяется до тех пор, пока не будет встречено нечто, что оно может распознать - в данном случае токен ZONETOK, то есть слово "zone". Когда произойдет переход в состояние 1, логика работы будет уже другая:
состояние 1
zone_set -> ZONETOK . quotedname zonecontent (правило 4)
QUOTE , и переход в состояние 4
quotedname переход в состояние 5
На первой строке имеется символ ".", описывающий наше текущее местонахождение: мы только что просмотрели ZONETOK и теперь ожидаем "quotedname". Ясно, что quotedname начинается с токена QUOTE, при появлении такового автомат переходит в состояние 4.
Если есть желание увидеть полное описание этого автомата, скомпилируйте пример 7 с флагами из раздела 7 (Отладка).
7.2. Конфликты: 'сдвиг/вывод', 'вывод/вывод'
Каждый раз, когда YACC предупреждает вас о конфликтах, у вас могут быть проблемы. Разрешение этих конфликтов в какой-то мере является формой искусства, и может быть, вам самим глубже разобраться в описываемом языке. Иногда даже больше, чем этого хотелось бы.
Проблемы состоят в том, как интерпретировать последовательности токенов. Представим, что мы объявили язык, который принимает следующие команды:
delete heater all
delete heater number1
Для него мы описали следующую грамматику:
delete_heaters:
TOKDELETE TOKHEATER mode
{
deleteheaters($3);
}
mode: WORD
delete_a_heater:
TOKDELETE TOKHEATER WORD
{
delete($3);
}
Вы, пожалуй, уже почуяли неладное. Автомат начинает считывать слово "delete", затем "heater", а затем решает, в какое состояние перейти на основе следующего токена. Следующий токен может быть "mode" (описывающий как именно удалять обогреватели), либо имя обогревателя, которое нужно удалить.
Проблема состоит в том, что для обеих команд следующим токеном является WORD. Поэтому YACC не знает, куда идти дальше. Это приводит к появлению предупреждения типа "вывод/вывод", при этом разбор delete_a_heater никогда не будет достигнут.
В данном конкретном случае конфликт разрешается легко (к примеру, переименованием первой команды в "delete heaters all", либо сделав "all" отдельным токеном), но порой сделать это довольно проблематично. Файл y.output, который создается при указании флага yacc --verbose, может здорово вам помочь.
8. Дополнительные материалы
В комплекте GNU YACC (Bison) поставляется info-файл (.info), который хорошо описывает синтаксис YACC. Lex упоминается лишь однажды, но в целом документация хороша. Info-файлы могут быть прочитаны с помощью Emacs или симпатичной программки "pinfo". Документация также доступна на сайте GNU: BISON Manual.
Man-страница Flex весьма полезна, если вы уже примерно знаете, чем занимается Flex. Flex Manual также доступен в интернете.
Прочтя настоящую статью, возможно, вы захотите узнать больше о Lex и YACC. Я не читал этих книг, но их названия звучат хорошо:
- Bison-The Yacc-Compatible Parser Generator
-
By Charles Donnelly and Richard Stallman. Доступно в магазине Amazon.
- Lex & Yacc
By John R. Levine, Tony Mason and Doug Brown. Книга признана стандартным трудом по этой теме, хотя и немного старовата. Обзоры есть на Amazon.
- Compilers : Principles, Techniques, and Tools
By Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. The 'Dragon Book'. Первое издание вышло в 1985, и книга до сих пор перепечатывается. Это классическая книга по конструированию компиляторов. Также на Amazon
Томас Ниманн (Thomas Niemann) написал статью о том, как написать компилятор и калькулятор с помощью Lex & YACC. Ее можно найти здесь.
Модерируемая группа новостей usenet comp.compilers также может быть полезна, однако не ожидайте, что там за вас будут решать ваши задачи! Перед тем, как послать вопрос в группу, прочтите их домашнюю страницу, и особенно файл FAQ.
Lex - A Lexical Analyzer Generator by M. E. Lesk and E. Schmidt. Одна из первых оригинальных работ. Можно найти здесь.
Yacc: Yet Another Compiler-Compiler by Stephen C. Johnson - один из первых оригинальных документов по YACC. Его можно найти здесь. Также в нем есть советы по стилю.
9. Благодарности
- Pete Jinks <pjj%cs.man.ac.uk>
- Chris Lattner <sabre%nondot.org>
- John W. Millaway <johnmillaway%yahoo.com>
- Martin Neitzel <neitzel%gaertner.de>
- Sumit Pandaya <sumit%elitecore.com>
- Esmond Pitt <esmond.pitt%bigpond.com>
- Eric S. Raymond
- Bob Schmertz <schmertz%wam.umd.edu>
- Adam Sulmicki <adam%cfar.umd.edu>
- Markus Triska <triska%gmx.at>
- Erik Verbruggen <erik%road-warrior.cs.kun.nl>
- Gary V. Vaughan <gary%gnu.org> (прочтите его книгу Autobook)
- Ivo van der Wijk ( Amaze Internet)