负前瞻分析算法

Question

考虑语法这样的规则的LR-家庭解析生成器（例如YACC，野牛等）：

Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ; 

这是一个普通的规则，不同之处在于它有一个限制：用此规则生成的短语不能以Terminal1, ..., TerminalN开头。 （当然，这个规则可以用一套通常的规则来代替，但它会导致更大的语法）。这对解决冲突很有用。

问题是，LR表构造算法是否存在对这种限制的修改？在我看来，这样的修改是可能的（如优先关系）。

当然，它可以在运行时进行检查，但我的意思是编译时检查（这是在构建分析表，如%prec进行检查%left，%right和%nonassoc指令在YACC-compartible发电机。）

Answer 1

我不明白为什么这不应该是可能的，但我也没有看到明显的原因，为什么它会有用。你有没有一个例子？

最简单的方法是做圆括号里提到的语法转换。这会产生更大的语法，但不会人为地增加LR状态的数量。

基本变换，只用位的挥手：

对于任何生产与终端限制：

• 如果生产具有非空的非端开始，更换非终端与终端限制版本。

• 如果生产与终端限制列表中的终端开始，除去生产

• 如果生产与终端不在终端限制列表，无需更改启动。

如果生产具有可空非终端开始，你必须创建的两个版本可空非终端，其中一个总是空，而另一个是不可为空;然后创建两个版本的制作，一个从每个新的非终端开始。然后应用上述变换，但解释“开始于”意味着“在任何始终为空的非终端之后开始”。

实际上您并不需要修改语法，因为上述转换可以在底层SLR机器的构建过程中动态完成，至少对于LR（0）和LALR（1）构造而言。