If a C programmer asks "do you want to see something cool?", run away.
--John Van Enk

Wednesday, July 25, 2007

Flex & Bison C++ Interoperability Continued

Итак, возвращаясь к когда-то написанному мной введению об interoperability лексических анализаторов на С++, сгенерированных при помощи Flex, и синтаксических анализаторов, сгенерированных при помощи Bison, в этой статье хочу разобрать простенький примерчик в котором лексический анализатор (далее лексер) распознает строки комментариев командного интерпретатора bash и пустые строки и пропускает их, а все остальные возвращает синтаксическому анализатору (далее парсеру) для последующего вывода в командную строку. Сначала я приведу код, а затем уж постараюсь объяснить по возможности что какая строчка значит, ну и соответственно команды которые необходимы чтобы это все собрать в кучу.

Файл intertest.cpp

#include <fstream>
#include "lexer.h"
#include "parser.h"
using namespace std;
using namespace test;
int main(int argc, char *argv[])
{
    ifstream infile(argv[1]);
    Lexer lexer(&infile);
    Parser parser(lexer);
    return parser.parse();
}

Тут я думаю обьяснения излишни ;-)

Файл lexer.h

#ifndef _LEXER_H
#define _LEXER_H

#ifndef __FLEX_LEXER_H
#undef yyFlexLexer
#include <FlexLexer.h>
#endif
#include <stdexcept>
#include "parser.h"
namespace test{
class Lexer: public yyFlexLexer {
    //tokenizer
    int yylex();
public:

    //ctor
    Lexer( std::istream* src = 0 );

    //dtor
    virtual ~Lexer();

    //functor
    Parser::token_type operator() ( Parser::semantic_type* lval, Parser::location_type* lloc = 0 );

    //error report routine
    virtual void LexerError( const char* msg );

private:

    Parser::semantic_type* yylval;
};
}
#endif

Следующая конструкция необходима для того, чтобы заголовочный файл
FlexLexer.h не был включен повторно в одну и ту же единицу трансляции
см. предыдущую статью

#ifndef __FLEX_LEXER_H
#undef yyFlexLexer
#include <FlexLexer.h>
#endif

По поводу перегрузки operator() подробно также можно почитать там же.

Файл lexer.lpp

