北方工业大学计算机专业编译原理实验报告――语法分析器详细代码报告

1、编译原理实验报告实验题目：语法分析器构造指导教师：杨健姓名：班级：学号：实验成绩：实验题目语法分析器构造实验目的和要求编译器实现技术是一大宝库，一方面以编译器的实现为背景可以实践几乎全部在数据结构与算法分析课程中学到的主要数据结构与算法；另一方面，编译器设计中使用的问题求解方法、处理问题的思路被广泛地用于自动数据处理（转换）及其它一些新的研究领域。没有编译器的出现就没有现代数字计算机的发展。本次课设即以“语法规则的存储与显示”、“句子的生成”、“语法（分析）树的建立”等等这些编译器中的一些基本功能的实现为题，对高级程序设计语言在计算机中的表达和相关的处理有一个初步认识，提前领略“数据的自动转换

2、与处理”这一计算机问题求解的核心技术。尽管这些功能的实现并不涉及较深入的编译技术，但也需要带着问题预先学习、掌握有关形式语言、编译原理与技术的若干基本概念。借助于词法分析程序提供的分析结果，编写一个算符优先语法分析程序，程序能进行语法结构分析和错误检查并产生相应的归约信息。同时给出出错信息和错误类型，从而加深对语法分析的理解。设计思想与框架 1.算符优先文法定义：设有不含空串的一文法G，如果G中没有形如GBC的产生式，其中B和C为非终结符，且对任意两个终结符a，b之间之多只有，=，三种关系的一种成立，则称G是一个算符优先文法。非终结符的FIRSTVT集合和LASTVT集合FIRSTVT（B）=

3、b|Bb或BCbLASTVT（B）=b|Ba或BaC2.算符优先矩阵算符优先关系矩阵，判断输入是否满足已知文法的依据。根据非终结符的FIRSTVT集合和LASTVT集合产生。1.“=”关系若Aab或AaBb，则a=b；2.“”关系若AaB，对每一个b属于FIRSTVT（B），有ab；3.“”关系若ABb，对每一个a属于LASTVT（B），有a b。3.如何归约在分析过程中，利用分析栈存放已识别的那部分句型，而句型的其余部分由剩余输入串组成，通过比较栈顶符号和下一个输入符号之间的关系，可以判别栈顶符号是否为句柄尾符号。如果是句柄尾，则沿栈顶向下，在栈内寻找句柄头。关系和关系之间包括的符号串就是句

4、柄，然后把它们弹出栈，并代之以归约后的非终结符。这样就完成了一次归约过程。 4.算符优先分析方法的局限性由于算符优先分析法去掉了单非终结符之间的归约，尽管在分析过程中，当决定是否为句柄时采取一些检查措施，但仍难完全避免把错误的句子得到正确的归约。此外，通常一个适用语言的文法也很难满足算符优先文法的条件，因而致使算符优先分析法仅适用于表达式的语法分析。输入:所给文法的源程序字符串。输出：二元组构成的序列。实现过程:算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。算符优先文法的执行过程为：输入已知文法，分析其

5、正确性，提取非终结符和终结符，构造非终结符的FIRSTVT集和LASTVT集，再次基础上构造算符优先关系矩阵，并用来判断表达式是否符合该文法。（1）输入已知文法，生成文法矩阵，判断该文法是否是算符优先文法。（2）用程序自动生成该文法的算符优先关系矩阵。（3）对人工输入的句型或句子，分析该句型或句子是否合法，能否用已知文法推出。（4）具有通用性。所开发的程序可适用于不同的文法和任意输入串，且能判断该文法是否为算符优先文法。（5）有运行实例。对于输入的文法和符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。核心算法void prior_analysis() int

6、i,j,m; char q,str,ch20; push(#);print(0,-1); u: readvt(&a); if(IsVT(stacktop) j=top; else j=top-1;do while(big(j,a)&strcmp(stack,#N)!=0) do q=stackj; if(IsVT(stackj-1) j=j-1; else j=j-2;while(!less(j,q);i=-1;while(top-j)!=0) ch+i=pop();chi+1=0;for (m=0;m项|算术表达式+项|算术表达式-项/ 项-因子|项*因子|项/因子/ 因子-变量|常数|(算

7、术表达式) / 算符优先关系表 /- / + - * / ( ) i # / + / - / * / / / ( = ? ? / i ? ? / # ? = /- #include #include #include using namespace std;#define N 100#define NULL 0FILE *fp;/预处理文件指针/定义符号栈的大小与输入字符串的大小以及算术表达式字符串的大小char stackN,stringsN,oldstringsN;char a;int top=-1,k=0,step=1,n=0,NoN,id=1;/二维数组定义字符之间的优先关系(1表示,

