/ 21 编译原理课程设计报告 软件学院05级 学号： 20054451 姓名：辛华 时间：2007年7月25日
/ 21 一、词法分析 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 -> digit digit* digit -> 0 | 1 ... | 9 3、算法思路： 本程序每次判断均连续输入几个的词，不同的词之间用“空格”隔开，因为所输入的字符串中含有“空格”，故在输入的时候启用文本监视器，利用字符串解析器扫描所输入的字符串，以逗号，空格，分号分开，以java.util包中的 模式匹配生成文法和保留字 对每个token进行分析，测试其匹配的模式，把它们区分开来 4、程序流程图 主程序流程图 N Y 结 束 是否输入结束字 符？ 输出判断结果 子程序扫描 置 初 值 开 始
/ 21 扫描程序流程图 N Y Y N Y N Y N Y N 5．运行环境 JDK6.0 实验二：LL1语法判断 一、实验目要求： 自定义一个文法集，输入文法产生式，计算文法的FIRST，FOLLOW和SELECT集合， 开 始 往下个字符扫描 输出判断结果 是否关键字？ 是否是结束字 符？ 是否运算符？ 结 束 无 法 识 别 是否数字？ 是否空格？
/ 21 利用SELECT集合构造预测分析表，接着用预测分析程序，栈 和预测分析表对输入串进行分析，给出分析过程。 二、设计思想： 设计算法实现： （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) 三、程序的详细分析过程及相应说明 预测分析程序工作过程：
/ 21 四、程序结构 （一）程序中的主要变量和存储结构说明 （1）主要变量 char nontermina[FZJ_NUM]={'E','D','T','S','F'} /* 文法的非终结符集*/; char termina[ZJF_NUM]={'i','+','*','(',')','#','$'}; /* 文法的终结符集*/; char vocab[ALL_NUM]={'E','D','T','S','F','i','+','*','(',')','#','$'} /* 文法的单词表*/ production *expression[20]; /* 存储产生式 */ firfol fstfow[10]; /* 存储非终结符的FIRST集, FOLLOW集*/ char nonrecycle; int recyclenum; /* 用来控制不出现重复计算同一个字符的FOLLOW集*/ （2）存储结构 /*---------------------------单链表--------------------------------*/ typedef struct firstnode { char value; struct firstnode *next; }firstset; /*---------------------------产生式,存有SELECT--------------------------------*/ typedef struct { char source; char result[10]; firstset *selects; }production; 上托栈顶符放入X N Y Y N N N N Y Y 把’#’和文法开始符压入分析栈； 当前输入符送a 把产生式右部反序进栈 X∈VT ? X=’#’ ? X=a ? X=a? 读下一输入符到a M[X,a]有产生式？ 出错 结束 出错 预测分析程序工作过程 Y
/ 21 /*---------------------------存放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 AdjList[20]; /*---------------------------邻接表--------------------------------*/ typedef struct{ AdjList adjlist; int n,e; }ALGraph; ALGraph *T; /*--------------------------- 栈--------------------------------*/ typedef struct Stack { char stack[MAX_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)
/ 21 判断是否能推出空 insert_first(firstset *L,char c) 将某个字符插入到单链表中去 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 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.实验目的： 了解算符优先分析法、算符优先文法、优先关系表构造、可归约串的刻画与寻找方法、算符优先分析算法等内容。能够采用一种编程语言(C语言)实现简单的表达式求值程序；能够使用自己编写的分析程序对简单的表达式进行分析并得出正确结果。 2.实验内容： 用高级编程语言编制表达式求值程序并进行相应的错误处理。 3.实验要求： 1. 对运算符的优先关系有明确的定义； 2. 编写的分析程序能够正确识别源程序中的数据和操作符；
/ 21 3. 对于源程序中的词法错误，给出简单的错误提示，保证顺利完成整个表达式的分析； 4. 实验报告要求做出详细说明，说明词法分析程序的工作过程，说明错误处理的实现。 4.实验内容： 本次程序选择8个显式操作符和一个隐式操作符’#’，下面是本程序能处理的各个操作符的优先级列表，空出的部分为没有优先关系： ( ) ! * / + - == # ( < = < < < < < < ) > > > > > > > > ! < > < > > > > > > * < > < > > > > > > / < > < > > > > > > + < > < < < > > > > - < > < < < > > > > == < > < < < < < > > # < < < < < < < = 本程序已基本涉及了所有类型的运算，并且能处理输入的正负数的情况，错误处理主要在表达式分析部分，而求值部分没有细分各种错误，下面是对各种错误的处理宏定义： 预定义 预定义值 说明 ProcessSuccessful 0 处理正常结束 NumberFormatError 1 数字格式错误 UnidentifiableCharIncluded 2 包含不可识别的字符 UnsupportedOperatorIncluded 3 包含不可识别的操作符 UnmatchableExpression 4 表达式不匹配 对于分析出的终结符，本程序用一个终结符节点表示，下面是其定义： struct TerminalNode{ int category; float val; }; 其中category是终结符的类型，通过ValMask来判断是否为常量，如果为常量，则可以通过判断与ValLong或ValFloat是否相等来确定常量的类型，本来想通过联合体来存储常量的值，但后来考虑到程序会变得复杂，并降低可读性，因此最后不管是什么类型，一律当成float型常量进行运算，以降低复杂性，但是这样就不能检查到除零错误。 上面是程序的预定义部分的说明，下面是程序的结构。本次程序编制与上一个词法分析程序有一定的相似
性，主函数负责各个部分的协调工作，不直接参与具体的分析及求值过程，通过下面的程序流程图可以看出：
/ 21 本程序一共有4个函数：int main(int,int[])，int isOperator(char), int GetTerminalList(char*,TerminalNode*,int&), int getResult(TerminalNode*,int,int&) 其中int isOperator(char)函数负责判断参数是否为合法操作符，int GetTerminalList(char*,TerminalNode*,int&)将参入的字符串参数分析并存入传入的指针参数所指的内存中，返回操作结果。int getResult(TerminalNode*,int,int&)分析终结符列表，如果分析正常终止，将结果放到终结符列表的第一个元素位置，如果有错误就直接返回错误信息并返回。这里，处于节省内存空间的考虑，并且分析栈的栈顶始终比终结符列表中指向要处理的元素的位置索引小，可以在原终结符列表中处理，为了程序的可读性，加入TerminalNode *stack = tlist。 5.运行环境 Vc6.0 实验四 LR分析程序设计 1实验目的 （1）构造LR 分析程序，利用它进行语法分析，判断给出的符号串是否为
/ 21 该文法识别的句子； （2）了解LR分析方法是严格的从左向右扫描，和自底向上的语法分析方法。 2实验内容和实验要求 (1)LR分析器能够构造来识别所有能用上下文无关文法写的程序设计语言的结构。 (2)LR分析方法是已知的最一般的无回溯，移进-归约方法，它能够和其他移进-归约方法一样有效地实现。 (3)LR方法能分析的文法类是预测分析法能分析的文法类的真超集。 3 待分析的语法描述 E->vI:T I->I,i|i T->r 4算法描述 4.1 LR分析法基本思想 LR分析法是一种能够根据分析栈中的文法符号串（状态）和向右顺序查看第k个输入字符就能够唯一确定LR（k）分析器的动作是移进还是用哪一条产生式归约的分析方法。 采用LR（0）分析法进行本次实验，即无需向前查看输入符号就能够确定分析器的动作。 4.2实现方法 LR（0）分析器由三个部分组成： (1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。 (2)分析表，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。由于它是总控程序的依据，所以在程序的第一部分就已经定义好。 (3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析器的动作就是由栈顶状态和当前输入符号所决定。
/ 21 (4)LR分析器及时察觉语法错误,快到自左向右扫描输入的最大可能。 为了使一个文法是LR的，只要保证当句柄出现在栈顶时，自左向右扫描的移进-归约分析器能够及时识别它便足够了。当句柄出现在栈顶
时，LR分析器必须要扫描整个栈就可以知道这一点，栈顶的状态符号包含了所需要的一切信息。如果仅知道栈内的文法符号就能确定栈顶是什么句柄。由于LR分析表的转移函数本质上就是这样的有限自动机，因为，如果这个识别句柄的有限自动机自底向上读栈中的文法符号的话，它达到的状态正是这时栈顶的状态符号所表示的状态，所以，LR分析器可以从栈顶的状态确定它需要从栈中了解的一切。 4.3算法分析 SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。 ACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能： (1)移进： action[i，a]= Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。 (2)归约： action[i，a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A-B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。 (3)接受acc: 当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。 (4)报错: 当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。
/ 21 5 总控程序框图 运行环境VC6.0 实验五 中间代码生成 1．题目： 设计一个语法制导翻译器，将算术表达式翻译成四元式。 2．设计思想： 设置堆栈，将字符和预算符号分别存储到堆栈当中，并且设置中间变量存储中间结果，再一一从堆栈中将符号和预算符号取出，经过处理进行输出，形成四元式。 3．运行环境 VC6.0
/ 21 最终实验设计 Pl0编译器 运行环境 JDK6.0 实验目的 把语法分析，词法分析，翻译成汇编指令联合在一起 需求说明 PL/0文法的巴斯科范式表示 <程序>::= <分程序>. <分程序>::= [<常量说明部分>][<变量说明部分>][<过程说明部分>]<语句> <常量说明部分>::= const<常量定义>{,<常量定义>}; <常量定义>::= <标识符>=<无符号整数> <无符号整数>::= <数字>{<数字>} <标识符>::= <字母>{<字母>|<数字>} <变量说明部分>::= var<标识符>{, <标识符>}; <过程说明部分>::= <过程首部><分程序>{;<过程说明部分>} <过程首部>::= procedure<标识符>; <语句> ::= <赋值语句>|<条件语句>|<当循环语句>|<过程调用语句> |<复合语句>|<读语句>|<写语句>|<空> <赋值语句>::= <标识符> := <表达式> <表达式> ::= [+|-]<项>{<加法运算符><项>} <项>::= <因子>
{<乘法运算符><因子>} <因子>::= <标识符>|<无符号整数>| ‘ ( ’ <表达式> ‘ ) ’ <加法运算符>::= +|- <乘法运算符>::= *|/ <条件>::= <表达式><关系运算符><表达式>|odd<表达式> <关系运算符>::= =|<>|<|<=|>|>= <条件语句>::= if<条件>then<语句> <当循环语句>::= while<条件>do<语句> <过程调用语句>::= call<标识符> <复合语句>::= begin<语句>{;<语句>}end <读语句>::= read ‘ ( ’<标识符>{, <标识符>} ‘ ) ’ <写语句>::= write ‘ ( ’<表达式>{, <表达式>} ‘ ) ’ <字母>::= a|b|c|d…..x|y|z <数字>::= 0|1|2|3…...8|9 1. 语法描述图
/ 21 程序语法描述图 分程序语法描述图
/ 21 语句语法描述 条件语句描述图 表达式语法描述
/ 21 项语法描述 因子语法描述 2. P-CODE指令系统 P—code代码是一个假想栈式计算机汇编语言，它不依赖于任何实际计算机，其指令格式如下： f l a 其中f为功能码；l表示层次差，即变量或过程被引用的分程序与说明该变量或过程的分程序之间的层次差；a的含义对不同的指令有所区别，可以是常数值、位移量、操作符代码等。 目标指令有8条： 1 LIT 0 a --------------- a为常数 a进栈 2 LOD l a l为调用层与说明层的层差 a为变量在所说明层中的相对位置 变量进栈 3 STO l a l为调用层与说明层的层差 a为变量在所说明层中的相对位置 栈顶的内容给变量 4 CAL l a l为层差 a为被调用过程的目标程序入口地址 调用过程 5 INT 0 a ------------------- a为开辟的单元个数 为被调用的过程在栈中开辟数据区 6 JMP 0 a ------------------- a为转向地址 无条件转移 7 JPC 0 a ------------------- a为转向地址 栈顶布尔值非零时转移 8 OPR l a l为层差 a为操作符编码 栈顶与次栈顶的内容进行运算，结果放次栈顶 PL/0编译程序的结构 PL/0语言的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。
/ 21 PL/0的编译程序和目标程序的解释执行程序都是用JAVA语言书写的，因此PL/0语言可在配备JAVA语言的任何机器上实现。 其编译过程采用一趟扫描方式，以语法分析类为核心，词法分析和代码生成类都作为一个独立的类，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需要生成相应的目标代码时，则调用代码生成程序。 用表格管理程序建立变量、常量和过程表示符的说明与引用之间的信息联系。 用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错位性质。 当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序的要求输入数据和输出运行结果。 PL/0的各类及其方法的功能简单描
述 此编译器采用JAVA语言编写，共采用了七个类，38个方法（函数），其中pl0类为main方法所在的类，是整个编译器进行的整体框架，YuFaAnalyse类为编译器的语法分析类，为整个程序的核心所在。 PL/0的各类及其方法的功能简单描述见下面图片（来自project截图）
/ 21
/ 21 PL/0编译程序的符号表结构 编译程序的符号表结构如下所示，值得注意的是，与课本上符号表不同的是，每个过程声明后紧跟着一个空符号，其adr属性存放过程的入口代码地址 PL/0编译程序的运行栈结构
/ 21 SL静态链：它指向定义该过程的直接外接过程的数据段基地址； DL 动态链：它指向调用该过程前正在运行过程的数据段基地址； RA 返回地址：记录调用该过程是目标程序的断点，即当时程序的地址寄存器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后不是then" 17 ,"没有遇到end" 18 ,"while循环缺少do" 19 ,"标识符长度越界" 20 ,"缺少逻辑运算符" 21 ,"标识符为过程名" 22 ,"缺少右括号"
/ 21 实验感想 经过一个多月的辛苦劳动，终于看到了自己的结果，虽然写的仅仅是较简单的PL0的编译器，但毕竟完全是自己一条条代码写出来，pl0也是自己学的，毕竟没学过，一个个错误调试出来的。心里还是蛮有成功感的。 虽然和金茂忠老师学习了半年的编译原理课程，感觉很简单的。但真到了自己独自做一个编译器的时候，立刻就傻眼了。根本不知道从哪儿开始。只好看书上的源代码，一条一条的，连每个字符都要看懂，否则就没法理解。就是现在想起那些从程序开头一下子就传到程序尾的变量，还是
头疼不已。 虽然学过java语言，却是很少练习，到了做东西的时候，才发现自己是多么的无知。遇到解决不了的问题就查文档，发帖子问别人。在遭到别人很多鄙视（大家都说我的问题很无知）的目光后，终于解决了所有的问题。 好不容易写了1000多代码，然后开始测试，于是开始了更为让人饶头的调试过程。 这简直比编程序还让人发疯，每出现一点错误，就要（在大概的位置）一条条测试，计算参数的值，计算数组指针的位置。有的时候不到50行代码，会出现100个错误，真是很无奈。 到现在终于明白真正的编译过程是这样的，不得不承认，仅仅学过不一定会掌握，实践才是最重要的！ 总结了几条经验： 1， 懂了不一定理解，理解了不一定做得出来。 2， 不要烦躁，尤其是在调试程序时。 3， 记得经常备份文件，否则不小心把写的代码搞坏了就绝望了。 4， 多写注释，这样调试时就容易很多。方便自己也方便别人。 5， 其实我得程序还是有些瑕疵的，比如说某些错误处理的定位不准确（差一行），嘿嘿，我知道错误出在哪儿，但就是不知道怎么改，这句话当我没说~~。