编译原理：算术表达式预测分析程序设计.doc

《编译原理：算术表达式预测分析程序设计.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验三：算术表达式预测分析程序设计LD1、实验目的：（1）掌握自上而下语法分析的要求与特点。（2）掌握LL(1)语法分析的基本原理和基本方法。（3）掌握相应数据结构的设计方法。2、实验内容：编程实现给定算术表达式的预测分析器。算术表达式文法如下：EàE+T

2、TTàT*F

3、FFà(E)

4、i3、设计说明：首先改写文法为LL(1)文法；构造LL(1)分析表，然后编写预测分析程序。4、设计分析与步骤（1）将原算术表达式方法改写为LL(1)文法为：E-->TE'E'-->+TE'

5、εT-->FT'T'-->*FT'

6、εF-->(E)

7、i（2）计算文法中每一个非终结符的FIRST

8、集和FOLLOW集FIRSTFOLLOWE{(,i}{#,)}E’{+,ε}{),#}T{(,i}{),+,#}T’{*,ε}{),+,#}F{(,i}{*}（3）构造预测分析表I()+*#EE--＞TE’E--＞TE’E’E’--＞εE’--＞+TE’E’--＞εTT--＞FT’T--＞FT’T’T’--＞εT’--＞εT’--＞*FT’T’--＞εFF--＞iF--＞(E)（4）程序设计用vector定义的A和B分别作为分析栈和输入栈，用string类型的INPUT获取用户输入的原始字符串。用string类型的二维数组存储预测分析表。1，#和E进分析栈

9、A，#和倒序用户输入串压入用户栈B2，判断A和B栈顶不同时为#，如果是则下一步，如果不是则跳出判断3，根据A和B栈顶元素查分析表查找规则(1)如果查到一般规则，则进行相应的A的弹栈与压栈并比较两栈顶元素，如果相等则都弹栈(2)如果查到含空串的规则，则A弹栈并比较两栈顶元素，如果相等则都弹栈(3)如果查表越界则显示错误4，重复3直到两栈顶都是#元素显示分析成功5，提示用户输入0继续分析下一条，其它输入退出程序。(5)程序代码#include#include#includeusingnamespacestd;intmai

10、n(){stringform[5][6]={{"TA","TA","","","",""},//预测分析表{"","","e","+TA","","e"},//列:E,A(代表E'),T,B(代表T'),F{"FB","FB","","","",""},//行:i,(,),+,*,#{"","","e","e","*FB","e"},//e代表空串{"i","(E)","","","",""}};vectorA;//分析栈vectorB;//输入栈vectorEMT;//空栈用于制空stringINPUT;//输入串charN;do

11、{A=EMT;//S代表分析栈,每次执行用空的EMT初始化A.push_back('#');A.push_back('E');INPUT="";//INPUT每次执行，制空输入串cout<<"输入要分析的字符串:";cin>>INPUT;INPUT.resize(INPUT.size()+1);INPUT[INPUT.size()-1]='#';B=EMT;//INPUT是将INPUT+#倒序压入的用户输入栈for(intx=INPUT.size()-1;x>=0;--x)B.push_back(INPUT[x]);stringYY="EATBF";stringXX=

12、"i()+*#";while(!(A[A.size()-1]=='#'&&B[B.size()-1]=='#')){inti=0,j=0;//查表，查找相应的规则for(i=0;i<5;++i)if(YY[i]==A[A.size()-1])break;for(j=0;j<6;++j)if(XX[j]==B[B.size()-1])break;if(i>=5

13、

14、j>=6)//如果查找超出表{cout<<"error!"<

15、else{//分析栈里的压栈与出栈A.pop_back();for(intk=form[i][j].size()-1;k>=0;--k)A.push_back(form[i][j][k]);if(A[A.size()-1]==B[B.size()-1])//一般规则{A.pop_back();B.pop_back();}elseif(A[A.size()-1]=='e')//含空串的规则{A.pop_back();if(A[A.size()-1]!='#'&&B[B.size()-1]!='#'&&A[A.size()-1]==B[B.size()-