编译原理课程设计报告(共21页)

1、精选优质文档-倾情为你奉上编译原理课程设计报告软件学院05级学号： 姓名：辛华时间：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 . | Z NUM - d

2、igit digit* digit - 0 | 1 . | 93、算法思路：本程序每次判断均连续输入几个的词，不同的词之间用“空格”隔开，因为所输入的字符串中含有“空格”，故在输入的时候启用文本监视器，利用字符串解析器扫描所输入的字符串，以逗号，空格，分号分开，以java.util包中的 模式匹配生成文法和保留字对每个token进行分析，测试其匹配的模式，把它们区分开来4、程序流程图主程序流程图 开 始 置 初 值 子程序扫描 输出判断结果是否输入结束字 符？ N Y 结 束 开 始 扫描程序流程图往下个字符扫描 是否空格？ N是否是结束字 符？ Y Y N是否关键字？ Y N 是否数字？ Y

3、 N是否运算符？ Y N 无 法 识 别 输出判断结果 结 束5运行环境 JDK6.0实验二：LL1语法判断一、 实验目要求：自定义一个文法集，输入文法产生式，计算文法的FIRST，FOLLOW和SELECT集合，利用SELECT集合构造预测分析表，接着用预测分析程序，栈 和预测分析表对输入串进行分析，给出分析过程。二、设计思想： 设计算法实现： （1）求FIRST集(用关系图法) （a）每个文法符号对应图中一个结点。 （b）如果文法中有产生式AX,且 =* ，则从对应A的结点到对应X的结点连一条箭弧。 （c）凡是从FIRST(A)的结点有路径可到达的终结符结点所标记的终结符都为FIRST(A

4、的成员。 （d）判定是否为某非终结符FIRST集的成员，若是则将加入该非终结符的FIRST集中。（2）求FOLLOW集 对于G中的每一AVN，为构造FOLLOW（A），可反复使用如下的规则，直到每个FOLLOW集不再增大为止。(a) 对于文法的开始符号S，令#FOLLOW（S）。(b) 对于每一ABP，令FIRST（）- = FOLLOW（B）。 (c) 对于每一ABP或ABP，且FIRST（），则令FOLLOW（A） FOLLOW（B）。（3）求SELECT集 若*，则SELECT(A)=FIRST()若=*，则SELECT(A)=(FIRST()-)FOLLOW(A)三、程序的详细分析过程

5、及相应说明预测分析程序工作过程： 上托栈顶符放入XNYYNNNNY Y把#和文法开始符压入分析栈； 当前输入符送a把产生式右部反序进栈XVT ?X=# ? X=a ?X=a?读下一输入符到aMX,a有产生式？出错结束出错预测分析程序工作过程Y四、程序结构 （一）程序中的主要变量和存储结构说明 （1）主要变量char nonterminaFZJ_NUM=E,D,T,S,F /* 文法的非终结符集*/;char terminaZJF_NUM=i,+,*,(,),#,$; /* 文法的终结符集*/;char vocabALL_NUM=E,D,T,S,F,i,+,*,(,),#,$ /* 文法的单词表

6、*/production *expression20; /* 存储产生式 */firfol fstfow10; /* 存储非终结符的FIRST集, FOLLOW集*/char nonrecycle;int recyclenum; /* 用来控制不出现重复计算同一个字符的FOLLOW集*/（2）存储结构/*-单链表-*/typedef struct firstnode char value; struct firstnode *next;firstset;/*-产生式,存有SELECT-*/typedef struct char source; char result10; firstset *

7、selects; production;/*-存放FIRST ,FOLLOW-*/typedef struct char value; firstset *firsts; firstset *follows; int success;firfol;/*-边表结点-*/ typedef struct node int adjvex; struct node * next; EdgeNode;/*-顶点表结点-*/ typedef struct vnode char vertex; EdgeNode * firstedge; VertexNode; typedef VertexNode AdjLi

8、st20;/*-邻接表-*/ typedef structAdjList adjlist; int n,e; ALGraph; ALGraph *T;/*- 栈-*/typedef struct Stack char stackMAX_STACK;int index; STACK,*pSTACK;（二）函数功能介绍ALGraph *CreateALGraph(ALGraph *G)建立有向图的邻接表存储DFSAL(ALGraph *G,int i)深度优先搜索 int search_position(char c,char a) 查找字符在数组的位置int isnontermina(char

9、x) 判断是否为非终结符int istermina(char x)判断是否为终结符int isunempty(char c) 判断是否能推出空insert_first(firstset *L,char c) 将某个字符插入到单链表中去int search_first(firstset *L,char c)判断某个字符是否在单链表中firstset *union_set(firstset *L,firstset *T) 合并两个单链表follow (char c)求Follow Setfirstset select() 求Select Setfirst(char c) 求First SetisL

10、L1() 判断某文法是否为LL1int isparalla(firstset *L,firstset *T) 判断两个单链表是否有交集void printstack(pSTACK stack)void initialization()void printtable()int isfull(pSTACK stack)void push(pSTACK stack, char s)void pop(pSTACK stack)void analyse()void searchtable_anddo(char Ac,char Ic) 打印预测分析过程的堆栈的知识实验3 算符优先1.实验目的：了解算符优先

11、分析法、算符优先文法、优先关系表构造、可归约串的刻画与寻找方法、算符优先分析算法等内容。能够采用一种编程语言(C语言)实现简单的表达式求值程序；能够使用自己编写的分析程序对简单的表达式进行分析并得出正确结果。2.实验内容：用高级编程语言编制表达式求值程序并进行相应的错误处理。3.实验要求：1. 对运算符的优先关系有明确的定义；2. 编写的分析程序能够正确识别源程序中的数据和操作符；3. 对于源程序中的词法错误，给出简单的错误提示，保证顺利完成整个表达式的分析；4. 实验报告要求做出详细说明，说明词法分析程序的工作过程，说明错误处理的实现。4.实验内容：本次程序选择8个显式操作符和一个隐式操作符

12、#，下面是本程序能处理的各个操作符的优先级列表，空出的部分为没有优先关系：()!*/+-=#(=!*/+-=#vI:TI-I,i|iT-r4算法描述4.1 LR分析法基本思想 LR分析法是一种能够根据分析栈中的文法符号串（状态）和向右顺序查看第k个输入字符就能够唯一确定LR（k）分析器的动作是移进还是用哪一条产生式归约的分析方法。采用LR（0）分析法进行本次实验，即无需向前查看输入符号就能够确定分析器的动作。4.2实现方法LR（0）分析器由三个部分组成：(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表，不同的文法分析表将不同，同一个文法采用的LR分析器不同

13、时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。由于它是总控程序的依据，所以在程序的第一部分就已经定义好。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。(4)LR分析器及时察觉语法错误,快到自左向右扫描输入的最大可能。为了使一个文法是LR的，只要保证当句柄出现在栈顶时，自左向右扫描的移进-归约分析器能够及时识别它便足够了。当句柄出现在栈顶时，LR分析器必须要扫描整个栈就可以知道这一点，栈顶的状态符号包含了所需要的一切信息。如果仅知道栈内的文法符号就能确定栈顶是什么

14、句柄。由于LR分析表的转移函数本质上就是这样的有限自动机，因为，如果这个识别句柄的有限自动机自底向上读栈中的文法符号的话，它达到的状态正是这时栈顶的状态符号所表示的状态，所以，LR分析器可以从栈顶的状态确定它需要从栈中了解的一切。 4.3算法分析 SP为栈指针，Si为状态栈，Xi为文法符号栈。状态转换表用GOTOi，X=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。ACTIONi，a规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：(1)移进：actioni，a= Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。(2)归约：

15、actioni，a=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A-B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTOi,A移进状态栈，其中i为修改指针后的栈顶状态。(3)接受acc:当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是#，则为分析成功。(4)报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。5 总控程序框图运行环境VC6.0实验五 中间代码生成1题目：设计一个语法制导翻译器，将算术表达式

16、翻译成四元式。2设计思想： 设置堆栈，将字符和预算符号分别存储到堆栈当中，并且设置中间变量存储中间结果，再一一从堆栈中将符号和预算符号取出，经过处理进行输出，形成四元式。3运行环境VC6.0最终实验设计Pl0编译器运行环境 JDK6.0实验目的把语法分析，词法分析，翻译成汇编指令联合在一起需求说明PL/0文法的巴斯科范式表示 := .:= := const,;:= =:= := |:= var, ;:= ;:= procedure;:= | := := := +|-:= := | ( ) := +|-:= *|/:= |odd:= =|=:= ifthen:= whiledo := call

17、:= begin;end:= read ( , ) := write ( , ) := a|b|c|d.x|y|z := 0|1|2|3.8|91. 语法描述图 程序语法描述图分程序语法描述图语句语法描述条件语句描述图表达式语法描述项语法描述因子语法描述2. P-CODE指令系统Pcode代码是一个假想栈式计算机汇编语言，它不依赖于任何实际计算机，其指令格式如下：fla其中f为功能码；l表示层次差，即变量或过程被引用的分程序与说明该变量或过程的分程序之间的层次差；a的含义对不同的指令有所区别，可以是常数值、位移量、操作符代码等。目标指令有8条：1LIT0a-a为常数a进栈2LODlal为调用层

18、与说明层的层差a为变量在所说明层中的相对位置变量进栈3STOlal为调用层与说明层的层差a为变量在所说明层中的相对位置栈顶的内容给变量4CALlal为层差a为被调用过程的目标程序入口地址调用过程5INT0a-a为开辟的单元个数为被调用的过程在栈中开辟数据区6JMP0a-a为转向地址无条件转移7JPC0a-a为转向地址栈顶布尔值非零时转移8OPRlal为层差a为操作符编码栈顶与次栈顶的内容进行运算，结果放次栈顶PL/0编译程序的结构PL/0语言的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。PL/0的编译程序和目标程序的解释执行程序都是用JAVA

19、语言书写的，因此PL/0语言可在配备JAVA语言的任何机器上实现。其编译过程采用一趟扫描方式，以语法分析类为核心，词法分析和代码生成类都作为一个独立的类，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需要生成相应的目标代码时，则调用代码生成程序。用表格管理程序建立变量、常量和过程表示符的说明与引用之间的信息联系。用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错位性质。当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序的要求输入数据和输出运行结果。PL/0的各类及其方法的功能简单描述 此编译器采用JAVA语言编写，共采用

20、了七个类，38个方法（函数），其中pl0类为main方法所在的类，是整个编译器进行的整体框架，YuFaAnalyse类为编译器的语法分析类，为整个程序的核心所在。PL/0的各类及其方法的功能简单描述见下面图片（来自project截图）PL/0编译程序的符号表结构编译程序的符号表结构如下所示，值得注意的是，与课本上符号表不同的是，每个过程声明后紧跟着一个空符号，其adr属性存放过程的入口代码地址PL/0编译程序的运行栈结构SL静态链：它指向定义该过程的直接外接过程的数据段基地址；DL 动态链：它指向调用该过程前正在运行过程的数据段基地址；RA 返回地址：记录调用该过程是目标程序的断点，即当时程序

21、的地址寄存器P的值，也就是调用过程指令的下一条指令的地址。PL/0编译程序给变量分配的地址只是确定变量在数据段内的相对位置。对每个过程从3开始顺序增加。3以前的三个单元为上面指出的三个联系单元。因此静态连接的作用是当一个过程引用包围它的过程所定义的标识符时，首先沿静态链跳过个数为层差的数据段，找到定义该标识符过程的数据段基地址，再加上所给标识符分配的相对位置，就得到该标识符在整个数据栈中的绝对位置。动态链和返回地址的作用是当一个过程结束后，为恢复调用该过程前的执行状态而设置的。PL/0编译程序的出错信息编号及描述0 ,缺少左括号1 ,非法字符：赋值符号:=2 ,等号后的字符为非法字符3 ,缺少等号4 ,声明过程中遇到的字符不是标识符5 ,缺少分号6 ,非法语句7 ,整数大小越界8 ,整数位数越界9 ,缺少右括号 10 ,语句和语句之间没有分号11 ,标识符不存在12 ,标识符不是变量名13 ,缺少赋值符号14 ,call后不是标识符15 ,call后不是过程名16 ,if后不是then17 ,没有遇到end18 ,while循环缺少do19 ,标