编译原理求first和follow python

### 编译原理中计算FIRST和FOLLOW集合

#### 计算 FIRST 集合
为了计算文法的 `FIRST` 集合，可以采用迭代的方法直到不再发生变化为止。对于每一个非终结符，如果它直接推导出一个终结符，则该终结符属于它的 `FIRST` 集；如果它能推出 ε (空串)，则 ε 属于它的 `FIRST` 集。

def compute_first(grammar, non_terminals, terminals):
    first_sets = {nt: set() for nt in non_terminals}
    
    changed = True
    
    while changed:
        changed = False
        
        for lhs, productions in grammar.items():
            for production in productions:
                original_size = len(first_sets[lhs])
                
                i = 0
                while i < len(production):
                    symbol = production[i]
                    
                    if symbol in terminals or symbol == 'ε':
                        first_sets[lhs].add(symbol)
                        break
                    
                    elif symbol in non_terminals:
                        first_sets[lhs] |= first_sets[symbol] - {'ε'}
                        
                        if 'ε' not in first_sets[symbol]:
                            break
                        
                    i += 1
                
                else:
                    first_sets[lhs].add('ε')
                
                new_size = len(first_sets[lhs])
                
                if new_size != original_size:
                    changed = True
    
    return first_sets

此函数接收三个参数：文法、非终结符列表以及终结符列表，并返回每个非终结符对应的 `FIRST` 集合[^1]。

#### 计算 FOLLOW 集合
`FOLLOW` 集合用于描述某个非终结符可能出现在句型中的位置之后可能出现哪些符号。初始时只有起始符号 S 的 `FOLLOW(S)` 中含有结束标记 `$` 或者 `#` 表示输入流结束。其他规则如下：

- 如果存在 A → αBβ 形式的产生式，则把 FIRST(β) 加入到 FOLLOW(B) 中（不包括 ε）
- 若 β 可以推导出 ε ，那么还需要将 FOLLOW(A) 添加至 FOLLOW(B)

def compute_follow(grammar, start_symbol, first_sets, non_terminals):
    follow_sets = {nt: set(['$']) if nt == start_symbol else set() for nt in non_terminals}

    changed = True
    
    while changed:
        changed = False
        
        for lhs, productions in grammar.items():
            for production in productions:
                rhs_symbols = list(reversed([s for s in production if s]))
                
                prev_follow_set = None
                
                for symbol in rhs_symbols:
                    if symbol in non_terminals:
                        current_follow_set = follow_sets[symbol]

                        if prev_follow_set is not None:
                            old_len = len(current_follow_set)
                            
                            current_follow_set.update(prev_follow_set.difference({'ε'}))
                            
                            if 'ε' in prev_follow_set:
                                current_follow_set.update(follow_sets[lhs])

                            new_len = len(current_follow_set)
                                
                            if new_len > old_len:
                                changed = True
                                    
                        else:
                            if symbol != lhs and lhs in follow_sets:
                                old_len = len(current_follow_set)
                                
                                current_follow_set.update(follow_sets[lhs])
                                
                                new_len = len(current_follow_set)
                                
                                if new_len > old_len:
                                    changed = True
                                        
                        prev_follow_set = first_sets[symbol].union({symbol}) if symbol in first_sets else {symbol}
                        
                    elif symbol == 'ε':
                        continue
                    
                    else:
                        prev_follow_set = {symbol}
        
    return follow_sets

这段代码实现了基于给定文法规则来构建相应的 `FOLLOW` 集合的功能[^3]。