编译原理-语法分析-实验报告(共10页).doc

《编译原理-语法分析-实验报告(共10页).doc》由会员分享，可在线阅读，更多相关《编译原理-语法分析-实验报告(共10页).doc（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上编译原理及实践结课大作业语法分析学生姓名 艾力娜托里干 依勒斯江木尔扎合买提 克勒曼沙布勒别克 学 号 所属学院 信息工程学院 专 业 计算机科学与技术 班 级 民本15-1班 信息工程学院一LL(1)预测语法分析器实现目标简单的算术表达式的LL(1)语法分析器实现工具Microsoft Visual C+ 6.0,使用C/C+语言实现代码编程。需求分析与概要设计：编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程

2、序是最终的一个语法单位。编译程序的语法规则可用上下文无关文法来刻画。语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发，向下推导，推出句子。而自下而上分析法采用的是移进归约法，基本思想是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。详细的算法描述：（1） 自顶向下带递归语法分析 （这个方法用的是老师给的文法）1、首先对所以的生成式消除左递归、提取公共左因子2、在源程序里建立一个字符串数组，将所有的生成式都存在这个数组中。3、给每个非终结符写一个带递归的匹配函数，其

3、中起始符的函数写在main函数里。这些函数对生成式右边从左向右扫描，若是终结符直接进行匹配，匹配失败，则调用出错函数。如果是非终结符则调用相应的非终结符函数。4、对输入的符号串进行扫描，从起始符的生成式开始。如果匹配成功某个非终结符生成式右边的首个终结符，则将这个生成式输出。匹配过程中，应该出现的非终结符没有出现，则出错处理。文法l 产生式 P :E - E+T T - T/FE - E-T T - FE - T F - (E)T - T*F F - i提取左因子并消除左递归得产生式 P :(0) ETe(1) e+Te(2) e-Te(3) e(4) TFt(5) t*Ft(6) t/Ft(

4、7) t(8)F(E)(9) Fi /*表示id */l 开始符号S: El 终结符集Vt: E, e, T, t, F l 非终结符集Vn: +, -, *, /, (, ), i 构造预测分析表l FIRST集:first(E)= first(T)= first(F)= , i first(e)=+, -, first(t)=*, /, l FOLLOW集:follow(E)=$, follow(e)=follow(E)=$, follow(T)=fitsr(e)- +follow(e)=+, _ , , $follow(t)=follow(T)+follow(t)=+, _ , , $f

5、ollow(F)=follow(t)- +follow(T)+follow(t)=*, /, +, _ , $预测分析器模型i+i$xy.$预测分析程序输出分析表图1-1非递归的预测语法分析器模型源代码#include#include#include#define Vtn 8#define Vnn 5#define Pn 10#define Pmaxlen 20#define MaxStLength 50#define MaxStackDepth 50char VnVnn=E,e,T,t,F;char VtVtn=i,+,-,*,/,(,),$;char PstrPnPmaxlen=E-Te,

6、e-+Te,e-Te,e-,T-Ft,t-*Ft,t-/Ft,t-,F-(E),F-i;int PrlenPn=2,3,3,1,2,3,3,1,3,1;int PintPn3=102,101,1,102,101,2,102,101,-1,104,103,3,104,103,4,104,103,-1,5,100,6,0;int analyseTableVnnVtn+1;int analyseStackMaxStackDepth+1; int topAnalyse; char stMaxStLength; /要分析的符号串/* -初始化-*/void InitanalyseTable()/*-预测

7、分析表存放各个产生式的编号，-1表示找不到相匹配的产生式-*/ for(int i=0;iVnn;i+) for(int j=0;jVtn;j+) analyseTableij=-1; analyseTable00=0; analyseTable05=0; analyseTable11=1; analyseTable12=2; analyseTable16=3; analyseTable17=3; analyseTable20=4; analyseTable25=4; analyseTable31=7; analyseTable32=7; analyseTable33=5; analyseTa

8、ble34=6; analyseTable36=7; analyseTable37=7; analyseTable40=9; analyseTable45=8; void Init() /分析栈的初始化 analyseStack0=7; /入栈 analyseStack1=100; /初始符入栈 topAnalyse=1; /初始符号串 int i; for(i = 0; i MaxStLength;i+) sti = 0;void Pop()topAnalyse-;/*-产生式入栈操作-*/void Push(int r) int i,len; Pop(); len=Prlenr;/为空时

