first集和follow集怎么求
时间: 2024-06-12 08:11:37 浏览: 223
在编译原理中,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 集。
```python
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 成员时,重复以上过程直到不再发生变化为止。
```python
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()`函数获取第一个字符的位置:
```python
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等。
下面是一个简单的伪代码示例:
```python
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)
```
请注意,实际的实现取决于具体的文法和工具环境,上述代码仅作示意。
阅读全文
相关推荐
















