2

所以我试图了解 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 文件。

野牛：

%{
#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. 它从词法分析器中读取一个标记，即一个ID.
  2. 它看到没有零终结符后面跟着 的情况ID，所以它知道它可以简单地移动这个标记。现在它ID的堆栈上有那个终端。
  3. 移动令牌后，它会再读取一个令牌，在您的情况下，这将是输入标记的结尾。
  4. 与 an 唯一有效的事情ID是将其简化为f. 所以它适用f → ID，现在f它的堆栈上有一个。
  5. 接下来它减少使用t → f以获得t.
  6. 由于前瞻不是TIMES，因此该规则t → t TIMES f将不适用，因此它减少了使用e → t来获取e。
  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 + ")"; }
    ;

[…]

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

于 2013-02-14T07:14:32.857 回答