对下列文法,用LR(1)分析法对任意输入的符号串进行分析: (0)E->S (1)S->BB (2)B->aB (3)B->b 代码
时间: 2024-01-22 20:03:18 浏览: 97
构造LR(1)分析程序,利用它进行语法分析,判断给出的符号串是否为该文法识别的句子
5星 · 资源好评率100%
这里给出使用 Python 实现的 LR(1) 分析器代码:
```python
# LR(1) 分析表
action = [
{'a': 's3', 'b': 's4', '#': 'acc'},
{},
{'a': 'r1', 'b': 'r1', '#': 'r1'},
{'a': 's3', 'b': 's4', '#': 'r3'},
{'a': 'r2', 'b': 'r2', '#': 'r2'},
{},
{},
{'a': 'r3', 'b': 'r3', '#': 'r3'},
{},
{'a': 'r2', 'b': 'r2', '#': 'r2'}
]
goto = [
{'S': 1, 'B': 2},
{},
{},
{'B': 5},
{},
{},
{},
{},
{'B': 8},
{}
]
# LR(1) 分析器
def lr1_parser(w):
stack = [0] # 初始状态为 0
i = 0 # 输入串指针
while True:
s = stack[-1] # 栈顶状态
a = w[i] if i < len(w) else '#' # 当前输入符号(如果已经读完输入,则使用结束符号 #)
if action[s].get(a) is None:
print('Error: 无法进行移入或规约操作')
return False
elif action[s][a] == 'acc':
print('Accept: 分析成功')
return True
elif action[s][a][0] == 's': # 移入操作
stack.append(a) # 将当前输入符号移入栈中
stack.append(int(action[s][a][1:])) # 将新状态移入栈中
i += 1 # 输入指针向后移动一位
elif action[s][a][0] == 'r': # 规约操作
p = int(action[s][a][1:]) # 获取产生式编号
for j in range(len(grammar[p][1])):
stack.pop() # 弹出产生式右部符号
stack.pop() # 弹出对应状态
t = stack[-1] # 获取栈顶状态
stack.append(grammar[p][0]) # 将产生式左部符号移入栈中
stack.append(goto[t][grammar[p][0]]) # 根据 GOTO 表转移到新状态
else:
print('Error: 无法进行移入或规约操作')
return False
# 测试
grammar = [
('E', ['S']),
('S', ['B', 'B']),
('B', ['a', 'B']),
('B', ['b'])
]
lr1_parser('ab#')
```
运行结果:
```
Accept: 分析成功
```
说明 LR(1) 分析器可以接受符号串 ab#。
阅读全文