我已经开始阅读有关 LR(k) 解析表构造的内容,所有解释 k > 0 算法的文本都建议在生成项目集之前为每个符号计算前瞻,然后在生成所有项目集时,应该合并多余的以生成最小的解析表。
考虑以下伪状态/项集构造例程:
- 首先假设可以在没有前瞻的情况下确定状态转换(k = 0)
- 计算当前状态的整个项目集
- 尝试确定当前状态动作:
- 如果集合中只有一个项目并且它已经消耗了所有输入(rhs 右侧的标记,则操作减少到项目的 lhs。
- 如果集合中的每个项目都需要输入,则动作是转移并进入下一个状态
- 如果有些项目需要输入而有些则没有,这是一个移位/减少冲突
- 如果两个或多个具有不同 lhs 的项目到达输入末尾,这是一个减少/减少冲突。如果发生了最后两种情况之一,这意味着我们需要在决定状态动作之前先看一下。将 k 增加 1 并返回步骤 2。
- 如果动作要转移,则通过模拟输入组合(如果 k > 0 则为前瞻)继续创建后续状态,并为每个新状态返回步骤 1。
使用上述步骤为任意 LR(k) 语法构建表是否可能/可行?如果没有,我错过了什么?