编译原理课程设计报告

编译原理课程设计报告软件学院05级学号：20054451姓名：辛华时间：2007年7月25日一、词法分析1、实验目的编程实现词法分析程序，加深理解对词法分析原理。2、实验要求a、识别出特殊符号（用顿号隔开），如=、+、-、*、/、、、=、=、==、!=、;、:、,、{、}、[、]、(、)等b、识别出关键字，如if;then;while;do;end;for等c、识别其它标记ID和NUM，并通过以下正规式定义其他标记：ID-letter(letter|digit)letter-a|b...|z|A|B...|ZNUM-digitdigit*digit-0|1...|93、算法思路：本程序每次判断均连续输入几个的词，不同的词之间用“空格”隔开，因为所输入的字符串中含有“空格”，故在输入的时候启用文本监视器，利用字符串解析器扫描所输入的字符串，以逗号，空格，分号分开，以java.util包中的模式匹配生成文法和保留字对每个token进行分析，测试其匹配的模式，把它们区分开来4、程序流程图主程序流程图NY出错是否输入结束字符？输出判断结果子程序扫描置初值开始扫描程序流程图NYYNYNYNYN5．运行环境JDK6.0实验二：LL1语法判断一、实验目要求：自定义一个文法集，输入文法产生式，计算文法的FIRST，FOLLOW和SELECT集合，利用SELECT集合构造预测分析表，接着用预测分析程序，栈和预测分析表对输入串进行分开始往下个字符扫描输出判断结果是否关键字？是否是结束字符？把产生式右部反序进栈结束把’#’和文法开始符压入分析栈；当前输入符送a是否数字？是否空格？析，给出分析过程。二、设计思想：设计算法实现：（1）求FIRST集(用关系图法)（a）每个文法符号对应图中一个结点。（b）如果文法中有产生式AαXβ,且α=*ε，则从对应A的结点到对应X的结点连一条箭弧。（c）凡是从FIRST(A)的结点有路径可到达的终结符结点所标记的终结符都为FIRST(A的成员。（d）判定ε是否为某非终结符FIRST集的成员，若是则将加入该非终结符的FIRST集中。（2）求FOLLOW集对于G中的每一A∈VN，为构造FOLLOW（A），可反复使用如下的规则，直到每个FOLLOW集不再增大为止。(a)对于文法的开始符号S，令#∈FOLLOW（S）。(b)对于每一A→αBβ∈P，令FIRST（β）-{ε}=FOLLOW（B）。(c)对于每一A→αB∈P或A→αBβ∈P，且ε∈FIRST（β），则令FOLLOW（A）FOLLOW（B）。（3）求SELECT集若α≠*ε，则SELECT(A→α)=FIRST(α)若α=*ε，则SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)三、程序的详细分析过程及相应说明预测分析程序工作过程：四、程序结构（一）程序中的主要变量和存储结构说明（1）主要变量charnontermina[FZJ_NUM]={'E','D','T','S','F'}/*文法的非终结符集*/;chartermina[ZJF_NUM]={'i','+','*','(',')','#','$'};/*文法的终结符集*/;charvocab[ALL_NUM]={'E','D','T','S','F','i','+','*','(',')','#','$'}/*文法的单词表*/production*expression[20];/*存储产生式*/firfolfstfow[10];/*存储非终结符的FIRST集,FOLLOW集*/charnonrecycle;intrecyclenum;/*用来控制不出现重复计算同一个字符的FOLLOW集*/（2）存储结构/*---------------------------单链表--------------------------------*/typedefstructfirstnode{charvalue;structfirstnode*next;}firstset;/*---------------------------产生式,存有SELECT--------------------------------*/typedefstruct{charsource;charresult[10];firstset*selects;}production;上托栈顶符放入XNYYNNNNYY结束X∈VT?X=’#’?X=a?X=a?读下一输入符到aM[X,a]有产生式？结束出错预测分析程序工作过程Y/*---------------------------存放FIRST,FOLLOW--------------------------------*/typedefstruct{charvalue;firstset*firsts;firstset*follows;intsuccess;}firfol;/*---------------------------边表结点--------------------------------*/typedefstructnode{intadjvex;structnode*next;}EdgeNode;/*---------------------------顶点表结点--------------------------------*/typedefstructvnode{charvertex;EdgeNode*firstedge;}VertexNode;typedefVertexNodeAdjList[20];/*---------------------------邻接表--------------------------------*/typedefstruct{AdjListadjlist;intn,e;}ALGraph;ALGraph*T;/*---------------------------栈--------------------------------*/typedefstructStack{charstack[MAX_STACK];intindex;}STACK,*pSTACK;（二）函数功能介绍ALGraph*CreateALGraph(ALGraph*G)建立有向图的邻接表存储DFSAL(ALGraph*G,inti)深度优先搜索intsearch_position(charc,chara[])查找字符在数组的位置intisnontermina(charx)判断是否为非终结符intistermina(charx)判断是否为终结符intisunempty(charc)判断是否能推出空insert_first(firstset*L,charc)将某个字符插入到单链表中去intsearch_first(firstset*L,charc)判断某个字符是否在单链表中firstset*union_set(firstset*L,firstset*T)合并两个单链表follow(charc)求FollowSetfirstsetselect()求SelectSetfirst(charc)求FirstSetisLL1()判断某文法是否为LL1intisparalla(firstset*L,firstset*T)判断两个单链表是否有交集voidprintstack(pSTACKstack)voidinitialization()voidprinttable()intisfull(pSTACKstack)voidpush(pSTACKstack,chars)voidpop(pSTACKstack)voidanalyse()voidsearchtable_anddo(charAc,charIc)打印预测分析过程的堆栈的知识实验3算符优先1.实验目的：了解算符优先分析法、算符优先文法、优先关系表构造、可归约串的刻画与寻找方法、算符优先分析算法等内容。能够采用一种编程语言(C语言)实现简单的表达式求值程序；能够使用自己编写的分析程序对简单的表达式进行分析并得出正确结果。2.实验内容：用高级编程语言编制表达式求值程序并进行相应的错误处理。3.实验要求：1.对运算符的优先关系有明确的定义；2.编写的分析程序能够正确识别源程序中的数据和操作符；3.对于源程序中的词法错误，给出简单的错误提示，保证顺利完成整个表达式的分析；4.实验报告要求做出详细说明，说明词法分析程序的工作过程，说明错误处理的实现。4.实验内容：本次程序选择8个显式操作符和一个隐式操作符’#’，下面是本程序能处理的各个操作符的优先级列表，空出的部分为没有优先关系：()!*/+-==#(=)!*/+-==#=本程序已基本涉及了所有类型的运算，并且能处理输入的正负数的情况，错误处理主要在表达式分析部分，而求值部分没有细分各种错误，下面是对各种错误的处理宏定义：预定义预定义值说明ProcessSuccessful0处理正常结束NumberFormatError1数字格式错误UnidentifiableCharIncluded2包含不可识别的字符UnsupportedOperatorIncluded3包含不可识别的操作符UnmatchableExpression4表达式不匹配对于分析出的终结符，本程序用一个终结符节点表示，下面是其定义：structTerminalNode{intcategory;floatval;};其中category是终结符的类型，通过ValMask来判断是否为常量，如果为常量，则可以通过判断与ValLong或ValFloat是否相等来确定常量的类型，本来想通过联合体来存储常量的值，但后来考虑到程序会变得复杂，并降低可读性，因此最后不管是什么类型，一律当成float型常量进行运算，以降低复杂性，但是这样就不能检查到除零错误。上面是程序的预定义部分的说明，下面是程序的结构。本次程序编制与上一个词法分析程序有一定的相似性，主函数负责各个部分的协调工作，不直接参与具体的分析及求值过程，通过下面的程序流程图可以看出：本程序一共有4个函数：intmain(int,int[])，intisOperator(char),intGetTerminalList(char*,TerminalNode*,int&),intgetResult(TerminalNode*,int,int&)其中intisOperator(char)函数负责判断参数是否为合法操作符，intGetTerminalList(char*,TerminalNode*,int&)将参入的字符串参数分析并存入传入的指针参数所指的内存中，返回操作结果。intgetResult(TerminalNode*,int,int&)分析终结符列表，如果分析正常终止，将结果放到终结符列表的第一个元素位置，如果有错误就直接返回错误信息并返回。这里，处于节省内存空间的考虑，并且分析栈的栈顶始终比终结符列表中指向要处理的元素的位置索引小，可以在原终结符列表中处理，为了程序的可读性，加入TerminalNode*stack=tlist。5.运行环境Vc6.0实验四LR分析程序设计1实验目的（1）构造LR分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子；（2）了解LR分析方法是严格的从左向右扫描，和自底向上的语法分析方法。2实验内容和实验要求(1)LR分析器能够构造来识别所有能用上下文无关文法写的程序设计语言的结构。(2)LR分析方法是已知的最一般的无回溯，移进-归约方法，它能够和其他移进-归约方法一样有效地实现。(3)LR方法能分析的文法类是预测分析法能分析的文法类的真超集。3待分析的语法描述E-vI:TI-I,i|iT-r4算法描述4.1LR分析法基本思想LR