1

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

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

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

任何帮助将不胜感激！

我的语法文件的一部分：

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 ::=
4

1 回答 1

1

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

表明问题是解析器已经识别的状态tens（那将是“二十”，“三十”，...，“九十”，对吗？），它现在需要一个separator（这可能是可选的）。如果前瞻标记是一个实际的分隔符，它必须决定是tens立即减少到（作为完成没有尾随数字one_to_99的前奏）还是移动or字符以便用 a和单个数字 ( ) 扩展。one_to_999WHITESPACEHYPHENtensseparatorone_to_9

解析器真的不能仅仅看分隔符就做出决定。它需要知道接下来会发生什么（例如，可能是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. 我不是喜欢无扫描解析的人之一，所以我什至不会试图解释为什么它被认为是一个好主意。
于 2016-11-07T21:58:16.010 回答