编译原理课程设计报告

编译原理课程设计报告一、分析通过设计，编制，调试一个语法及语义分析程序，加深对语法及语义分析原理的理解。IF〈布尔表达式〉THEN〈赋值语句〉ELSE〈赋值语句〉其中（1）、可以选择递归下降法、LL（1）、算符优先分析法、LR法完成以上任务，中间代码选用四元式。（2）、写出符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。（3）、编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。二、算法设计程序要求有三部分组成，即词法分析、语法分析、以及语义分析。其中词法分析部分要求完成对输入程序的关键字、标识符、常数、运算符进行识别；并分析词法分析的结果，检查程序输入的关键字是否为符合设计文法的关键字，检查标志符是否是合法标志符，识别运算符的种类。语法分析部分主要是以算符优先文法的设计思想和步骤完成对词法分析结果的的语法分析工作，判断输入的程序是否符合设计的IF-THEN-ELSE文法。在语法分析通过的基础上进行语义分析，其主要任务是完成对语法分析后的程序的语义分析，根据语法制导翻译去翻译输入的程序，从而得到程序的中间代码表示形式——四元式。词法分析、语法分析和语义分析的流程图如下：开始输入需编译的文件名（文件名.txt）调用cifa()函数进行此法分析此法分析成功判断文件是否存在语法分析语义分析分析成功？分析成功？输出四元式结束NNNNYYYY（1）词法分析A词法分析器的功能和输出形式输入：所给文法的源程序字符串输出：二元组（单词种别,单词符号的属性值）构成的序列B.待分析的简单语言的词法因为是模拟简单编译器,所以就以C语言的小型子集作为模拟编译器的词法.模拟程序语言的单词符号可分为下列五种;关键字:{(相当于Pascal语言中的begin),if,else,while,}(相当于Pascal语言中的end)所有的关键字都是小写字母.运算符:+,-,*,/,=,,=,==,,=,,&&,||,!界符:逗号,分号,左圆括号,右圆括号,#常数:在这里只涉及到int型常量其他单词是标识符（ID）和整形常数（NUM），通过以下正规式定义：ID=letter（letter|digit）*NUM=digitdigit*空格由空白，制表符和换行符组成，空格一般用来分隔ID，NUM，运算符，界符和关键字，词法分析阶段通常会被过滤掉。C.词法分析的设计思想:算法的基本任务是从字符串表示的源程序中识别出其具有独立意义的单词符号,其基本思想是根据扫描到的单词符号的第一个字符的种类,拼出相应的单词符号。（2）语法分析语法分析要处理的输入是词法分析的输出即单词序列。该部分主要用到两个栈，一个用来保存单词标志号的状态栈另一是用来保存单词本身信息的符号栈。程序从词法分析输出的单词序列中读取一个单词，检查单词是否是合法单词，如果是合法的，则取符号栈的栈顶元素，和当前单词的标志号进行优先级比较，如果小于当前单词的优先级那么将当前单词压入符号栈，将其标志号压入状态栈；如果大于当前单词的优先级那么继续弹出状态栈的元素，和上一个符号栈弹出的元素进行比较，如果两优先级相等则继续弹，如果小于上一次弹出的元素的优先级，则弹的所有元素按先后弹的倒置顺序排列为一个句柄，查找产生式找到相应的产生式进行规约，把规约或的元素当多当前一的元素继续进行比较，直到词法分析输出结果全部遍历完。在规约的过程中记下规约的次数，和每次规约的元素，以便语义分析和中间代码生成。（3）语义分析语义分析主要是将语义分析结果转化成三地址码表示的中间代码的过程。在语法分析的过程中，在每次规约的过程中记录规约的类型和各个类型规约的次数。即当规约的语句是布尔表达式时每规约一次都将规约的语句转化成三地址码的形式保存在字符串E中并记录E中规约产生式的次数在m1.quad中；如果规约的产生式是第一个赋值语句块中的赋值语句，则将规约的产生式以三地址形式保存在字符串B1中并记录B1中规约产生式的次数在m2.quad中；如果规约的产生式是第二个赋值语句块中的赋值语句，则将规约的产生式以三地址形式保存在字符串B2中并记录B2中规约产生式的次数在m3.quad中。最后控制将B1、B2和E中的内容输入。三、LL（1）文法LL(1)文法分析流程图：•构造不带回溯的自上而下分析的文法条件1.文法不含左递归，2.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A→1|2|…|n则FIRST(i)∩FIRST(j)＝(ij)3.对文法中的每个非终结符A，若它存在某个候选首符集包含，则FIRST(A)∩FOLLOW(A)=如果一个文法G满足以上条件，则称该文法G为LL(1)文法。构造预测分析表的步骤：①对每个产生式A→1|…|n执行②,③。②对FIRST(A)中每个终结符a,把A→i加入到M[A,a],其中a∈FIRST(i)③若ε∈FIRST(i),则对任何属于FOLLOW(A)的终结符b,将A→i加入M[A,b]。④把所有无定义的M[A,a]标记为出错。在上面的属性文法中我们使用了这样的假定：每当需要临时变量时，newtemp产生新的临时名字；lookup(id.name)用于根据名字的拼写检查符号表中是否存在该名字的条目。如果有，返回该条目的指针，否则lookup返回nil，以表示没有找到；E的属性place用来存放E值的变量名在符号表的登录项或一整数码（若此变量是一个临时变量）；函数newtemp用来产生一个新的临时变量的名字，把该名字也存入符号表，并返回该条目的地址。过程emit将其参数写到输出文件上。emit的参数构成一个三地址语句；变量nextstat给出在输出序列中下一个三地址语句的序号，emit在产生每个三地址语句后将nextstat加1。我们给relop以属性op，用来确定该关系算符究竟代表哪个关系运算。E.true，E.falsen和S.next都是三地址语句的标号，它们都是继承属性.。E.true和E.false分别表示E为真和为假时控制流应该转向的标号，这两个属性由E的上下文决定；S.next表示执行完S后应该执行的第一个三地址语句的标号，它也是由S的上下文决定语法分析方法描述开始时，将#和文法开始符号放入栈底。总控程序在任何时候都是根据栈顶符号X和当前的输入符号进行工作的，它与文法无关总控程序根据现行栈顶符号X和当前输入符号a，执行下列三种动作之一:1.若X＝a＝‘＃’，则宣布分析成功，停止分析。2.若X＝a‘＃’，则把X从STACK栈顶逐出，让指针指向下一个输入符号。3.若X是一个非终结符，则查看分析表M。若M[X，a]中存放着关于X的一个产生式，把X逐出STACK栈顶，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为，则意味不推什么东西进栈)。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作。若M[X，a]中存放着“出错标志”，则调用出错诊察程序ERROR。四、详细设计4.1语法规则定义的文法，如下：（0）Z---S（1）S---AB（2）A----CDE（3）C---void（4）D---main（5）E---()（6）B---{F}（7）F---GF（8）F---G（9）G---HIJ（10）H--int（11）I--KLM（12）K--character（13）L--=（14）M---num（15）J--;4.2程序流程图语法分析是编译程序的核心部分,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠错工作.法分析的方法有多种多样，常用的方法有递归子程序方法、运算符优先数法、状态矩阵法、LL（K）方法和LR（K）方法。归纳起来，大体上可分为两大类，即自顶向下分析方法和自底向上分析方法.Syntax进行语法分析.对于语法分析，这里采用LR(1)分析法，判断程序是否满足规定的结构.构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。4.3基本树形结构：if语句：while语句：for循环语句：if语句表达式语句语句while语句表达式语句表达式语句表达式for语句表达式复合语句：五、实验结果要编译的文件：词法分析：语句复合语句语句语句声明输出的四元式：六、心得体会这段时间的课程设计让我知道计算机将高级语言翻译成机器语言的过程，并且体会到了中间的设计分析处理过程，再一次熟悉了C语言的编写。也学到了许多课本上没写的东西，在实验的编写中有许多的坎坷，但是在大家集体和老师的帮助下，都慢慢的克服，也没有什么困难是不可克服的！经过这个实验，也深入体会到计算机的内部世界，进一步的摸清楚计算机的构架。为以后的学习工作再一次奠定了基础，受益匪浅！七、源代码#includeiostream.h#includefstream.h#includestring.h#includeiomanip.h#includemalloc.henumkeyword{$right_paren,$left_paren,$mul,$div,$add,$sub,$fenhao,$equal,$IF,$THEN,$ELSE,$greater,$less,$id,$num,$end};//关键字的枚举typedefstructToken{keywordtype;charch;}Token;//定义的token结构typedefenum{JUMP,JG,JL,equal,END,add,mul,sub,div}OpKind;//操作符定义为opkindtypedefstruct{intlabel;//标号OpKindop;//操作符charpar1,par2;//操作数union{charresult;//结果intaddress;//地址};}Quad;//四元式入口#defineMAX_TOKEN256//Token表大小#defineMAX_QUAD256//四元式数组大小Tokentokentable[MAX_TOKEN];Quadquad[MAX_QUAD];inttoken_index;//token表索引inttotal_len;//token表有效长度intquad_len;//四元式表有效长度intquad_index;//四元式索引Tokencur;Tokenqueue[10];intlabel,k,one;//标记接口charcurchar;//存储当前待比较字符charcurtocmp;//存储当前栈顶字符ifstreamins;inttrueadd,falseadd,end;inttable[5][8]={{1,0,0,0,0,1,0,0},{0,1,1,0,0,0,1,1},{1,0,0,0,0,1,0,0},{0,1,1,1,1,0,1,1},{1,0,0,0,0,1,0,0}};//存储预测分析表，1为有产生式，0为没有inti,j;intflag;structLchar{charchar_ch;structLchar*next;}Lchar,*temp,*top,*base;intright;//定义开关项boolinitialize(charfilename[255]);//文件打开初始化boolaccidence();//词法分析voidprint();//输出单词表voidbackpath(int,int);//回填出口voidERROR();voidsentence();//分析语句voidboolean();//分析E-idid|idid语句boolnexttoken();//读下一单词charnewchar();voidpush();//进队列chardosome(void);//算法函数voidpushs(charpchar);//入栈函数voidpop(void);//出栈函数voiddoforpush(int