8、-1表示,0表示=,-2表示错误)int MNN=1,1,-1,-1,-1,1,-1,1,1,1,-1,-1,-1,1,-1,1,1,1,1,1,-1,1,-1,1,1,1,1,1,-1,1,-1,1, -1,-1,-1,-1,-1,0,-1,-2,1,1,1,1,-2,1,-2,1,1,1,1,1,-2,1,-2,1,-1,-1,-1,-1,-1,-2,-1,0; char *word6=N+N,N-N,N*N,N/N,)N(,i;/可归约字符串int print(int t,int m) coutn step+setw(10); coutstacksetw(10); if(m=1) cou

9、tsetw(8); else if(m=0) cout=setw(8); else coutsetw(8); coutasetw(10); cout&stringsksetw(10); if(t) cout归约setw(8); Non+=step-1; else cout移进setw(8); return 0;void push(char ch) stack+top=ch;char pop()char a;a=stacktop-;stacktop+1=0; return a;int ch_di(char ch) switch(ch) case+: return 1; case-: return

10、 2; case*: return 3; case/: return 4; case(: return 5; case): return 6; casei: return 7;case#: return 8; default: return 0;int IsVT(char ch) if(ch=N) return 0; else return 1;int readvt(char *a) if(IsVT(stringsk) (*a)=stringsk; k+; return 1; else k+; return 0;int big(int t,char a) if(Mch_di(stackt)-1

11、ch_di(a)-1=1)return 1;elsereturn 0;int less(int t,char a) if(Mch_di(stackt)-1ch_di(a)-1=-1)return 1;elsereturn 0;int equal(int t,char a) if(Mch_di(stackt)-1ch_di(a)-1=0)return 1;elsereturn 0;void error(int t) if(ch_di(stackt)=6|ch_di(stackt)=7) printf(n错误e2:缺少运算符!);else if(ch_di(stackt)=5)printf(n错误

12、e1:非法左括号!);else printf(n错误e3:非法右括号!);void prior_analysis() int i,j,m; char q,str,ch20; push(#);print(0,-1); u: readvt(&a); if(IsVT(stacktop) j=top; else j=top-1;do while(big(j,a)&strcmp(stack,#N)!=0) do q=stackj; if(IsVT(stackj-1) j=j-1; else j=j-2;while(!less(j,q);i=-1;while(top-j)!=0) ch+i=pop();c

13、hi+1=0;for (m=0;m=5;m+)if(strcmp(wordm,ch)=0)str=N;push(str); print(1,1); if(less(j,a) push(a);print(0,-1);if(stacktop!=#)goto u; else if(equal(j,a) push(a);print(0,0); if(stacktop!=#)goto u;elseerror(j);a=#;while(a!=#);void main() cout*算符优先语法分析程序*endl;coutE+T|E-T|Tendl;coutT*F|T/F|Fendl;cout(E)|ien

14、dl;cout E表示算术表达式.T表示项.F表示因子.i表示变量或常数.endl;cout 优先表endl;cout + - * / ( ) i #endl;cout endl; cout endl;cout endl;cout endl;cout ( = e1endl;cout e2 e2 endl;cout e2 e2 endl;cout # e3 =endl;if(fp=fopen(预处理.txt,r)=NULL)/如果预处理文件中是空的cout请先将实验1文件夹中的预处理.txt文件复制到实验2文件夹中!|ch1=)&ch=)ch=fgetc(fp); if(ch=#) cout算符

15、优先语法分析结束!endl;fclose(fp); system(pause);exit(0); while(ch!= &ch!=#) ch=fgetc(fp); oldstrings+i=ch; oldstringsi=0; if(isalnum(oldstringsj) strings+m=i; else strings+m=oldstringsj; j+; while(oldstringsj!=0) if(isalnum(oldstringsj) if(isalnum(oldstringsj-1)=0) strings+m=i; else strings+m=oldstringsj; j

16、+; stringsm+1=#; stringsm+2=0;coutendl; cout算术表达式id为: oldstringsendl; cout转换为输入串: stringsendl; cout 步骤号 符号栈 优先关系 当前分析符 剩余输入串 动作; prior_analysis(); n=0; coutendl; cout算术表达式id+的归约产生式步骤号为:; while(Non) cout Non; n+;coutendl; while(stack0!=0) pop();while(No-n)Non=0; top=-1; a=0; k=0; step=1; n=0;cout算符优先

17、语法分析结束!endl;fclose(fp);system(pause);exit(0);问题及处理问题1：预处理文件不存在当预处理文件不存在时，程序执行时会做出相应的提醒，并且预处理文件是我们此次实验的重要文件，必须在它存在的前提下才能正常运行程序，得到语法分析。问题2：分析的时候把+判断成非法运算符判断标志flag为0，导致在数据第一个元素返回值也是0，使得判断出错。把flag判断改为-1，使得与数组各下标位不冲突。实验结果程序设计语言和自然语言不一样，都是用符号来描述，每个特定的符号表示特定的意思，而且程序设计语言是上下文无关的。上下文无关就是某一个特定语句所要表达的意思和它所处的上下文

18、没有关系，只有它自身决定。词法分析器的功能输入源程序，按照构词规则分解成一系列单词符号。单词是语言中具有独立意义的最小单位，包括关键字、标识符、运算符、界符和常量等。(1) 关键字 是由程序语言定义的具有固定意义的标识符。例如，Pascal 中的begin，end，if，while都是保留字。这些字通常不用作一般标识符。(2) 标识符 用来表示各种名字，如变量名，数组名，过程名等等。(3) 常数 常数的类型一般有整型、实型、布尔型、文字型等。(4) 运算符 如+、-、*、/等等。(5) 界符 如逗号、分号、括号、等等。输出：词法分析器所输出单词符号常常表示成如下的二元式：(单词种别，单词符号的属性值)单词种别通常用整数编码。标识符一般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可将其全体视为一种。运算符可采用一符一种的方法。对于每个单词符号，除了给出了种别编码之外，还应给出有关单词符号的属性信息。单词符号的属性是指单词符号的特性或特征。截图一：截图二：截图三：截图四：实验心得在算符优先文法的程序设计过程中，程序比较复杂，光数据结构设计阶段就占据了很长的时间，几种数据结构很难确定那种能满足程序要求。一旦确定了数据结构，程序编写还是比较顺利。很快程序就可以对正确的输入做出正确的处理，不过没有查错纠错的能力，之后加入查错纠错的功能花费了很大的力气