在遞歸規則中組合類似的構造

Question

這是Jison中的解析器，但我猜這同樣適用於Bison。

我有一個規則有一個表達式的定義。

expr 
    : NUMBER -> { type: "number", value: $1 } 
    | "(" expr ")" -> $2 
    | expr "+" expr -> { type: "+", left: $1, right: $3 } 
    | expr "-" expr -> { type: "-", left: $1, right: $3 } 
    | expr "*" expr -> { type: "*", left: $1, right: $3 } 
    | expr "/" expr -> { type: "/", left: $1, right: $3 } 
    ; 

我同樣的語法我也有一個「過濾表達式」，也支持「參數」的規則。

filterExpr 
    : NUMBER -> { type: "number", value: $1 } 
    | PARAM -> { type: "param", name: $1 } /* parameter */ 
    | "(" filterExpr ")" -> $2 
    | filterExpr "+" filterExpr -> { type: "+", left: $1, right: $3 } 
    | filterExpr "-" filterExpr -> { type: "-", left: $1, right: $3 } 
    | filterExpr "*" filterExpr -> { type: "*", left: $1, right: $3 } 
    | filterExpr "/" filterExpr -> { type: "/", left: $1, right: $3 } 
    ; 

這有效，但是當我添加運算符時，我必須更改這兩個定義。有沒有辦法在語法中結合「expr」和「filterExpr」的共同部分？

Answer 1

使用BNF的擴展來描述Javascript本身（正式ECMAScript，由ECMA-262定義），它允許使用布爾限定符（標準語言中的「參數」）來增加規則。這正是你正在尋找的效果，它顯然簡化了語言的複雜語法的表達。標準的section 5.1.5 (Grammar Notation)中可以找到BNF擴展的完整解釋;總之，參數可以從左側傳遞到右側的非終端，或者可以爲RHS終端明確設置或取消設置;此外，它們可以用於根據參數的存在與否來過濾可能的產品。 （這篇文章末尾有一個例子。）

這個特殊的BNF擴展不會增加BNF的生成能力;通過簡單列舉可能性，可以機械地消除它的所有用途。可悲的是，我知道沒有實現這種形式的語法生成器（儘管某些Javascript實現當然可能包含一個自定義的解析器生成器）。

出於您的目的，預處理您的jison語法以實現非常相似的內容很容易。事實上，預處理一個野牛語法文件相對容易，但jison更容易，因爲您可以通過編程來計算語法並將其作爲JSON對象傳遞給jison。這個功能沒有很好的記錄，但是jison手冊包含了足夠的例子，它應該是直接使用的。例如，請參閱CommonJS section。

---

正如所承諾的，這裏是從ECMA-262的語法的摘錄，顯示使用該BNF擴展：

IdentifierReference可以有兩個可能的布爾預選賽（Yield和Await）引起四個合格可能性。它始終可以是Identifier;只有在不符合Yield屬性的限定條件時纔可以使用關鍵字yield，僅在不符合Await的條件下使用關鍵字await。

IdentifierReference[Yield, Await]: 
    Identifier 
    [~Yield]yield 
    [~Await]await 

所以這單節就相當於四個非終端，它可以機械製造：

IdentifierReference: Identfier | yield | await 
IdentifierReference_Yield: Identifier | await 
IdentifierReference_Await: Identifier | yield 
IdentifierReference_Yield_Await: Identifier 

下面是它的應用方式：一個Expression可以用三個屬性合格，所有這一切通過（→,?Yield）到右側的非終端。

Expression[In, Yield, Await]: 
    AssignmentExpression[?In, ?Yield, ?Await] 
    Expression[?In, ?Yield, ?Await], AssignmentExpression[?In, ?Yield, ?Await] 

甲yield表達只允許在AssignmentExpression合格的變體與Yield：

AssignmentExpression[In, Yield, Await]: 
    ConditionalExpression[?In, ?Yield, ?Await] 
    [+Yield]YieldExpression[?In, ?Await] 

最後，具有明確的參數的示例。在生產用於GeneratorMethod，Yield被明確爲PropertyName生產（其防止yield被識別爲在參數列表中的標識符）指定和GeneratorBody被定義爲FunctionBody與Yield（允許yield表達式和禁止yield作爲標識符）並且沒有Await（不允許await表達式，但允許await作爲標識符）。

GeneratorMethod[Yield, Await]: 
    * PropertyName[?Yield, ?Await]( UniqueFormalParameters[+Yield, ~Await]){ GeneratorBody } 

GeneratorBody: 
    FunctionBody[+Yield, ~Await] 

大部分上述複雜的是通過向後兼容的堅持要求：因爲對於早期JS版本編寫的程序可能使用yield和await作爲變量名，這些關鍵字在沒有語法語境只保留在早期版本中可用。 （這是一個過於簡單化，但細節已經超出了這個問題的範圍。）