张瑞编译原理实验报告
黑龙江大学
“编译原理课程设计”读书报告
学院
年级
专业
学号
姓名
报告日期
成绩
软件学院 2012级 软件工程 20122515 张瑞 2014年6月28日
黑龙江大学计算机科学技术学院
黑龙江大学软件学院
概述
“编译原理”课程是计算机专业中一门重要的专业理论课，是一
门理论性和实践性都很强的课程。为配合《编译原理》课程的教学，
培养学生的实际工作能力，加深对课堂教学内容的理解，通过设计一
个小型编译器，更深刻地领会其基本概念、基本工作原理和实现方法，
从而具有初步开发系统软件和应用软件的实际能力，特开设此课程设
计。通过设计、编制、调试一个对PL/0语言进行词法、语法及中间
代码生成的程序，加深对编译原理的理解。掌握对单词序列的词法检
查和分析、掌握计算机语言的语法分析的过程。熟练运用一种分析方
法（自上而下或自下而上的方法）分析一个给定的文法以及通过思考
以及动手制作分析器的过程来锻炼自己的编程能力和逻辑思维能力
体会计算机编译器的奥妙之处。
一、开发环境简介 Microsoft visual C++ 6.0.
开发环境:是指在基本硬件和数字软件的基础上,为支持系统软件
和应用软件的工程化开发和维护儿使用的一组软件,简称SDE。它有
软件工具和环境继承机制构成,前者用以支持软件开发的相关过程、
活动和人物,后者为工具集成和软件的开发、维护及管理提供统一的
支持。
1.支持开发完备模型 2.灵活控制
二、基本理论阐述、当前理论或实践应用现状
《编译原理》理论和实践并重,叙述严谨、简明,富有启发性,且内
容深入浅出,便于自学。《编译原理》不仅可以作为高等院校相关专业
的教材,也可以作为计算机专业人员的参考用书。
编译器的构造工具是根据用户输入的语言的文法,编译器的构造
工具可以生成程序来处理以用户输入的文法书写的文本。随着计算机
应用范围的扩大,在软件自动生成,文档处理,特定专业的语言等领域,
编译器的构造工具这一技术显得越来越重要.
在分析语法成分时比较方便直观,更便于操作。运行程序的同时不
断修正改进程序,直至的到最优源程序。
三、小型编译器系统架构
它是一个编译器的架构.通俗的来说,它实现了一个库,在这个库上,
可以很容易的实现不同的编译相关的程序,当然,编译器自然是其中最
重要的一个. 当然其他像编译时间的代码分析也是很容易实现的。构
造识别符号串的自动机、词法分析程序的构造、语法分析程序的构造、
中间语言的生成程序、编译程序的代码生成。
四、小型编译器主要功能模块与实现
（1）功能介绍
1. 词法分析功能：对代码进行分词操作，分出以下5类单词： 关键字、标识符、常量、运算符、分隔符。
2. 算术表达式、关系表达式和逻辑表达式的分析与化简：提取
代码中的所有算术表达式，可用LL(1)分析或算符优先分析算术表达
式。关系表达式和逻辑表达式也可用算术表达式的程序进行分析。分
析成功后进行化简操作，方便语法分析程序分析。
3. LL(1)语法分析：自己写的简单C语言的方法，支持赋值语
句、判断语句、循环语句，
用自顶向下的分析方法，对化简之后的单词流进行分析。
4.四元式生成与后缀式。对词法分析分词后的单词流生成中间代码。其中算术表达式先生成后缀式。然后再根据后缀式的结果生成四元式。对多条逻辑表达式采用先计算再跳转的操作。对if语句判断跳转，if中的表达式支持多条逻辑表达式，但不支持嵌套。while和if相同。
5.汇编语言生成：根据四元式生成汇编语言。
（2）相关理论
1>.词法分析（英语：lexical analysis）是计算机科学中将字符序列转换为单词（Token）序列的过程。进行词法分析的程序或者函数叫作词法分析器，也叫扫描器（Scanner）。词法分析器一般以函数的形式存在，供语法分析器调用。词法分析阶段是编译过程的第一个阶段，是编译的基础。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用Lex等工具自动生成。
2>.LL(1)文法：对文法G的句子进行确定的自顶向下语法分析的充分必要条件是，G的任意两个具有相同左部的产生式A—>α|β 满足下列条件：
（1）如果α、β均不能推导出ε,
则 FIRST(α) ∩ FIRST(β) = Φ。
（2）α 和 β 至多有一个能推导出 ε。
（3）如果 β *═> ε,则 FIRST(α) ∩ FOLLOW(A) = Φ。 将满足上述条件的文法称为LL(1)文法。第一个L代表从左向右扫描输入符号串，第二个L代表产生最左推导，1代表在分析过程中执行每一步推导都要向前查看一个输入符号——当前正在处理的输入符号。LL(1)文法既不是二义性的，也不含左递归，对LL(1)文法的所有句子均可进行确定的自顶向下语法分析。并不是所有的语言都可以用LL(1)文法来描述，而且不存在判定某种语言是否是LL(1)文法的算法。也就是说，确定的自顶向下分析只能实现一部分上下文无关语言的分析，这就是LL(1)文法所产生的语言。另外，在上述LL(1)文法的条件中，要求：ε ∈ FIRST(α1)，ε ∈ FIRST(α2)，„ε ∈ FIRST(αn) 中至多有一个成立。
3>.语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.语法分析程序可以用YACC等工具自动生成。
4>.后缀式：即逆波兰式。逆波兰式是波兰逻辑学家卢卡西维奇
（Lukasiewicz)发明的一种表示表达式的方法。这种表示方式把运算符写在运算对象的后面，例如，把a+b写成ab+，所以也称为后缀式。这种表示法的优点是根据运算对象和算符的出现次序进行计算，不需要使用括号，也便于用械实现求值。对于表达式x:=(a+b)*(c+d)，其后缀式为xab+cd+*:=。 原表达式：a*(b*(c+d/e)-f)# /* # 为表
达式结束符号*/后缀式：abcde/+*f-*#
5>.四元式：四元式是一种更接近目标代码的中间代码形式。由于这种形式的中间代码便于优化处理，因此，在目前许多编译程序中得到了广泛的应用。四元式实际上是一种“三地址语句”的等价表示。它的一般形式为：(op,arg1,arg2,result)其中， op为一个二元 (也可是一元或零元)运算符；arg1,arg2分别为它的两个运算 (或操作)对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入result中。四元式还可写为类似于PASCAL语言赋值语句的形式：result ∶= arg1 op arg2 每个四元式只能有一个运算符，所以，一个复杂的表达式须由多个四元式构成的序列来表示。例如，表达式A+B*C可写为序列T1∶=B*C,T2∶=A+T1其中，T1，T2是编译系统所产生的临时变量名。当op为一元、零元运算符 (如无条件转移)时，arg2甚至arg1应缺省，即result∶=op arg1或 op result ；对应的一般形式为：(op,arg1,arg2,result).
（3）算法描述
1>.词法分析器
1. Design the regular grammar.
2. Design the regular expression.
3. Construct the DFA.
4. Write the program.
数据结构
typedef struct
{
int type;
char token[size];
}symbol;
Char*keywords[keywordsnum] =
{
char *operators[operatorsnum] = {
char *jiefu[jiefunum] = {
char *luoji[luojinum] = {
char *zhushi[zhushinum] = {
char *str[8] = {
*通过读文件的形式一个字符一个字符读入进行分析
*下面是词法分析的主要函数
void lex(char *filename)
{
int error = 0; int flag = 0; char ch; fp.open(filename); int linenum = 1; int i,j; i = 0; int x = 0; ch = fp.get();
{ if(ch == ' ' || ch == '\t') { } else if(ch == '\n') { } else if(isalpha(ch) == 1) { } else if(isdigit(ch) == 1) { table[i].token[x] = ch; table[i].token[x] = ch; ch = fp.get(); if(isalpha(ch) == 0 && isdigit(ch) == 0 && ch != '_') { } else if(isdigit(ch) == 1 || isalpha(ch) == 1 || ch == '_') x++; table[i].token[++x] = '\0'; i++; flag = 0; x = 0; x = 0; linenum++; ch = fp.get(); x = 0; ch = fp.get();
} if(isdigit(ch) == 1) x++; else if(ch == '.' && flag == 0) { } else if(ch == '.' && flag == 1) { } if(isdigit(ch) == 0) { } table[i].token[++x] = '\0'; i++; x = 0; flag = 0; cout
} } else { } table[i].token[++x] = '\0'; i++; else { } char ch2 = fp.get(); if(ist(ch,ch2) == 1) { } else { } table[i].token[0] = ch; table[i].token[1] = '\0'; x = 0; i++; ch = ch2; table[i].token[0] = ch; table[i].token[1] = ch2; table[i].token[2] = '\0'; x = 0; i++; ch = fp.get(); for(j = 0; j
} } cout
2>.语法分析器
1).自顶向下的LL（1）分析
2).先求first、follow、select集构造分析表
3).进行语法分析
4).本实验采用静态存分析表的方式
5).可以分析算符表达式
*分析栈
*和剩余串
*进栈和匹配操作
3>.语言表达式翻译程序
*完成中间代码的生成，
*转成四元式的形式。
*利用两个栈进行四元式的产生
*其一栈为算符栈根据优先关系进栈和出栈
*另一个为操作数或变量栈
*当剩余串算符优先级比算符栈低时出栈生成相应的四元式 *再根据四元式转化成汇编代码
四元式结构体
struct TR
{
};
汇编结构体
struct AS
{
};
v-> void main
t-> int
d-> 标识符
e-> 常量
w-> while
i-> if char L[5]; char operation[5]; char A[5]; char B[5]; char w; char opr1[5]; char opr2[5]; char T[5];
（4）程序流程图
（5）测试用例与实验结果
#include
void main()
{
int a; int b; a=6; b=3; while(a>b) { a=a+0;
}# }
if(a>b) { } b=b+1;
词法分析
*输出文件部分：
*编译器输出部分：
语法分析： *输入文法
PQUVWKECTSF v(){}td,;=diwk+-*/>
U t V dW W ,dW W =E W k K d=E;K K i(E){K} K w(E){K} K QK K k E TC
C +TC
C -TC
C c
C k
C >TC
C
动态生成的分析表
此文法select有交集，当C遇到‘>’时可以退出
此文法select有交集，当C遇到‘
通过手动的修改可以进行语法分析 k’空和
四元式的生成
五、读书工程心得总结
深入了解4遍式编译程序的运行原理，通过设计一个小型的编译器，加深对课堂学习内容的理解，更深刻的领会编译器的基本工作原理和实现方法。实验中模拟了词法分析，语法分析，语义分析，中间代码以及目标代码生成。从中真正学习到了编译的精髓，虽然其中有熬夜编代码的疲惫，但是真正做成的时候就会发现，做成成品的喜悦远比辛劳要重要得多，有志者事竟成。
六、参考文献
1.书目名称：编译原理(第2版)
作 者：张素琴 吕映芝
出 版 社：清华大学出版社
出版时间：2005年02月
内容提要：本书介绍编译系统的一般构造原理、基本实现技术和一些自动构造工具。主要由语言基础知识、词法分析、语法分析、中间代码生成、代码优化、目标代码生成、符号表的构造和运行时存储空间的组织等部分组成。
书中在介绍编译程序构造基本原理的同时引入“PL/0语言的编译程序”结构及文本,还引入了LEX、YACC使用方法与实例。
本书是高等院校计算机科学与技术专业的本科生教材,也可作为教师、研究生软件工程技术人员的参考书。
2.书目名称：编译原理（第2版）
原书名： Compilers:Principles,Techniques,and Tools 原出版社： Pearson Education
作者： [美]Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman 译者： 李建中 姜守旭
出版社：机械工业出版社
出版日期：2003 年9月
内容提要：本书深入讨论了编译器设计的重要主题，包括词法分析、
语法分析、语法制导分析、类型检查、运行环境、中间代码生成、代码生成、代码优化等，并在最后两章中讨论了实现编译器的一些编程问题和几个编译器实例，每章都提供了大量的练习和参考文献。本书从介绍编译的原理性概念开始，然后通过构建一个简单的一遍编译器来逐一解释这些概念。 本书是编译原理课程的经典教材，作者曾多次使用本书的内容在贝尔实验室、哥伦比亚大学、普林斯顿大学和斯坦福大学向本科生和研究生讲授初等及高等编译课程。 本书作者alfred v．aho、ravi sethi和jeffrey d．ullman是世界著名的计算机 科学家，他们在计算机科学理论、数据库等很多领域都做出了杰出贡献。本书 是编译领域无可替代的经典著作，被广大计算机专业人士誉为“龙书”。本书一 直被世界各地的著名高等院校和科研机构(如贝尔实验室、哥伦比亚大学、普 林斯顿大学和斯坦福大学等)广泛用作本科生和研究生编译原理与技术课程的 教材，本书对我国计算机教育界也具有重大影响。 书中深入讨论了编译器设计的重要主题，包括词法分析、语法分析、语法制 导分析、类型检查、运行环境、中间代码生成、代码生成、代码优化等，并在 最后两章中讨论了实现编译器的一些编程问题和几个编译器实例，而且每章都 提供了大量的练习和参考文献。
3.书目名称：编译原理及实践
作者：（美）Kenneth C.Louden著，冯博琴，冯岚等译
出版社：机械工业出版社
版次：2000年3月第1版
内容提要：本书结合对现代编译器设计理论的详细研究，完整描述了一个可运行的小规模语言编译器（包括源代码）。本书反映了作者的这样一些观点：不掌握理论就不会理解实际的编译器设计；而对大学生来说，看不到理论在实际中的应用就不会真正地理解理论。把本书讨论的概念统一起来，就是一个完整的可运行的编译器，它使用每一章所讨论的技术进行开发，用C语言写成。每章最后有大量的练习，使学生的注意力集中在编程问题上。
4.书目名称：编译程序构造原理和实现技术
作者：金成植
出版社：高等教育出版社
出版时间：2000年7月第1版 2004年4月第6次印刷
内容提要：本书经教育部高等学校计算机教学指导委员会推荐，列入“九五”国家级重点教材建设项目和“面向21世纪课程教材”。 本书是作者在其编著的《编译原理与实现》基础上编写的，结合了多年的教学经验，是一本比较成功的教材。它主要以Pascal类语言为模型，介绍过程式语言的编译程序构造原理和实现技术。本书共分十章，主要包括词法分析和语法分析的理论与技术，语义分析原理与技术，运行时的存储分配原则，动作文法和属性文法技术，中间代码生成、中间代码优化和目标代码生成的原理与技术等。
本书的特点是概念清晰，层次分明，循序渐进，整体性强，便于教学，并反映当前的实用技术。
5. （美） Alfred V.Aho Ravi Sethi Jeffrey D.Ullman 著. 李建中、姜守旭 译.编译原理.机械工业出版社.2003.8
6.（美）Bruce Eckel 著. 陈吴鹏 饶若楠 等译.机械工业出版社。2005.9
7. 书目名称:《现代编译程序实现—Java语言》(第二版,英文影印版)
原书名: Modern Compiler Implementation in Java,Second Edition
原出版社: Cambridge University Press作 者: (美)A A.W.Appel等 出 版 社:电子工业出版社 出版时间:2004 年9月
8. 秦明,李波. 计算机操作系统实验与实践:基于Windows与Linux[M中国电力出版社,2004,4:第13-15页,第36-54页
9. 书目名称:编译原理(第2版)作 者:张素琴
出 版 社:清华大学出版社出版时间:2005年02月
10. 姜守旭 译.编译原理.机械工业出版社.2003.8