c++ - Bison/Flex 以相反的顺序处理 token

Question

因此，我试图了解 Bison 和 Flex(以及两者如何结合使用)。我得到的示例语法非常简单，

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

我想知道为什么我的输出是向后的(我还没有添加括号)。这是我的 flex 和 bison 文件。

Bison :

%{
#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;
}

Answer 1

Bison 生成一个 bottom-up LALR(1)解析器。你可以想象它的工作原理是这样的:

1. 它从词法分析器读取一个标记，即 ID。
2. 它看到没有零终端片后跟 ID 的情况，所以它知道它可以简单地移动这个标记。现在它的堆栈上有 ID 终端。
3. 移动 token 后，它会再读取一个 token ，在您的情况下这将是输入标记的结尾。
4. 对 ID 进行的唯一有效操作是将其减少为f。所以它应用 f → ID，现在它的堆栈上有一个 f。
5. 接下来它减少使用t → f来获得t。
6. 由于前瞻不是TIMES，规则t → t TIMES f 将不适用，因此它减少使用e → t 得到e。
7. 由于前瞻性也不是 PLUS，因此这里也没有任何可移动的内容。
8. 由于 e 是根符号，而前瞻是文件结束标记，您就完成了。

这种自下而上的操作对您来说可能看起来很奇怪，但通常比自上而下的解析更强大，并且还会导致更具描述性的错误消息。您可以看到它在什么时候使用前瞻来决定下一步。您还可以想象，如果您有实际数字并正在实现一些玩具计算器，这种自下而上的方法将允许您在解析整个表达式之前计算部分表达式。说明书有details on the algorithm .

I'm expecting the output to be: "(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 + ")"; }
    ;

[…]

这使用字符串作为非终结符的语义值。注意你cannot use C++ with non-POD types像 std::string。现在，当解析器执行其规则时，您期望的形式的表达式被“由内而外”组装。使用单个 AST 变量的方法适用于您的简单示例，但是具有两个非终端子项(如 e → e plus t)的规则必须组合两个字符串。最好为此使用语义值。您可以定义自己的 C++ 类型来保存各种信息，例如术语的文本表示、数值和源中定义它的位置。