柠檬解析器减少错误

Question

我试图写一个语法来解析英语句子中的数字，并且我可以成功地解析多达999。一旦我添加了支持数千个地方的逻辑，我就会得到一个reduce解析冲突，并且我很难理解是什么导致了冲突。

我已经附加了一部分由柠檬生成的parser.out文件，我希望有人能对这个问题有所了解。我还包含了很大一部分语法，在这里，线下的所有东西都是独立工作的，但是一旦我在行上方添加了成千上万的逻辑，我就开始遇到问题。

我的想法是，我遇到了一个类似于“悬空的其他”的问题，但我的分隔符。然而，这通常显示为一个shift-reduce错误，而看起来我只是一个reduce错误。柠檬文档有点稀疏，我不太确定如何读取parser.out文件的内容。例如，在HYPHEN reduce 15 ** Parsing conflict **行中，15甚至提到了什么？

任何帮助都将不胜感激！

语法文件的一部分：

final_number(A) ::= one_to_999999(B).
final_number(A) ::= ZERO.

one_to_999999(A) ::= thousands(B) separator one_to_999(C).
one_to_999999(A) ::= thousands(B).
one_to_999999(A) ::= one_to_999(B).

thousands(A) ::= one_to_999(B) separator THOUSAND.
thousands(A) ::= THOUSAND.

/* -------------------------------------- */

one_to_999(A) ::= hundreds(B) separator one_to_99(C).
one_to_999(A) ::= hundreds(B).
one_to_999(A) ::= one_to_99(B).

one_to_99(A) ::= tens(B) separator one_to_9(C).
one_to_99(A) ::= tens(B).
one_to_99(A) ::= ten_to_19(B).
one_to_99(A) ::= one_to_9(B).

hundreds(A) ::= one_to_9(B) separator HUNDRED.
hundreds(A) ::= HUNDRED.

separator ::= WHITESPACE.
separator ::= HYPHEN.
separator ::= .

parser.out中有错误的部分：

State 5:
          one_to_99 ::= tens * separator one_to_9
     (15) one_to_99 ::= tens *
          separator ::= * WHITESPACE
          separator ::= * HYPHEN
     (65) separator ::= *

                             $ reduce       15     one_to_99 ::= tens
                      THOUSAND reduce       15     one_to_99 ::= tens
                    WHITESPACE shift-reduce 63     separator ::= WHITESPACE
                    WHITESPACE reduce       15      ** Parsing conflict **
                        HYPHEN shift-reduce 64     separator ::= HYPHEN
                        HYPHEN reduce       15      ** Parsing conflict **
                     separator shift        4      
                     {default} reduce       65     separator ::=

Answer 1

实际上这里没有足够的信息来诊断完整的问题，但我想我可以填补空白。

说明的是，问题是解析器识别tens的状态(即“20”、“30”、.、“90”，对吗？)现在它需要一个separator (这可能是可选的)。如果展望令牌是一个实际的分隔符，则必须决定是立即将tens还原为one_to_99 (作为在没有尾随数字的情况下完成one_to_999的前奏)还是移动WHITESPACE或HYPHEN字符，以便使用separator和单数(one_to_9)扩展tens。

解析器实际上不能只看分隔符令牌就做出这个决定。它需要知道下面的内容(例如，THOUSAND或ONE，以及其他可能性)。

在向语法添加数千个之前不会发生这种情况，因为如果没有THOUSAND的可能性，如果在数字的末尾没有一个数字，那么在tens令牌后面也没有分隔符。因此，如果存在显式分隔符，则必须有一个数字，因此需要进行移位。一旦添加了THOUSAND选项，分隔符令牌的存在就不再是一个足够的指南。

试图显式匹配解析器中的空白与通常所说的“无扫描解析”类似，尽管这里并不是这样的，因为您可能确实有一个扫描器。然而，扫描器没有正确地完成它的工作；它未能删除没有语法值的标记。虽然有些人喜欢无扫描解析，但人们普遍认为这会增加前瞻性需求。注1由于不能增加对柠檬解析器(或许多其他基于yacc的解析器生成器)的展望，因此使用此类工具进行无扫描解析是有问题的。

在这种情况下，很难看到通过强制解析器处理分隔符可以得到什么，而且很明显您丢失了什么(LALR(1)可解析性)，因此我建议您只需在扫描仪中的地板上删除空白和连字符，并将它们从解析器中删除。您可能会争辩说，这样做会导致错误的句子，如three hundred forty---two。确实如此，但是您的当前语法允许three hundred-forty two (在我所见过的任何样式指南中都是不正确的)，并且可能禁止forty - two，这取决于您的扫描器用于识别连字符的模式。

如果您想要“正确的连字符”，一定要从扫描仪中返回连字符(但不是空格)，然后只在有用的地方接受它们：

one_to_99 ::= tens
            | tens one_to_9
            | tens HYPHEN one_to_9
            ;

不会产生任何移位/减少冲突。

备注

1. 我不是喜欢无扫描解析的人之一，所以我甚至不会试图解释为什么它被认为是一个好主意。