编写一个算符优先分析程序,输入文法我们小组采用文档读入的方式,判断是否为算符文法,同时构造并输出该文法的每个非终结符的 FIRSTVT 集和 LASTVT 集构造并输出算符优先分析表,判断是否为算符优先文法
时间: 2024-02-09 09:11:18 浏览: 76
下面是一个基于Python语言实现的算符优先分析程序,可以根据输入的文法判断是否为算符文法,并构造并输出每个非终结符的FIRSTVT集和LASTVT集,同时构造并输出算符优先分析表,判断是否为算符优先文法。
```python
import re
class Operator:
def __init__(self, symbol, priority, assoc):
self.symbol = symbol
self.priority = priority
self.assoc = assoc
class Grammar:
def __init__(self, productions):
self.productions = productions
self.terminals = set()
self.nonterminals = set()
self.start_symbol = productions[0][0]
for production in productions:
self.nonterminals.add(production[0])
for symbol in production[1]:
if symbol.islower():
self.terminals.add(symbol)
else:
self.nonterminals.add(symbol)
def is_operator_grammar(self):
for production in self.productions:
for i in range(len(production[1]) - 1):
if production[1][i].islower() and production[1][i+1].islower():
return False
return True
def firstvt(self):
firstvt_set = {}
for nt in self.nonterminals:
firstvt_set[nt] = set()
for production in self.productions:
nt = production[0]
rhs = production[1]
if rhs[0].islower():
firstvt_set[nt].add(rhs[0])
else:
for i in range(len(rhs)):
if rhs[i].islower():
firstvt_set[nt].add(rhs[i])
break
else:
firstvt_set[nt] |= firstvt_set[rhs[i]]
if 'ε' not in rhs[i]:
break
return firstvt_set
def lastvt(self):
lastvt_set = {}
for nt in self.nonterminals:
lastvt_set[nt] = set()
for production in self.productions:
nt = production[0]
rhs = production[1]
if rhs[-1].islower():
lastvt_set[nt].add(rhs[-1])
else:
for i in range(len(rhs)-1, -1, -1):
if rhs[i].islower():
lastvt_set[nt].add(rhs[i])
break
else:
lastvt_set[nt] |= lastvt_set[rhs[i]]
if 'ε' not in rhs[i]:
break
return lastvt_set
def operator_table(self):
operators = {'+': Operator('+', 1, 'left'), '-': Operator('-', 1, 'left'),
'*': Operator('*', 2, 'left'), '/': Operator('/', 2, 'left'),
'(': Operator('(', 0, 'left'), ')': Operator(')', 0, 'left'),
'#': Operator('#', -1, 'left')}
table = {}
for nt in self.nonterminals | self.terminals:
table[nt] = {}
for symbol in self.nonterminals | self.terminals:
table[nt][symbol] = None
for production in self.productions:
rhs = production[1]
for i in range(len(rhs) - 1):
if rhs[i].islower() and rhs[i+1].islower():
continue
op1 = operators[rhs[i]] if rhs[i] in operators else None
op2 = operators[rhs[i+1]] if rhs[i+1] in operators else None
if op1 and op2:
if op1.assoc == 'left' and op1.priority >= op2.priority:
table[rhs[i]][rhs[i+1]] = '<'
elif op1.assoc == 'right' and op1.priority > op2.priority:
table[rhs[i]][rhs[i+1]] = '<'
else:
table[rhs[i]][rhs[i+1]] = '>'
for symbol in self.nonterminals | self.terminals:
op = operators[symbol] if symbol in operators else None
if op:
if op.symbol == '(':
table[symbol][')'] = '='
elif op.symbol == ')':
table[symbol]['('] = None
elif op.priority == 1:
table[symbol]['+'] = '>'
table[symbol]['-'] = '>'
table[symbol]['*'] = '<'
table[symbol]['/'] = '<'
elif op.priority == 2:
table[symbol]['+'] = '>'
table[symbol]['-'] = '>'
table[symbol]['*'] = '>'
table[symbol]['/'] = '>'
elif op.symbol == '#':
table[symbol]['#'] = None
return table
def is_operator_precedence_grammar(self):
for nt in self.nonterminals | self.terminals:
if self.operator_table()[nt][nt] is not None:
return False
return True
def read_grammar(filename):
productions = []
with open(filename, 'r') as f:
for line in f:
line = line.strip()
if line:
match = re.match(r'^(\w+)\s*->\s*(\S*)$', line)
if match:
nt = match.group(1)
rhs = match.group(2)
productions.append((nt, rhs))
return Grammar(productions)
if __name__ == '__main__':
grammar = read_grammar('grammar.txt')
if grammar.is_operator_grammar():
print('输入的文法是算符文法')
print('FIRSTVT集:')
for nt, firstvt_set in grammar.firstvt().items():
print(f'{nt}: {firstvt_set}')
print('LASTVT集:')
for nt, lastvt_set in grammar.lastvt().items():
print(f'{nt}: {lastvt_set}')
table = grammar.operator_table()
print('算符优先分析表:')
for nt in grammar.nonterminals | grammar.terminals:
print('\t', end='')
for symbol in grammar.nonterminals | grammar.terminals:
if table[nt][symbol] is None:
print(f'{nt}{symbol}'.ljust(4), end='')
else:
print(table[nt][symbol].ljust(4), end='')
print()
if grammar.is_operator_precedence_grammar():
print('输入的文法是算符优先文法')
else:
print('输入的文法不是算符优先文法')
else:
print('输入的文法不是算符文法')
```
在这个程序中,首先通过read_grammar函数从文件中读取文法,并创建一个Grammar对象表示该文法。然后,程序判断该文法是否为算符文法,并分别构造并输出每个非终结符的FIRSTVT集和LASTVT集。接着,程序构造算符优先分析表,并输出该表。最后,程序判断该文法是否为算符优先文法。注意,这个程序中的默认结束符是'#',如果您的文法中使用了不同的结束符,需要进行相应的修改。程序假设文法中的产生式都是以箭头'->'进行分隔的,如果您的文法格式不同,需要进行相应的调整。
阅读全文