编译原理预测分析程序的实现

实验二预测分析 一、实验目的 预测分析表的实现 二、实验内容 设有文法G： E→TE’ E’→+TE’|ε T→FT’ T’→*FT’|ε F→(E)|i; 根据文法编写预测表分析总控程序，分析句子是否为该文法的句型。 当输入字符串： +i时，分析字符串是否为文法的句型 三、实验步骤（详细的实验步骤） (1)文法 E→TE’ E’→+TE’|ε T→FT’ T’→*FT’|ε F→(E)|i; (2)FIRST集 FIRST(E)={(,i}; FIRST(E’)={+,ε}; FIRST(T)={(,i}; FIRST(T’)={*,ε}; FIRST(F)={(,i}; (3)FALLOW集 FOLLOW(E)={),#}; FOLLOW(E’)={),#}; FOLLOW(T)={+,),#}; FOLLOW(T’)={+,),#}; FOLLOW(F)={*,+,),#}; (4)预测分析表   i + * ( ) # E E->TE’     E->TE’     E’   E’->+TE’     E’->ε E’->ε T T->FT’     T->FT’     T’   T’->ε T’->*FT’   T’->ε T’->ε F F->i     F->(E)                   (5)分析过程 步骤 符号栈 输入串 应用句型 0 #E i1*i2+i3#   1 #E’T i1*i2+i3# E->TE’ 2 #E’T’F i1*i2+i3# E->TE’ 3 #E’T’i i1*i2+i3# F->i 4 # E’T’ i1*i2+i3#   5 # E’T’F* *i2+i3# T’->*FT’ 6 # E’T’F *i2+i3#   7 #E’T’i i2+i3# F->i 8 # E’T’ i2+i3#   9 #E’ +i3# T’->ε 10 # E’T+ +i3# E’->+TE’ 11 #E’T +i3#   12 # E’T’F i3# T->FT’ 13 # E’T’i i3# F->i 14 # E’T’ i3#   15 # E’ # T’->ε 16 # # E’->ε         (6)程序伪代码 BEGIN 首先把‘#’然后把文法开始符号推进STACK栈; 把第一个输入符号读进a; FLAG:=TRUE; WHILE FLAG DO BEGIN 把STACK栈顶符号托出去并放在X中; IF X属于VTTHEN IF X=aTHEN把下一输入符号读进a; ELSE ERROR; ELSE IF X=’#’ THEN IF  X=a THEN FLAG:=FALSE ELSE ERROR; ELSE IF M[A,a]={X->X1X2…Xk} THEN 把Xk,X(k-1),…,X1一一推进栈 ELSE ERROR; END OF WHILE STOP END (7)运行结果截图 注：为了将E和E’区分开，所以就有e来表示E’，因为在处理中E’会被当成两个字符来处理，所以就简化的表示了。对于T’是同样的道理，用t来表示。 四、总结 此次的实验是对预测分析表程序的实现，先通过给定文法写出FIRST集FOLLOW集以及预测分析表，根据预测分析表，编写程序分析句子。此次的实验之中，存储非终结符使用的是栈来存储，存储输入串则用到的是数组来存储。对于分析表，用函数的形式来存储相应的产生式。本次的实验加强了对预测分析程序的知识应用，对于预测分析程序的运行有了更进一步的认识和掌握。最重要的是通过本次的实验对本的知识进一步的掌握了。 五、源程序 // analyze.cpp : 定义控制台应用程序的入口点。 //程序可以运行 VS2015里能完全运行。 #include"stdafx.h" #include #include usingnamespacestd; //typedefstruct { //    char *base; //    char *top; //    int size; //}SqStack; //定义栈 charstack[13]; int base = 0; int top = 1; char VT[5] = { 'i','+','*','(',')' };  /*用来存放5个终结符*/ charinputString[13]; /*用来存储用户输入的字符串，最长为20个字符*/ charchanShengShi[13];          /*用来存放预测分析表M[A,a]中的一条产生式*/ intfirstCharIntex = 0;          /*如果a匹配产生式，则每次firstCharIntex自增 1 */                                /*firstCharIntex用来存放用户输入串的第一个元素的下标*/ int M(char A, char a);    /* 若预测分析表M[A,a]中存在产生式， 则将该产生式赋给字符数组chanShengShi[10]，并返回 1。若M[A,a]中无定义产生式则返回 0 */ intyuCeFenXi();//预测分析主函数 voidprintStack();          /*打印栈内元素    */ voidprintinputString();    /*打印用户输入串  */ voidinit() { inti; for (i = 0; i<13; i++) { inputString[i] = NULL;    /*初始化数组inputString[10] */ stack[i] = NULL; chanShengShi[i] = NULL; /*初始化数组chanShengShi[10]*/ } } char pop() {          /*弹出栈顶元素，用topChar返回*/ chartopChar; topChar = stack[--top]; returntopChar; } intpush(charch) { if (top>12) { cout<<" 栈溢出！ ";      /*栈空间溢出*/ return 0; } else { stack[top] = ch;  /*给栈顶空间赋值*/ top++; return 1; } } int M(charA, chara) {                        /*该函数模拟预测分析表中的二维数组              */ if (A == 'E'&&a == 'i') { strcpy_s(&chanShengShi[0], 4, "Te$"); cout<<"            E->TE'"; return 1; } if (A == 'E'&&a == '(') { strcpy_s(&chanShengShi[0], 4, "Te$"); cout<<"            E->TE'"; return 1; } if (A == 'e'&&a == '+') { strcpy_s(&chanShengShi[0], 5, "+Te$"); cout<<"            E'->+TE'"; return 1; } if (A == 'e'&&a == ')') { strcpy_s(&chanShengShi[0], 2, "$"); cout<<"            E'->ε"; return 1; } if (A == 'e'&&a == '#') { strcpy_s(&chanShengShi[0], 2, "$"); cout<<"            E'->ε"; return 1; } if (A == 'T'&&a == 'i') { strcpy_s(&chanShengShi[0], 4, "Ft$"); cout<<"          T->FT'"; return 1; } if (A == 'T'&&a == '(') { strcpy_s(&chanShengShi[0], 4, "Ft$"); cout<<"            T->FT'"; return 1; } if (A == 't'&&a == '+') { strcpy_s(&chanShengShi[0], 2, "$"); cout<<"            T'->ε"; return 1; } if (A == 't'&&a == '*') { strcpy_s(&chanShengShi[0], 5, "*Ft$"); cout<<"            T'->*FT'"; return 1; } if (A == 't'&&a == ')') { strcpy_s(&chanShengShi[0], 2, "$"); cout<<"            T'->ε"; return 1; } if (A == 't'&&a == '#') { strcpy_s(&chanShengShi[0], 2, "$"); cout<<"            T'->ε"; return 1; } if (A == 'F'&&a == 'i') { strcpy_s(&chanShengShi[0], 3, "i$"); cout<<"            F->i"; return 1; } if (A == 'F'&&a == '(') { strcpy_s(&chanShengShi[0], 5, "(E)$"); cout<<"              F->(E)"; return 1; } else return 0; /*没有定义产生式则返回0*/ } intsearch(chartemp) { inti, flag = 0;      /*flag变量做为标志，若找到temp则赋1，否则赋0*/ for (i = 0; i<5; i++) { if (temp == VT[i]) {/*终结符集合中存在temp*/ flag = 1; break; } } if (flag == 1) return 1;  /*flag==1说明已找到等于temp的元素*/ else return 0; } voidprintinputString() {  /*输出用户输入的字符串*/ int temp = firstCharIntex; cout<<"                    ";  /*该句控制输出

格式

pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载

*/ do { cout<>inputString; push('#'); push('E'); /*while循环为语法分析主功能语句块*/ cout<<" 步骤栈输入字符串所用产生式 ";  /*输出结果提示语句*/ while (1) { cout<<"    "<= 0) { push(chanShengShi[i]);  /*将当前产生式逆序压入栈内*/ i--; } } else { cout<<" 语法错误!!";  /*若预测分析表M[A,a]不存在产生式，说明语法错误*/ return 0; } } } else {      /*说明X为终结符*/ if (X == inputString[firstCharIntex]) { /*如果X等于a,说明a匹配*/ firstCharIntex++;  /*输入串的第一个元素被约去，下一个元素成为新的头元素*/ } else { cout<<" error!! "; return 0; } } counter++; } } intmain() { yuCeFenXi();  /*调用语法预测分析函数*/ //return 0; system("pause"); }