c++ - Bison 获取下一个可能的标记或确定正在尝试的规则

Question

我正在使用 bison 从我无法控制的规范中解析 lan​​g。在它的定义中有一个递归规则，并且由于该语言使用缩进，这导致了减少/减少错误。所以为了摆脱减少/减少我添加了一个分号。我有一个布局跟踪器，它已经自动插入分号和大括号。我正在考虑扩展插入分号的规则以支持我添加的不在规范中的规则，但我想不出一种方法来知道我们何时处于递归规则的末尾。

是否有可靠的方法知道我何时处于递归规则的末尾或关于不同方法的任何建议？或者像它一样困惑是否有某种方法可以在解析器和词法分析器之间进行双向通信？

目前正在使用拉式解析器。我认为使用推送解析器可以让我更好地跟踪我在词法分析器中的位置，但是当我尝试使用 define 指令生成推送解析器时，该选项无法识别。我使用带有自定义词法分析器的 bison 3.0.4，使用 C++ api 生成纯解析器。

编辑:

exp                     : infixexp  TYPE_SEP  type                                                      {}                     
                        | infixexp  TYPE_SEP  context RIGHT_ARROW type                                  {}
                        | infixexp                                                                      {}

infixexp                : lexp qop infixexp                                                             {}    
                        | MINUS infixexp                                                                {}      
                        | lexp                                                                          {}

lexp                    : BACKSLASH apat_list FUNC_TYPE_CONS exp                                        {}   
                        | KW_LET decls KW_IN exp                                                        {}    
                        | KW_IF exp SEMI_COLON KW_THEN exp SEMI_COLON KW_ELSE exp                       {}    //conditional
                        | KW_CASE exp KW_OF L_BRACE alts R_BRACE                                        {}   
                        | KW_DO L_BRACE stmts R_BRACE                                                   {}   
                        | fexp SEMI_COLON                                                               {}

fexp                    : aexp                                                                          {}   
                        | fexp  aexp                                                                    {}  

literal                 : INTEGER                                                                       {}
                        | FLOAT                                                                         {}
                        | CHAR                                                                          {}
                        | STRING                                                                        {}

aexp                    : qvar                                                                          {}  
                        | gcon                                                                          {}   
                        | literal
                        | L_PAREN exp R_PAREN                                                           {}   
                        | L_PAREN exp_list R_PAREN                                                      {}   
                        | L_BRACKET exp R_BRACKET                                                       {}  
                        | L_BRACKET exp_list R_BRACKET                                                  {}  
                        | L_BRACKET exp DOTDOT R_BRACKET                                                {}  
                        | L_BRACKET exp DOTDOT exp R_BRACKET                                            {}  
                        | L_BRACKET exp COMMA exp DOTDOT exp R_BRACKET                                  {}  
                        | L_BRACKET exp PIPE qual_list R_BRACKET                                        {}  
                        | L_PAREN infixexp qop  R_PAREN                                                 {}  
                        | L_PAREN qop infixexp R_PAREN                                                  {}   
                        | qcon  L_BRACE fbind_list R_BRACE                                              {}   
                        | aexp  L_BRACE fbind_list R_BRACE                                              {}   
apat                    : qvar                                                                          {}  
                        | qvar AT_SYM  apat                                                             {}  
                        | gcon                                                                          {}  
                        | qcon  L_BRACE fpat_list R_BRACE                                               {}  
                        | literal                                                                       {}
                        | WILDCARD                                                                      {}
                        | L_PAREN pat R_PAREN                                                           {}  
                        | L_PAREN pat COMMA pat_list R_PAREN                                            {}  
                        | L_BRACKET pat_list  R_BRACKET                                                 {} 
                        | TILDE apat                                                                    {}  

添加了语法部分。它基本上是 Haskell 2010 规范的修改版本。通过在 lexp 的定义中的 fexp 之后添加分号解决了 reduce/reduce 冲突。

我正在模拟缩进/缩进并插入左括号和花括号。我基本上在想 the lexer hack但无法弄清楚如何与 Bison 一起做。并且有多个递归规则，但只有一个导致减少/减少错误。

编辑 2:

jsfiddle with the original reduce/reduce errors

Answer 1

处理缩进感知语言的常用方法是在词法扫描器中制造 INDENT 和 DEDENT 标记。使用推送接口(interface)会更容易，因此很遗憾您使用的是未实现该功能的 bison C++ API。

但也可以在词法扫描器和解析器之间使用垫片来轻松完成。您可以在 this answer 中查看 Python shim 的示例。 ; ply 也不提供推送解析器接口(interface)，因此 shim 保留一个小的持久 token 队列，这些 token 将被发送到解析器并在向真正的词法扫描器询问下一个 token 之前检查该队列。

正如该答案所表明的，在大多数布局感知语言中，并非所有换行符实际上都具有语义意义。例如，在 Python 本身中，圆括号、大括号或方括号内的换行符只是普通的空格。 shim 也可以很容易地实现该规则(尽管我没有通过在链接的答案中这样做而使代码复杂化)，只需跟踪括号的级别即可。

并非所有语言都让生活变得如此轻松；例如，您可能有一种语言，由于存在函数文字，缩进可以在括号列表中重新声明自己。或者你可能有一种像 ecmascript 这样的语言，如果替代解析不可能，其中分号插入规则允许甚至在括号之外的行上运行。 Haskell 有类似的规则，如果无法进行替代解析，则可以插入大括号。

起草 ecmascript 规则的目的是使编写解析器成为可能。 (或者，更准确地说，我认为该规则是通过对现有解析器进行逆向工程而起草的，但我无法证明这一点。)事实证明，可以通过构造字典来实现 ecmascript 自动分号插入可以用换行符分隔而无需插入分号的标记对。 (或者，或者，如果可能的话，必须在它们之间插入分号的成对标记，这是另一个集合的倒数。)这些集合可以通过语法分析自动构建，使用每个产生式的 FIRST 和 FOLLOW 集合。 (ecmascript 规则的细节需要做一些调整，因为有一些标记对可以出现在一个有效的程序中，但不允许用换行符分隔。例如，return 3 是一个有效的语句，但如果 return 在一行的末尾并且 3 在下一行，则必须自动插入一个分号')。 Bison 不会自动执行此分析，因此它依赖于自定义工具，但这并不是特别困难。

Haskell 似乎并不那么随和。我在 Haskell report, section 9.3 中看到, 在该部分的末尾:

The parse-error rule is hard to implement in its full generality, because doing so involves fixities. For example, the expression

do a == b == c

has a single unambiguous (albeit probably type-incorrect) parse, namely

(do { a == b }) == c

because (==) is non-associative. Programmers are therefore advised to avoid writing code that requires the parser to insert a closing brace in such situations.

这不是很有希望，但它也表明实现不会是完美的，并且恳请程序员不要期望完美的解析器实现:)

我认为将链接答案中的 IndentWrapper shim 翻译成 C++ 并不困难，即使对于不太熟悉 Python 的人来说也是如此，所以我没有费心在这里做。如果该假设不正确，请告诉我。