用python写一个实验。要求如下 根据给定文法,先求出 FirstVt 和 LastVt 集合,构造算符优先关系表(要求算符优先 关系表 输出到显示器或者输出到文件); (2)根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式(要求 输出归约过程)
时间: 2024-02-22 18:59:14 浏览: 56
好的,以下是一个 Python 实现,包括求解 FirstVt 和 LastVt 集合、构造算符优先关系表、以及根据算法和优先关系表分析表达式是否正确的功能。
```python
# 定义文法 G(E'):E' → #E#,E → E+T | T,T → T*F | F,F → (E) | i
grammar = {
"E'": ["#", "E", "#"],
"E": ["E", "+", "T"],
"T": ["T", "*", "F"],
"F": ["(", "E", ")", "i"]
}
# 求解 FirstVt 和 LastVt 集合
first_vt = {}
last_vt = {}
for non_terminal in grammar:
first_vt[non_terminal] = set()
last_vt[non_terminal] = set()
for non_terminal in grammar:
for production in grammar[non_terminal]:
# 计算 FirstVt
if production[0].islower() or production[0] == "(":
first_vt[non_terminal].add(production[0])
elif production[0] in grammar:
first_vt[non_terminal] = first_vt[non_terminal].union(first_vt[production[0]])
# 计算 LastVt
if production[-1].islower() or production[-1] == ")":
last_vt[non_terminal].add(production[-1])
elif production[-1] in grammar:
last_vt[non_terminal] = last_vt[non_terminal].union(last_vt[production[-1]])
# 打印 FirstVt 和 LastVt 集合
print("FirstVt:")
for non_terminal in first_vt:
print(non_terminal + ":", first_vt[non_terminal])
print("\nLastVt:")
for non_terminal in last_vt:
print(non_terminal + ":", last_vt[non_terminal])
# 构造算符优先关系表
precedence_table = {}
precedence_table["#"] = {}
for terminal in first_vt["E'"]:
precedence_table["#"][terminal] = "<"
for non_terminal in grammar:
precedence_table[non_terminal] = {}
for terminal in first_vt[non_terminal]:
precedence_table[non_terminal][terminal] = "<"
for terminal in last_vt[non_terminal]:
precedence_table[non_terminal][terminal] = ">"
if "#" in last_vt[non_terminal]:
precedence_table[non_terminal]["#"] = "="
# 打印算符优先关系表
print("\n算符优先关系表:")
for symbol in precedence_table:
print("|", end="")
for terminal in ["#", "+", "*", "(", ")", "i"]:
print(" " + precedence_table[symbol].get(terminal, " "), end=" |")
print()
# 分析表达式的函数
def analyze_expression(expression):
# 在表达式首尾加上 "#",方便处理
expression = "#" + expression + "#"
stack = ["#"]
i = 0
while i < len(expression) and stack:
top = stack[-1]
if top in first_vt and expression[i] in first_vt[top]:
stack.append(expression[i])
i += 1
elif top in grammar and precedence_table[top][expression[i]] == "<":
stack.append(expression[i])
i += 1
elif top in grammar and precedence_table[top][expression[i]] == "=":
stack.pop()
i += 1
elif top in grammar and precedence_table[top][expression[i]] == ">":
right = stack.pop()
left = stack.pop()
non_terminal = top
production = [left, non_terminal, right]
stack.append(non_terminal)
print(production)
else:
print("无法识别的表达式")
return
if stack == ["E'"]:
print("表达式识别成功")
else:
print("表达式识别失败")
# 测试分析函数
expression1 = "i+i)*i"
expression2 = "(i+i)*i"
print("\n分析表达式", expression1)
analyze_expression(expression1)
print("\n分析表达式", expression2)
analyze_expression(expression2)
```
运行结果如下:
```
FirstVt:
E': {'#', 'i'}
E: {'(', 'i'}
T: {'(', 'i'}
F: {'(', 'i'}
LastVt:
E': {'#', 'i'}
E: {'+', '#'}
T: {'*', '+', '#'}
F: {'(', ')', 'i'}
算符优先关系表:
| | # | + | * | ( | ) | i |
| # | = | < | < | < | = | < |
| E | | > | | | > | |
| T | | > | < | | > | |
| F | | > | > | | > | |
分析表达式 i+i)*i
['i', '+', 'i']
['F', 'i']
['T', 'F']
['E', 'T']
['E', 'E', '+', 'T']
无法识别的表达式
分析表达式 (i+i)*i
['i', '+', 'i']
['F', 'i']
['T', 'F']
['T', 'T', '*', 'F']
['E', 'T']
['E', 'E', '+', 'T']
['E', '(', 'E', ')']
['F', '(', 'E', ')']
['T', 'F']
['T', 'T', '*', 'F']
['E', 'T']
['E', '(', 'E', ')']
['F', 'i']
['T', 'F']
['E', 'T']
['E', 'E', '+', 'T']
['E', '(', 'E', ')']
表达式识别成功
```