求出每个非终结符的first集和follow集

在编译原理中，求解每个非终结符的First集和Follow集是语法分析中的重要步骤。下面是对这两个概念的介绍：

1. First集：对于文法中的每个非终结符，其First集包含了该非终结符能够推导出的终结符的集合。求解First集的方法如下：
- 如果X是一个终结符，则First(X) = {X}。
- 如果X是一个非终结符，则First(X)包含了所有可以从X推导出的终结符的集合。具体求解方法是：
- 对于每个产生式X -> Y1Y2...Yn，将First(Y1)中的所有终结符加入到First(X)中。
- 如果Y1可以推导出ε（空串），则将First(Y2)中的所有终结符加入到First(X)中。
- 重复上述步骤，直到没有新的终结符可以加入到First(X)中。

2. Follow集：对于文法中的每个非终结符，其Follow集包含了该非终结符可能紧跟在其后的终结符的集合。求解Follow集的方法如下：
- 对于文法的开始符号S，将$（结束标记）加入到Follow(S)中。
- 对于每个产生式A -> αBβ，将First(β)中除去ε（空串）的所有终结符加入到Follow(B)中。
- 如果存在产生式A -> αB或A -> αBβ，其中First(β)包含ε（空串），则将Follow(A)中的所有终结符加入到Follow(B)中。

相关问题

编译原理实验求非终结符的First，Follow集

### 计算非终结符的First集

在编译原理中，`FIRST`集合对于给定的一个符号（可以是非终结符或字符串），表示该符号推导出的第一个可能的终结符字符。如果存在ε（空串）的可能性，则也包括ε。

#### 定义
- 对于任何终结符 `a`，定义 `FIRST(a)` 为 `{ a }`。
- 如果有一个规则形如 A → ε，则将 ε 加入到 FIRST(A) 中[^1]。

#### 算法描述
为了计算某个非终结符A的`FIRST`集合：

1. 初始化所有非终结符对应的`FIRST`集合为空；
2. 将所有的单个终结符加入其自身的`FIRST`集中；
3. 遍历文法规则表中的每条规则R：设 R 的形式为 A -> X₁X₂...Xₖ (k ≥ 0)，依次执行如下操作直到不再发生变化为止：
- 若 Xi 是终结符，则将其加入至 FIRST(A) 并停止处理当前规则;
- 否则如果是非终结符且 FIRST(Xi) 不含 ε ，那么把 FIRST(Xi)\{ε} 添加到 FIRST(A);
- 当遇到含有 ε 的情况时继续考察下一个符号Xi+1, 直到最后一个符号或者中途遇到了不含 ε 的 FIRST 集合.
4. 特殊情况下，当整个右侧都可以推出 ε 时，也将 ε 放入左侧非终结符的 FIRST 集合内；

def compute_first_sets(grammar_rules):
    first = {}
    
    # Initialize all non-terminals with empty sets and terminals with singleton sets containing themselves
    for symbol in grammar_symbols:
        if is_terminal(symbol): 
            first[symbol] = {symbol}
        else: 
            first[symbol] = set()
            
    changed = True
    
    while changed:
        changed = False
        
        for rule in grammar_rules:
            head, body = rule.split('->')
            current_set = set()

            for symbol in body.strip().split():
                if 'epsilon' not in first[symbol]:
                    current_set |= first[symbol]
                    break
                
                elif symbol != 'epsilon':
                    current_set |= first[symbol].difference({'epsilon'})
                    
            else:
                current_set.add('epsilon')

            new_elements = current_set.difference(first[head])
                
            if new_elements:
                first[head] |= new_elements
                changed = True
                    
    return first

### 计算非终结符的Follow集

`FOLLOW`集合用于指定某非终结符后面可能出现哪些终结符。这对于预测解析器来说非常重要。

#### 定义
- FOLLOW(S) 总是包含 `$`(输入结束标记), 其中 S 表示起始符号；
- 设有产生式 A→αBβ , 则一切属于 FIRST(β)-{ε} 的符号都应放入 FOLLOW(B) 中; 如果 β 能够派生出 ε 或者 β=ε ，即 FIRST(β) 包括 ε ，此时还需要进一步考虑 FOLLOW(A) 是否应该被加到 FOLLOW(B) 上去.

#### 算法描述
初始化阶段设置起始符号S的`FOLLOW(S)={$}`，其余均为∅。之后通过遍历文法规则来更新各个非终结符的`FOLLOW`集合:

1. 对每一个产生式的右部进行扫描，
2. 基于上述定义逐步扩展相应的`FOLLOW`集合,
3. 迭代此过程直至没有任何新的成员能够加入任何一个`FOLLOW`集合之中。

def compute_follow_sets(start_symbol, grammar_rules, first_sets):
    follow = {}

    for nt in non_terminals:
        follow[nt] = set() 

    follow[start_symbol].add('$')  

    changed = True   

    while changed:
        changed = False    

        for rule in grammar_rules:
            lhs, rhs = map(str.strip, rule.split('->'))

            symbols = list(rhs)

            for i in range(len(symbols)):
                B = symbols[i]

                if is_nonterminal(B):

                    beta = ''.join(symbols[i + 1:])
                        
                    if beta or not beta and i == len(symbols) - 1:
                        fbeta = first(beta, first_sets).copy()

                        if 'epsilon' in fbeta:
                            fbeta.remove('epsilon')
                            
                        old_size = len(follow[B])

                        follow[B] |= fbeta | (set() if beta else follow[lhs])  
                        
                        if len(follow[B]) > old_size:
                            changed = True
                        
    return follow

给出此文法每个非终结符的FIRST集和FOLLOW集： A→BAC|gDB|CC B→bCDE|ε C→DaB|ha D→dD|ε E→gAf|c

首先，我们需要计算出每个非终结符可以推导出的所有可能的首符号（FIRST集）。

对于A，它可以推导出BAC、gDB和CC，因此

FIRST(A) = {g, d, h}

对于B，它可以推导出bCDE或者ε，因此

FIRST(B) = {b, ε}

对于C，它可以推导出DaB或者ha，因此

FIRST(C) = {d, h}

对于D，它可以推导出dD或者ε，因此

FIRST(D) = {d, ε}

对于E，它可以推导出gAf或者c，因此

FIRST(E) = {g, c}

接下来，我们需要计算出每个非终结符可以跟随在其他符号后面的所有可能符号（FOLLOW集）。

对于A，它在开始符号的位置，因此$A$的FOLLOW集包含了输入串的结束标记$#$(假设#不在文法中)。另外，B在A的右边，因此当B出现在某个位置时，A的FOLLOW集也应该包括紧随B后面的符号。同样的，当C出现在位置中，A的FOLLOW集也应该包括C后面的符号。因此，

FOLLOW(A) = {#, b, h}

对于B，它只在A的右边出现，因此B的FOLLOW集只需要包含跟随在A后面的符号。因此，

FOLLOW(B) = {a, h, #}

对于C，它可以在A和D的右边出现，因此C的FOLLOW集应该包括紧随A和D后面的符号。因此，

FOLLOW(C) = {b, d, h, #}

对于D，它可以在C和E的右边出现，因此D的FOLLOW集应该包括紧随C和E后面的符号。因此，

FOLLOW(D) = {a, h, #}

对于E，它只在B的右边出现，因此E的FOLLOW集只需要包含跟随在B后面的符号。因此，

FOLLOW(E) = {d, h, #}