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

Question

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

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

目前正在使用拉式解析器。我认为使用推送解析器可以让我更好地跟踪我在词法分析器中的位置，但是当我尝试使用 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 规范的修改版本。 reduce/reduce 冲突通过在 lexp 的定义中的 fexp 之后添加分号来解决。

我正在模拟 indent/dedents 并插入左括号和花括号。我基本上是在考虑 the lexer hack 但不知道如何用 Bison 来做。并且有多个递归规则，但只有一个导致 reduce/reduce 错误。

编辑 2：

jsfiddle with the original reduce/reduce errors

Answer 1

处理 indentation-aware 语言的常用方法是在词法扫描器中制作 INDENT 和 DEDENT 标记。使用推送接口更容易，所以不幸的是您使用的是 bison C++ API，它没有实现该功能。

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

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

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

起草 ecmascript 规则的目的是使编写解析器成为可能。（或者，更准确地说，我认为该规则是由 reverse-engineering 现有的解析器起草的，但我无法证明这一点。）事实证明，可以通过以下方式实现 ecmascript 自动 semi-colon 插入构造成对标记的字典，可以用换行符分隔而不插入分号。（或者，或者，如果可能的话，必须在它们之间插入分号的成对标记，这是另一个集合的倒数。）这些集合可以通过语法分析自动构建，使用每个产生式的 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 的人来说也不难，所以我没有费心在这里做。如果该假设不正确，请告诉我。

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

Bison get next possible tokens or determine which rule is being attempted

c++

haskell

bison