%option 8bit
%option noyywrap
%option c++
%option yyclass="test::Lexer"
%option pointer
%option nodefault
string [^#\n]+\n
garbage .*\n
%{
#include "lexer.h"
#include "parser.h"
%}
%%
{string} {
      yylval->str=yytext;
      return Parser::token::STRING;
}
{garbage} //skip all other
%%
namespace test{

//ctor
Lexer::Lexer( std::istream* src ): yyFlexLexer( src, 0 ){}

//dtor
Lexer::~Lexer( ){};

//error report routine

void Lexer::LexerError( const char* msg ) {
    throw std::runtime_error( msg );
}

//function call operator overloading 
Parser::token_type Lexer::operator() ( Parser::semantic_type* lval, Parser::location_type* lloc ) {
    yylval = lval;
    return Parser::token_type( yylex() );
}
}

%option 8bit - использовать 8 битную кодировку символов

%option noyywrap - yywrap() - функция которая вызывается по достижению конца файла, ее можно использовать для того чтобы открыть новый файл и продолжить сканировать его (в этом случае функция возвращает 0). Поскольку нам это не нужно, то используя эту опцию указываем что yywrap всегда возвращает 1 - сканирование завершено

%option c++ - генерировать код на С++

%option yyclass="test::Lexer" - сгенерировать реалзацию функции yylex(), осуществляющей сканирование для класса Lexer, унаследованного от yyFlexLexer и находящегося в пространстве имен test, это необходимо для того, чтобы в теле правил flex файла были доступны указатели на переменные, передаваемые парсером в лексер при вызове последнего для получения следующего токена

%option pointer - опция, контролирующая каким образом определен yytext, - как указатель на распознанную строку или как статический буфер, содержащий ее копию. Нам нужен указатель, потому на всякий случай указываем ее.

%option nodefault - по умолчанию весь ввод который не может быть распознан лексером вываливается в консоль, нам этого behaviour не нужно, говорим об этом flex'у

string [^#\n]+\n - регулярное выражение для строки - строка это все что угодно кроме символов '#' и '\n' встречающееся в тексте более одного раза и заканчивающееся символом '\n'

garbage .*\n - выражение для "мусора" - т.е. всего что не подходит под определение строки

Далее включаем заголовочные файлы лексера и парсера. Файл парсера нужен для констант токенов, которые в нем определены.
%{
#include "lexer.h"
#include "parser.h"
%}

Далее начинается секция правил flex'а
%%

Следующее правило служит для распознавания строки. Поскольку оба правила могут распознать одну и ту же строку, то указываем именно правило для string первым поскольку при разрешении таких неоднозначностей flex использует первое в списке правил для обработки ввода (first rule match).
{string} {
    yylval->str=yytext; //копируем
    return Parser::token::STRING;
}

{garbage} //все что не нужно пропускаем 
//(т.е. не делаем return)


Далее идет секция кода
%%
В ней размещаем реализацию методов класса Lexer.

Файл parser.ypp

%skeleton "lalr1.cc"
%parse-param {test::Lexer& yylex}
%define "parser_class_name" "Parser"
%name-prefix="test"
/*
 *   Секция кода
 */
%{
/*
 *   Этот код (находящийся перед директивой %union)
 *   будет включен в сгенерированный bison'ом 
 *   заголовочный файл ДО ОПРЕДЕЛЕНИЯ КЛАССА 
 *   СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА Parser
 */
namespace test{
class Lexer;
}
%}
%union {
      char* str;
}
%{
/*
 *   Этот код (находящийся после директивы %union)
 *   будет включен в сгенерированный файл парсера 
 *   (синтаксического анализатора)
 *   (parser.cс например)
 */
#include "lexer.h"
#include <cstdio>
#include <stdexcept>
%}
%token <str> STRING
%start file
%%
/*
 *  Grammar rules follow
 */
file    :
      | file STRING   { printf("%s",$2);}
      ;
%%
void test::Parser::error (const location_type& loc, const std::string& msg){
    throw std::runtime_error(msg);
};

%skeleton "lalr1.cc" - используем шаблон для генерации кода парсера на С++

%parse-param {test::Lexer& yylex} - указываем что конструктор сгенерированного парсера должен принимать аргумент - ссылку на лексер

%define "parser_class_name" "Parser" - указываем что сгенерированный bison'ом класс парсера должен называться Parser

%name-prefix="test" - указываем что пространство имен в котором находится сгенерированный bison'ом класс будет называться test

namespace test{
class Lexer;
}
- объявляем класс Lexer, потому как оба класса (Lexer и Parser) зависят друг от друга - Lexer использует типы определенные в Parser а конструктор Parser принимает ссылку на Lexer в качестве аргумента.

%union {
char* str;
}
Директива %union используется для следующей цели:
иногда бывает необходимо возвратить из лексического анализатора в синтаксический кроме константы, определяющей токен (лексическую единицу) еще и значение связанное с этим токеном (например если в тексте встретилось 8536 то лексический анализатор возвращает токен INTEGER (целочисленная константа) а само значение присваивается переменной, имеющей тип Parser::semantic_type* var , следующим образом:
var->integer=atoi(yytext));

При этом в файле Bison директива %union выглядит следующим образом

%union{
int integer;
}


Указатель на переменную типа Parser::semantic_type передается парсером лексеру при вызове последнего для получения следующего токена затем в теле правила это значение может быть получено путем использования следующей конструкции: $номер_элемента_правила

%{
/*
*   Этот код (находящийся после директивы %union)
*   будет включен в сгенерированный файл парсера 
*   (синтаксического анализатора)
*   (parser.cс например)
*/
#include "lexer.h"
#include <cstdio>
#include <stdexcept>
%}
- в сгенерированном файле реализации парсера (например parser.cc) интерфейс класса Lexer уже должен быть известен, поэтому включаем его заголовочник.

%token <str> STRING - объявление токена конструкция в угловых скобках указывает на то, что с этим токеном связано значение и что оно хранится в поле str union'a

%start file - объявляем стартовое правило

file    :
      | file STRING   { printf("%s",$2);}
      ;

правило определяющее что из себя представляет файл - это набор из 0 или более токенов STRING. Правила записываются в расширенной форме нотации Бэкуса - Наура (Enhanced Backus Naur Form - EBNF).
Конструкция в теле правила $2 - это обращение к значению токена STRING (тому самому которое хранится внутри union)

Далее следует секция кода, в которую можно поместить различные функции - я разместил в ней реализацию метода error класса Parser, которую и так надо писать самому.

Теперь собираем все в кучу:

$flex -olexer.cpp lexer.lpp
$bison --defines=parser.h -oparser.cpp parser.ypp
$g++ intertest.cpp parser.cpp lexer.cpp -o test

Проверим на следующем файле

#!/bin/bash
#comment

ls -l

#another comment

ps


Результат работы программы

commander@a64:~/work/src/test$ ./test test.bash
ls -l
ps


Фуф! Вот кажись и все ;-). Have fun!