Bison/Flex以相反的順序處理令牌

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文件。

野牛：

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

野牛生成bottom-upLALR(1)解析器。你可以想像它的工作原理是這樣的：

1. 它讀取從詞法分析器一個道理，即一個ID。
2. 它看到，沒有任何情況下，一個零終端片後跟ID，所以它知道它可以簡單地轉移這個令牌。現在它的堆棧中有ID終端。
3. 移動令牌後，它會再讀取一個令牌，這將成爲您的案例中輸入標記的結尾。
4. 與ID唯一有效的做法是將減小到f。所以它適用f → ID，現在它的棧上有一個f。
5. 接下來它減少使用t → f獲得t。
6. 作爲先行不TIMES，規則t → t TIMES f將不適用，因此使用e → t獲得e它減少。
7. 因爲預見不是​​也沒有任何東西在這裏轉移。
8. 由於e是根符號，並且超前是文件結束標記，所以您完成了。

這種自下而上的操作對您來說可能看起來很奇怪，但總的來說它更強大，並且還可能導致比自上而下的解析更多的描述性錯誤消息。您可以看到它在哪個時間使用前瞻來決定下一步。你也可以想象，如果你有實際的數字並且正在實現一些玩具計算器，這種自下而上的方法將允許你在分析整個表達式之前評估表達式的部分內容。該手冊有details on the algorithm。

我期待的輸出爲："(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 + ")"; } 
    ; 

[…] 

這使用字符串作爲你的非終端的語義值。 Noite that you cannot use C++ with non-POD types like std::string。現在，您所期望的表單的表達式在解析器執行其規則時「內外」組裝。單個AST變量的方法適用於您的簡單示例，但具有兩個非終端子項（如e → e plus t）的規則必須組合兩個字符串。最好爲此使用語義值。您可以定義您自己的C++類型來保存各種信息，例如該術語的文本表示，一個數值以及它在其中定義的位置。