实验三 算符优先分析算法的设计与实现

《实验三 算符优先分析算法的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验三算符优先分析算法的设计与实现（8学时）一、实验目的根据算符优先分析法，对表达式进行语法分析，使其能够判断一个表达式是否正确。通过算符优先分析方法的实现，加深对自下而上语法分析方法的理解。二、实验要求1、输入文法。可以是如下算术表达式的文法（你可以根据需要适当改变）：E→E+T

2、E-T

3、TT→T*F

4、T/F

5、FF→（E）

6、i2、对给定表达式进行分析，输出表达式正确与否的判断。程序输入/输出示例：输入：1+2;输出：正确输入：(1+2)/3+4-(5+6/7);输出：正确输入：((1-2)/3+4输出：错误

7、输入：1+2-3+(*4/5)输出：错误三、实验步骤1、参考数据结构char*VN=0,*VT=0;//非终结符和终结符数组charfirstvt[N][N],lastvt[N][N],table[N][N];typedefstruct//符号对(P,a){charVn;charVt;}VN_VT;typedefstruct//栈{VN_VT*top;VN_VT*bollow;intsize;}stack;2、根据文法求FIRSTVT集和LASTVT集给定一个上下文无关文法，根据算法设计一个程序，求文法中每个

8、非终结符的FirstVT集和LastVT集。算符描述如下：/*求FirstVT集的算法*/PROCEDUREinsert(P,a);IFnotF[P,a]thenbeginF[P,a]=true;//(P,a)进栈end;ProcedureFirstVT;Beginfor对每个非终结符P和终结符adoF[P,a]=falsefor对每个形如Pa…或P→Qa…的产生式doInsert(P,a)whilestack非空begin栈顶项出栈，记为(Q,a)for对每条形如P→Q…的产生式doinsert(P,a)e

9、nd;end.同理，可构造计算LASTVT的算法。3、构造算符优先分析表依据文法和求出的相应FirstVT和LastVT集生成算符优先分析表。算法描述如下：for每个形如P->X1X2…Xn的产生式dofori=1ton-1dobeginifXi和Xi+1都是终结符thenXi=Xi+1ifi<=n-2,Xi和Xi+2是终结符,但Xi+1为非终结符thenXi=Xi+2ifXi为终结符,Xi+1为非终结符thenforFirstVT中的每个元素adoXi

10、LastVT中的每个元素adoa>Xi+1;end4、构造总控程序算法描述如下：stackS;k=1;//符号栈S的使用深度S[k]=‘#’REPEAT把下一个输入符号读进a中；IfS[k]VTthenj=kelsej=k-1;WhileS[j]>adoBeginRepeatQ=S[j];ifS[j-1]VTthenj=j-1elsej=j-2untilS[j]

11、nbegink=k+1;S[k]=aendelseerror//调用出错诊察程序untila=‘#’5、对给定的表达式，给出准确与否的分析过程6、给出表达式的计算结果。（本步骤可选作）四、实验报告要求1.写出编程思路、源代码（或流程图）；2.写出上机调试时发现的问题，以及解决的过程；3.写出你所使用的测试数据及结果；4.谈谈你的体会。5.上机8小时，完成实验报告2小时。