目二 (1)文法: S->aSb|c|ε (2)分析句子:aabb (3)使用语法分析之递归下降法分析写一个程序,给出结果是否是该文法的句子。
时间: 2024-03-13 20:45:13 浏览: 124
使用递归下降法分析该句子:
1. 对于S->aSb规则,读入第一个字符a,匹配成功,继续读入下一个字符a
2. 对于S->aSb规则,读入第二个字符a,匹配成功,继续读入下一个字符b
3. 对于S->ε规则,读入第三个字符b,不匹配,尝试其他规则
4. 对于S->c规则,读入第三个字符b,不匹配,尝试其他规则
5. 对于S->ε规则,读入第三个字符b,不匹配,尝试其他规则
6. 回溯到第一次使用S->aSb规则的位置,将第二个字符a重新归还到输入流中
7. 对于S->ε规则,读入第二个字符a,不匹配,尝试其他规则
8. 对于S->c规则,读入第二个字符a,不匹配,尝试其他规则
9. 对于S->aSb规则,读入第二个字符a,匹配成功,继续读入下一个字符b
10. 对于S->ε规则,读入第三个字符b,不匹配,尝试其他规则
11. 对于S->c规则,读入第三个字符b,不匹配,尝试其他规则
12. 对于S->ε规则,读入第三个字符b,匹配成功,此时已经匹配完整个句子
因此,该句子aabb是该文法的句子。下面是使用Python编写的递归下降分析程序:
```python
def S():
global i
if i < len(s) and s[i] == 'a':
i += 1
S()
if i < len(s) and s[i] == 'b':
i += 1
else:
error()
elif i < len(s) and s[i] == 'c':
i += 1
else:
pass
def error():
print("该句子不是该文法的句子!")
exit()
s = 'aabb'
i = 0
S()
if i == len(s):
print("该句子是该文法的句子!")
else:
error()
```
注意,在递归下降分析程序中,我们需要使用一个全局变量i来记录当前读取的位置。在S函数中,我们按照规则依次匹配字符,如果匹配成功,继续递归调用S函数;如果匹配失败,则回溯到上一层递归调用的位置,尝试其他规则。如果最终i指向了句子末尾,则说明该句子是该文法的句子;否则说明该句子不是该文法的句子,报错并退出程序。
阅读全文