编译原理实验报告1225111005方迪恺

学院：计算机科学与技术班级：12级计算机科学与技术学号：1225111005姓名：方迪恺题目：基于初等函数运算的编译系统目录：一、前言二、词法分析器2.1实验目的2.2实验内容与要求2.3词法模式设计与正则式的确立2.4记号表2.5NFA2.6DFA2.7状态转换表2.8程序设计思路与主要算法三、语法分析器3.1实验目的3.2实验内容与要求3.3构造上下文无关文法3.4改写为LL(1)文法3.5预测分析表3.6递归下降子程序3.7实验结果及讨论四、语义分析器4.1实验目的4.2实验内容与要求4.3后序遍历得到后缀表达式4.4程序结构设计4.5实验结果及讨论五、实验总结六、参考文献一、【前言】本实验主要内容是实现一个初等函数运算语言的解释器或编译器。初等函数是由幂函数、指数函数、对数函数、三角函数、反三角函数与常数经过有限次的有理运算（加、减、乘、除）及有限次函数复合所产生、并且能用一个解析式表示的函数。如表一所示，本实验中仅要求完成部分初等函数，包括三角函数、幂函数、指数函数、对数等类型。表一、实验要求的初等函数表函数类型函数名称参数说明sin(x)正弦函数xcos(x)余弦函数xtg(x)正切函数xctg(x)余切函数xx^y幂函数/指数函数x：底数,y：指数log(x,y)对数x:底数,y：lg(x)以10为底的对数Xln(x)以e为底的对数Xlog(x)以2为底的对数X本程序从输入界面或文件中接收一个包含了各种初等函数表达式的字符串，程序对这些表达式进行计算和求值，并根据要求输出相应的值。例1：输入：x=0.5*PI;y=E;z=3;?1/3*(ln(y)+5*sin(x))+(7+z)^2;输出：102例2：输入：x=0.5*PI;y=E;?1/3*(ln(y)+5*sin(x))+(7+z)^2;输出：2+(7+z)^2初等函数运算语言相关的内容如下：1）语言中仅使用实数这一种数据类型。所有常数、变量及表达式都为实数类型。2）语言中可以定义变量来存放数值，变量的定义方式与c语言中的标识符相同。3）可以通过赋值语句给变量赋值。4）表达式是一个初等函数（函数、变量、常数等通过四则运算或函数嵌套而成）。5）输出语句是：?表达式。将在界面上输出该表达式的值。如果其中有某一个变量没有赋值，那么将输出该表达式简化后的式子。二、词法分析器设计2.1【实验目的】1、为初等函数运算语言构造语法分析器。2、掌握生成词法分析器的方法，加深对词法分析原理的理解。3、掌握设计、编制并调试词法分析程序的思想和方法。2.2【实验内容及要求】一、根据下面的要求设计初等函数运算语言的词法模式，并用正则式表达出来1、初等函数运算语言的常量为实数类型，其定义方式为实数的最一般书写方式，如：123.321。具体要求：不支持整数部分大于0时首数字为0；不支持小数点后结尾为0；不支持科学记数法；不支持仅为整数时有小数点。2、初等函数运算语言的变量采用与C语言的标识符定义一样的方式：首字符为字母或下划线；其他的为字母、数字及下划线的混合串；区分大小写；变量长度不超过32个字符。3、初等函数运算语言需要处理的函数仅为表一中所列举的内容。4、初等函数运算语言支持四则运算，其计算的符号与C语言相同，为：+-*/。5、初等函数运算语言的合法的分隔符包括：空格、制表符、、分行符圆括号（左、右）、分号。其中空格、制表符、分行符可以出现在任何两个不同的单词中间；圆括号（左、右）用于表达式中，用于改变运算的优先级，以及标识函数的参数；分号用于标识一个语句的结束。6、初等函数运算语言支持的常量还包括：PI,E。2.3【词法模式设计与正则式的确定】我们将程序中可能出现的单词分为以下四类：运算符（如+等）、标识符（如变量X等）、分隔符（如；等）、常量（如5等）。正则式的确定：运算符:Operation=+|-|*|/|=|^标识符（变量）：Variable=(_|a|b|…|z|A|B|…Z)(_|a|b|…|z|A|B|…|Z|0|1|2|…|9)*分隔符：Compart=空格|\t|\n|（|）|；常量：Constant=(ε|-)((0|(1-9)(0-9)*)(.(0-9)*(1-9)|ε))|PI|E关键字：Keyword=sin|cos|tg|ctg|log|lg|ln(由于这些关键字的识别与普通标识符差不多，所以可以在识别出标识符后马上进行判断是不是关键字来实现，不需要再单独进行构造)2.4【记号表】sincostgctglog(x,y)lglnlog(x)();?+0123456789101112-*/=常量变量^，{}无法识别标识符1314151617181920212223PIE#2425262.5【NFA】只需要对变量以及常量构造NFA。2.6【DFA】根据得到的NFA进行转换，主要有两个目标：1.消除其中所有的ε状态转移，即状态转换图中没有标记ε的边。2.对每一个状态和字符只有一个下一个状态，进行确定化工作。具体的计算过程不再演示，最后将DFA进行合并的结果如下：（特此说明：这里引入了一个操作符—，主要考虑到—在程序中具有两个双重的含义：一个是代表某个负数，另一个是代表运算符减号，所以在DFA中加入了减号状态，这样可以方便后期的编码工作。2.7【状态转移表】//_____________________________________________________//状态装换表//char01-9_-.//013412//111117//234//375//44475//556//6567//_____________________________________________________//o是初始状态，3,4,6状态表示实数，1状态表示标识符，7状态表示‘-’为减号2.8【程序设计思路与主要算法】根据我们最后得到的状态转移表，我们就可以进行程序的编码工作。由于程序代码量不大，所以我采用的是直接编码型词法分析器。程序的整体思路如下：需要被计算的代码存储在“.txt”文本之中。用文件指针FILE*fp;打开文本文件。调用voidanalyse(FILE*fp)函数，实现的功能是利用ch=fgetc(fp)将字符串读入到arr字符数组之中同时对此时Ch变量中的特殊字符利用Switch结构进行检测，检测出到底是哪一个特殊符号并赋予其记号流。调用move(ch,s)函数，每读入一个字符就需要根据状态表进行跳转，以当前所在状态S为基础，读入一个新字符后跳转到下一个状态。每读入一个字符就要判断它是不是标识符中允许出现的字符是否调用voidjudge(chararr[])函数对arr数组中的字符串进行检测，根据当前的S所在状态来判断出它到底是标识符还是常量还是关键字根据不同结果来进行不同的操作，如果是标识符和常量，则需要将内容存入数组之中将结果存入记号流数组之中并进行输出，同时函数返回继续进行字符读入，直到遇到#结束返回到程序继续从文件读入字符串处程序主要函数说明：intIskey(stringc);//判断是否是关键字，返回值为其记号boolIschar(charc);//判断是否是字母boolIsnum(charc);//判断是否是1-9的数字voidmove(charch,ints);//状态表跳转函数voidjudge(chararr[]);//字符串判断函数，以及实现特殊字符的识别voidanalyse(FILE*fp);//完成字符的逐个读入以及调用move函数进行状态转移，遇到输入停止时调用judge函数进行识别判断。externintmark[100];//将记号流存入mark数组之中，作为语法分析器的输入。externintpointer;//记号流数组访问下标，最后的结果代表记号个数externstringvariable[100];//存储标识符及常量的具体内容，作为语法分析器的一个输入。此程序实现结果截图：输入：（1.txt）x=0.5*PI;y=E;z=3;?1/3*(ln(y)+5*sin(x))+(7+z)^2;#根据之前定义的记号表，可以证明结果是正确的，词法分析器完成。三、语法分析器设计3．1【实验目的】1、为初等函数运算语言构造LL（1）语法分析器。2、掌握LL（1）语法分析器的方法，加深对自上而下语法分析原理的理解。3、掌握设计、编制并调试LL（1）语法分析程序的思想和方法。3．2【实验内容及要求】一、根据初等函数运算语言运算法则，将语法模式用上下文无关文法表达。1、注意运算的优先性，避免产生二义性文法。二、将上述文法改写为LL(1)文法。三、根据LL（1）文法给出预测分析表。四、根据预测分析表，给出解析LL(1)文法的递归下降子程序。五、本语法分析程序的输入是实验一生成的记号流；本程序需定义语法树的数据结构；语法分析的输出是一棵语法树。六、当输入存在语法错误时，需给出语法错误的提示，指出语法错误发生的位置和错误类型。3．3【构造上下文无关文法】G=(N,T,P,S)N={S,A,B,C,D,E}T={变量|？|；|#|ε|=|+|-|*|/|-|实数|（|）|sin|cos|tg|ctg|lg|ln|log|,}S=SP:S-A?B;#S-C;A|εC-变量=BB-B+C|B-C|CC-C*D|C/D|DD-E|sin(E)|cos(E)|tg(E)|ctg(E)|lg(E)|ln(E)|log(E)|log(E,E)|E^EE-(B)|-E|变量|实数3．4【改写为LL(1)文法】消除文法的二义性以及左递归，将上下文无关文法改成LL(1)文法：G=(N,T,P,S)N={S,A,B,C,D,E，F,G,H,I,J}T={变量|？|；|#|ε|=|+|-|*|/|-|实数|（|）|sin|cos|tg|ctg|lg|ln|log|,}S=SP:S-A?B;A-C;A|εC-变量=BB-DEE-+DE|-DE\|εD-FGG-*FG|/FG|εF-HI|cos(H)|sin(H)|tg(H)|ctg(H)|lg(H)|ln(H)|log(HJJ-,H)|)H-(B)|-H|变量|实数3．5【预测分析表】通过计算各个非终结符的First集和Follow集来构造出预测分析表。由于具体过程比较复杂，所以这里直接给出最后所得到的预测分析表：3．6【递归下降子程序】说明：//为了编程的方便，我们把非终结符也赋予记号（非终结符所对应的ASIC码）//________________________________________________//SABCDEFGHIJ//8365666768697071727374//________________________________________________所以此语法分析器的输入为：1.词法分析器得到的记号流2.标识符（变量）以及常量的具体内容（根据读取的顺序依次存放在数组之中）编程的基本思想：为每一个非终结符构造一个子程序，每一个子程序的过程体中按该产生式的候选项分情况展开，遇到终结符直接匹配，而遇到非终结符就调用相应非终结符的子程序。该分析从调用文法开始符号的子程序开始，直到所有非终结符都展开为终结符并得到匹配为止。具体函数如下：voidprint();//用于输出当时的匹配过程intGetNextToken();//用于获取当前输入进行匹配的记号intmatch(intch);//终结符进行匹配的函数intA();intB();intC();intD();intE();intF();intG();intH();intI();intJ();structAnalyzeTree//语法树的结点结构{intToken;//存记号stringcontent;//存记号的内容，针对的是变量及常量structAnalyzeTree*child;structAnalyzeTree*brother;}*Root,*P;程序的思路是非常清