主页 / coding / 问题 / 78818407
Accepted
Chris Geo
Asked: 2024-08-01 05:38:32 +0800 CST

如何找到 LR0 项目的 FOLLOW 集？

  • 772

我正在尝试实现一个 LR1 解析器，使用这篇wikipedia 文章中的帮助。我已经为 LR0 项创建了一个闭包函数，当尝试为 LR1 项创建闭包时（关于向 LR0 项添加前瞻的部分），我需要计算 FIRST 和 FOLLOW 集，但是 wiki 提到了2 个 FOLLOW 集，一个接受 LR0 项，另一个只接受项集和非终结符。第二个很容易理解：

pub fn lr0_follow_in_item_set(
    rules: &[Rule],
    item_set: &[LR0Item],
    nt: &NonTerminal,
) -> BTreeSet<Terminal> {
    let mut res = BTreeSet::new();
    for item in item_set { // 
        if Some(TerminalOrNonTerminal::NonTerminal(*nt)) == item.next_symbol(rules) { // item in item set where dot is before the desired non terminal
            res.extend(lr0_follow(rules, item)); // union of the follow sets
        }
    }
    res
}

但是我找不到 LR0 项 ( lr0_follow(rules, item)) 的 FOLLOW 实现，它是否与 FOLLOW(nonterminal) 相同，其中 nonterminal 是项点后的非终端（如果有，否则返回空集）？

注意：我的 LR1 解析器不使用 epsilon。

我不知道该尝试什么，因为我找不到此特定 FOLLOW 集的任何资源。

parsing

1 个回答

  1. Best Answer

    你或多或少是正确的 - 使用 LR(0)，你根本不用担心前瞻，所以当你需要前瞻时，你只需查看 FOLLOW(nonterminal)

    按照您链接的1维基百科文章的术语来说，当您有一个项目“I：A → α·B β，x”时，LR(0)，x(前瞻)始终为空。因此，在计算 FOLLOW(I) 时，当 FIRST(β) 包含 epsilon 时，您不会使用 x，而是使用语法中的 FOLLOW(A)。

    所以最终得到的等式是

    如果 ε ∈ FIRST(β)
      FOLLOW(I) = (FIRST(β) - {ε}) ∪ FOLLOW(A)
    否则
      FOLLOW(I) = FIRST(β)

    1您需要对该 wiki 页面上的细节保持谨慎——当他们显示“LR(1) 的完整项目集 0”时，他们实际上拥有 LALR(1) 的完整项目集，而没有真正讨论 LR(1) 和 LALR(1) 之间的区别

    • 0

相关问题