FIRST 集合算法伪代码详解

本文提供 FIRST 集合算法的伪代码，帮助理解和实现该算法。

1. 初始化 FIRST 集合为空集

FIRST(A) = {} // 对于每个符号 A

2. 对于每个终结符，将其本身加入 FIRST 集合

对于每个终结符 a
    FIRST(a) = {a}

3. 对于每个非终结符 A，执行以下步骤：

对于每个非终结符 A
    // a. 如果 A 可以推出空串，将空串加入 FIRST 集合
    如果 A -> ε
        FIRST(A) = FIRST(A) ∪ {ε}
    
    // b. 对于每个 A 的产生式 A->X1X2...Xn，执行以下步骤：
    对于每个 A 的产生式 A -> X1X2...Xn
        i. 将 FIRST(X1) 加入 FIRST(A)
        FIRST(A) = FIRST(A) ∪ FIRST(X1)
        
        ii. 如果 FIRST(X1) 包含空串，将 FIRST(X2) 加入 FIRST(A)
        如果 ε ∈ FIRST(X1)
            FIRST(A) = FIRST(A) ∪ FIRST(X2)
        
        iii. 如果 FIRST(X2) 包含空串，将 FIRST(X3) 加入 FIRST(A)
        如果 ε ∈ FIRST(X2)
            FIRST(A) = FIRST(A) ∪ FIRST(X3)
        
        iv. 重复 ii 和 iii，直到所有 Xi 的 FIRST 集合都不包含空串，或者所有 Xi 都已处理完毕
        直到 ε ∉ FIRST(Xi) 或 i > n

4. 返回所有符号的 FIRST 集合

示例：

假设文法 G 为：

S -> AB | a
A -> a | ε
B -> b

则 FIRST 集合为：

FIRST(S) = {a}
FIRST(A) = {a, ε}
FIRST(B) = {b}

注意：

ε 表示空串。
∪ 表示集合的并集。
该算法的实现需要递归调用，直到所有符号的 FIRST 集合都已计算完毕。

希望以上内容对您理解 FIRST 集合算法有所帮助。