有关编译原理first集合和follow集合的相关问题？

Question

已知文法 G(E) 
E →T|E＋T T→F|T *F F →(E)|id
求所有非终结符的first集合和follow集合

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

首先，我们需要了解一些基本的概念：

1. 第一集（First Set）：如果一个符号是某个规则的第一个输入符号，那么这个符号就是该规则的第一集。例如，在上面的例子中，符号 "T" 是第一个输入符号，因此它属于第一集。

2. 跟随集（Follow Set）：如果一个符号是某个规则的最后一个输出符号，那么这个符号就是该规则的跟随集。例如，在上面的例子中，符号 "T" 是最后一个输出符号，因此它属于跟随集。

接下来，我们来求解给定的文法的所有非终结符的第一集和跟随集。

import re

# 文法定义
grammar = """
E -> T | E + T
T -> F | T * F
F -> (E) | id
"""

def first_and_follow(tokens):
    # 初始化跟随集为全集
    follow_set = set()
    
    for token in tokens:
        if re.match(r'\d+', token):  # 如果是数字，则直接添加到跟随集中
            follow_set.add(token)
        
        else:  # 否则，遍历当前token的前缀，并检查是否是第二个输入符号
            prefix = token[:-1]
            for rule in grammar.split('\n'):
                match = re.match(r'(\w+)\s+->\s+(\w+)', rule)
                if match:
                    right_hand_side = match.group(2)
                    left_hand_side = match.group(1)
                    if left_hand_side == prefix:
                        follow_set.add(right_hand_side)
                        break
    
    return follow_set

tokens = ['T', 'T', 'T', 'F', 'id']
print(first_and_follow(tokens))

注意：这段代码使用了Python的正则表达式库re来进行匹配和搜索。在实际应用中，你可能需要根据具体的编程语言和环境进行相应的调整。此外，对于一些特定的文本或语料库，可能需要对正则表达式进行适当的修改以获取更精确的结果。