1

我正在尝试使用 JFlex 和 Cup 为 javascript-ish 语言编写解析器，但我遇到了一些致命的移位/减少问题和减少/减少问题。

我已经彻底搜索并找到了大量示例，但我无法将这些推断到我的语法中。到目前为止我的理解是，这些问题是因为解析器无法决定它应该采取哪种方式，因为它无法区分。

我的语法如下：从INPUT开始；

INPUT::= PROGRAM;

PROGRAM::= FUNCTION NEWLINE PROGRAM
| NEWLINE PROGRAM;

FUNCTION ::= function OPTIONAL id p_izq ARG p_der NEWLINE l_izq NEWLINE BODY l_der;

    OPTIONAL ::= 
    | TYPE;


    TYPE::= integer 
    | boolean

    ARG ::=  
    | TYPE id MORE_ARGS;

    MORE_ARGS ::=   
    | colon TYPE id MORE_ARGS;


    NEWLINE ::= salto NEWLINE 
    | ;

    BODY ::=  ;

我遇到了几个冲突，但这两个只是一个例子：

 Warning : *** Shift/Reduce conflict found in state #5
 between NEWLINE ::= (*) 
 and     NEWLINE ::= (*) salto NEWLINE 
 under symbol salto
 Resolved in favor of shifting.

 Warning : *** Shift/Reduce conflict found in state #0
 between NEWLINE ::= (*) 
 and     FUNCTION ::= (*) function OPTIONAL id p_izq ARG p_der NEWLINE l_izq NEWLINE BODY l_der 
 under symbol function
 Resolved in favor of shifting.

PS：语法要复杂得多，但我认为如果我看到这些移位/减少问题是如何解决的，我将能够解决其余的问题。

感谢您的回答。

4

1 回答 1

5

PROGRAM是无用的（在技术意义上）。也就是说，它不能产生任何句子，因为在

PROGRAM::= FUNCTION NEWLINE PROGRAM
       |   NEWLINE PROGRAM;

的两个产生PROGRAM式都是递归的。要使非终结符有用，它需要能够最终生成一些终结符字符串，并且要做到这一点，它必须至少具有一个非递归生成；否则，递归永远不会终止。我很惊讶 CUP 没有向您提及这一点。或者可能确实如此，而您选择忽略警告。

这是一个问题——无用的非终结符真的无法匹配任何东西，所以它们最终会导致解析错误——但这不是你报告的解析冲突。冲突来自同一产生式的另一个特征，这与您不能除以 0 的事实有关。

关于虚无的事情是，任何数量的虚无仍然是虚无。所以如果你有很多空无，有人过来问你到底有多少空无，你会有一点问题，因为要从“0 *很多”中得到“丰富”，你必须计算“0 / 0”，这不是一个明确定义的值。（如果你有很多二，有人问你有多少二，那不是问题：假设大量二的结果是 40；你可以很容易地计算出 40 / 2 = 20，这样算出完美，因为 20 * 2 = 40。）

所以这里我们没有算术，我们有符号串。不幸的是，不包含符号的字符串实际上是不可见的，就像 0 是所有这些千年一样，直到一些阿拉伯数学家注意到什么都不写的价值。

这一切都发生在你有

PROGRAM::= ... something ...
       |   NEWLINE PROGRAM;

但NEWLINE被允许不生产任何东西。

NEWLINE ::= salto NEWLINE 
        |   ;

所以第二次递归产生PROGRAM可能什么也没增加。而且它可能不会添加很多次，因为生产是递归的。但是解析器需要是确定性的：它需要准确地知道有多少空存在，以便它可以将每个NEWLINE空归约为非终结符，然后归约一个新的PROGRAM非终结符。它真的不知道要添加多少虚无。

简而言之，可选的虚无和重复的虚无是模棱两可的。如果要在语言中插入无，则需要确保有固定的有限数量的无，因为这是解析器可以明确剖析无的唯一方法。

现在，由于该特定递归的唯一要点（据我所知）是允许空的换行符终止的语句（由于换行符而可见，但什么也不做）。您可以通过更改递归来避免任何事情来做到这一点：

PROGRAM ::= ...
        |   salto PROGRAM;

尽管它与您当前的问题无关，但我不得不提一下，CUP 是一个 LALR 解析器生成器，您可能在互联网上学到或阅读的所有关于递归下降解析器无法处理左递归的东西都不适用。（我删除了关于解析技术教学方式的咆哮，所以你必须尝试从我留下的提示中恢复它。）自下而上的解析器生成器，如 CUP 和 yacc/bison喜欢左递归。当然，它们也可以处理右递归，但很不情愿，因为除了左递归之外，它们需要为每个递归浪费堆栈空间. 所以没有必要为了处理缺陷而扭曲你的语法；只是自然地写语法并快乐。（所以你很少需要非终端来代表“其余”的东西。）

PD：没有什么是对 1934 年歌剧《波吉和贝丝》中的一首歌的文化特定参考。

于 2017-06-04T05:29:31.083 回答