Bison/Flex，減少/減少，不同生產中的標識符

Question

我在做野牛/ flex的分析器。

這是我的代碼部分：

我要實現的任務生產，使該標識符既可以是boolean_expr或EXPR，它的類型將通過符號表進行檢查。 所以它允許這樣的：

int a = 1; 
boolean b = true; 
if(b) ... 

但是，降低/減少，如果我包括這兩個長期和boolean_expr標識，任何解決方案來解決這個問題呢？

Answer 1

本質上，你要做的是在你的語法中注入語義規則（類型信息）。這是可能的，但這並不容易。更重要的是，這並不是一個好主意。如果語法和語義描述得很好，幾乎總是最好的。

完全相同，因爲呈現的語法是毫不含糊的，並且LALR(1)。但是，後一個特徵很脆弱，並且在完成語法時難以維護它。

例如，您不包括你的賦值語法在你的問題，但它會

assignment: identifier '=' expr 
      | identifier '=' boolean_expr 
      ; 

不同於所示的語法部分的剩餘部分，即生產是不明確的，因爲：

x = y 

不知道任何關於y,y可以減少到term或boolean_expr。

一個可能更有趣的例子是在語法中增加了括號。這樣做的最顯而易見的方法是添加兩種生產：

term: '(' expr ')' 

boolean_expr: '(' boolean_expr ')' 

產生的語法也不含糊，但它不再是LALR(1)。考慮以下兩個聲明：

boolean x = (y) < 7 
boolean x = (y) 

在第一個，y必須是int使得(y)可以減少到一個term;在第二個y必須是boolean，以便(y)可以減少到boolean_expr。沒有歧義;一旦看到（或不看）<，就完全清楚要選擇哪種減少。但是<不是超前記號，而實際上它可能是從y任意遙遠：

boolean x = ((((((((((((((((((((((y... 

所以產生明確的語法不是LALR(k)任何k。你可以解決這個問題

---

的一種方法是通過給符號表掃描訪問在詞彙層面注入類型的信息。然後，掃描器可以在符號表中查找已掃描的標識符標記，並使用符號表中的信息來決定三種標記類型之一（或更多，如果您有更多數據類型）：undefined_variable,integer_variable和boolean_variable。然後，你將有，例如：

declaration: "int" undefined_variable '=' expr 
      | "boolean" undefined_variable '=' boolean_expr 
      ; 

term: integer_variable 
    | ... 
    ; 

boolean_expr: boolean_variable 
      | ... 
      ; 

，將工作，但它應該是顯而易見的，這是不可伸縮的：每次添加一個類型的時候，你就必須擴大雙方的語法和詞彙的描述，因爲現在的語義不僅與語法混淆，甚至還與詞法分析混雜在一起。一旦你讓語義脫離盒子，它往往會污染一切。

有些語言的確是最方便的解決方案：例如，如果區分typedef名稱和標識符名稱，C語法分析就容易得多，因此您可以判斷(t)*x是演員還是乘法演員。 （但是對於C++來說這並不容易，C++有更復雜的名稱查找規則，並且爲了找到正確的解析也需要語義分析。）

但是，老實說，我會建議你做而不是使用C語言 - 更少的C++ - 作爲如何設計語言的模型。編譯器難以解析的語言對於人類來說也很難解析。該"most vexing parse"仍然是痛苦的正規來源C++新人，甚至有時會絆倒了比較有經驗的程序員：

class X { 
    public: 
    X(int n = 0) : data_is_available_(n) {} 
    operator bool() const { return data_is_available_; } 
    // ... 
    private: 
    bool data_is_available_; 
    // ... 
}; 

X my_x_object(); 
// ... 
if (!x) { 
    // This code is unreachable. Can you see why? 
} 

總之，你最好用可以被解析成一個AST沒有任何語言語義信息。一旦解析器產生了AST，就可以在單獨的通道中進行語義分析，其中一個將檢查類型約束。這是最乾淨的解決方案。沒有顯式類型，語法略有簡化，因爲expr現在可以是任何expr：

expr:  conjunction | expr "or" conjunction ; 
conjunction: comparison | conjunction "and" comparison ; 
comparison: product  | product '<' product ; 
product:  factor  | product '*' factor ; 
factor:  term  | factor '+' term ; 
term:  identifier 
    |  constant 
    |  '(' expr ')' 
    ; 

每個動作在上面會簡單地創建一個新的AST節點並設置$$到新節點。在解析結束時，AST會走過來驗證所有expr都具有正確的類型。

如果這看起來對您的項目來說太過分了，那麼您可以在還原操作中進行語義檢查，從而有效地將AST漫步與解析混合在一起。這對於立即評估似乎很方便，但它也需要在解析器的語義類型中包含顯式類型信息，這會增加不必要的開銷（並且，正如前面提到的，讓語義干擾解析器的不妥當）。在這種情況下，每個動作都會看起來像這樣：

expr : expr '+' expr { CheckArithmeticCompatibility($1, $3); 
         $$ = NewArithmeticNode('+', $1, $3); 
        }