Skip to main content

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!

Comments

  1. Спасибо, отличная статья!

    ReplyDelete
  2. Спасибо за проделанную работу. Очень помогло.

    ReplyDelete
  3. да мне такая информация когда-то тоже пригодилась бы. Но пришлось изобретать велосипед.

    ReplyDelete
  4. Очень тяжело заставить себя расписать то, что сам же и делал. Хотя бы для самого же себя:-) Сколько раз упрекал себя в этом.

    ReplyDelete
  5. мне писать не трудно, а лишняя систематизация информации не повредит. Может когда еще придется с этим работать через определенное время? Поэтому стараюсь записывать в блог такие вещи. Тяжелее потом вспоминать

    ReplyDelete
  6. Добрый день, пытаюсь то же гденерировать парсер, только у меня получается вот такая ошибка:
    C:\tmp\tmp\bin>bison.exe builder.yacc
    m4: m4_syscmd subprocess failed: No such file or directory
    m4:C:\tmp\tmp/share/bison/lalr1.cc:25: cannot run command `cat <<'_m4eof'
    @fatal("lalr1.cc": using %%defines is mandatory@)@
    _m4eof
    ': No such file or directory
    C:\tmp\tmp/share/bison/lalr1.cc:25: error: b4_cat: cannot write to stdout
    C:\tmp\tmp/share/bison/lalr1.cc:25: the top level

    может посдкажете в чем проблемма?

    ReplyDelete
  7. похоже на то что у вас не настроено окружение. Если вы используете Windows то я бы порекомендовал установить Cygwin или воспользоваться MSYS. А так похоже что m4 (http://www.gnu.org/software/m4/) не может выполнить комманду "cat <<" при обработке скелетона lalr1.cc

    ReplyDelete
  8. Спасибо за совет, но все оказалось проще, при генерации не стал указывать параметр defines=parser.h
    а он судя по всему обязателен. У меня уже был рабочий вариант для Си, вот решил последовать примеру и сделать то же многопоточно и вообще :), но кавалерийский метод не сработал, вот теперь разбираюсь с документацией, т.к. все равно ошибки есть, правда уже при компилляции. Почему-то код объявления лексера
    %{
    namespace test{
    class Lexer;
    }
    %}
    вставляется не в файл определения парсера, а файл реализации, хотя до юнион написан.

    ReplyDelete
  9. А вы могли ошибиться? Может быть код включения хедерников и объявления лексера нужно поместить например так:

    %code requires {
    namespace test{
    class Lexer;
    }
    }

    ReplyDelete
  10. $flex -V
    flex 2.5.35

    $bison -V
    bison (GNU Bison) 2.3

    c этими версиями пример работает, хотя походу дела и пришлось исправить несколько незначительных ошибок вроде пропущенной закрывающей скобки. Сейчас поправлю примеры

    ReplyDelete
  11. bison (GNU Bison) 2.4.1
    flex 2.5.4 (под win32 новее найти не смог, а самому собрать пока не получилось)
    Бизон у меня новее, там в документации вот что пишут
    %code {code} [Directive]
    This is the unqualified form of the %code directive. It inserts code verbatim at a languagedependent
    default location in the output1.

    requires
     Language(s): C, C++
     Purpose: This is the best place to write dependency code required for YYSTYPE and
    YYLTYPE. In other words, it’s the best place to define types referenced in %union
    directives, and it’s the best place to override Bison’s default YYSTYPE and YYLTYPE
    definitions.

    ну как-то так. У меня все заработало корректно.
    А вообще огромное спасибо, за хорошии статьи, они на порядок облегчили разбор flex/bison.

    ReplyDelete
  12. Есть один момент не совсем корректный,
    ---------
    {string} {
    yylval->str=yytext; //копируем
    -------
    если правило будет сложным, например:
    obj_key '{' string_value '}' ';'
    то, насколько понимаю, после разбора yytext будет содержать указатель на строку "}", а не string_value, ИМХО надо именно копировать строку, например так,
    strcpy(yylval->name, yytext);
    но для этого name конечно же надо объявить как-то так
    char name[128];
    может и не совсем прямой способ и наверно вполне очевидный... но как человек разнеженный std:string на этом сильно запоролся и долго не мог понять что не так.

    ReplyDelete
  13. да, там бок в том, что union может содержать только POD типы и чтоб не парить мозг с управлением памятью и копированием (yytext все равно остается валидным указателем, который указывает если мне не изменяет память на один из элементов по моему статического буфера "внутри" сгенерированной реализации) я скопировал указатель. Ну а char name[128] - не есть гуд имхо, лучше уж тогда указатель на char и управление памятью + strcpy.

    ReplyDelete
  14. кроме того можно добавить к или вычесть из (смотря куда он в конце-концов указывает после разбора) указателя yytext необходимое смещение, ну и естественно не помешало бы name в union сделать char const*, думаю. И да там во флексе была проблема c несколькими input buffers - раз и два. Не смотрел пропатчили они скелетон или нет.

    ReplyDelete

Post a Comment

СООБЩЕНИЕ СПАМЕРАМ: прежде чем пытаться оставить ссылку на свой ресурс в комментарии, прошу обратить внимание на тег nofollow, которым они помечены и зря не терять ни свое ни мое время. А будете упорствовать еще и noindex поставлю