编译原理课程设计报告

1、编译原理课程设计报告软件学院05级学号：20054451姓名：辛华 时间：2007年7月25日一、词法分析1、实验目的编程实现词法分析程序，加深理解对词法分析原理。2、实验要求a、 识别出特殊符号（用顿号隔开），如=、+、-、*、/、=、=、！=、；、：、，、卜卜（、）等b、 识别出关键字，如if;the n;while;do;e nd;for等c、识别其它标记 ID和NUM，并通过以下正规式定义其他标记：ID - letter （ letter | digit ）letter - a | b . | z | A |B . | ZNUM - digit digit*digit - 0 | 1

2、. | 93、算法思路：本程序每次判断均连续输入几个的词，不同的词之间用“空格”隔开，因为所输入的字符串中含有“空格”，故在输入的时候启用文本监视器，利用字符串解析器扫描所输入的字符串，以逗号，空格，分号分开，以java.util 包中的模式匹配生成文法和保留字对每个token进行分析，测试其匹配的模式，把它们区分开来4、程序流程图主程序流程图扫描程序流程图5 .运行环境JDK6.0实验二：LL1语法判断、实验目要求：FIRST，FOLLOV和 SELECT集合,自定义一个文法集，输入文法产生式，计算文法的利用SELECT集合构造预测分析表， 接着用预测分析程序，栈 和预测分析表对输入串进行分

3、析，给出分析过程。二、设计思想：设计算法实现：(1) 求 FIRST 集( 用关系图法 )(a) 每个文法符号对应图中一个结点。(b) 如果文法中有产生式 A a X3 ,且a =* ,则从对应 A的结点到对应 X的 结点连一条箭弧。(c) 凡是从 FIRST(A)的结点有路径可到达的终结符结点所标记的终结符都为 FIRST(A 的成员。(d) 判定&是否为某非终结符FIRST集的成员，若是则将加入该非终结符的FIRST集中。(2) 求 FOLLOW对于G中的每一 A VN为构造FOLLO( A),可反复使用如下的规则，直到每个 FOLLOWI不再增大为止。(a) 对于文法的开始符号 S,令#

4、 FOLLOWS)。(b) 对于每一 AaP,令 FIRST (3) - e = FOLLOW (B)。(c) 对于每一 Aa B P或 Aa B3 卩，且& FIRST (3)，则令 FOLLO( A) FOLLOW( B)。(3) 求 SELECT集若aM * e,则SELECT(Aa )=FIRST( a )若 a =* e,贝USELECT(Aa )=(FIRST( a )- e ) U FOLLOW(A)三、程序的详细分析过程及相应说明预测分析程序工作过程：把轴文法开始符压入分析栈; 当前输入符送a把产生式右部反序进栈YMX,a有产生式？N出错上托栈顶符放入XX Vt ?X= # ?

5、X=a ?X=a?丫读下一输入符到a出错Y结束预测分析程序工作过程四、程序结构(一)程序中的主要变量和存储结构说明(1)主要变量char non termi naFZJ_NUM=E,D,T,S,F /*文法的非终结符集 */;char terminaZJF_NUM=i,+,*,(,),#,$; /*文法的终结符集 */;char vocabALL_NUM=E,D,T,S,F,i,+,*,(,),#,$ /*文法的单词表 */production *expressio n20; /* 存储产生式 */firfol fstfow10; /*存储非终结符的FIRST 集，FOLLOW集 */char

6、 non recycle;intrecycle num; /*用来控制不出现重复计算同一个字符的FOLLOW集 */(2)存储结构/* 单链表*/typedef struct first nodechar value;struct first node *n ext;firstset;/* 产生式,存有SELECT*/typedef structchar source;char result10;firstset *selects;product ion;/* 存放 FIRST ,FOLLOW*/typedef structchar value;firstset *firsts;firstse

7、t *follows;int success;firfol;/* 边表结点 */typedef struct nodeint adjvex;struct node * next;EdgeNode;/* 顶点表结点 */typedef struct vnode char vertex;EdgeNode * firstedge;VertexNode;typedef VertexNode AdjList20;/* 邻接表 */typedef structAdjList adjlist;int n,e;ALGraph;ALGraph *T;/* 栈*/typedef struct Stackchar

8、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 x)判断是否为非终结符int istermina(char x)判断是否为终结符int isunempty(char c)判断是否能推出空 insert_first(firstset *L,char c)将某个字符插入

9、到单链表中去 int search_first(firstset *L,char c)判断某个字符是否在单链表中 firstset *union_set(firstset *L,firstset *T) 合并两个单链表 follow (char c)求 Follow Set firstset select()求 Select Set first(char c)求 First Set isLL1()判断某文法是否为 LL1 int isparalla(firstset *L,firstset *T)判断两个单链表是否有交集 void printstack(pSTACK stack) void i

