如何实现LR0项目的FOLLOW集？LR1 Parser开发中的疑问

你的猜想不对。维基中提到的lr0_follow(rules, item)并非项目点后非终结符的FOLLOW集，而是项目点右侧所有符号组成的串的FIRST集合；如果点位于项目的末尾（右侧无符号），则返回该项目左部非终结符的FOLLOW集。

逻辑解释 #

在LR1项目的闭包计算中，当处理形如A → α·B β的项目时，生成非终结符B的LR1项目需要的前瞻符，本质是原项目点右侧串β能推导出的首个终结符集合（即FIRST(β)）。由于你的Parser不使用ε，FIRST(β)的计算无需考虑空串扩展：

• 若β非空，直接取β中第一个符号的FIRST集；
• 若β为空（即项目是A → α·），则前瞻符变为FOLLOW(A)——这表示当前项目完成后，后续可能出现的终结符。

Rust实现示例 #

use std::collections::BTreeSet;

// 假设你已定义以下核心类型：
// struct Rule { ... }
// struct LR0Item { ... }
// #[derive(Clone, Ord, PartialOrd, Eq, PartialEq)] struct NonTerminal(u32);
// #[derive(Clone, Ord, PartialOrd, Eq, PartialEq)] struct Terminal(u32);
// enum TerminalOrNonTerminal { Terminal(Terminal), NonTerminal(NonTerminal) }

// 辅助函数：计算符号串的FIRST集（无ε场景）
fn first_of_sequence(rules: &[Rule], symbols: &[TerminalOrNonTerminal]) -> BTreeSet<Terminal> {
    let mut res = BTreeSet::new();
    for sym in symbols {
        match sym {
            TerminalOrNonTerminal::Terminal(t) => {
                res.insert(t.clone());
                break; // 无ε，第一个终结符即为全部FIRST集
            }
            TerminalOrNonTerminal::NonTerminal(nt) => {
                // 需提前实现非终结符的FIRST集计算函数
                let first_nt = first_of_non_terminal(rules, nt);
                res.extend(first_nt);
                break; // 无ε，无需继续遍历后续符号
            }
        }
    }
    res
}

// 实现目标函数lr0_follow
pub fn lr0_follow(rules: &[Rule], item: &LR0Item) -> BTreeSet<Terminal> {
    // 假设LR0Item可分解为：左部非终结符、右部符号列表、点的位置
    let (left_nt, right_symbols, dot_pos) = item.decompose();
    let remaining_symbols = &right_symbols[dot_pos..];

    if remaining_symbols.is_empty() {
        // 点在项目末尾，返回左部非终结符的FOLLOW集
        follow_of_non_terminal(rules, left_nt)
    } else {
        // 计算剩余符号串的FIRST集
        first_of_sequence(rules, remaining_symbols)
    }
}

补充说明 #

• 你需要提前实现first_of_non_terminal（非终结符的FIRST集计算）和follow_of_non_terminal（非终结符的FOLLOW集计算），这两个是语法分析中的经典辅助函数，无ε场景下实现逻辑更简洁。
• 结合你已实现的lr0_follow_in_item_set，遍历项目集中点位于目标非终结符之前的项目，将每个项目的lr0_follow结果取并集，即可得到该非终结符在当前项目集中的FOLLOW集，用于生成LR1闭包的新项目前瞻符。

内容的提问来源于stack exchange，提问作者Chris Geo