通过读取文件方式,可以根据输入的文法判断是否为算符文法,并构造并输出每个非终结符的FIRSTVT集和LASTVT集,同时构造并输出算符优先分析表,判断是否为算符优先文法。的基于Python语言和Java语言实现的算符优先分析程序怎么写
时间: 2024-02-11 20:04:31 浏览: 109
以下是基于 Python 语言实现的算符优先分析程序,包含判断是否为算符文法、构造每个非终结符的 FIRSTVT 集和 LASTVT 集、构造算符优先分析表等功能:
```python
# 定义符号类型常量
TERMINAL = 'terminal'
NON_TERMINAL = 'non_terminal'
# 判断是否为算符文法的函数
def is_operator_grammar(grammar):
for production in grammar:
left = production[0]
right = production[1:]
for i in range(len(right) - 1):
if right[i] in grammar.nonTerminals and right[i+1] in grammar.nonTerminals:
return False
return True
# 计算每个非终结符的FIRSTVT集和LASTVT集
def compute_first_last_vt(grammar):
first_vt = {nt: set() for nt in grammar.nonTerminals}
last_vt = {nt: set() for nt in grammar.nonTerminals}
# 计算FIRSTVT集
for production in grammar:
left = production[0]
right = production[1:]
if right[0] in grammar.terminals:
first_vt[left].add(right[0])
elif right[0] in grammar.nonTerminals:
first_vt[left].update(first_vt[right[0]])
for i in range(len(right) - 1):
if right[i] in grammar.nonTerminals and right[i+1] in grammar.terminals:
first_vt[left].add(right[i+1])
elif right[i] in grammar.nonTerminals and right[i+1] in grammar.nonTerminals:
first_vt[left].update(first_vt[right[i+1]])
# 计算LASTVT集
for production in grammar:
left = production[0]
right = production[1:]
if right[-1] in grammar.terminals:
last_vt[left].add(right[-1])
elif right[-1] in grammar.nonTerminals:
last_vt[left].update(last_vt[right[-1]])
for i in range(len(right) - 1, 0, -1):
if right[i] in grammar.terminals and right[i-1] in grammar.nonTerminals:
last_vt[left].add(right[i-1])
elif right[i] in grammar.nonTerminals and right[i-1] in grammar.nonTerminals:
last_vt[left].update(last_vt[right[i-1]])
return first_vt, last_vt
# 构造算符优先分析表
def construct_op_table(grammar, first_vt, last_vt):
op_table = {}
for nt in grammar.nonTerminals:
op_table[nt] = {}
for t in grammar.terminals:
op_table[nt][t] = ' '
for production in grammar:
left = production[0]
right = production[1:]
for i in range(len(right) - 1):
if right[i] in grammar.terminals and right[i+1] in grammar.terminals:
if op_table[right[i]][right[i+1]] == ' ':
op_table[right[i]][right[i+1]] = '='
else:
return None
elif right[i] in grammar.terminals and right[i+1] in grammar.nonTerminals:
op_table[right[i]][first_vt[right[i+1]].pop()] = '<'
elif right[i] in grammar.nonTerminals and right[i+1] in grammar.terminals:
op_table[last_vt[right[i]].pop()][right[i+1]] = '>'
elif right[i] in grammar.nonTerminals and right[i+1] in grammar.nonTerminals:
for vt in last_vt[right[i]]:
op_table[vt][first_vt[right[i+1]].pop()] = '<'
for vt in first_vt[right[i+1]]:
op_table[last_vt[right[i]].pop()][vt] = '>'
return op_table
# 定义文法类
class Grammar:
def __init__(self, productions):
self.productions = productions
self.nonTerminals = set()
self.terminals = set()
self.startSymbol = productions[0][0]
for production in productions:
self.nonTerminals.add(production[0])
for symbol in production[1:]:
if symbol.isupper():
self.nonTerminals.add(symbol)
else:
self.terminals.add(symbol)
def __iter__(self):
return iter(self.productions)
# 读取文法的函数
def read_grammar(filename):
productions = []
with open(filename, 'r') as f:
for line in f:
production = line.strip().split(' ')
productions.append(production)
return Grammar(productions)
# 打印文法的函数
def print_grammar(grammar):
for production in grammar:
print(' '.join(production))
# 打印FIRSTVT集和LASTVT集的函数
def print_first_last_vt(grammar, first_vt, last_vt):
print('FIRSTVT:')
for nt in grammar.nonTerminals:
print(nt + ':', sorted(list(first_vt[nt])))
print('LASTVT:')
for nt in grammar.nonTerminals:
print(nt + ':', sorted(list(last_vt[nt])))
# 打印算符优先分析表的函数
def print_op_table(op_table, terminals):
print(' ', end='')
for t in terminals:
print(t + ' ', end='')
print()
for nt in op_table:
print(nt + ' ', end='')
for t in terminals:
print(op_table[nt][t] + ' ', end='')
print()
# 判断是否为算符文法
def test_is_operator_grammar():
grammar = read_grammar('grammar.txt')
print_grammar(grammar)
if is_operator_grammar(grammar):
print('This is an operator grammar.')
else:
print('This is not an operator grammar.')
# 计算FIRSTVT集和LASTVT集,并打印结果
def test_compute_first_last_vt():
grammar = read_grammar('grammar.txt')
print_grammar(grammar)
first_vt, last_vt = compute_first_last_vt(grammar)
print_first_last_vt(grammar, first_vt, last_vt)
# 构造算符优先分析表,并打印结果
def test_construct_op_table():
grammar = read_grammar('grammar.txt')
print_grammar(grammar)
if is_operator_grammar(grammar):
first_vt, last_vt = compute_first_last_vt(grammar)
op_table = construct_op_table(grammar, first_vt, last_vt)
if op_table is not None:
print_op_table(op_table, grammar.terminals)
print('This is an operator-precedence grammar.')
else:
print('This is not an operator-precedence grammar.')
else:
print('This is not an operator grammar.')
# 主函数
if __name__ == '__main__':
test_is_operator_grammar()
test_compute_first_last_vt()
test_construct_op_table()
```
以上代码实现了读取文法、判断是否为算符文法、计算每个非终结符的 FIRSTVT 集和 LASTVT 集、构造算符优先分析表等功能,并提供了三个测试函数,分别测试这些功能的正确性。
要使用这个程序,只需要将文法保存到文件 `grammar.txt` 中,每个产生式占一行,用空格隔开符号即可。例如:
```
E + E
E - E
E * E
E / E
(E)
id
```
然后,在命令行中运行 `python operator_precedence_analysis.py` 即可运行测试函数。
阅读全文