Blog

C++ でlexer/parserをかくなら re2c+lemon がオススメな件

yacc や lex をつかっていても「なんかよくわからんけどうごく」という状態になりがちだったり、グローバル変数にまみれたりしがちだが、re2c + lemon だとそのへんがすっきりする。

レキサを以下のようにかく。yyfill を自前でかかなければいけないのがちょっと面倒だが、このようなクラスを手軽にかけるのはやはり便利である。flex ではこうはいかないのだ。

#ifndef CALC_SCANNER_H_
#define CALC_SCANNER_H_

#include <stdio.h>
#include <string.h>
#include <string>
#include <sstream>
#include <vector>
#include <iostream>
#include <fstream>
#include "scanner.def.h"
#include "parser.h"

class Scanner {
private:
    // iostream sucks. very slow.
    std::istream *ifs;
 
    // buffer memory
    char* m_buffer;
    // current position
    char* m_cursor;
    char* m_limit;
    char* m_token;
    char* m_marker;
    int m_buffer_size;
    int m_lineno;
 
public:

    void increment_line_number() {
        m_lineno++;
    }

    Scanner( std::istream *ifs_, int init_size=1024 )
        : m_buffer(0)
        , m_cursor(0)
        , m_limit(0)
        , m_token(0)
        , m_marker(0)
        , m_buffer_size(init_size)
        , m_lineno(1)
    {
        m_buffer = new char[m_buffer_size];
        m_cursor = m_limit = m_token = m_marker = m_buffer;
        ifs = ifs_;
    }
 
    ~Scanner() {
        delete [] m_buffer;
    }
 
    bool fill(int n) {
 
        // is eof?
        if (ifs->eof()) {
            if ((m_limit-m_cursor) <= 0) {
                return false;
            }
        }
 
        int restSize = m_limit-m_token;
        if (restSize+n >= m_buffer_size) {
            // extend buffer
            m_buffer_size *= 2;
            char* newBuffer = new char[m_buffer_size];
            for (int i=0; i<restSize; ++i) { // memcpy
                *(newBuffer+i) = *(m_token+i);
            }
            m_cursor = newBuffer + (m_cursor-m_token);
            m_token = newBuffer;
            m_limit = newBuffer + restSize;
 
            delete [] m_buffer;
            m_buffer = newBuffer;
        } else {
            // move remained data to head.
            for (int i=0; i<restSize; ++i) { //memmove( m_buffer, m_token, (restSize)*sizeof(char) );
                *(m_buffer+i) = *(m_token+i);
            }
            m_cursor = m_buffer + (m_cursor-m_token);
            m_token = m_buffer;
            m_limit = m_buffer+restSize;
        }
 
        // fill to buffer
        int read_size = m_buffer_size - restSize;
        ifs->read( m_limit, read_size );
        m_limit += ifs->gcount();
 
        return true;
    }
 
    std::string text() {
        return std::string( m_token, m_token+length() );
    }
    int length() {
        return (m_cursor-m_token);
    }
    int lineno() {
        return m_lineno;
    }
 
    int scan(YYSTYPE& yylval) {
std:
        m_token = m_cursor;
 
    /*!re2c
        re2c:define:YYCTYPE = "char";
        re2c:define:YYCURSOR = m_cursor;
        re2c:define:YYMARKER = m_marker;
        re2c:define:YYLIMIT = m_limit;
        re2c:define:YYFILL:naked = 1;
        re2c:define:YYFILL@len = #;
        re2c:define:YYFILL = "if (!fill(#)) { return 0; }";
        re2c:yyfill:enable = 1;
        re2c:indent:top = 2;
        re2c:indent:string="    ";

        INTEGER                = [1-9][0-9]*;
        WS                     = [ \r\n\t\f];
        ANY_CHARACTER          = [^];

        INTEGER {
            yylval.int_value = atoi(this->text().c_str());
            return TOKEN_INT;
        }
        "+" { return TOKEN_ADD; }
        "-" { return TOKEN_SUB; }
        "*" { return TOKEN_MUL; }
        "/" { return TOKEN_DIV; }
        WS {
            goto std;
        }
        ANY_CHARACTER {
            printf("unexpected character: '%c(%d)'\n", *m_token, *m_token);
            goto std;
        }

    */

    }
};

#endif // CALC_SCANNER_H_

yylval とパーザの状態をあらわすクラスを定義する。YYSTYPE という名前は yacc からもらっている。もっといい名前のつけかたがある気がするが。

#ifndef CALC_SCANNER_DEF_H_
#define CALC_SCANNER_DEF_H_

typedef union {
    int int_value;
} YYSTYPE;

struct ParserState {
    int result;
    ParserState() :result(0) {
    }
};

#endif // CALC_SCANNER_DEF_H_

パーザは以下のように書く。%extra_argument で、パーザにたいする追加の引数を定義できる。AST を返したい場合などはこれを介してやればスレッドセーフとなるだろう。もはやグローバル変数をつかう必要はないのだ。

%token_prefix TOKEN_

%left ADD SUB.
%left MUL DIV.

%token_type { YYSTYPE }

%extra_argument { ParserState *state }

%include {
#include <iostream>
#include "scanner.def.h"
}

%syntax_error {
    fprintf(stderr, "Syntax error\n");
}

%parse_failure {
    fprintf(stderr,"Giving up.  Parser is hopelessly lost...\n");
}

%start_symbol program

program ::= expr(A). {
    state->result = A.int_value;
}

expr(A) ::= primary_expression(B). {
    A.int_value = B.int_value;
}
expr(A) ::= expr(B) SUB primary_expression(C). {
    A.int_value = B.int_value - C.int_value;
}
expr(A) ::= expr(B) ADD primary_expression(C). {
    A.int_value = B.int_value + C.int_value;
}
expr(A) ::= expr(B) DIV primary_expression(C). {
    A.int_value = B.int_value / C.int_value;
}
expr(A) ::= expr(B) MUL primary_expression(C). {
    A.int_value = B.int_value * C.int_value;
}

primary_expression(A) ::= INT(B). {
    A.int_value = B.int_value;
}

さてこのパーザとレキサをうごかす main プログラムがこちらだ。まったくグローバル変数をつかっていないし、パーザとレキサの間の関係性が非常に明確である。つなぎこみ部分を自分でかけるので可能性は無限大だ。

#include <sstream>
#include <cassert>
#include <cstdlib>
#include "scanner.h"
#include "parser.c"

int main() {
    YYSTYPE yylval;
    Scanner scanner(&std::cin);
    void *pParser = ParseAlloc(malloc);
    int tokenID;

#if 0
    ParseTrace(stderr, (char*)"[Parser] >> ");
#endif

    ParserState state;
    // scanner.scan return 0 when get EOF.
    while (tokenID = scanner.scan(yylval)) {
        // printf("GET TOKEN: %d\n", tokenID);
        Parse(pParser, tokenID, yylval, &state);
    }
    Parse(pParser, 0, yylval, &state);
    ParseFree(pParser, free);

    printf("RESULT: %d\n", state.result);
    return 0;
}

今回は手抜きなので parser はクラスになっていないが、これも非常に簡単にクラスにできる。lemon は lempar.c というテンプレートを元にパーザを生成しているので、このファイルをちょっといじればよいのだ。

lemon + re2c だと lex + yacc よりとてもスマートにかけるので、今後はこのくみあわせでいこうとおもっている。