LR0分析程序的设计与实现代码
时间: 2023-08-13 13:08:31 浏览: 115
以下是一个简单的LR(0)分析程序的设计和实现代码,使用了Python语言:
```python
# LR(0)分析程序
# 定义文法
grammar = {
'S': ['E'],
'E': ['E+T', 'T'],
'T': ['T*F', 'F'],
'F': ['(E)', 'id']
}
# 定义项目
def closure(I):
J = I[:]
while True:
item_added = False
for item in J:
dot_pos = item.index('.')
if dot_pos == len(item) - 1:
continue
next_symbol = item[dot_pos + 1]
if next_symbol in grammar:
for production in grammar[next_symbol]:
new_item = next_symbol + '->.' + production
if new_item not in J:
J.append(new_item)
item_added = True
if not item_added:
break
return J
# 定义goto函数
def goto(I, X):
J = []
for item in I:
dot_pos = item.index('.')
if dot_pos == len(item) - 1:
continue
next_symbol = item[dot_pos + 1]
if next_symbol == X:
new_item = item[:dot_pos+1] + X + '.' + item[dot_pos+2:]
J.append(new_item)
return closure(J)
# 构造LR(0)自动机
states = []
C = closure(['S->.E'])
states.append(C)
queue = [C]
while len(queue) > 0:
C = queue.pop(0)
for symbol in grammar.keys():
s = goto(C, symbol)
if len(s) == 0:
continue
if s not in states:
states.append(s)
queue.append(s)
# 构造LR(0)分析表
action = {}
goto = {}
for i in range(len(states)):
state = states[i]
for item in state:
dot_pos = item.index('.')
if dot_pos == len(item) - 1:
for j in range(len(grammar)):
if list(grammar.keys())[j] == item[0]:
action[(i, '$')] = ('accept', None)
else:
continue
else:
a = item[dot_pos + 1]
if a.islower() or a.isupper():
j = states.index(goto(state, a))
action[(i, a)] = ('shift', j)
elif a == '$':
continue
else:
for j in range(len(grammar)):
if list(grammar.keys())[j] == a:
action[(i, a)] = ('reduce', j)
break
for symbol in grammar.keys():
s = goto(state, symbol)
if len(s) == 0:
continue
j = states.index(s)
goto[(i, symbol)] = j
# 测试
def parse_LR0(string):
stack = [0]
input_str = string + '$'
output = []
while True:
state = stack[-1]
a = input_str[0]
if (state, a) not in action:
print('error')
return None
act, num = action[(state, a)]
if act == 'shift':
stack.append(num)
input_str = input_str[1:]
elif act == 'reduce':
output.append(num)
production = grammar[list(grammar.keys())[num]][0]
for i in range(len(production.split()) * 2):
stack.pop()
state = stack[-1]
stack.append(goto[(state, production.split()[0])])
elif act == 'accept':
output.append(len(grammar) - 1)
return output
```
这段代码实现了一个简单的LR(0)分析程序,包括构造LR(0)自动机和分析表,以及使用分析表进行语法分析的过程。
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)