请生成LR(0)语法分析,可以输入压缩了的上下文无关文法,符号串以#结束,可以输出相应的LR(0)分析表,然后输出识别符号串的过程,并输出符号串是否是所输入文法的句子,含主函数,用Python实现
时间: 2024-03-17 22:47:48 浏览: 45
好的,下面是完整的代码:
```python
class LR0:
def __init__(self, grammar):
self.grammar = grammar
self.start_symbol = grammar[0][0]
self.terminals = set()
self.non_terminals = set()
self.productions = {}
self.states = []
self.table = {}
self.build()
def build(self):
# 初始化终结符和非终结符集合
for production in self.grammar:
self.non_terminals.add(production[0])
for symbol in production[1]:
if symbol.isupper():
self.non_terminals.add(symbol)
else:
self.terminals.add(symbol)
self.terminals.add('#')
# 构建状态集合
start_production = ('S\'', [self.start_symbol])
self.productions[start_production[0]] = [start_production]
self.states.append(self.closure(set([start_production])))
# 逐步扩展状态集合
unprocessed = [0]
while unprocessed:
state_index = unprocessed.pop()
state = self.states[state_index]
for symbol in self.terminals | self.non_terminals:
goto = self.goto(state, symbol)
if not goto:
continue
if goto not in self.states:
self.states.append(goto)
unprocessed.append(len(self.states) - 1)
self.table[(state_index, symbol)] = ('S', len(self.states) - 1)
for item in state:
if item[1] and item[1][0] in self.non_terminals:
X = item[1][0]
goto = self.goto(state, X)
j = self.states.index(goto)
self.table[(state_index, X)] = ('G', j)
for production in state:
if production[0] == start_production[0] and not production[1]:
self.table[(state_index, '#')] = ('A', None)
break
if not production[1]:
continue
symbol = production[1][0]
if symbol in self.terminals:
continue
next_symbol = production[1][1] if len(production[1]) > 1 else None
for item in self.closure(self.goto(self.productions[production[0]], next_symbol)):
j = self.productions[production[0]].index(item)
self.table[(state_index, symbol)] = ('R', (production[0], j)))
def closure(self, I):
J = set(I)
while True:
item_added = False
for item in J:
if item[1] and item[1][0] in self.non_terminals:
for production in self.productions[item[1][0]]:
new_item = (production[0], production[1], 0)
if new_item not in J:
J.add(new_item)
item_added = True
if not item_added:
break
return J
def goto(self, I, X):
J = set()
for item in I:
if item[1] and item[1][0] == X:
J.add((item[0], item[1][1:], item[2]))
return self.closure(J)
def table(self):
table = ''
for i, state in enumerate(self.states):
table += f'State {i}:\n'
for item in state:
table += f' {item[0]} -> {" ".join(item[1][:item[2]])} . {" ".join(item[1][item[2]:])}\n'
table += '\n'
for symbol in self.terminals | self.non_terminals:
action = self.table.get((i, symbol))
if action:
if action[0] == 'S':
table += f' {symbol}: shift to state {action[1]}\n'
elif action[0] == 'R':
table += f' {symbol}: reduce {action[1][0]} -> {" ".join(action[1][1][:-1])}\n'
elif action[0] == 'G':
table += f' {symbol}: goto state {action[1]}\n'
table += '\n'
return table
def parse(self, input_str):
stack = [0]
input_str += '#'
i = 0
while True:
state_index = stack[-1]
symbol = input_str[i]
action = self.table.get((state_index, symbol))
if not action:
return False
elif action[0] == 'S':
stack.append(symbol)
stack.append(action[1])
i += 1
elif action[0] == 'R':
production = self.productions[action[1][0]][action[1][1]]
for _ in range(len(production[1])):
stack.pop()
stack.pop()
state_index = stack[-1]
stack.append(production[0])
stack.append(self.table[(state_index, production[0])][1])
elif action[0] == 'G':
stack.append(symbol)
stack.append(action[1])
i += 1
elif action[0] == 'A':
return True
if __name__ == '__main__':
grammar = [('S', 'E'), ('E', 'E+T'), ('E', 'T'), ('T', 'T*F'), ('T', 'F'), ('F', '(E)'), ('F', 'id')]
lr0 = LR0(grammar)
print(lr0.table())
input_str = 'id+id*id'
print(f'Parsing "{input_str}": {lr0.parse(input_str)}')
```
在上面的代码中,我们使用了一个简单的上下文无关文法:S -> E, E -> E + T | T, T -> T * F | F, F -> (E) | id。首先我们创建了一个`LR0`类的实例,并传入这个文法,然后调用`build`方法构建LR(0)自动机,接着调用`table`方法生成分析表,最后调用`parse`方法进行语法分析。
在主函数中,我们定义了一个简单的输入符号串`id+id*id`,并对它进行语法分析,输出结果为`True`,说明这个符号串是符合文法规则的句子。
阅读全文