实验三：算术表达式预测分析程序设计
LD
1、实验目的：
（1）掌握自上而下语法分析的要求与特点。
（2）掌握LL(1)语法分析的基本原理和基本方法。 （3）掌握相应数据结构的设计方法。
2、实验内容：
编程实现给定算术表达式的预测分析器。 算术表达式文法如下： E →E+T | T T →T*F | F F →(E) | i
3、设计说明：
首先改写文法为LL(1)文法；构造LL(1)分析表，然后编写预测分析程序。
4、设计分析与步骤
（1）将原算术表达式方法改写为LL(1)文法为： E-->TE' E'-->+TE'|ε T-->FT' T'-->*FT'|ε F-->(E)|i
（2）计算文法中每一个非终结符的FIRST 集和FOLLOW 集
FIRST FOLLOW
E E’ T T’ F
（3）构造预测分析表
{ (,i } { +,ε } { (,i } { *,ε } { (,i }
{ #,) } { ),# } { ),+,# } { ),+,# } { * }
I ( )
+
*
#
E E--＞TE’
E--＞TE’
E’ E’--＞ε E’--＞+TE’
E’--＞ε
T T--＞FT’
T--＞FT’
T’ T’--＞ε
T’--＞ε
T’--＞*FT’
T’--＞ε
F F--＞i F--＞(E)
（4）程序设计
用vector定义的A 和B 分别作为分析栈和输入栈，用string 类型的INPUT 获取用户输入的原始字符串。用string 类型的二维数组存储预测分析表。 1，#和E 进分析栈A ，#和倒序用户输入串压入用户栈B
2，判断A 和B 栈顶不同时为#，如果是则下一步，如果不是则跳出判断 3，根据A 和B 栈顶元素查分析表查找规则
(1)如果查到一般规则，则进行相应的A 的弹栈与压栈并比较两栈顶元素，如果相等则都弹栈
(2)如果查到含空串的规则，则A 弹栈并比较两栈顶元素，如果相等则都弹栈 (3)如果查表越界则显示错误
4，重复3直到两栈顶都是#元素显示分析成功
5，提示用户输入0继续分析下一条，其它输入退出程序。
(5)程序代码
#include
#include #include using namespace std; int main() {
string form[5][6]={
{"TA","TA","","","",""}, //预测分析表
{"","","e","+TA","","e"}, //列:E,A(代表 E'),T,B(代表 T'),F {"FB","FB","","","",""}, //行:i,(,),+,*,# {"","","e","e","*FB","e"}, //e代表空串 {"i","(E)","","","",""} };
vector A;//分析栈 vector B;//输入栈
vector EMT; //空栈用于制空 string INPUT;//输入串 char N; do{
A=EMT; //S代表分析栈, 每次执行用空的EMT 初始化 A.push_back('#'); A.push_back('E');
INPUT=""; //INPUT 每次执行，制空输入串 cout>INPUT;
INPUT.resize(INPUT.size()+1); INPUT[INPUT.size()-1]='#';
B=EMT; //INPUT是将INPUT+#倒序压入的用户输入栈 for(int x=INPUT.size()-1;x>=0;--x) B.push_back(INPUT[x]); string YY="EATBF"; string XX="i()+*#";
while(!(A[A.size()-1]=='#'&&B[B.size()-1]=='#')) {
int i=0,j=0;//查表，查找相应的规则 for(i=0;i
if(YY[i]==A[A.size()-1]) break;
for(j=0;j
if(XX[j]==B[B.size()-1]) break;
if(i>=5||j>=6) //如果查找超出表 {
cout
}
else if(form[i][j]=="") //如果查到的为空规则 {
cout
{ //分析栈里的压栈与出栈 A.pop_back();
for(int k=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(); }
else if(A[A.size()-1]=='e') //含空串的规则 {
A.pop_back();
if(A[A.size()-1]!='#'&&B[B.size()-1]!='#'&&A[A.size()-1]==B[B.size()-1]) {
A.pop_back(); B.pop_back(); } } } }
if(A[A.size()-1]=='#'&&B[B.size()-1]=='#') cout>N&&N=='y');
return 0; }
（6）测试用例
1、输入i ，预期显示success!
2、输入iii ，预期显示error! 3、输入a ，预期显示error! 4、输入(i)，预期显示success! 5、输入(a)，预期显示error! 6、输入(i+i)，预期显示success! 7、输入(i+i，预期显示error!
8、输入((i*i)+i)*i，预期显示success! 9、输入((((i+i*i))))，预期显示success! 10、输入(i+ia，预期显示error!
11、输入i+i*i+i*a，预期显示error!
测试结果如下图：
图1-1测试结果
（7）实验总结
通过本次试验，掌握了自上而下语法分析的要求与特点。掌握LL(1)语法分析的基本原
理和基本方法。掌握相应数据结构的设计方法。首先将实验题目的文法改为LL （1）文法，然后再构造LL （1）分析表，根据分析表构造文法分析的规则。在本次实验中，我将上课的理论知识用于实践操作中，提升了我对理论知识的理解，加强了我的动手编程能力，其中，此次实验用到的栈的相关知识，让我回顾了以前数据结构所学的知识，并用于实验中，发现我对所学过的并不能熟练的运用，在以后的编程我应该多运用所学过的知识，不断的巩固以前的知识。
实验三：算术表达式预测分析程序设计
LD
1、实验目的：
（1）掌握自上而下语法分析的要求与特点。
（2）掌握LL(1)语法分析的基本原理和基本方法。 （3）掌握相应数据结构的设计方法。
2、实验内容：
编程实现给定算术表达式的预测分析器。 算术表达式文法如下： E →E+T | T T →T*F | F F →(E) | i
3、设计说明：
首先改写文法为LL(1)文法；构造LL(1)分析表，然后编写预测分析程序。
4、设计分析与步骤
（1）将原算术表达式方法改写为LL(1)文法为： E-->TE' E'-->+TE'|ε T-->FT' T'-->*FT'|ε F-->(E)|i
（2）计算文法中每一个非终结符的FIRST 集和FOLLOW 集
FIRST FOLLOW
E E’ T T’ F
（3）构造预测分析表
{ (,i } { +,ε } { (,i } { *,ε } { (,i }
{ #,) } { ),# } { ),+,# } { ),+,# } { * }
I ( )
+
*
#
E E--＞TE’
E--＞TE’
E’ E’--＞ε E’--＞+TE’
E’--＞ε
T T--＞FT’
T--＞FT’
T’ T’--＞ε
T’--＞ε
T’--＞*FT’
T’--＞ε
F F--＞i F--＞(E)
（4）程序设计
用vector定义的A 和B 分别作为分析栈和输入栈，用string 类型的INPUT 获取用户输入的原始字符串。用string 类型的二维数组存储预测分析表。 1，#和E 进分析栈A ，#和倒序用户输入串压入用户栈B
2，判断A 和B 栈顶不同时为#，如果是则下一步，如果不是则跳出判断 3，根据A 和B 栈顶元素查分析表查找规则
(1)如果查到一般规则，则进行相应的A 的弹栈与压栈并比较两栈顶元素，如果相等则都弹栈
(2)如果查到含空串的规则，则A 弹栈并比较两栈顶元素，如果相等则都弹栈 (3)如果查表越界则显示错误
4，重复3直到两栈顶都是#元素显示分析成功
5，提示用户输入0继续分析下一条，其它输入退出程序。
(5)程序代码
#include
#include #include using namespace std; int main() {
string form[5][6]={
{"TA","TA","","","",""}, //预测分析表
{"","","e","+TA","","e"}, //列:E,A(代表 E'),T,B(代表 T'),F {"FB","FB","","","",""}, //行:i,(,),+,*,# {"","","e","e","*FB","e"}, //e代表空串 {"i","(E)","","","",""} };
vector A;//分析栈 vector B;//输入栈
vector EMT; //空栈用于制空 string INPUT;//输入串 char N; do{
A=EMT; //S代表分析栈, 每次执行用空的EMT 初始化 A.push_back('#'); A.push_back('E');
INPUT=""; //INPUT 每次执行，制空输入串 cout>INPUT;
INPUT.resize(INPUT.size()+1); INPUT[INPUT.size()-1]='#';
B=EMT; //INPUT是将INPUT+#倒序压入的用户输入栈 for(int x=INPUT.size()-1;x>=0;--x) B.push_back(INPUT[x]); string YY="EATBF"; string XX="i()+*#";
while(!(A[A.size()-1]=='#'&&B[B.size()-1]=='#')) {
int i=0,j=0;//查表，查找相应的规则 for(i=0;i
if(YY[i]==A[A.size()-1]) break;
for(j=0;j
if(XX[j]==B[B.size()-1]) break;
if(i>=5||j>=6) //如果查找超出表 {
cout
}
else if(form[i][j]=="") //如果查到的为空规则 {
cout
{ //分析栈里的压栈与出栈 A.pop_back();
for(int k=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(); }
else if(A[A.size()-1]=='e') //含空串的规则 {
A.pop_back();
if(A[A.size()-1]!='#'&&B[B.size()-1]!='#'&&A[A.size()-1]==B[B.size()-1]) {
A.pop_back(); B.pop_back(); } } } }
if(A[A.size()-1]=='#'&&B[B.size()-1]=='#') cout>N&&N=='y');
return 0; }
（6）测试用例
1、输入i ，预期显示success!
2、输入iii ，预期显示error! 3、输入a ，预期显示error! 4、输入(i)，预期显示success! 5、输入(a)，预期显示error! 6、输入(i+i)，预期显示success! 7、输入(i+i，预期显示error!
8、输入((i*i)+i)*i，预期显示success! 9、输入((((i+i*i))))，预期显示success! 10、输入(i+ia，预期显示error!
11、输入i+i*i+i*a，预期显示error!
测试结果如下图：
图1-1测试结果
（7）实验总结
通过本次试验，掌握了自上而下语法分析的要求与特点。掌握LL(1)语法分析的基本原
理和基本方法。掌握相应数据结构的设计方法。首先将实验题目的文法改为LL （1）文法，然后再构造LL （1）分析表，根据分析表构造文法分析的规则。在本次实验中，我将上课的理论知识用于实践操作中，提升了我对理论知识的理解，加强了我的动手编程能力，其中，此次实验用到的栈的相关知识，让我回顾了以前数据结构所学的知识，并用于实验中，发现我对所学过的并不能熟练的运用，在以后的编程我应该多运用所学过的知识，不断的巩固以前的知识。