lxqで字句解析 + 構文解析を行って簡単な電卓を作る

lxq とは

lxq は筆者が製作している字句解析器及び構文解析器を宣言的に記述、自動生成するためのプログラムです。今のところ C++ のコードを生成します。wikiはこちら
処理できる構文クラスは LALR(1) です。
C++ の場合、出力されたヘッダファイルを include し必要なセマンティックアクションを包含したクラスを渡すだけでポータビリティに字句解析器と構文解析器を利用できます。

使い方など

基本的に、

• 字句解析器生成系の定義されたブロック
• トークンの情報を定めたブロック
• パーサーの情報を定めたブロック

を lxq ファイルに記述し、コマンドラインで

lxq ifile.lxq ofiles_directry

とすれば次の三つのファイルが生成されます。

• lxq.hpp
• (lexer name).hpp
• (parser name).hpp

(lexer name).hpp 及び (parser name).hpp は入力する ifile.lxq ファイルに書かれているそれぞれの Lexer 部、 Parser 部の名前の定義によって変わります。

実行ファイル

MSVC2015 で製作しています。
動作中の文字コードを変えたかったり別の環境で使いたい場合は別途ビルドしてください。
処理系依存の機能を使っていないので、 Linux 環境や gcc 5.2.0 などでもビルドできるはずです（未確認）。
Download (Windows 8.1 or later, x86)

何ができるのか（もっと具体的に！）

Lexer部

<lexer> mylexer{
    mul = "\*";
    div = "/";
    add = "\+";
    sub = "\-";
    l_paren = "\(";
    r_paren = "\)";
    semicolon = ";";
    recover = "recover";

    [make_id]
    id = "[0-9]+";

    [drop]
    space = " +";
}

トークンに結びつける文字列を決める際に正規表現が使えます。
この正規表現はNFAから最小DFAに変換しているので、Flexなどにあるバックトラックを使った右文脈などは利用できませんが、以下の機能が利用できます。

regexp	作用
ab	aとbの連結
.	任意の文字にマッチ
[A-Z]	文字クラス
[^A-Z]	否定文字クラス
a{n,m}	n個からm個までのaにマッチ
a{n,}	n個以上のaにマッチ
a{n}	n個のaにマッチ
a*	0個以上のaにマッチ
a+	1個以上のaにマッチ
a?	0個か1個のaにマッチ
a|b	aかbにマッチ
(a)	優先順位変更

ちなみにトークンにも、トークン特有の値があります。例えば数値トークンである文字列"256"などです。この文字列はいつ数値として扱えるように変換するべきでしょうか。lxqには正規表現のマッチした文字列に対して何らかのセマンティックデータに変換したいのであれば、セマンティック関数をトークンの前に記述します。この場合[make_id]が相当します。
make_id関数は、このレキサーを利用する際に次の様な実装がなければなりません。

// セマンティックデータ
struct semantic_data : public lxq::semantic_data{
    semantic_data(double value) : value(value){}
    double value;
};
   :
   :
   :
struct semantic_action{
    // lexer用.
    // 文字列(range)から値を生成する.
    // atoiしてるだけ
    template<class Iter>
    lxq::semantic_data *make_id(Iter first, Iter last){
        return new semantic_data(static_cast<double>(std::atoi(std::string(first, last).c_str())));
    }
    :
    :

値としてセマンティックデータを得ることに成功しました。

また、使用しないトークン（Whitespace）は字句解析結果に残さずそのまま捨てる事ができます。
その場合はセマンティック関数に[drop]とだけ記述してください。

token部

<token> mytoken{
    <right>{ unary_minus; }
    <left>{
        mul, div;
        add, sub;
    }
    l_paren, r_paren, recover, semicolon;
    id;
}

トークンの優先順位と結合方向を制定し、parser部でコンフリクト回避のヒントを与える事で構文の定義を簡潔に済ませることができます。
基本的にカンマで同じ優先順位のトークンを区切り、セミコロンで次に優先順位の低いトークンの定義に入ります。
<left>及び<right>ブロックで囲われたトークンは結合方向の情報をトークンに与えます。
基本的には lexer 部で定義したトークンしか記述できませんが、unary_minusの様に lexer 部で定義していないトークンも規定することができます。
これはunary_minusが parser 部で導出規則の優先順位を強制的に変換するタグとして利用されるためです。

parser部

<parser> myparser{
    Lines
        : [print]   Lines E(0) semicolon
        | []        Lines semicolon
        | [recover] error recover semicolon
        | []
        ;

    E
        : [make_add] E(0) add E(1)
        | [make_sub] E(0) sub E(1)
        | [make_mlt] E(0) mul E(1)
        | [make_div] E(0) div E(1)
        | [identity] l_paren E(0) r_paren
        | [make_inv] <unary_minus> sub E(0)
        | [identity] id(0)
        ;
}

トークンから構文規則を記述します。
BNF が分かれば大体どうなっているか理解できると思います。
[]で囲まれた記述がセマンティックアクションです。その規則が還元されたときに発動します。ない場合は何も起こりません。
また、セマンティックアクションがない状態でかつ導出規則の右辺もないと、その導出規則はεを導出可能と判断されます。
あってもなくてもどちらでも良い規則という事ですね。
また、右辺のシーケンスに(n)等という様に数字が付けられていた場合はセマンティックアクションの n 番目の引数として実行時に渡されます。
<>で囲まれたトークンはタグです。
errorトークンは特殊な予約語で、構文解析中にエラーが起こった際にこの記述のされているルールが適用されます。
例の場合、意味は『不正なトークンに出会ったらエラーを検出できる状態まで内部状態を戻して、復帰に必要なrecoverトークンとsemicolonトークンに出会うまで解析を続行し、復帰用のセマンティックアクションrecoverを呼び出す』というものです。
recover関数内でプログラマはエラーを修復してもいいですし、例外を送出するなどして構文解析を停止させても構いません。

生成されたファイルを利用する。

#include <iostream>
#include <cstdlib>
#include "lxq.hpp"
#include "mylexer.hpp"
#include "myparser.hpp"

入出力用の<iostream>と、std::atoi用の<cstdlib>をまず include します。
次に生成された3つのファイルlxq.hpp mylexer.hpp myparser.hppを include します。

次はセマンティックデータとセマンティックアクションです。
Lexer部の説明でちらっと書きましたが、全体像はこんな感じです。

// セマンティックデータとセマンティックアクション
// ここあたりは人力で書く

struct semantic_data : public lxq::semantic_data{
    semantic_data(double value) : value(value){}
    double value;
};

struct semantic_action{
    // lexer用.
    // 文字列(range)から値を生成する.
    // atoiしてるだけ
    template<class Iter>
    lxq::semantic_data *make_id(Iter first, Iter last){
        return new semantic_data(static_cast<double>(std::atoi(std::string(first, last).c_str())));
    }

