柠檬解析器减少错误

Question

我正在尝试编写一个语法来解析英语句子中的数字，我最多可以成功解析 999。一旦我添加了支持千位的逻辑，我就得到了 reduce 解析冲突，我很难理解是什么原因造成的。

我附上了 lemon 生成的 parser.out 文件的一部分，我希望有人能阐明这个问题。我还包含了语法的很大一部分，行以下的所有内容都可以独立运行，但是一旦我添加了行以上数千的逻辑，我就开始运行问题。

我的想法是，我运行遇到了类似于“dangling else”但使用我的分隔符的问题。但是，这通常表现为 shift-reduce 错误，而我似乎只有 reduce 错误。 Lemon 文档有点稀疏，我不确定如何阅读 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 的状态（即“二十”、“三十”、...、“九十”，对吗？）现在需要一个 separator （这可能是可选的）。如果先行标记是一个实际的分隔符，它必须决定是立即将 tens 减少到 one_to_99（作为完成没有尾随数字的 one_to_999 的前奏）还是移动 WHITESPACE 或 HYPHEN 字符，以便使用 separator 和单个数字 (one_to_9) 扩展 tens。

解析器确实无法仅通过查看分隔符标记来做出该决定。它需要知道接下来的内容（例如，可能是 THOUSAND 或 ONE，以及其他可能性）。

在将千位添加到语法之前不会发生这种情况，因为没有 THOUSAND 的可能性，如果数字末尾没有单个数字，则 [=11 后面没有分隔符=] 令牌。因此，如果有明确的分隔符，则必须有一个数字，因此需要进行移位。添加 THOUSAND 选项后，分隔符标记的存在不再是一个充分的指南。

尝试在解析器中显式匹配空格类似于通常所说的“无扫描器解析”，尽管这里并非严格如此，因为您可能确实有一个扫描器。但是，扫描仪没有正常工作；它无法删除没有语法价值的标记。虽然有人喜欢无扫描器解析，但普遍认为它会增加前瞻性要求。 [注 1] 由于您不能增加 lemon 解析器的前瞻性（也不能增加许多其他基于 yacc 的解析器生成器），因此使用此类工具进行无扫描器解析是有问题的。

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

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

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

不会产生任何 shift/reduce 冲突。

备注

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

柠檬解析器减少错误

lemon parser reduce error

grammar

parsing

lemon

备注