文法First集Follow集求解算法代码
时间: 2023-06-17 17:08:01 浏览: 103
以下为文法的First集和Follow集求解算法代码,其中文法的表示方式采用BNF范式。
```
# 文法表示方式:BNF范式
grammar = {
"<start>": ["<expr>"],
"<expr>": ["<term><expr_tail>"],
"<expr_tail>": ["+<term><expr_tail>", "-<term><expr_tail>", ""],
"<term>": ["<factor><term_tail>"],
"<term_tail>": ["*<factor><term_tail>", "/<factor><term_tail>", ""],
"<factor>": ["(<expr>)", "<id>", "<num>"],
"<id>": ["a", "b", "c"],
"<num>": ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
}
# 计算First集
def calc_first(grammar):
first = {}
for symbol in grammar:
first[symbol] = set()
while True:
updated = False
for symbol in grammar:
for production in grammar[symbol]:
if production == "":
continue
first_alpha = set()
for alpha in production:
if alpha in first:
first_alpha |= first[alpha]
if alpha not in first:
break
else:
if len(first_alpha - first[symbol]) > 0:
updated = True
first[symbol] |= first_alpha
if not updated:
break
return first
# 计算Follow集
def calc_follow(grammar, first):
follow = {}
for symbol in grammar:
follow[symbol] = set()
follow["<start>"].add("$")
while True:
updated = False
for symbol in grammar:
for production in grammar[symbol]:
for i, alpha in enumerate(production):
if alpha not in grammar:
continue
follow_alpha = set()
for beta in production[i + 1:]:
if beta in first:
follow_alpha |= first[beta] - {""}
if "" not in first[beta]:
break
else:
follow_alpha |= {beta}
break
else:
if len(follow_alpha - follow[alpha]) > 0:
updated = True
follow[alpha] |= follow_alpha
if "" in follow_alpha or i == len(production) - 1:
follow[symbol] |= follow[alpha]
if "" in follow_alpha:
follow[symbol] |= follow[symbol]
if not updated:
break
return follow
# 测试
first = calc_first(grammar)
print("First set:")
for symbol in first:
print(f"{symbol} -> {first[symbol]}")
follow = calc_follow(grammar, first)
print("Follow set:")
for symbol in follow:
print(f"{symbol} -> {follow[symbol]}")
```
在上述代码中,`calc_first(grammar)`函数用于计算文法的First集,`calc_follow(grammar, first)`函数用于计算文法的Follow集。其中,在计算Follow集时需要使用到First集,因此需要将计算First集的结果作为参数传入`calc_follow`函数中。
具体实现中,使用了两个字典`first`和`follow`来分别保存文法的First集和Follow集。在计算过程中,首先每个非终结符的First集初始化为空集,每个非终结符的Follow集初始化为$S$符号的Follow集($S$为起始符号)。接着,使用循环遍历所有的产生式,根据产生式的右部计算出First集或Follow集,并将其加入到相应的集合中。在计算First集时,需要使用到之前已经计算出的First集;在计算Follow集时,需要使用到之前已经计算出的Follow集和First集。在计算过程中,如果发现某个集合发生了更新,则需要重新进行循环,直到所有集合都不再更新为止。
最后,将计算得到的First集和Follow集打印出来,用于验证结果的正确性。