为什么用 BNFC 解析这个程序会失败？

Question

给定以下语法：

comment "/*" "*/" ;

TInt.  Type1 ::= "int" ;
TBool. Type1 ::= "bool" ;
coercions Type 1 ;


BTrue.   BExp   ::= "true" ;
BFalse.  BExp   ::= "false" ;

EOr.     Exp    ::= Exp  "||" Exp1 ;
EAnd.    Exp1   ::= Exp1 "&&" Exp2 ;
EEq.     Exp2   ::= Exp2 "==" Exp3 ;
ENeq.    Exp2   ::= Exp2 "!=" Exp3 ;
ELt.     Exp3   ::= Exp3 "<" Exp4 ;
EGt.     Exp3   ::= Exp3 ">" Exp4 ;
ELte.    Exp3   ::= Exp3 "<=" Exp4 ;
EGte.    Exp3   ::= Exp3 ">=" Exp4 ;
EAdd.    Exp4   ::= Exp4 "+" Exp5 ;
ESub.    Exp4   ::= Exp4 "-" Exp5 ;
EMul.    Exp5   ::= Exp5 "*" Exp6 ;
EDiv.    Exp5   ::= Exp5 "/" Exp6 ;
EMod.    Exp5   ::= Exp5 "%" Exp6 ;
ENot.    Exp6   ::= "!" Exp ;
EVar.    Exp8   ::= Ident ;
EInt.    Exp8   ::= Integer ;
EBool.   Exp8   ::= BExp ;
EIver.   Exp8   ::= "[" Exp "]" ;
coercions Exp 8 ;

Decl. Decl ::= Ident ":" Type ;
terminator Decl ";" ;


LIdent.  Lvalue ::= Ident ;

SBlock.  Stm ::= "{" [Decl] [Stm] "}" ;
SExp.    Stm ::= Exp ";" ;
SWhile.  Stm ::= "while" "(" Exp ")" Stm ;
SReturn. Stm ::= "return" Exp ";" ;
SAssign. Stm ::= Lvalue "=" Exp ";" ;
SPrint.  Stm ::= "print" Exp ";" ;
SIf.     Stm ::= "if" "(" Exp ")" "then" Stm "endif" ;
SIfElse. Stm ::= "if" "(" Exp ")" "then" Stm "else" Stm "endif" ;

terminator Stm "" ;

entrypoints Stm;

使用 bnfc 创建的解析器无法解析

{ c = a; }

虽然它解析

c = a;

或

{ print a; c = a; }

我认为解析器看到 Ident 并且不知道它是声明还是语句、LR 东西等可能是一个问题（仍然有一个 lookeahed 标记就足够了？？）。但是我在 BNFC 文档中找不到任何说明它不适用于所有语法的注释。

有什么想法可以让它发挥作用吗？

Answer 1

我认为您会收到该语法的 shift/reduce 冲突报告，尽管该错误消息出现的位置可能很可能取决于 BNFC 使用哪种工具生成解析器。据我所知，所有后端工具处理shift/reduce冲突的方法都是一样的，即（1）警告用户冲突，然后（2）解决冲突以支持转移。

有问题的是这个：（我省略了类型注释以减少混乱）

Stm ::= "{" [Decl] [Stm] "}" ;

这里，[Decl] 和 [Stm] 是宏，它们会自动为具有这些名称的非终端生成定义（或后端工具将接受的等效内容）。具体来说，自动生成的作品有：

[Decl] ::= /* empty */
       |   Decl ';' [Decl]

[Stm]  ::= /* empty */
       |   Stm [Stm]

(第一条规则中的;是“终结符”声明的结果。我不知道为什么BNFC会生成右递归规则，但我是这样解释参考手册的——之后快速浏览一下 -- 我相信他们有他们的理由。对于这个问题的目的来说，这无关紧要。

重要的是 Decl 和 Stm 都可以以 Ident 开头。因此，假设我们正在解析 { id ...，它可能是 { id : ... 或 { id = ...，但我们只读取了 { 和前瞻标记 id。所以有两种可能：

id 是 Decl 的开始。我们应该移动 Ident 并转到包含 Decl → Ident • ':' Type
的状态
id 是 Stm 的开始。在这种情况下，我们需要在将 Ident 转换为 Stm 生产之前减少产量 [Decl] → •。

所以我们有一个 shift/reduce 冲突，因为我们看不到第二个下一个标记（: 或 =）。而且，如上所述，在这种情况下，shift 通常会获胜，因此 LR(1) 解析器将承诺自己期望 Decl。因此，{ a = b ; } 将失败。

LR(2) 解析器生成器可以很好地处理此语法，但很难找到。（现代野牛可以生成 GLR 解析器，它比 LR(2) 更强大，但需要一些额外的计算时间，但不是 BNFC 工具所需的版本。）

可能的解决方案

允许声明与语句混合。这个是我的偏好。它很简单，许多程序员希望能够在第一次使用时声明一个变量，而不是在封闭块的开头。
通过将类型放在前面（如在 C 中）或通过添加诸如 var（如在 Javascript ):
修改语法以延迟前瞻。总是可以为任何 LR(k) 语言找到 LR(1) 文法（前提是 k 是有限的），但这可能很乏味。一个丑陋但有效的替代方法是继续词法扫描，直到找到 : 或其他一些非空白字符，以便 id : 被标记为 IdentDefine 或类似的字符。（这是 bison 使用的解决方案，碰巧。这意味着你不能在标识符和后面的 : 之间放置注释，但是很少有（如果有的话）很好的理由放置在这种情况下发表评论。

为什么用 BNFC 解析这个程序会失败？

Why parsing this program with BNFC fails?

parsing

bnf

bnfc

可能的解决方案