前提:给定预测分析表,见教材 P76 表 4.1(对应文法为文法 4.2) 要求:构造出相关预测分析程序,并返回一个符号串的分析结果,如果是一个合法的符号串输出正确标志并返回 True,否则输出错误标志并返回 False。 参考:教材 P76-78 4.5 预测分析程序。
时间: 2023-12-10 10:38:23 浏览: 54
首先需要对预测分析表进行解释,其中:
- 非终结符号用大写字母表示,终结符号用小写字母表示。
- $M[A,a]$ 表示在处理非终结符号 $A$ 时,遇到终结符号 $a$ 时应该采用哪个产生式进行推导。
- 如果 $M[A,a]$ 为 $\varnothing$,则说明在处理非终结符号 $A$ 时,不能遇到终结符号 $a$。
接下来,可以按照教材中 4.5 节的方法编写预测分析程序:
```python
def predict_analysis(string):
# 初始化分析栈和输入缓冲区
stack = ['$']
input_str = string + '$'
# 初始化指向输入缓冲区的指针和分析栈顶指针
i = 0
top = 0
# 开始分析
while stack[top] != '$':
# 如果分析栈顶是终结符号,则必须匹配输入缓冲区中的符号
if stack[top].islower():
if stack[top] == input_str[i]:
top -= 1
i += 1
else:
print('Error: 不匹配的终结符号')
return False
# 如果分析栈顶是非终结符号,则查找预测分析表并推导产生式
elif stack[top].isupper():
prod = M[stack[top]][input_str[i]]
if prod:
top -= 1
# 将产生式右部的符号逆序入栈
for symbol in reversed(prod):
stack.append(symbol)
else:
print('Error: 预测分析表中无法找到产生式')
return False
# 如果分析栈顶不是终结符号也不是非终结符号,则说明出现了错误
else:
print('Error: 分析栈顶出现了非法符号')
return False
# 分析完成,如果输入缓冲区也为空,则说明符号串合法
if input_str[i] == '$':
print('Success: 符号串合法')
return True
else:
print('Error: 输入缓冲区还有剩余符号')
return False
```
其中,预测分析表可以按照以下方式定义:
```python
# 预测分析表
M = {
'E': {'i': ['T', 'E\''], '+': None, '*': None, '(': ['T', 'E\'']},
'E\'': {'i': None, '+': ['+', 'T', 'E\''], '*': None, '(': None, ')': [], '$': []},
'T': {'i': ['F', 'T\''], '+': None, '*': None, '(': ['F', 'T\'']},
'T\'': {'i': None, '+': [], '*': ['*', 'F', 'T\''], '(': None, ')': [], '$': []},
'F': {'i': ['i'], '+': None, '*': None, '(': ['(', 'E', ')']}
}
```
例如,对于符号串 `i+i*i$`,调用 `predict_analysis('i+i*i')` 将返回 True,而对于符号串 `i+i**i$`,调用 `predict_analysis('i+i**i')` 将返回 False。