### Python 实现文法求解 FIRSTVT 和 LASTVT 集合并构造优先关系表 以下是基于给定需求的解决方案，其中包括计算 `FIRSTVT` 和 `LASTVT` 的方法以及如何构建算符优先关系表。 #### 计算 FIRSTVT 集合 为了计算 `FIRSTVT` 集合，可以按照如下逻辑实现： 1. 初始化布尔矩阵用于记录每个非终结符对应的终结符是否属于其 `FIRSTVT`。 2. 对于形如 \( A \to a\ldots \) 或 \( A \to Ba\ldots \)，分别处理不同的情况来更新 `FIRSTVT`。 3. 使用栈结构解决间接推导的情况。 ```python def initialize_map(non_terminals, terminals): """初始化二维字典""" map_dict = {} for nt in non_terminals: map_dict[nt] = {t: False for t in terminals} return map_dict def compute_firstvt(grammar, terminals, non_terminals): firstvt = {nt: [] for nt in non_terminals} # 存储最终结果 map_dict = initialize_map(non_terminals, terminals) stack = [] for lhs in grammar: rhs_list = grammar[lhs] for rhs in rhs_list: if rhs and rhs[0] in terminals: # 形如 A -> a... map_dict[lhs][rhs[0]] = True stack.append((lhs, rhs[0])) elif len(rhs) > 1 and rhs[1] in terminals: # 形如 A -> Bc... map_dict[lhs][rhs[1]] = True stack.append((lhs, rhs[1])) while stack: (current_nt, current_t) = stack.pop() for key in grammar: productions = grammar[key] for production in productions: if production and production[0] == current_nt: # 如果存在 P -> Q... 则加入当前终结符 if not map_dict[key][current_t]: map_dict[key][current_t] = True stack.append((key, current_t)) for nt in non_terminals: for t in terminals: if map_dict[nt][t]: firstvt[nt].append(t) return firstvt ``` #### 计算 LASTVT 集合 对于 `LASTVT` 的计算方式类似于 `FIRSTVT`，只需调整扫描方向即可。具体来说，在判断规则时关注的是右侧最后一个字符而非第一个字符。 ```python def compute_lastvt(grammar, terminals, non_terminals): lastvt = {nt: [] for nt in non_terminals} # 存储最终结果 map_dict = initialize_map(non_terminals, terminals) stack = [] for lhs in grammar: rhs_list = grammar[lhs] for rhs in rhs_list: if rhs and rhs[-1] in terminals: # 形如 A -> ...a map_dict[lhs][rhs[-1]] = True stack.append((lhs, rhs[-1])) elif len(rhs) > 1 and rhs[-2] in terminals: # 形如 A -> ...Ba map_dict[lhs][rhs[-2]] = True stack.append((lhs, rhs[-2])) while stack: (current_nt, current_t) = stack.pop() for key in grammar: productions = grammar[key] for production in productions: if production and production[-1] == current_nt: # 如果存在 P -> ...Q 则加入当前终结符 if not map_dict[key][current_t]: map_dict[key][current_t] = True stack.append((key, current_t)) for nt in non_terminals: for t in terminals: if map_dict[nt][t]: lastvt[nt].append(t) return lastvt ``` #### 构造优先关系表 通过比较每一对终结符之间的优先级关系（<、=、>），我们可以得到完整的优先关系表。 ```python def construct_priority_table(firstvt, lastvt, grammar, terminals): priority_table = {t1: {t2: None for t2 in terminals} for t1 in terminals} for lhs in grammar: for rhs in grammar[lhs]: for i in range(len(rhs)-1): if rhs[i] in terminals and rhs[i+1] in non_terminals: for t in firstvt[rhs[i+1]]: priority_table[rhs[i]][t] = '<' if rhs[i] in non_terminals and rhs[i+1] in terminals: for t in lastvt[rhs[i]]: priority_table[t][rhs[i+1]] = '>' if rhs[i] in terminals and rhs[i+1] in terminals: priority_table[rhs[i]][rhs[i+1]] = '=' return priority_table ``` --- ### 示例运行 假设输入文法规则为： \[ S \to E \\ E \to TE' \\ E' \to +TE' | \epsilon \\ T \to FT' \\ T' \to *FT' | \epsilon \\ F \to (E) | id \] 定义语法和符号集合： ```python terminals = {'+', '*', '(', ')', 'id'} non_terminals = {'S', 'E', 'E\'', 'T', 'T\'', 'F'} grammar = { 'S': ['E'], 'E': ['TE\''], 'E\'': ['+TE\'', 'ε'], 'T': ['FT\''], 'T\'': ['*FT\'', 'ε'], 'F': ['(E)', 'id'] } ``` 调用函数： ```python firstvt_result = compute_firstvt(grammar, terminals, non_terminals) lastvt_result = compute_lastvt(grammar, terminals, non_terminals) priority_table = construct_priority_table(firstvt_result, lastvt_result, grammar, terminals) print("FIRSTVT:", firstvt_result) print("LASTVT:", lastvt_result) print("Priority Table:") for k, v in priority_table.items(): print(k, ":", v) ``` ---