使用python实现LR(0)语法分析
时间: 2023-12-10 07:05:45 浏览: 31
下面是使用Python实现LR(0)语法分析的示例代码:
```python
# LR(0)语法分析
# 使用字典存储文法,key为非终结符,value为产生式列表
grammar = {
'S': ['E'],
'E': ['E+T', 'T'],
'T': ['T*F', 'F'],
'F': ['(E)', 'i']
}
# 计算FIRST集
first = {}
for non_terminal in grammar.keys():
first[non_terminal] = set()
for non_terminal in grammar.keys():
for production in grammar[non_terminal]:
if production[0].isupper():
first[non_terminal].update(first[production[0]])
else:
first[non_terminal].add(production[0])
i = 1
while i < len(production) and '' in first[production[i - 1]]:
if production[i].isupper():
first[non_terminal].update(first[production[i]])
else:
first[non_terminal].add(production[i])
i += 1
# 计算项集闭包
def closure(I):
J = set(I)
while True:
item_count = len(J)
for item in list(J):
dot_idx = item.index('.')
if dot_idx == len(item) - 1:
continue
next_symbol = item[dot_idx + 1]
if next_symbol.isupper():
for production in grammar[next_symbol]:
new_item = next_symbol + '->.' + production
if new_item not in J:
J.add(new_item)
item_first = set()
if next_symbol in first:
item_first.update(first[next_symbol])
if '' in item_first:
item_first.remove('')
item_first.update(item[d] for d in J if d.endswith(next_symbol + '->.'))
for a in item_first:
new_item = item[:dot_idx + 1] + a + '.' + item[dot_idx + 2:]
if new_item not in J:
J.add(new_item)
if len(J) == item_count:
break
return frozenset(J)
# 计算项集族
C = []
C.append(closure({'S->.E'}))
for I in C:
for X in set(item[item.index('.') + 1] for item in I if item.index('.') < len(item) - 1):
goto_I = set()
for item in I:
if item.index('.') == len(item) - 1:
continue
if item[item.index('.') + 1] == X:
goto_I.add(item[:item.index('.')] + X + '.' + item[item.index('.') + 2:])
if len(goto_I) == 0:
continue
J = closure(goto_I)
if J not in C:
C.append(J)
# 构造LR(0)分析表
action = {}
goto = {}
for i, I in enumerate(C):
for item in I:
if item.index('.') == len(item) - 1:
if item.startswith('S->E.'):
action[i, '$'] = 'acc'
else:
for a in follow[item[0]]:
action[i, a] = 'reduce ' + item[0] + '->' + item[:item.index('.')]
else:
j = C.index(closure({item[:item.index('.')] + item[item.index('.') + 1] + '.' + item[item.index('.') + 2:]}))
if item[item.index('.') + 1].islower():
action[i, item[item.index('.') + 1]] = 'shift ' + str(j)
else:
goto[i, item[item.index('.') + 1]] = j
# LR(0)语法分析
stack = [0]
input_str = input('请输入要分析的句子:') + '$'
idx = 0
while True:
state = stack[-1]
if input_str[idx] in action and state in action[input_str[idx]]:
op, val = action[input_str[idx]][state].split(' ')
if op == 'shift':
stack.append(int(val))
stack.append(input_str[idx])
idx += 1
elif op == 'reduce':
production = val.split('->')
for i in range(len(production[1])):
stack.pop()
stack.pop()
state = stack[-1]
stack.append(int(goto[state, production[0]]))
stack.append(production[0])
elif op == 'acc':
print('句子符合语法规则')
break
else:
print('句子不符合语法规则')
break
```
调用示例:
```
请输入要分析的句子:i+i*i
句子符合语法规则
```