编译原理课程设计.doc

学 院： 信息工程学院姓 名: 李 孟 洪班 级： 计科0601学 号： 061106115指导教师： 陈 宏 建完成时间： 2009.6.11 分数教师签名 一、课程设计的目的 编译原理课程兼有很强的理论性和实践性，是计算机专业的一门非常重要的专业基础课程，它在系统软件中占有十分重要的地位，是计算机专业学生的一门主修课。为了让学生能够更好地掌握编译原理的基本理论和编译程序构造的基本方法和技巧，融会贯通本课程所学专业理论知识，提高他们的软件设计能力，特设定该课程的课程设计，通过设计一个简单的PASCAL语言（EL语言）的编译程序，提高学生设计程序的能力，加深对编译理论知识的理解与应用。二、课程设计的任务课程设计是一项综合性实践环节，是对平时实验的一个补充，课程设计内容包括课程的主要理论知识，但由于编译的知识量较复杂而且综合性较强，因而对一个完整的编译程序不适合平时实验。通过课程设计可以达到综合设计编译程序的目的。本课程的课程设计要求学生编写一个完整的编译程序，包括词法分析器、语法分析器以及实现对简单程序设计语言中的逻辑运算表达式、算术运算表达式、赋值语句、IF语句、While语句以及dowhile语句进行编译，并生成中间代码和直接生汇编指令的代码生成器。三、课程设计方案编译器设计的编译程序涉及到编译中的四个阶段，它们的基本知识点如下：1) 词法分析程序的功能是输入源程序，输出单词符号。词法分析程序将依据语言词法规则，分析由字符组成的源程序，把它识别为一个一个具有独立意义的最小语法单位，即“单词”，并识、别出与其相关的属性，再转换成长度上统一的标准形式-属性字，最终将字符串形式的源程序改造成单词符号串形式的中间程序，以供其他部分使用。2) 语法分析程序在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。自上而下语法分析从识别符号出发，不断建立直接推导，试图构造一个最左推导序列，最终由它推导初与输入符号串相同的终结符号串。从语法树的角度看，自顶向下分析过程将以识别符号串为根结点，试图 向下构造一棵语法树，其末端结点符号串正好与输入符号串相同。3) 中间代码生成是将输入的经词法和语法分析过后的源程序翻译成中间四元式以便生成汇编指令。执行中间代码生成的程序为间代码生成器。4) 目标代码生成是将有中间代码生成器生成的四元式生成具体的机器指令序列或汇编代码。本课程设计只会生成汇编指令。四、课程设计详细分析1、词法分析器设计词法分析是编制一个读单词的过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。程序语言的单词符号一般分为五种：关键字（保留字/基本字）if、while、begin；标识符：常量名、变量名；常数：34、56.78、true、a、；运算符：+、-、*、/、and、or、.、；界限符：， ； （ ） /*。 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码，单词符号的属性值)。例如源程序为C语言。输入如下一段：main()int a=-5,b=4,j;if(a=b) j=a-b; else j=b-a；要求输出：（2，“main”）（5，“（”）（5，“）”）（5，”“）（1，”int”）（2，”a”）（4，”=”）（3，”-5”）（5，”,”）（2，”b”）（4，”=”）（3，”4”）（5，”,”）（2，”j”）（5，”;”）（1，”if”）（5，”（“）（2，”a”）（4，”=”）（2，”b”）（5，”）“）（2，”j”）（4，”=”）（2，”a”）（4，”-”）（2，”b”）（5，”;”）（1，”else”）（2，”j”）（4，”=”）（2，”b”）（4，”-”）（2，”a”）（5，”;”）（5，“”）构建关键字表：单词符号类号单词符号类号单词符号类号+3&14,25-4|15void26 *5=16int27/6(17float287)18char291122do33=12:23!34&13;24main35词法分析的设计方法有手工构造方法和程序自动生成方法两种：1. 词法分析程序的手工构造方法：自然语言描述 直接构造 正规文法 转换规则NFA 子集法 DFA 状态集的划分 最小化DFA正规表达式 转换规则 词法分析程序 编码 程序流程图2.自动生成 利用程序的自动生成器（如LEX等）自动生成词法分析程序。2、语法分析器设计LR分析程序：从逻辑上说，一个LR分析程序包括一个总控（驱动）程序和一张分析表两部分。所有的LR分析器的总控程序都是一样的，只是分析表因文法不同而各有不同。分析表是LR分析程序的核心部分，它有“动作”和“状态转换”两部分。ACTION和GOTO都是二维数组。分析表是LR分析程序的核心部分。常见的LR分析表的方法是4种：LR(0)分析表构造、SLR分析表构造、LR分析表构造发和向前LR分析表构造。 LR分析算法：在分析的每一步，通用的总控程序按照状态栈顶状态Q和当前输入符号a查询LR分析表，并执行其中ACTIONQ,a和GOTO部分规定的操作。可以用一个三元式表示分析的每一步栈中状态Q，文法符号串a的变化情况；下一步通过查询LR分析表，执行其中ACTION Qi,Ak规定的操作。为了使源程序能被正确地翻译，产生等价的目标程序，源语言的使用者和实现者都应该遵循关于源语言的共同约定。因此，每种程序设计语言都有自己的程序构成规则-语法规则。使用者可以依据这些规则，以确定所书写程序的正确形式与结构；实现者则依据这些规则，以确定翻译程序可以接受什么样的程序以及怎样翻译该程序。具体的语法规则如下所示：定义的文法，如下： （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-; 根据上面文法画出的分层有限自动机并根据分层自动机构造的LR(1)分析表。具体的实现程序在随本报告一起的代码中，在这里不再赘述。3. 中间代码分析器设计进入编译程序的第三阶段：中间代码产生阶段。为了使编译程序有较高的目标程序质量，或要求从编译程序逻辑结构上把与机器无关和与机器有关的工作明显的分开来时，许多编译程序都采用了某种复杂性介于源程序语言和机器语言之间的中间语言。常用的几种中间语言有: 逆波兰式、四元式、三元式、树表示。本课程设计主要实现逆波兰式的生成。逆波兰式的定义和设计思想及算法1、逆波兰式定义: 将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。2、生成逆波兰式的设计思想及算法(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。(4)如果不是数字，该字符则是运算符，此时需比较优先关系。做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。4. 目标代码生成器的设计由于只需生成汇编指令，下表列出各语句、四元式和汇编指令的相互对应关系，借助于该关系很容易就可以由四元式到汇编指令的转换程序语句四元式汇编指令A=B（=，B，-，A）MOV R1，BMOV A, R1A=B op C（op，B, C, A）MOV R1, Bop R1, CMOV A, R1if(A) goto L(jnz, A, -, 0)CMP A, 0JNZ Lif(AB) goto L（j, A, B, 0）CMP A,BJNC Lif(AB) goto L（j+”,当前字符为，此时，分析器到底是将其分析为大于关系运算符还是大于等于关系运算符呢？又比如，+分析为正号还是加法符号，以及对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。这些在程序设计初期实现都比较困难，在几位同学的帮助下，在后期这些问题都得到了比较有效的解决。在前个问题中，我们用到了超前搜索方法，当当前待分析字符串出现“a+”,当前字符为时，分析器读入下一个字符+，这时可知应将解释为大于运算符。但此时，超前读了一个字符+，所以要回退一个字符，词法分析器才能正常运行。而后一个问题就由一个预处理子程序来完成。在语法分析器设计过程中，程序相当复杂，但是本人在网上找到了一个比较好的例子，然后自己改写下用在了本程序中，减少了自己编写代码的时间。总之，通过本次课程设计一定程度上提高了软件开发能力，对编译原理这一门课程也有了比较深刻的了解。最后，由于所学知识不够全面，课程设计在很多方面还有待完善，在以后的学习过程中，会掌握更多知识，力求做到更好。六、实验指导书与参考书1秦振松，编译原理及编译程