编译原理Chap1.

2019/12/17第1页有了编译技术，计算机语言由单一的机器语言发展到现今的数千种高级语言。计算机科学中最成熟的一个分支，集中体现了计算机发展的成果与精华。计算机软件学科理论与实践相结合的典范。编译程序使得多数计算机用户不必考虑与机器有关的繁琐细节，使程序员独立于机器。2019/12/17第2页•加深对程序语言的内部机制的理解,更好地运用程序设计语言。•包括软件概念和技术，可用于一般的软件设计。词法分析器的匹配技术：文本编辑器、信息检索系统•蕴涵着抽象问题和解决问题的方法，对引导科学思维，提高解决问题的能力有重要作用。必修主干课程，操作系统和编译系统构成程序设计者与计算机之间的基本界面。为什么要学习编译原理2019/12/17第3页课程主要内容•介绍编译系统的一般构造原理、基本实现技术形式语言基础知识、词法分析、语法分析、中间代码生成、代码优化、目标代码生成、符号表的构造和运行时存储空间的组织等。•引入一个小型编译程序的教学模型——“PL/0语言的编译程序”，建立起编译程序实现的整体概念。编译原理=形式语言理论+编译技术2019/12/17第4页•理论和实践要求很高•掌握有关编译的经典基础理论•能够运用先进的软件开发技术构造小型编译系统学习本课程的基本要求•先修课程程序设计语言算法与数据结构：栈分配、堆分配、静态分配等存储分配方式。线性表、二叉查找树、哈希表等多种数据结构。离散数学：集合论与数理逻辑是形式语言与自动机理论的数学基础。2019/12/17第5页编译器的设计一般的软件设计编译器相关的理论和技术，比编译器本身价值更大。编译原理课程应用领域有穷自动机模式识别情报检索文本编辑程序上下文无关文法语法制导翻译建立多种文本处理程序代码优化技术由非结构化到结构化的程序转换程序校验2019/12/17第6页CompilersPrinciples,Techniques,andTools参考书籍无可替代的经典著作，“龙书”。1986年完成，作者是著名的贝尔实验室的科学家核心编译原理至今没变，直到今天，价值非凡。被国际著名高校特别是美国著名大学作为教科书。对我国计算机教育界也具有重大影响,国内很多教材都参照它。编译原理AlfredV.Aho李建中等译机械工业出版社2019/12/17第7页CompilerConstructionPrincipleandPratice编译原理及实践KennethC.Louden冯博琴等译机械工业出版社参考书籍注重实践在讲解编译原理的各个部分的同时，也在逐步实现一个用C语言写的完整的编译器Tiny。用每一章中学到的不同技术分块建立起来的。通过TINY编译器的建立，从整体上掌握编译器构造的方法。对Lex和Yacc进行了很详细的说明2019/12/17第8页参考书籍编译原理课程设计王雷刘志成机械工业出版社用开源Java编译器GJC作编译教学的基础平台通过分析一个真正实用的现代编译系统，把编译理论应用到实际的工程实践中。给出3个具体的课程设计实验，介绍如何用书本上的编译理论实现一个真正的编译器。2019/12/17第9页课程安排讲课：38学时实验：16学时(词法分析、语法分析、语义分析、符号表)答疑时间周四12:00-13:00网络中心307联系方式史一民信息科学与技术学院计算机系E-mail：[e-mail]课时及答疑2019/12/17第10页第8-15周周一3-4节计科楼201室上机实验安排2019/12/17第11页课程考核标准平时成绩+上机成绩+考卷成绩卷面：80分上机、平时（测验、作业、出勤）：20分2019/12/17第12页1.掌握编译程序中所涉及的有关名词术语2.理解编译程序总体框架，明确编译程序工作的基本过程及各阶段的基本任务教学目标第一章编译程序概述2019/12/17第13页第一章编译程序概述1.1什么是编译程序1.2编译过程和编译程序的结构1.3编译阶段的组合1.4编译技术的发展和应用1.5编译程序实现的途径练习题小结2019/12/17第14页1.1什么是编译程序低级语言（LowlevelLanguage)机器语言、汇编语言特点：与特定的机器有关，功效高，但使用复杂、繁琐、费时、易出错高级语言特点：不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。Fortran、Pascal、C语言等程序设计语言2019/12/17第15页•汇编程序把汇编语言书写的程序翻译成机器语言程序。•编译程序把高级语言书写的程序翻译成汇编或目标程序。翻译程序•翻译程序将源程序转换为目标程序的程序。汇编程序、编译程序以及各种变换程序的总称。2019/12/17第16页•一种相当复杂的程序，长度可从10,000行到1,000,000行不等。编写甚至读懂都非易事。•大多数的计算机科学家和专业人员也从来没有编写过一个完整的编译器。•任何一个与计算机打交道的专业人员都应掌握编译器的基本结构和操作。高级语言书写的程序编译程序低级语言程序编译程序(compiler)2019/12/17第17页源程序的编译和运行编译或汇编阶段运行阶段源程序目标程序编译程序或汇编程序输出数据目标程序+运行子程序输入数据2019/12/17第18页对源程序进行解释执行的程序。类似于口译，不生成目标代码与编译系统比较的特点：较简单可移植性好，易于查错，但速度慢。解释程序（Interpreter）2019/12/17第19页编译和解释程序目标程序源程序编译程序初始数据计算结果源程序解释程序初始数据计算结果2019/12/17第20页功能工作结果实现技术上解释程序编译程序解释程序和编译程序的区别根本区别：是否生成目标代码源程序的一个执行系统源程序的一个转换系统源程序的执行结果源程序的目标代码执行中间代码把中间代码转换成目标程序很多语言如BASIC,LISP和PROLOG等等最初都是解释执行的，后来也都有了编译系统。JAVA环境同时需要解释和编译系统的支持。2019/12/17第21页“编译-解释执行”系统源程序源程序的中间形式输出数据输入数据解释程序编译程序2019/12/17第22页Java虚拟机（JVM)本地计算机系统Java语言“编译-解释执行”系统Java虚拟机：把字节码解释成具体平台上的机器指令执行，屏蔽了与操作系统平台相关信息。Java编译程序：生成字节码，在不同平台上运行时不需要重新编译。编译程序.javaJava源程序文件.class二进制字节码文件2019/12/17第23页•源语言(源程序)(Sourcelanguage)(Sourceprogram)•目标语言(目标程序)(ObjectorTargetlanguage)(ObjectorTargetprogram)•实现语言(Implementationlanguage)术语•宿主机：运行编译程序的计算机。•目标机：运行编译程序所产生的目标代码的计算机。源程序编译程序目标程序2019/12/17第24页1.2编译过程和编译程序的结构翻译外文资料：1、识别出句子中的单词；2、分析句子的语法结构；3、根据句子的含义进行初步翻译；4、对译文进行修饰；5、写出最后的译文。2019/12/17第25页翻译和编译工作的比较代码优化目标代码生成修辞加工写出译文综合词法分析语法分析语义分析、生成中间代码识别单词分析句子根据语义初步翻译分析编译程序翻译外文编译过程词法分析语法分析语义分析及中间代码生成代码优化目标代码生成2019/12/17第26页编译程序的逻辑结构中间代码生成词法分析语法分析语义分析代码优化目标代码生成表格管理错误处理图1.2编译程序的逻辑结构图(P6)2019/12/17第27页1、词法分析由词法分析器（扫描器）(Scanner)完成任务：识别单词依据：构词规则字符序列单词序列具有独立意义的最小单位2019/12/17第28页词法分析程序的结果-----二元组y=x+r*6类别值自身值标识符y分界符（赋值）=标识符x分界符（加号）+标识符r分界符（乘号）*常数62019/12/17第29页1保留字begin2保留字var3标识符sum4逗号，5标识符first6逗号，……beginvarsum,first,count:real;sum:=first+count*10(P3)2019/12/17第30页2、语法分析由语法分析器(SyntaxAnalyzer)完成，又称Parser。任务：实现“组词成句”，构造分析树，指出语法错误，指导翻译依据：语法规则输入：Token序列输出：语法树（语法成分）2019/12/17第31页2.语法分析语句表达式；函数调用标识符（表达式）常数字符串printfhelloprintf(“hello”)；2019/12/17第32页2.语法分析赋值语句标识符标识符整数标识符表达式=yx表达式表达式+r6表达式表达式*赋值语句::=标识符=表达式表达式::=表达式+表达式|表达式*表达式表达式::=(表达式)|标识符|整数|实数y=x+r*62019/12/17第33页3.语义分析任务：分析语法单位的语义获取标识符的属性：类型、作用域等语义检查：运算的合法性、取值范围等子程序的静态绑定：代码的相对地址变量的静态绑定：数据的相对地址(SemanticAnalysis)2019/12/17第34页语义分析任务举例表达式赋值语句确定表达式的类型自定义函数分析赋值号左侧是否为变量检查实参和形参个数、类型2019/12/17第35页4.中间代码生成(IntermediateCode)定义：从语法树生成的更接近目标代码的中间表示形式，由此生成目标代码。形式：逆波兰表示(Anti-PolishNotation)、三元式、三元组、四元组(三地址码)、语法树特点：简单规范、机器无关、易于优化与转换逆波兰（后缀表示）id1id2id3*+四元组(*,id2,id3,T1)(+,id1,T1,T2)EE+Eid1E*Eid2id3例:id1+id2*id3语法树2019/12/17第36页四元式t1、t2、t3为编译程序引入的临时工作单元运算符左运算对象右运算对象结果(1)inttoreal6--t1(2)*rt1t2(3)+t2xt3(4)=t3yy=x+r*62019/12/17第37页对代码进行等价变换以提高执行效率——速度、存储空间两种优化与机器无关的优化与机器有关的优化5.代码优化2019/12/17第38页与机器无关的优化局部优化常数运算在编译期间完成：8+9*4公共子表达式的提取:基本块内循环优化强度削减代码外提5.代码优化2019/12/17第39页运算符左运算对象右运算对象结果(1)Inttoreal6--t1(2)*rt1t2(3)+xt2t3(4)=t3y运算符左运算对象右运算对象结果(1)*r6.0t1(2)+t1xy(1)inttoreal6--t1(4)=t3yy=x+r*62019/12/17第40页6.目标代码生成将中间代码转换成目标机上的机器指令代码或汇编代码movr,R1mul#6.0,R1movx,R2addR1,R2movR2,y运算符左运算对象右运算对象结果(1)*r6.0t1(2)+t1xyy=x+r*62019/12/17第41页7、表格管理管理各种符号表（常数、标号、变量、过程、结构……），查、填（登记、查找）源程序中出现的符号和编译程序生成的符号，为编译的各个阶段提供信息。辅助语法检查、语义检查完成静态绑定、管理编译过程Hash表、链表等各种查、填表技术2019/12/17第42页8、错误处理进行各种错误的检查、报告、纠正，以及相应的出错处理词法：拼写……语法：语句结构、表达式结构……语义：类型不匹配……全最大限度发现错误准准确指出错误的性质和发生地点局部化将错误的影响限制在尽可能小的范围内若能自动