代码之家 › 专栏 › 技术社区 › Chris Geo

如何找到LR0项目的FOLLOW集合?

lr1 lalr compiler-construction rust parsing

-1

Chris Geo · 技术社区 · 8 月前

我正在尝试使用下面的帮助实现LR1解析器 wikipedia article 。我已经为LR0项目制作了一个闭包函数,当试图为LR1项目制作闭包时(关于向LR0项目添加lookaheads的部分),我需要计算FIRST和FOLLOW集,但维基引用了 2 FOLLOW sets ,一个接受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项目的FOLLOW实现( lr0_follow(rules, item) ),它是否与FOLLOW(非终结符)相同,其中非终结符是项目点后的非终结符(如果有,则返回空集)?

注意:我的LR1解析器不使用epsilons。

我不知道该尝试什么,因为我找不到这个特定关注集的任何资源。

1 回复 | 直到 8 月前

1

0

Chris Dodd 8 月前

你或多或少是正确的——使用LR(0),你根本不用担心看前方,所以当你需要看前方时,你可以看FOLLOW(非终结符)

按照你的链接条款来表达 ^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. _{你需要对维基页面上的细节有点小心——当他们显示“LR(1)的完整项目集0”时,他们实际上已经有了LALR(1}