西安电子科技大学编译原理复试第一章 引言

1编译原理西安电子科技大学计算理论与技术研究所王小兵xbwang@2相关领域程序设计语言的应用－程序设计（PLA）程序设计语言的翻译－编译器的构造（PLT）程序设计语言的设计－语法、语义（PLD）知识点

中国计算机科学与技术学科教程(CCC2002)程序设计基础(PF)：程序设计基本结构、算法与问题求解、基本数据结构、递归、事件驱动程序设计。(PLA)程序设计语言(PL)：程序设计语言概论、虚拟机、语言翻译简介、声明和类型、抽象机制、面向对象程序设计(核心)；函数程序设计、语言翻译系统、类型系统、程序设计语言的语义、程序设计语言的设计(选修)。(PLA、PLT、PLD)课程简介3课程简介目的了解PL的基本要素、工作原理、语言翻译的基本方法；用不同的PL进行程序设计，即自学计算机语言的能力；具备语言翻译的基本技能；了解计算机科学的基础理论；课程特点提高自学能力；理论与实践并重；理论的演变是缓慢的、理论基础是相通的；相同的原理可应用于不同的技术；适应飞速变化的技术的根本是注重基础理论学习；4课程简介教材刘坚编译原理基础西电出版社刘坚《编译原理基础》习题与上机解答西电出版社参考书目吕映芝等编译原理清华大学出版社陈火旺等程序设计语言编译原理国防工业出版社Aho等编译原理技术与工具人民邮电出版社AndrewW.Appel现代编译程序实现－Java语言高等教育出版社StevenS.Muchnick高级编译器设计与实现机械工业出版社Hopcroft等自动机理论、语言和计算机导论机械工业出版社5课程简介学习方法要作笔记；多思考，勤发问；多实践、以用促学；合理使用参考解答；作业与上机提前一星期通知交作业；验收上机题，并交上机报告；6往届学生报告编译原理是四大天书中的天书，事实上没有那么恐怖。第二、三章只要多看书，勤做作业，学好也不难。第四、五章尽管没有涉及算法，但是它与程序的运行方面有很大关系，理解起来还是比较吃力的。课随好学，但是上机就困难了，由于平时编程方面的欠缺，对于程序如何组织，如何编写，总感觉无从下手。7往届学生报告函数绘图语言采用的分析方法是递归子程序，优点是分析方法非常简单易懂，但涉及到大量栈存储空间操作，大大降低了分析的效率。实际中的编译器和解释器的构造方法通常采用自动化工具（Lex/Yacc），其语法分析大部分采用LALR(1)文法，其驱动器具有通用性，与文法无关，效率高，但分析表十分复杂，难于手工构造。8第一章引言1.1从面向机器的语言到面向人类的语言面向机器的语言：机器指令、汇编语言面向人类的语言：通用程序设计语言、非过程式语言计算机语言举例[例1]通用程序设计语言与汇编语言（包括机器指令）

Pascal语句：x:=a+b；

C++语句： x=a+b； 汇编指令： 十六进制代码

汇编指令

A10002 MOVAX,[A] 8B1E0202 MOVBX,[B] 01D8 ADDAX,BX A30402 MOV[X],AX91.1从面向机器的语言到面向人类的语言[例2]SQL：查询003号学生所选课程与成绩SELECT学号,姓名,课程名,成绩FROM学生,选课WHERE学生.学号="003";学号姓名性别001张梧男002李煦男003王沁女004刘荔女学号课程代码课程名成绩0010104离散数学800010205数据结构900030104离散数学850030205数据结构95学号姓名课程名成绩003王沁离散数学85003王沁数据结构95对吗？101.1从面向机器的语言到面向人类的语言[例3]Lex和Yacc

Lex的正规式：char(char|digit)*returnid Yacc的产生式：E:E'+'E|E'*'E|id[例4]Unix的shell命令

SHELL=/bin/sh #includeenv_precomp.mk CPDIR=/u/pbsrc/chp ORAHOME=/oracle/app/oracle/product/734

111.1从面向机器的语言到面向人类的语言按范型划分的程序设计语言SimpleProceduralLanguages：FORTRANCBlock-StructuredProceduralLanguages：PascalObject-BasedLanguages：AdaC++SmalltalkFunctionalLanguages：LISPMLLogicProgrammingLanguages：PrologCC2002-PL过程式语言、面向对象语言：通用程序设计语言，如FORTRAN、Pascal、C/C++、Ada83/Ada95、Java等；函数语言：面向特点领域的、递归特性，如Lisp；说明性、非算法式语言：浓厚的数学特征，如LEX/YACC、SQL等；脚本式语言：仅是一种安排，如shell语言，XML等。121.1从面向机器的语言到面向人类的语言其他面向特定应用领域的语言计算机辅助设计：MATLAB集成电路设计：VHDL、Verilog虚拟现实与人机交互：VRML……问题：如何将形形色色的语言翻译成可以在计算机上运行的0、1串？131.2语言之间的翻译习惯称法汇编语言－机器指令：汇编（或交叉汇编）程序设计语言－汇编语言或机器指令：编译（或解释）高级语言之间：转换（或预编译）逆向：反汇编、反编译141.3编译器与解释器语言翻译的两种基本形态 先翻译后执行 边翻译边执行编译器源程序目标程序目标程序输入数据输出解释器源程序输出输入数据[例5]假设有源程序P：read(x);write("x=",x);

