1

像这样的EBNF

Goal = Stmt
Stmt = "if" "expr" "then" Stmt ("else" Stmt)?
Stmt = "S"

我应该将其转换为

Goal = Stmt
X = "else" Stmt
Stmt = "if" "expr" "then" Stmt | "if" "expr" "then" Stmt X 
Stmt = "S"

或者

Goal = Stmt
Stmt = "if" "expr" "then" Stmt | "if" "expr" "then" Stmt "else" Stmt
Stmt = "S"

这两个 BNF 对 GLR 解析器的含义相同吗？

------------------------ 附加内容 ------------------------ ------

如果词法是

"if" "expr" "then" "if" "expr" "then" "S" "else" "S"

GLR 解析器应该得到两棵树

Goal
    Stmt
        "if"
        "expr"
        "then"
        Stmt
            "if"
            "expr"
            "then"
            Stmt
                "S"
        "else"
        Stmt
            "S"

和

Goal
    Stmt
        "if"
        "expr"
        "then"
        Stmt
            "if"
            "expr"
            "then"
            Stmt
                "S"
            "else"
             Stmt
                "S"

但是第一个转换的 BNF 只能得到第一棵树，因为当它遇到时"else"，reduce/shift 没有冲突，冲突在遇到 X。

第二个 BNF 在遇到时会发生 reduce/shift 冲突"else"，因此解析器将拆分为两个线程在不同的条件下进行解析。

我对吗？是否有任何 ACTION、GOTO TABLE 生成器可以像对待第二个 BNF 一样对待第一个 BNF？

4

1 回答 1

1

它们是等效的语法，将解析相同的语言。

您的 X 语法仅在一处使用 X。最终效果就好像 X 的主体在 X 被引用的地方被替换了。在实践中，产生 X 将迫使解析器做更多的工作。除非您想将语义操作附加到 X 的归约上，否则额外的工作不会提高效率。

就这种一次性产生式使语法更易于维护而言，这样做很有用。在这样的小语法中，我看不到重点。在实际语法中（我们有一个用于 IBM COBOL 的 GLR 语法，有 5000 个产生式 [责备 IBM，而不是我们]），这种结构非常有用，额外的解析开销无关紧要。

于 2015-04-01T09:13:32.003 回答