代码之家 › 专栏 › 技术社区 › JesseBuesking

柠檬解析器减少错误

lemon grammar parsing

1

JesseBuesking · 技术社区 · 9 年前

reduce 解析冲突,我很难理解是什么导致了冲突。

我已经附加了解析器的一部分。由lemon生成的文件,我希望有人能对这个问题有所了解。我还包括了语法的一大部分,其中线下的所有内容都是独立工作的,但一旦我添加了线上数千条的逻辑,我就开始遇到问题。

悬挂 “但使用我的分隔符。然而,这通常表现为 shift-reduce 错误,而看起来我只有 减少 错误Lemon文档有点稀疏,我不太确定如何读取解析器。超出文件的内容。例如,在 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 ::= .

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

1 回复 | 直到 9 年前

1

Community Mohan Dere 5 年前

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

所指出的是,问题在于解析器已经识别的状态 tens (那就是“二十”、“三十”、“九十”,对吧?)现在它需要一个 separator 经皮电刺激神经疗法 立即 one_to_99 (作为完成的前奏 one_to_999 无尾随数字)或将 WHITESPACE 或 HYPHEN 字符以扩展 经皮电刺激神经疗法 用一个 分离器 和一位数( one_to_9

解析器实际上不能仅仅通过查看分隔符标记来做出决定。它需要知道接下来是什么(例如, THOUSAND 或 ONE 以及其他可能性)。

在语法中添加数千之前不会发生这种情况,因为没有 千 ,如果数字末尾没有单个数字,则在后面没有分隔符 经皮电刺激神经疗法 这也是一种象征。因此,如果有显式分隔符,则必须有一个数字,因此需要移位。一旦您添加 千 选项,分隔符标记的存在不再是一个足够的指南。

试图在解析器中显式匹配空白与通常所称的“无扫描解析”类似,但这里的情况并非如此,因为您可能确实有一个扫描程序。然而,扫描仪没有正常工作;它无法删除没有语法值的标记。虽然有人喜欢无扫描解析,但人们普遍认为它会增加前瞻性要求。[注1]由于您无法增加lemon解析器的前瞻性(也无法增加许多其他基于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
            ;

这将不会产生任何偏移/减少冲突。

笔记

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