前提:给定预测分析表,见教材 P76 表 4.1(对应文法为文法 4.2) 要求:构造出相关预测分析程序,并返回一个符号串的分析结果,如果是一个合法的符号串输出正确标志并返回 True,否则输出错误标志并返回 False。 参考:教材 P76-78 4.5 预测分析程序。
时间: 2023-12-10 14:38:25 浏览: 36
预测分析程序是一种自顶向下的语法分析方法,它可以根据给定的文法和预测分析表来判断一个符号串是否为该文法的句子,并给出该句子的分析过程。
以下是该文法对应的预测分析表:
| | id | + | * | ( | ) | $ |
|---|---|---|---|---|---|---|
| E | E->TX | | | E->TX | | |
| X | | E->+TX | | | E->ε | E->ε |
| T | T->FY | | | T->FY | | |
| Y | | E->ε | T->*FY | | E->ε | E->ε |
| F | F->id | | | F->(E) | | |
其中,每个非终结符号对应一行,每个终结符号对应一列,表格中的每个格子里都填写了相应的产生式。例如,第一行第一列的格子填写了 E->TX,表示当遇到输入符号串中的 id 时,应该使用该产生式进行推导。
根据上述预测分析表,我们可以编写对应的预测分析程序,具体步骤如下:
1. 定义一个栈 stack 和一个输入符号串 input。
2. 将 $ 和文法的起始符号 E 入栈。
3. 从输入符号串中读入一个符号 a,如果 a 不是 $,则重复步骤 4 到 6,否则进入步骤 7。
4. 弹出栈顶的符号 X。
5. 如果 X 是一个终结符号,则比较 X 和 a 是否相等,如果相等则从输入符号串中读入下一个符号 a,否则表示输入错误,返回 False。
6. 如果 X 是一个非终结符号,则查找预测分析表中对应的产生式 A->β,将 β 的倒序依次压入栈中。
7. 如果栈顶符号为 $,且输入符号串中也只剩下 $,则表示分析成功,返回 True,否则表示输入错误,返回 False。
根据上述算法,我们可以编写出以下 Python 代码实现该预测分析程序:
```python
def analyze(input_str):
stack = ['$','E']
input_str += '$'
i = 0
while len(stack) > 0:
X = stack.pop()
a = input_str[i]
if X == a:
i += 1
elif X in ['id','+','*','(',')']:
return False
else:
rule = P[X][a]
if rule != None:
for symbol in reversed(rule):
if symbol != 'ε':
stack.append(symbol)
else:
return False
return True
P = {
'E': {'id':['T','X'],'+':None,'*':None,'(':['T','X'],')':None,'$':None},
'X': {'id':None,'+':['+','T','X'],'*':None,'(':None,')':['ε'],'$':['ε']},
'T': {'id':['F','Y'],'+':None,'*':None,'(':['F','Y'],')':None,'$':None},
'Y': {'id':['ε'],'+':['ε'],'*':['*','F','Y'],'(':None,')':['ε'],'$':['ε']},
'F': {'id':['id'],'+':None,'*':None,'(':['(','E',')'],')':None,'$':None}
}
input_str = 'id*id+id$'
print(analyze(input_str)) # True
```
其中,预测分析表 P 以字典形式表示,每个非终结符号对应一个子字典,子字典中每个终结符号都对应一个产生式。例如,P['E']['id'] 表示 E 非终结符号在遇到输入符号串中的 id 时应该采用的产生式。如果遇到输入符号与预测分析表中的格子为空,则说明输入错误,返回 False。