first集和follow集怎么求

在编译原理中，First集和Follow集是用于构造语法分析表的两个重要概念。

First集：对于文法中的每个非终结符，求出它能推导出的所有字符串的首符号集合，这个集合就是该非终结符的First集。

Follow集：对于文法中的每个非终结符，求出它在所有产生式右部中紧随其后的符号的集合，这个集合就是该非终结符的Follow集。

求解First集和Follow集的方法如下：

1. 对于每个终结符，它的First集就是它本身。

2. 对于每个非终结符，如果它可以推导出空串，则将空串加入它的First集。

3. 对于每个产生式A->α，将α的首符号加入A的First集。

4. 对于每个非终结符A，将所有能推导出A的产生式右部的Follow集加入A的Follow集。

5. 对于每个产生式A->αBβ，将B的First集加入A->αBβ的Follow集。如果B可以推导出空串，则将A的Follow集加入A->αBβ的Follow集。

相关问题

求first集和follow集

### 计算 FIRST 集

在编译原理中，计算 FIRST 集的过程涉及两个主要操作：直接收取和反复传送。

- **直接收取**：当存在形如 \( U \rightarrow a\ldots \) 的产生式（其中 \( a \) 是终结符），则将 \( a \) 添加到 \( First(U) \)[^1] 中。

- **反复传送**：如果有一个产生式形式为 \( U \rightarrow P\ldots \)，这里 \( P \) 表示非终结符，则需将 \( First(P) \) 中的所有元素复制给 \( First(U) \)。需要注意的是，在处理非终结符时，还需考虑可能存在的 ε 生产情况；即如果某个非终结符可以推导出空串 (ε)，那么还需要继续查看后续符号来更新当前非终结符的 FIRST 集合。

对于终止符来说，它们自身的集合就是自己的 FIRST 集。

def compute_first_sets(grammar):
    first = {}
    
    # Initialize all non-terminals with empty sets and terminals with themselves.
    for symbol in grammar.symbols:
        if not is_non_terminal(symbol):  # Assuming we have an `is_non_terminal` function to check this.
            first[symbol] = {symbol}
            
    while True:
        updated = False
        
        for production in grammar.productions:
            head, body = production.head, production.body
            
            original_size = len(first.get(head, set()))
            
            new_elements = set()
            for symbol in body:
                if 'epsilon' in first.get(symbol, {}):
                    new_elements.update(first[symbol].difference({'epsilon'}))
                else:
                    new_elements.update(first[symbol])
                    break
                
            first.setdefault(head, set()).update(new_elements)
                
            if len(first[head]) != original_size:
                updated = True
                    
        if not updated:
            break
    
    return first

### 计算 FOLLOW 集

FOLLOW 集用于描述紧跟在一个特定符号之后可能出现的终端字符。特别地：

- 对于文法起始符号 S，默认情况下总是有 `#` 属于它的 FOLLOW(S)=#{ }。

为了构建其他符号的 FOLLOW 集，通常会遍历整个文法规则列表，并应用如下规则：

- 如果 A → αBβ 是一个生产规则，则任何出现在 β 的 FIRST 集内的终端都会被加入到 B 的 FOLLOW 集里；
- 若上述条件下的 β 能够派生为空序列，则 FOLLOW(A) 应该也属于 FOLLOW(B);
- 当遇到新的 FOLLOW 成员时，重复以上过程直到不再发生变化为止。

def compute_follow_sets(grammar, first_set):
    follow = {}

    start_symbol = get_start_symbol(grammar)

    # 初始化所有的非终结符的follow集为空集，
    # 并且设置文法开始符号的follow集中含有结束标志'#'
    for nt in grammar.non_terminals:
        follow[nt] = set()

    follow[start_symbol].add('#')

    changed = True
    while changed:
        changed = False
        for rule in grammar.rules:
            lhs = rule.lhs
            rhs_symbols = list(rule.rhs)

            for i, sym in enumerate(rhs_symbols[:-1]):
                next_sym = rhs_symbols[i + 1]

                if is_non_terminal(sym):
                    f_next = first_set[next_sym].copy() - {'epsilon'}
                    old_len = len(follow[sym])

                    follow[sym].update(f_next)

                    if 'epsilon' in first_set[next_sym]:
                        follow[sym].update(follow[lhs])

                    if len(follow[sym]) > old_len:
                        changed = True

            last_sym = rhs_symbols[-1] if rhs_symbols else None
            if isinstance(last_sym, NonTerminalType):
                old_len = len(follow[last_sym])
                follow[last_sym].update(follow[lhs])
                if len(follow[last_sym]) > old_len:
                    changed = True

    return follow

求first集和follow集代码

在上下文中，你提到的"first集"和"follow集"通常是正则表达式理论中的概念，用于分析确定语言是否是正规的。在编程中，特别是在编写词法分析器或自动机时，会计算输入串的所有可能匹配的起始位置（first集）以及能够跟随某个特定符号后的所有可能符号（follow集）。这是状态机设计的一部分。

这是一个简单的例子，在Python的`re`模块中，可以利用`nonzero()`函数获取第一个字符的位置：

import re

def first_set(regex):
    return set(range(len(regex))) if regex else None

regex = 'a*b+c'
first = first_set(regex)

而`follow_set`通常需要更复杂的算法，例如在LL(k)解析器生成器中，它会基于输入文法来计算。这通常涉及到递归地处理文法规则，并不是直接可用的内置函数。你需要手动计算或使用专门的工具库如ANTLR等。

下面是一个简单的伪代码示例：

def follow_set(symbol, grammar):
    # 假设grammar是DFA或CFG的一个表示形式
    follows = set()
    for rule in grammar.rules:
        if symbol in rule.lhs and rule.rhs[-1] not in follows:
            follows.add(rule.rhs[-1])
    return follows

# 假设rule_list包含输入文法的规则
follow = follow_set('b', rule_list)

请注意，实际的实现取决于具体的文法和工具环境，上述代码仅作示意。