10、nitialization() 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. 实验目的：了解算符优先分析法、 算符优先文法、 优先关系表构造、 可归约串的刻画与 寻找方法、算符优先分析算法等内容。能够采用一种编程语言 （C 语言）实现简单 的表达式求值程序； 能够使用自己编写的分析程序对简

11、单的表达式进行分析并得 出正确结果。2. 实验内容：用高级编程语言编制表达式求值程序并进行相应的错误处理。3. 实验要求：1. 对运算符的优先关系有明确的定义；2. 编写的分析程序能够正确识别源程序中的数据和操作符；3. 对于源程序中的词法错误，给出简单的错误提示，保证顺利完成整个表达式 的分析；4. 实验报告要求做出详细说明，说明词法分析程序的工作过程，说明错误处理 的实现。4. 实验内容：本次程序选择8个显式操作符和一个隐式操作符下面是本程序能处理 的各个操作符的优先级列表，空出的部分为没有优先关系：()*/+-=#(=!*/+-=#vI:TI-I,i|iT-r4 算法描述4.1 LR分析

12、法基本思想LR 分析法是一种能够根据分析栈中的文法符号串(状态)和向右顺序查 看第k个输入字符就能够唯一确定LR( k)分析器的动作是移进还是用哪一条 产生式归约的分析方法。采用 LR( 0)分析法进行本次实验，即无需向前查看输入符号就能够确定 分析器的动作。4.2 实现方法LR( 0)分析器由三个部分组成：(1) 总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2) 分析表，不同的文法分析表将不同，同一个文法采用的 LR分析器不同时， 分析表将不同，分析表又可以分为动作表(ACTION和状态转换(GOTO表两个 部分，它们都可用二维数组表示。 由于它是总控程序的依据，

13、所以在程序的第一 部分就已经定义好。(3) 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定(4) LR分析器及时察觉语法错误，快到自左向右扫描输入的最大可能。为了使一个文法是LR的，只要保证当句柄出现在栈顶时，自左向右扫描的 移进-归约分析器能够及时识别它便足够了。当句柄出现在栈顶时，LR分析器必须要扫描整个栈就可以知道这一点，栈顶的状态符号包含了所需要的一切信息。 如果仅知道栈内的文法符号就能确定栈顶是什么句柄。由于LR分析表的转移函数本质上就是这样的有限自动机，因为，如果这个识别句柄的有限自动机自底向 上读栈中的文法符号的话，它达到

14、的状态正是这时栈顶的状态符号所表示的状 态，所以，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 表示状态号。归约：actioni ，a=r k:当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有ApB的产生式，若B的长度为R(即|

15、B|=R)，则从状态栈和文法符号栈 中自顶向下去掉R个符号，即栈指针SP减去R,并把A移入文法符号栈内， j=GOTOi,A移进状态栈，其中i为修改指针后的栈顶状态。(3) 接受 acc:当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是#，则为分析成功。报错：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串5总控程序框图运行环境VC6.0实验五中间代码生成1题目设计一个语法制导翻译器，将算术表达式翻译成四元式。2.设计思想:设置堆栈，将字符和预算符号分别存储到堆栈当中，并且设置中间变量存储中间结果,再一一从堆栈中将符号

16、和预算符号取出，经过处理进行输出，形成四元式。3运行环境VC6.0最终实验设计Pl0 编译器运行环境 JDK6.0实验目的把语法分析，词法分析，翻译成汇编指令联合在一起需求说明PL/0 文法的巴斯科范式表示程序:= 分程序 .分程序 := 常量说明部分 变量说明部分 过程说明部分 语句 常量说明部分 := const 常量定义 , 常量定义 ;常量定义 := 标识符 =无符号整数 无符号整数 := 数字 数字 标识符 := 字母 字母|数字变量说明部分:= var标识符, 标识符;过程说明部分 := 过程首部分程序;过程说明部分 过程首部 :=procedurev标识符 ;语句 := 赋值语句

17、 |条件语句 |当循环语句 |过程调用语句 |复合语句|读语句|写语句|空赋值语句 := 标识符 := 表达式表达式:=+卜 项加法运算符 项项 := 因子乘法运算符 因子因子:=v标识符|无符号整数1（表达式）加法运算符：=+|-乘法运算符：=*|/条件:=v表达式 关系运算符 表达式|odd表达式V 关系运算符 :=| = | =条件语句:=if条件then语句v当循环语句:= whilev条件do语句V过程调用语句:=callv标识符v读语句:=read v写语句 :=writev 字母 :=a|b|c|dv数字 :=0|1|2|3v复合语句 :=beginv语句;v语句end标识符,

18、v标识符）表（ 达式, v 表达式 ）.x|y|z8|91. 语法描述图程序一分程序 一(T)程序语法描述图分程序分程序语法描述图吾旬ide nt条件项项语句语法描述条件语句描述图表这式裘迭式call : ident语句轰迭式表达式表达式表达式语法描述语旬/条件（面 y语句J语句2. P-CODE指令系统P code代码是一个假想栈式计算机汇编语言，它不依赖于任何实际计算机，其指令格 式如下：1Ia其中f为功能码；I表示层次差，即变量或过程被引用的分程序与说明该变量或过程的 分程序之间的层次差；a的含义对不同的指令有所区别，可以是常数值、位移量、操作符代 码等。目标指令有8条：1LIT0aa为

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

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

21、理程序诃梏分祈程序V语法分析程序代码生成程序岀错处理程序P1/0高言解軽执行聊序希出藪塞 表示數鬣潼-表示调用关系PL/0的各类及其方法的功能简单描述此编译器采用JAVA语言编写，共采用了七个类，38个方法（函数），其中pl0类为main 方法所在的类，是整个编译器进行的整体框架，YuFaAnalyse类为编译器的语法分析类，为整个程序的核心所在。PL/0的各类及其方法的功能简单描述见下面图片（来自 project截图）PLQ编译器用到的类及其方法功能简单介绍IB Uft主程序-teClass用于表示符号表中的符号（毎个髡号有ne, ki. rJ, level, adrSMft ）naaeCl

22、assO 方法mJl. 铁於构艇数setAcr 0 方法用于设置修攻某个符号对族的血属性 用于旻示错融行号1类型号 内容erro 0方驶底造因数CiTdjQdyse司激析类用于腳由川沪个“山Ci?aAr.alyse 0 方法嚨函数|框飜过紬文件名准立-个输入沆gellrroUf 0 方法用亍返酮尉祈说鬧个数嗣（）方法用于在湧文件中逮取一个符号佻C鳳讥）麟舟说（）卿的符麹合加个讥曲 lJ&A&alyse重点？ ? ? is法分析.别倔不眞了.自己看电YnJiAnalyseO 法初造函亂接校一个词法分折的对耒ge;Irr?SvTiber 0 方怯用于理亟齣分析时甦觸齢数printCode ()方法

23、显示生成的Fah代码uJyC方法十分洛序分飙相当亍“ckdcaratig()方法帶明vardeclarati on ()方迭翅声明mmO方法也f符号表position D 万法T查抚符号裏StktttiAtl 0j$法丽分析coiditiorOT 法黏分侨ex?ressicnO?法下表达式分祈tern 0方法项的分侨factor ()方法因子分析prmtihM()方法區踰躲（W（这个仅仅翩耐base 0方法:用钿遍磐卜的亦法imerprtO 方法下解品肝执孤心帰PL/O编译程序的符号表结构编译程序的符号表结构如下所示，值得注意的是，与课本上符号表不同的是，每个过程声明后紧跟着一个空符号，其ad

24、r属性存放过程的入口代码地址ENA騎容容容容容内内内内内内jiix my texIniHEHEA AKIND UAL 0 XI ND constant KINDKIND variable KI HD procedureKIND UAL 0LEUL ADF 8UfiL IE LEUL 0 RDP U0 0L LA nu u3 4R RD DA AUAL 0 LEUL 0 ADA 0LEUL 0 ADR 2PL/0编译程序的运行栈结构一 proccdmc A： pro-cedure B：pro ccdurc 程 序 体Ccall B：S序体Acall C tcall B;call A；的局部变童R

25、ADL t SL* fC的局部变量RADL *t SL* E的扃部变量RADL SLA的局部吏星RADL -* SL*f三理序变量区000左为程序结构.上为运行吋数据栈变化情况SL 静态链：它指向定义该过程的直接外接过程的数据段基地址；DL 动态链：它指向调用该过程前正在运行过程的数据段基地址；RA 返回地址：记录调用该过程是目标程序的断点，即当时程序的地址寄存器P 的值，也就是调用过程指令的下一条指令的地址。PL/0 编译程序给变量分配的地址只是确定变量在数据段内的相对位置。 对每个过程从 3 开始顺序增加。 3 以前的三个单元为上面指出的三个联系单元。因此静态连接的作用是当一 个过程引用包围它的过程所定义的标识符时， 首先沿静态链跳过个数为层差的数据段， 找到 定义该标识符过程的数据段基地址， 再加上所给标识符分配的相对位置， 就得到该标识符在 整个数据栈中的绝对位置。 动态链和返回地址的作用是当一个过程结束后， 为恢复调用该过 程前的执行状态而设置的。PL/0 编译程序的出错信息编号及描述0,缺少左括号 1, 非法字符：赋值符号 :=2,等号后的字符为非法字符 3, 缺少等号 4,声明过程中遇到的字符不是标识符5, 缺少分号 6, 非法语句 7, 整数大小越界 8, 整数位数越界 9, 缺少右括号 10, 语句和语句之间