9、if(len=1)&(Pintr0=-1) return;/不为空时 topAnalyse+=len; for(i=0;ilen;i+) analyseStacktopAnalyse-i=Pintri; /逆序入栈void ShowStack() int i; for(i =0;i=100) printf(%c,VnanalyseStacki-100);elseprintf(%c, VtanalyseStacki); /*-返回表中的位置，-1表示未找到-*/int Index(char c) int i=0; while(iVtn)&(c!= Vti) i+; if(iVtn)&(c=Vti

10、) return i; else return -1;void Identify()int current,step,r; printf(n%s：nn, st);step = 0;current = 0; printf(%dt,step);ShowStack();printf(tt%stt- -n, st+current); while(1)if(analyseStacktopAnalyse100) if(VtanalyseStacktopAnalyse=stcurrent) Pop();current+;step+;printf(%dt,step);ShowStack();printf(tt

11、%stt出栈、后移n, st+current); elseprintf(字符 %c 与字符 %c 不匹配！, VtanalyseStacktopAnalyse, stcurrent);printf(此串不是此文法的句子n);return;else int n,m;n=analyseStacktopAnalyse - 100; m=Index(stcurrent);if(m=-1) printf( %c 字符不符合输入，输入出错！ ,stcurrent);printf(此串不是此文法的句子n);return; r = analyseTablenm; if( r!=-1) Push(r); ste

12、p+;printf(%dt, step);ShowStack();printf(tt%stt%sn, st+current,Pstrr); elseprintf(无可用产生式，此串不是此文法的句子！n);return;if(topAnalyse=0&stcurrent=$) break;/void main() InitanalyseTable(); while(1) Init(); printf(请输入符号串(以$结束) : ); int i=0; char c; c=getchar(); while(iMaxStLength) if(c=$) sti=$; break; else if(c

13、!= &c!=n) sti+=c; c=getchar(); if(c=n) printf(请以$结束：); c=getchar(); if(iTe2 $etF i+i*i$ T-Ft3 $eti i+i*i$ F-i4 $et +i*i$ 出栈、后移5 $e +i*i$ t-6 $eT+ +i*i$ e-+Te7 $eT i*i$ 出栈、后移8 $etF i*i$ T-Ft9 $eti i*i$ F-i10 $et *i$ 出栈、后移11 $etF* *i$ t-*Ft12 $etF i$ 出栈、后移13 $eti i$ F-i14 $et $ 出栈、后移15 $e $ t-16 $ $ e

14、-请输入符号串(以$结束) : i-(i+i/i)$i-(i+i/i)$：0 $E i-(i+i/i)$ - -1 $eT i-(i+i/i)$ E-Te2 $etF i-(i+i/i)$ T-Ft3 $eti i-(i+i/i)$ F-i4 $et -(i+i/i)$ 出栈、5 $e -(i+i/i)$ t-6 $eT- -(i+i/i)$ e-Te7 $eT (i+i/i)$ 出栈、8 $etF (i+i/i)$ T-Ft9 $et)E( (i+i/i)$ F-(E)10 $et)E i+i/i)$ 出栈、后移11 $et)eT i+i/i)$ E-Te12 $et)etF i+i/i)$

15、 T-Ft13 $et)eti i+i/i)$ F-i14 $et)et +i/i)$ 出栈、后移15 $et)e +i/i)$ t-16 $et)eT+ +i/i)$ e-+Te17 $et)eT i/i)$ 出栈、后移18 $et)etF i/i)$ T-Ft19 $et)eti i/i)$ F-i20 $et)et /i)$ 出栈、后移21 $et)etF/ /i)$ t-/Ft22 $et)etF i)$ 出栈、后移23 $et)eti i)$ F-i24 $et)et )$ 出栈、后移25 $et)e )$ t-26 $et) )$ e-27 $et $ 出栈、后移28 $e $ t-29 $ $ e-请输入符号串(以$结束) :总结体会1.通过本实验,我们不仅对语法分析有了进一步的了解,而且对相关知识点有了更深刻的了解.2.LL(1)文法是不含二义性的,也不含左递归的.故在构造分析器前要对所给的文法提取左因子,消除左递归.专心-专注-专业