2

私は、一般的な関数の構文糖衣を持っているLispのような言語を解析しようとしています。たとえば、plus関数は（+ 1 2）または1 + 2と書くことができます。言語を解釈しようとする前に糖衣構文を削除すると、解釈プロセスが大幅に容易になると思います。実装する必要があるのは関数呼び出しの場合であり、すべての中置演算子には対応する組み込み関数が必要です。レクサーから受け取ったトークンを反復処理するパーサーを作成し、それらを並べ替えて式をプレフィックス表記に入れることができると考えていました。ただし、これには、パーサーの出力もトークンのリストである必要があります。それはSpirit.Qiで可能ですか？私が理解している限り、スピリット。

4

1 に答える 1

5

もちろん、すべてが可能です。

そうは言っても、ASTを操作してみませんか。

  • 通訳中の入力表現について心配する必要はありません
  • 字句解析/構文解析中の通訳について心配する必要はありません

このようなAST表現を考えてみましょう（一種の単純化されたs式に触発されています）：

typedef boost::make_recursive_variant<
        std::string,
        std::vector< boost::recursive_variant_ >
   >::type expr_t;

s_exprまたはbinobjを受け入れて同じASTに解析するルールを定義できます

qi::rule<It, std::vector<expr_t>(), Skipper> binop;
qi::rule<It, expr_t(), Skipper> expr, s_expr, name;

expr   = binop | s_expr;

binop = (s_expr >> (string("+") | string("-") | string("*") | string("/")) >> expr)
    [
        phx::push_back(_val, _2),
        phx::push_back(_val, _1),
        phx::push_back(_val, _3)
    ];

name = as_string [ lexeme [ +(graph - char_("()") ) ] ];

s_expr = ('(' > +expr > ')') | name;

フルデモ

私はここにこのアイデアの完全なデモを持っています：https ：//gist.github.com/3047788

楽しみのために、私は投げました

  • カルマ（display.hpp / display.cpp）を使用(1 + 3)して、と同じ構文ツリーにどのように解析されるかを示すASTダンパー(+ 1 3)
  • 基本的な評価エンジン（eval.hpp / eval.cpp）1

test.cppのデモメイン：

int main()
{
    for (const auto input : std::list<std::string> {
         "",
         "(+ 1 3)",
         "(1 + 3)",
         "(1 + 4 / 2)",
         "(1 + (* 4 5 6) / 2)",
         "(avg   1 + (* 4 5 6) / 2)",
         "(trace 1 + (* 4 5 6) / 2 1 1 1 1 999)",
         "(avg   1 + (* 4 5 6) / 2 1 1 1 1 999)",
         "(avg   1 + (* 4 (unknown-function 5) 6) / 2 a b c)",
     })
    {
        std::cout << "----------------------\n";
        expr_t ast = doParse(input, qi::space);

        try 
        {
            std::cout << "eval<double>: " << eval<double>(ast) << std::endl;
            std::cout << "eval<int>   : " << eval<int>   (ast) << std::endl;
        } catch(std::exception const& e)
        {
            std::cerr << e.what() << '\n';
        }
    }
}

結果は次のようになります。

----------------------
parse failed: ''
warning: undefined '<no ast>'
eval<double>: 0
warning: undefined '<no ast>'
eval<int>   : 0
----------------------
parse success
input       : (+ 1 3)
ast parsed  : (+ 1 3)
eval<double>: 4
eval<int>   : 4
----------------------
parse success
input       : (1 + 3)
ast parsed  : ((+ 1 3))
eval<double>: 4
eval<int>   : 4
----------------------
parse success
input       : (1 + 4 / 2)
ast parsed  : ((+ 1 (/ 4 2)))
eval<double>: 3
eval<int>   : 3
----------------------
parse success
input       : (1 + (* 4 5 6) / 2)
ast parsed  : ((+ 1 (/ (* 4 5 6) 2)))
eval<double>: 61
eval<int>   : 61
----------------------
parse success
input       : (avg   1 + (* 4 5 6) / 2)
ast parsed  : (avg (+ 1 (/ (* 4 5 6) 2)))
eval<double>: 0
eval<int>   : 0
----------------------
parse success
input       : (trace 1 + (* 4 5 6) / 2 1 1 1 1 999)
ast parsed  : (trace (+ 1 (/ (* 4 5 6) 2)) 1 1 1 1 999)
trace( 61 1 1 1 1 999 )
eval<double>: 0
trace( 61 1 1 1 1 999 )
eval<int>   : 0
----------------------
parse success
input       : (avg   1 + (* 4 5 6) / 2 1 1 1 1 999)
ast parsed  : (avg (+ 1 (/ (* 4 5 6) 2)) 1 1 1 1 999)
eval<double>: 167.167
eval<int>   : 167
----------------------
parse success
input       : (avg   1 + (* 4 (unknown-function 5) 6) / 2 a b c)
ast parsed  : (avg (+ 1 (/ (* 4 (unknown-function 5) 6) 2)) a b c)
error: can't apply 'unknown-function' to 1 args (std::exception)

1型システムがないことを覚えておいてください。そのため、すべての値を（eg double result = eval<double>(ast)）として解釈するには、ハードコードされたデータ型を指定する必要があります。シンボルテーブルもありませんので、組み込み関数のみが存在し+-/* traceますavg

于 2012-07-04T15:19:19.013 に答える