    // 足す.
    lxq::semantic_data *make_add(lxq::semantic_data *x_, lxq::semantic_data *y_){
        semantic_data *x = static_cast<semantic_data*>(x_);
        semantic_data *y = static_cast<semantic_data*>(y_);
        return new semantic_data(x->value + y->value);
    }

    // 引く.
    lxq::semantic_data *make_sub(lxq::semantic_data *x_, lxq::semantic_data *y_){
        semantic_data *x = static_cast<semantic_data*>(x_);
        semantic_data *y = static_cast<semantic_data*>(y_);
        return new semantic_data(x->value - y->value);
    }

    // 掛ける.
    lxq::semantic_data *make_mlt(lxq::semantic_data *x_, lxq::semantic_data *y_){
        semantic_data *x = static_cast<semantic_data*>(x_);
        semantic_data *y = static_cast<semantic_data*>(y_);
        return new semantic_data(x->value * y->value);
    }

    // 割る.
    lxq::semantic_data *make_div(lxq::semantic_data *x_, lxq::semantic_data *y_){
        semantic_data *x = static_cast<semantic_data*>(x_);
        semantic_data *y = static_cast<semantic_data*>(y_);
        return new semantic_data(x->value / y->value);
    }

    // そのままコピー.
    lxq::semantic_data *identity(lxq::semantic_data *x){
        return new semantic_data(static_cast<semantic_data*>(x)->value);
    }

    // 符号を反転する.
    lxq::semantic_data *make_inv(lxq::semantic_data *x_){
        semantic_data *x = static_cast<semantic_data*>(x_);
        return new semantic_data(-x->value);
    }

    // プリント.
    lxq::semantic_data *print(lxq::semantic_data *x_){
        semantic_data *x = static_cast<semantic_data*>(x_);
        std::cout << x->value << std::endl;
        return nullptr;
    }

    // エラー復帰.
    lxq::semantic_data *recover(){
        std::cout << "reenter expr." << std::endl;
        return nullptr;
    }
};

今までのパーサーから実際に電卓を動作させてみます。まずは解析対象となる文字列を用意します。
ここではエラー処理を行うため、最初に意図的に不正な文字列の並びを記述しています。

int main(){
    // 解析対象の文字列.
    std::string str = "-1 + + ; ; recover; (2 - 3) * 4 / 5; 1 / 4;";

    // セマンティックアクションを内部に持つインスタンスを生成する.
    semantic_action sa;

    // 字句解析.
    using lexer = mylexer<std::string::iterator>;
    std::vector<lexer::token_type> result = lexer::tokenize(str.begin(), str.end(), sa);

    // 構文解析.
    std::unique_ptr<lxq::semantic_data> ptr;
    using parser = myparser::parser<lexer, semantic_action>;
    parser p(sa);
    try{
        if(p.parse(ptr, result.begin(), result.end()) != result.end()){
            std::cout << "parsing error" << std::endl;
            return 0;
        }
    }catch(parser::parsing_error e){
        // 構文規則に書いたエラーハンドリングだけでは捕えきれなかったエラーをここでハンドルする.
        std::cout << "parsing error: " << e.char_num << ", '" << std::string(e.first, e.last) << "'" << std::endl;
    }

    return 0;
}

では実行してみましょう。

reenter expr.
-0.8
0.25

ひとつめの結果は不正な式を受理したときのメッセージです。
ふたつめ、みっつめはそのままの計算結果です。