编译器P目标程序目标程序3x=3解释器x=3P3151.3编译器与解释器编译器源程序目标程序目标程序输入数据输出解释器源程序输出输入数据特点编译器：工作效率高，即时间快、空间省；交互性与动态特性差、可移植性差。被大多数PL的翻译所采用；解释器：工作效率低，即时间慢、空间费；交互性与动态特性好、可移植性好。早期的Basic和现在的Java等。基本功能：二者相同；采用技术：从翻译的角度来讲，两种方式所涉及的原理、方法、技术相似。161.4编译器的工作原理与基本组成通用程序设计语言的主要成份从语言抽象的演变看： 过程→抽象数据类型（ADT，程序包）→类共同特点：两大部分组成，声明＋操作＝完整定义以过程式语言为例：声明性语句：提供操作对象的性质，如数据类型、值、作用域等；操作性语句：确定操作的计算次序，完成实际操作。过程头＋过程体＝过程定义

编译器对两类语句的翻译：声明：生成相应的环境，一般是配置存储空间；操作：生成可执行的代码序列。171.4编译器的工作原理与基本组成[例6]一Pascal的过程如下：(1)proceduresample(y:integer); {过程头}(2)varx:integer; {过程体（开始）}(3)beginx:=y;(4)ifx>100thenx:=0(5)end; {过程体（结束）}(1)：声明，提供调用信息，如过程名、参数、返回值等。（接口）(2)至(5)：过程体，可含声明或操作。（实现）。编译器对声明性语句的处理一般是生成相应的环境（存储空间），对操作性语句则是生成此环境中的可执行代码序列。为便于编译器的处理，操作性语句中使用的每个操作对象，均应在使用前声明，即符合先声明后引用的原则。181.4编译器的工作原理与基本组成以阶段划分编译器自然语言的翻译过程： 识别单词 识别句子结构 理解意思 译成中文并修饰编译器的工作过程： 词法分析 语法分析 语义分析 目标代码生成编译器的阶段（逻辑模块）中间代码的重要作用191.4编译器的工作原理与基本组成编译器各阶段的工作[例7]Pascal源程序语句如下：

varx,y,z:real; x:=y+z*60;（源程序）varx,y,z:real;x:=y+z*60;

（记号流）varid1,id2,id3:real;id1:=id2+id3*60;（语法树）词法分析语法分析201.4编译器的工作原理与基本组成语义分析中间代码生成(1)(itr,60,, T1)(2)(*,id3,T1, T2)(3)(+,id2,T2, T3)(4)(:=,T3,,id1)中间代码的形式与作用：(序号)(op，arg1,arg2,result)result:=arg1oparg2211.4编译器的工作原理与基本组成(1)(itr,60,, T1)(2)(*,id3,T1, T2)(3)(+,id2,T2, T3)(4)(:=,T3,,id1)中间代码优化(1)(*,id3,60.0,T1)(2)(+,id2,T1,id1)MOVF id3,R2MULF #60.0,R2MOVF id2,R1ADDFR2,R1MOVF R1,id1目标代码生成R2:=id3R2:=R2*60.0R1:=id2R1:=R1+R2id1:=R1id1:=id2+id3*60.0x:=y+z*60;221.4编译器的工作原理与基本组成各阶段工作的归纳

词法分析：识别单词，至少分以下几大类：关键字（保留字）、标识符、字面量、特殊符号；语法分析：得到语言结构并以树的形式表示；语义分析：考察结构正确的句子是否语义合法，修改树结构；中间代码生成（可选）：生成一种既接近目标语言，又与具体机器无关的表示，便于优化与代码生成；（到目前为止，编译器与解释器可以一致）231.4编译器的工作原理与基本组成中间代码优化（可选）：局部优化、循环优化、全局优化等；优化实际上是一个等价变换，变换前后的指令序列完成相同功能，但在占用的空间上和程序执行的时间上都更省、更有效。目标代码生成：不同形式的目标代码－汇编、可重定位、内存形式（Load-and-Go）;符号表管理：合理组织符号，便于各阶段查找、填写等；出错处理：错误的种类－词法错、语法错、静态语义错、动态语义错。241.4编译器的工作原理与基本组成编译器的分析/综合模式

前端：语言结构和意义的分析；后端：语言意义处理；中间代码：前端与后端的分界；251.4编译器的工作原理与基本组成编译器基础架构(Infrastructure)：源代码的中间表示、一组前端、一组后端；261.4编译器的工作原理与基本组成编译器扫描的遍数每个阶段将程序完整分析一遍的工作模式称为一遍扫描。确定扫描遍数的因素有：软、硬件条件，如内存太小，或全局优化语言结构，如规定标识符的先声明后引用x:=f(a);…functionf(a:integer):integer;编译技术，如拉