2

そこで、私は Bison と Flex を理解しようとしています (そして、この 2 つがどのように連携するか)。私が与えられた文法例はとてもシンプルで、

e → e plus t
e → t 
t → t TIMES f
t → f
f → LPAREN e RPAREN
f → ID

私のテスト入力は「x」だけで、出力は次のようになると予想しています。

"(e (t (f (ID x))))"

私が得ている実際の出力は次のとおりです。

ID x f t

なぜ出力が逆になっているのか疑問に思っています (まだ括弧を追加していません)。これが私のフレックスファイルとバイソンファイルです。

バイソン：

%{
#include "expr-parse-defs.h"
#include <iostream>

    std::string AST;
%}

%union {
  char *sval;
}

%token <sval> ID PLUS TIMES LPAREN RPAREN

%%


e :  
    | e PLUS t          { AST += std::string("e ") + $2 + "t "; }
    | t                 { AST += "t "; }
    ;

t : 
    | t TIMES f         { AST += std::string("t ") + $2 + "f "; }  
    | f                 { AST += "f "; } 
    ;

f : 
    | LPAREN e RPAREN   { AST += $1 + std::string("e ") + $3; }
    | ID                { AST += std::string("ID ") + $1 + " " ; }
    ;

%%


int main() {
    yyparse();
    std::cout << AST;
    return 0;
}

フレックス：

%{
#include <cstring>
#include <string>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include "expr-parse.tab.h"
#include "expr-parse-defs.h"


  using namespace std;
  int tokenpos = 0;

    char * process_token(const char* token){
        // we have to copy because we can't rely on yytext not changing underneath us:
        char *res = new char[strlen(yytext) + 3]; 
        strcpy(res, yytext);
        yylval.sval = res;
    }

%}

ID [a-zA-Z][a-zA-Z0-9_]*

%%
"+"   { yylval.sval = process_token("PLUS"); return PLUS; }
"*"   { yylval.sval = process_token("TIMES"); return TIMES; }
"("   { yylval.sval = process_token("LPAREN"); return LPAREN; }
")"   { yylval.sval = process_token("RPAREN"); return RPAREN; }
{ID}  { yylval.sval = process_token("ID"); return ID; } 
[\n]    

%%

int yyerror(const char *s) {
    cerr << "this is a bad error message and needs to be changed eventually" << endl;
    return 0;
}
4

1 に答える 1

4

Bison は、ボトムアップ LALR(1)パーサーを生成します。その仕組みは次のように想像できます。

  1. レクサーから 1 つのトークン、つまり an を読み取りますID。
  2. 端子がゼロのピースの後に が続くケースは存在しないことがわかり、このトークンIDを単純にシフトできることがわかります。これで、そのID端末がスタックに配置されました。
  3. トークンをシフトした後、もう 1 つのトークンを読み取ります。これは、この場合、入力マーカーの終わりになります。
  4. を使用する唯一の有効な方法は、IDに減らすことfです。したがって、それは適用され、スタックに がありますf → ID。f
  5. 次に、を取得するためにusingを還元します。t → ft
  6. 先読みは ではないTIMESため、ルールt → t TIMES fは適用されないため、を取得するために使用を減らします。e → te
  7. 先読みもそうではないのでPLUS、ここでもシフトするものは何もありません。
  8. ルート シンボルと同様eに、先読みはファイルの終わりマーカーであり、完了です。

このボトムアップ操作は奇妙に思えるかもしれませんが、一般的にはトップダウン解析よりも強力であり、より説明的なエラー メッセージが表示される可能性もあります。どの時点で先読みを使用して次のステップを決定するかを確認できます。また、実際の数値があり、おもちゃの電卓を実装している場合、このボトムアップ アプローチにより、式全体を解析する前に式の一部を評価できることも想像できます。マニュアルには、アルゴリズムの詳細が記載されています。

私は出力が次のようになることを期待しています:"(e (t (f (ID x))))"

そしたらこう書きます。例として、これを取ります：

%{
#include "expr-parse-defs.h"
#include <iostream>

#define YYSTYPE std::string;
%}

%token ID PLUS TIMES LPAREN RPAREN

%%

e :  
    | e PLUS t          { $$ = std::string("(e ") + $1 + " " + $3 + ")"; }
    | t                 { $$ = std::string("(e ") + $1 + ")"; }
    ;

[…]

これは、文字列を非終端記号のセマンティック値として使用します。のような非 POD 型では C++ を使用できないことに注意してくださいstd::string。パーサーがそのルールを実行している間に、予期した形式の式が「裏返して」組み立てられます。AST単一の変数を使用したアプローチは単純な例では機能しますが、2 つの非終端子を持つルールでe → e plus tは、2 つの文字列を結合する必要があります。これにはセマンティック値を使用するのが最善です。独自の C++ 型を定義して、用語のテキスト表現、数値、定義されたソース内の場所など、さまざまな情報を保持できます。

于 2013-02-14T07:14:32.857 に答える