如何使用Jison生成解析器來處理語法歧義？

我想通過Jison爲語言ChucK在JavaScript中生成一個解析器，並且已經有了一個良好的開端，除了在生成的解析器無法處理的語言中存在歧義之外。最初的ChucK編譯器由Bison生成，並且必須以某種方式解決這些歧義。如何使用Jison生成解析器來處理語法歧義？

爲了這個問題的目的，我已經簡化了問題到一個解釋的語法，其中只給出了一個含糊之處。作爲參考，我已經把所有相關文件（包括生成的parser）的gist。項目結構如下：

language/lexer.js：詞法分析器。
language/grammar.js：語法定義以及通過Jison生成解析器的函數（generate）。
language/helpers.js：幫助函數
src/parser.js：生成的解析器。
testparse.js：使用以下源代碼測試解析器的程序：Type var => out;。

語法本身看起來如下：

grammar = { 
    Program: [ 
     ['ProgramSection', '$$ = new yy.Program($1);'] 
    ], 
    ProgramSection: [ 
     ['Expression SEMICOLON', '$$ = new yy.ExpressionStatement($1);'] 
    ], 
    Expression: [ 
     ['DeclExpression', '$$ = $1;'], 
     ['Expression OP DeclExpression', '$$ = new yy.ExpFromBinary($1, $2, $3);'] 
    ], 
    DeclExpression: [ 
     ['TypeDecl VarDeclList', '$$ = new yy.DeclExp($1, $2, 0);'], 
     ['PrimaryExpression', '$$ = $1;'] 
    ], 
    VarDeclList: [ 
     ['VarDecl', '$$ = new yy.VarDeclList($1);'] 
    ], 
    VarDecl: [ 
     ['ID', '$$ = new yy.VarDecl($1);'] 
    ], 
    TypeDecl: [ 
     ['ID', '$$ = new yy.TypeDecl(new yy.IdList($1), 0);'] 
    ], 
    PrimaryExpression: [ 
     ['ID', '$$ = new yy.ExpFromId($1);'] 
    ] 
};

歧義的是，非末端DeclExpression可以匹配TypeDecl VarDeclList或PrimaryExpression。這使得Jison發出如下警告：

States with conflicts: 
State 7 
    TypeDecl -> ID . #lookaheads= ID SEMICOLON OP 
    PrimaryExpression -> ID . #lookaheads= ID SEMICOLON OP

而生成的解析器未能解析測試代碼（Type var => out;）像這樣：

Error: Parse error on line 1: Unexpected 'SEMICOLON'

據我瞭解，它的=>操作後的一部分解析器嘗試匹配規則TypeDecl VarDeclList。

那麼，我該如何生成一個能夠處理這種歧義的解析器呢？

來源

2013-12-09 aknuds1

我發現我可以通過選擇任一 'SLR'（SLR）或 'LR'（LR1）分析器類型產生用於本（簡化的）語法的功能解析器：

// Generate SLR parser, since default LALR has conflicts 
exports.generate = new Parser(parserConfig, {type: "slr"}).generate;

我仍然想知道爲什麼默認（LALR（1））不起作用，因爲這應該是Bison生成的。

來源

2013-12-09 16:46:19 aknuds1

你的語法不以LALR工作的原因（1）語法分析器是因爲你是模棱兩可的LALR（1）語法分析器在DeclExpression狀態的TypeDecl和PrimaryExpression狀態。

讓我試着解釋。正如錯誤消息所述，解析器在TypeDecl和PrimaryExpression上檢測到衝突。兩者都有ID作爲標記，但由於LALR（1）解析器只能向前查看一個標記，這意味着解析器在處於DeclExpression狀態時不知道該做什麼。另一方面，單反有一種動態的頭腦，它會以犧牲一些記憶來解決衝突。

如果你想讓它在LALR（1）語法分析器工作，只是重構你的DeclExpression規則要像ID VarDeclList | ID，這樣解析器不必查找一個頭，以便找到正確的規則。

來源

2017-11-17 08:08:36 blackshade

如何使用Jison生成解析器來處理語法歧義？

回答

相關問題