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

《编译原理预测分析程序的实现.doc》由会员分享，可在线阅读，更多相关《编译原理预测分析程序的实现.doc（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验二 预测分析表一、实验目的预测分析表的实现二、实验内容设有文法G：ETEE +TE|TFTT *FT| F(E)|i;根据文法编写预测表分析总控程序，分析句子是否为该文法的句型。当输入字符串： +i时，分析字符串是否为文法的句型三、实验步骤（详细的实验步骤）(1)文法ETEE +TE|TFTT *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

2、(T)=+,),#;FOLLOW(F)=*,+,),#;(4)预测分析表i+*()#EE-TEE-TEEE-+TEE-E-TT-FTT-FTTT-T-*FTT-T-FF-iF-(E)(5)分析过程步骤符号栈输入串应用句型0#Ei1*i2+i3#1 #ETi1*i2+i3#E-TE2 #ETFi1*i2+i3#E-TE3 #ETii1*i2+i3#F-i4 # ETi1*i2+i3#5 # ETF* *i2+i3#T-*FT6 # ETF *i2+i3#7 # ETi i2+i3#F-i8 # ET i2+i3#9 #E +i3#T-10 # ET+ +i3#E-+TE11 #ET +i3#12

3、 # ETF i3#T-FT13 # ETi i3#F-i14 # ET i3#15 # E #T-16# #E-(6)程序伪代码BEGIN 首先把#然后把文法开始符号推进STACK栈; 把第一个输入符号读进a; FLAG:=TRUE; WHILE FLAG DO BEGIN 把STACK栈顶符号托出去并放在X中; IF X属于VT THEN IF X=a THEN 把下一输入符号读进a; ELSE ERROR; ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR; ELSE IF MA,a=X-X1X2Xk THEN 把Xk,X(k-1),

4、X1一一推进栈 ELSE ERROR; END OF WHILE STOP END(7)运行结果截图注：为了将E与E区分开，所以就有e来表示E，因为在处理中E会被当成两个字符来处理，所以就简化的表示了。对于T是同样的道理，用t来表示。四、总结此次的实验是对预测分析表程序的实现，先通过给定文法写出FIRST集FOLLOW集以及预测分析表，根据预测分析表，编写程序分析句子。此次的实验之中，存储非终结符使用的是栈来存储，存储输入串则用到的是数组来存储。对于分析表，用函数的形式来存储相应的产生式。本次的实验加强了对预测分析程序的知识应用，对于预测分析程序的运行机制有了更进一步的认识与掌握。最重要的是通

5、过本次的实验对书本的知识进一步的掌握了。五、源程序/ analyze.cpp : 定义控制台应用程序的入口点。/程序可以运行 VS2015里能完全运行。#include stdafx.h#include#include using namespace std;/typedef struct /char *base;/char *top;/int size;/SqStack; /定义栈char stack13;int base = 0;int top = 1;char VT5 = i,+,*,(,) ; /*用来存放5个终结符*/char inputString13; /*用来存储用户输入的字符

6、串，最长为20个字符*/char chanShengShi13; /*用来存放预测分析表MA,a中的一条产生式*/int firstCharIntex = 0; /*如果a匹配产生式，则每次firstCharIntex 自增 1 */ /*firstCharIntex用来存放用户输入串的第一个元素的下标*/int M(char A, char a); /* 若预测分析表MA,a中存在产生式， 则将该产生式赋给字符数组chanShengShi10，并返回 1。若MA,a中无定义产生式则返回 0 */int yuCeFenXi();/预测分析主函数void printStack(); /*打印栈内

7、元素 */void printinputString(); /*打印用户输入串 */void init() int i;for (i = 0; i12) cout 栈溢出！ ; /*栈空间溢出*/return 0;else stacktop = ch; /*给栈顶空间赋值*/top+;return 1;int M(char A, char a) /*该函数模拟预测分析表中的二维数组 */if (A = E& a = i) strcpy_s(&chanShengShi0, 4, Te$);cout TE;return 1;if (A = E& a = () strcpy_s(&chanSheng

8、Shi0, 4, Te$);cout TE;return 1;if (A = e& a = +) strcpy_s(&chanShengShi0, 5, +Te$);cout +TE;return 1;if (A = e& a = ) strcpy_s(&chanShengShi0, 2, $);cout ;return 1;if (A = e& a = #) strcpy_s(&chanShengShi0, 2, $);cout ;return 1;if (A = T& a = i) strcpy_s(&chanShengShi0, 4, Ft$);cout FT;return 1;if (

9、A = T& a = () strcpy_s(&chanShengShi0, 4, Ft$);cout FT;return 1;if (A = t& a = +) strcpy_s(&chanShengShi0, 2, $);cout ;return 1;if (A = t& a = *) strcpy_s(&chanShengShi0, 5, *Ft$);cout *FT;return 1;if (A = t& a = ) strcpy_s(&chanShengShi0, 2, $);cout ;return 1;if (A = t& a = #) strcpy_s(&chanShengSh

10、i0, 2, $);cout ;return 1;if (A = F& a = i) strcpy_s(&chanShengShi0, 3, i$);cout i;return 1;if (A = F& a = () strcpy_s(&chanShengShi0, 5, (E)$);cout (E);return 1;elsereturn 0; /*没有定义产生式则返回0*/int search(char temp) int i, flag = 0; /*flag变量做为标志，若找到temp则赋1，否则赋0*/for (i = 0; i5; i+) if (temp = VTi) /*终结符

11、集合中存在temp*/flag = 1;break;if (flag = 1)return 1; /*flag=1说明已找到等于temp的元素*/elsereturn 0;void printinputString() /*输出用户输入的字符串*/int temp = firstCharIntex;cout ; /*该句控制输出格式*/do cout inputStringtemp;temp+; while (inputStringtemp - 1 != #);cout ;void printStack() /*输出栈内内容*/int temp;for (temp = 1; temptop;

12、temp+) cout stacktemp;int yuCeFenXi() char X; /*X变量存储每次弹出的栈顶元素*/char a; /*a变量存储用户输入串的第一个元素*/int i;int counter = 1; /*该变量记录语法分析的步骤数*/cout inputString;push(#);push(E);/*while循环为语法分析主功能语句块*/cout 步骤 栈 输入字符串 所用产生式 ; /*输出结果提示语句*/while (1) cout endl;cout counter; /*输出分析步骤数*/cout ; /*输出格式控制语句*/printStack();

13、 /*输出当前栈内所有元素*/X = pop(); /*弹出栈顶元素赋给变量X*/printinputString(); /*输出当前用户输入的字符串*/if (search(X) = 0) /*在终结符集合VT中查找变量X的值，存在返回 1，否则返回 0*/if (X = #) /*栈已经弹空，语法分析结果正确，返回 1*/cout endl;cout 分析成功！ ; /*语法分析结束，输入字符串符合文法定义*/return 1;else a = inputStringfirstCharIntex;if (M(X, a) = 1) /*查看预测分析表MA,a是否存在产生式，存在返回1，不存在

14、返回0*/for (i = 0; i= 0) push(chanShengShii); /*将当前产生式逆序压入栈内*/i-;else cout 语法错误!; /*若预测分析表MA,a不存在产生式，说明语法错误*/return 0;else /*说明X为终结符*/if (X = inputStringfirstCharIntex) /*如果X等于a,说明a匹配*/firstCharIntex+; /*输入串的第一个元素被约去，下一个元素成为新的头元素*/else cout error! ;return 0;counter+;int main()yuCeFenXi(); /*调用语法预测分析函数*/return 0;system(pause);第 14 页