c++ - 野牛获取下一个可能的 token 或确定尝试哪个规则

我正在使用野牛从我无法控制的规范中解析一个lang。在其定义中有一个递归规则，并且由于该语言使用缩进，因此会导致减少/减少错误。为了摆脱减少/减少，我添加了一个半冒号。我有一个布局跟踪器，它已经自动插入了半冒号和花括号。我当时正在考虑扩展插入半冒号的规则，以支持规范中未添加的分号，但我想不出一种方法来了解何时到达递归规则的末尾。

有什么可靠的方法可以知道我何时处于递归规则的末尾或对其他方法的建议吗？还是很混乱，是否有某种方法可以在解析器和词法分析器之间获得双向通讯？

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

我在模拟缩进/缩进并插入大括号和大括号。而且我基本上是在考虑the lexer hack，但不知道如何用Bison做到这一点。而且有多个递归规则，但是只有一个递归规则导致了减少/减少错误。

编辑2：

jsfiddle with the original reduce/reduce errors

最佳答案

处理缩进感知语言的通常方法是在词汇扫描器中构造INDENT和DEDENT令牌。使用push接口更容易，因此不幸的是您使用的是无法实现该功能的bison C ++ API。

但这也可以在词汇扫描器和解析器之间使用填充程序而不会造成太大麻烦。您可以在this answer中看到Python填充程序的示例； ply也不提供推送解析器接口，因此填充程序会保留一小段持久的令牌队列，这些令牌将被发送到解析器，并在向真正的词法扫描器请求下一个令牌之前检查该队列。

正如该答案所表明的那样，在大多数可识别布局的语言中，并非所有换行符实际上在语义上都是重要的。例如，在Python本身中，括号，花括号或方括号内的换行符只是普通的空格。该规则也可以由填充程序轻松实现（尽管我没有通过链接的答案来使代码复杂化），只需跟踪括号的级别即可。

并非所有的语言都使生活如此轻松。例如，您可能会使用一种语言，因为存在函数文字，缩进可以在括号列表中重新声明其自身。或者，您可能会使用类似ecmascript的语言，其中如果不可能进行替代分析，则分号插入规则甚至允许在括号外的连续行。 Haskell有一个类似的规则，如果无法进行替代解析，则可以插入大括号。

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

Haskell似乎不那么宽容。我在该部分结尾的Haskell report, section 9.3中看到：


  解析错误规则很难完全实现，因为这样做涉及固定性。例如，表达式

do a == b == c

  
  具有一个明确的（尽管可能类型不正确）解析，即

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

  
  因为（==）是非关联的。因此，建议程序员避免在这种情况下编写要求解析器插入右括号的代码。


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

我认为，即使对于不太熟悉Python的人，将链接答案中的IndentWrapper垫片转换为C ++也不会很困难，因此我在这里没有做任何麻烦。如果该假设不正确，请告诉我。

关于c++ - 野牛获取下一个可能的 token 或确定尝试哪个规则，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34540653/