编译原理复习清华吕映芝

编译原理第1页，共102页。清华大学计算机科学与技术系吕映芝2003.9.9第1章 编译程序概论什么是编译程序翻译和解释编译过程和编译程序的结构*1.4

编译程序的实现途径1.5

编译技术在其它软件中的应用有关学习问题参考书第2页，共102页。1.1

什么是编译程序4

语言和翻译：语言是人类交流思想和信息的工具。从自然语言来说，世界上存在着许多种语言，各国之间要交流信息,就要有各种语言之间的翻译。4

编译程序：编译程序就是一个语言的翻译程序,是把一种语言（称源语言）书写的程序翻译成另一种等价功能语言（称目标语言）的程序。换句话说，编译是指把一种用源语言表示的算法转换到另一种等价的用目标语言表示的算法。第3页，共102页。1.1

什么是编译程序4

编译程序的必要性：计算机是当代科学发展的重要工具，已渗入到

各行各业乃至家庭生活中。所以如何让他为人类工作服务，就必须建立人与计算机之间的信息交流。但计算机只认识由“0”和“1”构成的机器语言，并不认识C、C++、Java、

Pascal等高级程序设计语言。每台计算机都有自己独特的指令系统，即机器语言，最早的程序就是用8进制和16进制码的机器语言书写的。第4页，共102页。1.1

什么是编译程序用机器语言书写程序，不仅不易学，而且可调试性、可读性、可维护性和结构性都很差，开发时间也很长。4

因此，编译程序最初的定义是把一种高级程序设计语言的源程序（面向人的）翻译成另一种等价的低级程序设计语言（面向硬件的）即机器语言或汇编语言。4

所以，编译程序是人用某种语言书写的某个翻译程序。第5页，共102页。1.1

什么是编译程序·

编译程序的功能编译程序机器语言（目标语言）O:目标语言(程序)I:

实现语言SOI高级程序设计语言（源语言）用T型图表示S:源语言(程序)第6页，共102页。1.1

什么是编译程序4

随着计算机及其应用的发展，出现了各种应用更方便的高级语言，如:FORTRAN

、PL/1

、ALGOL

60

、COBOL

、PASCAL、Ada

、LISP

、C

、C++、JAVA等。4

早期开发的软件需转换，因此，编译程序不仅是高级语言翻译成机器语言，广泛地讲：4

编译程序第7页，共102页。高级语言高级语言低级语言中间语言高级语言中间语言高级语言低级语言1.1

什么是编译程序高级语言4

例：高级语言

FORTRANPASCALCJAVAPL/1C++

COBOLCAdaJAVA第8页，共102页。1.1

什么是编译程序4

逆向工程

低级语言 高级语言例：IBM

/

4700（汇编语言）

C4

交叉编译

在一个机器上对某种高级语言进行编译，产生的目标语言是另一个机器的汇编语言或机器语言。例：在WAX机上编译Ada语言，产生PC机的汇编语言，这样的目标语言只能在PC机上运行，如嵌入式系统对交叉编译的应用。4

当功能相同时，不同语言之间的区别，只是语言的词法、语法和语义规则形式不同。运行环境也可能不同。第9页，共102页。例：计算园面积C程序：function

circle(

);{int

r

;float s

;scanf

(“%d”,

&

r

);s

=3.1416

*

r

*

r

;printf

(“%d

\n”,s

);}Pascal

程序：第10页，共102页。procedure

circle;var

r

:

integer

;s

:

real

;beginread

(

r

)

;s

:=

3.1416

*

r

*

r

;write

(

s

)

;end

;1.2

翻译和解释翻译：按源程序的实际输入顺序，处理程序语句，得到可执行的目标程序。解释：按源语言的定义边解释边执行。解释执行是按照被解释的源程序的逻辑流程进行处理的，不产生目标程序。解释程序源程序第11页，共102页。输入输出解释解释执行优点：交互方便，节省空间。缺点：效率低。因对源程序的循环语句部分要反复解释执行。共同点：都需进行词法、语法、语义分析。可比喻为：翻译（编译）---笔译（产生目标程序）解释---口译（不产生目标程序）第12页，共102页。1.3

编译过程和编译程序结构第13页，共102页。4

编译过程4

编译程序结构4

编译的趟（遍）(pass)编译过程词法分析语法分析语义分析中间代码生成代码优化目标代码生成第14页，共102页。词法分析读字符流的源程序、识别单词–例：position

:=

initial

+

rate

*

60

;（转换为内部表示，拼标识符、数和复合单词等）第15页，共102页。–单词类型标识符（1）算符(赋值号)单词值

position:=（复合单词）词法分析–单词类型单词值标识符（2）initial算符(加号)+标识符（3）算符(乘号)*rate整数60界符（分号）；第16页，共102页。语法分析·

功能：层次分析，把源程序的单词组成语法短语(表示成语法树或其它内部码)。现用“巴科斯-瑙尔范式”（EBNF）描述。–例:<赋值语句>::=<标识符>:=<表达式><表达式>::=<表达式>+<表达式><表达式>::=<表达式>*<表达式><表达式>::=“(”<表达式>“)”<表达式>::=<标识符><表达式>::=<常数>第17页，共102页。语法分析（语法树）:=+60*positioninitialrate第18页，共102页。语义分析·

语义审查静态语义检查上下文相关性如：类型匹配和类型转换例:Program

p(

);var

rate:real;procedure

initial;…position

:=

initial

+

rate

*

60;/*

error

*/…类型匹配错误第19页，共102页。语义分析60:=+*positioninitialrateinttoreal类型转换第20页，共102页。中间代码生成·

源程序的内部(中间)表示结构简单、含义明确的记号系统，介于高级语言与低级语言之间,与目标机无关，便于优化、移植并容易生成目标代码。通常的中间代码有三元式、四元式、树结构或适合相应语言的中间代码。例：P-Code、C-Code、bytecode等。第21页，共102页。中间代码生成（四元式）例：id1:=id2+id3

*

60；翻译成四元式四元式：3地址（操作符，操作对象1，操作对象2，操作结果）第22页，共102页。id3

t1id2

t2t3

—(inttoreal

60

—

t1

)(*

t2(+

t3(:=

id1)))代码优化代码优化：是对中间代码进行等价变换，以提高目标代码的时、空效率例：上面的4条指令可变成2条，并且节省2

个工作单元。(*

id3

60.0

t1

)(+

id2

t1

id1

)第23页，共102页。目标代码生成(*

id3

60.0

t1

)(+

id2

t1

id1

)movf

id3,R2mulf

#60.0,R2movf

id2,R1addf

R2,R1movf

R1,id1R1、R2是寄存器第24页，共102页。符号表管理记录源程序中使用的名字收集每个名字的各种属性信息–类型、作用域、分配存储信息值：35第25页，共102页。Const

常量Var

变量类型：int层次：2地址：dx+5CONST

A=35，B=49；VAR

C，D，E；PROCEDURE

P；VAR

G表格管理(以PL/0为例）名字

类型层次/值地址

存储空间Const（常量）无层次第26页，共102页。出错处理编译的任何时候都可能发现源程序中的错误。检查词法、语法和语义中的错误（静态）。编译程序的处理能力，如存储空间越界（动态）报告出错信息和位置处理和恢复第27页，共102页。编译程序结构词法分析程序语法分析程序语义分析程序中间代码生成程序代码优化程序目标代码生成程序符号表管理程序出错管理程序第28页，共102页。出错处理语法分析语义分析词法分析中间代码生成代码优化表格管理目标代码生成目标代码源程序第29页，共102页。编译的趟（遍）(pass)从头到尾对源程序或各种形式的中间表示进行扫描，称为一遍编译的前端（front

end）中间代码生成后（代码优化后）编译的后端（back

end）目标代码生成开始从源程序扫描是第一遍的输入每前一遍的输出是后一遍的输入分遍的原则按实际情况而定第30页，共102页。1.4

编译程序的实现途径应考虑：开发周期、目标程序的效率、可移植性、可调试性、可维护性和可扩充性等。构造方式：l

手工构造：用机器语言、汇编语言或高级程序设计语言书写。l

自动构造工具：Lex,Yacc。Lex,Yacc分别是词法和语法分析器的生成器。l

移植方式：目标程序用中间语言l

自展方式：用T型图表示第31页，共102页。1.4

编译程序的实现途径4

自展方式：S

OIC1PC

C2PCCPCC2步骤1：(1)(2)PCC1CPCPC实现目标(3)注释：

PC表示PC机的机器语言或汇编语言C1

、C2是C的子集，

C1

C2第32页，共102页。自展方式步骤2：C2C1PCC1PCC2PCPCPCCC2PCC2PCCPCPCPC步骤3：第33页，共102页。1.5

编译技术在其它软件中的应用4

软件测试工具如：FORTRAN，C的静态和动态测试工具（可测试程序的语句覆盖率，路径覆盖率等）4

高级程序设计语言的转换4

网络中的协议4

数据库系统中各种命令语言的翻译4

各种软件支持环境第34页，共102页。编译程序在系统软件中的所在层操作系统语言处理系统应用软件层裸机第35页，共102页。应用软件层语言处理系统等操作系统复习讨论：编译程序由哪些部分组成?说明每个部分的功 能。如果在PC机上只有C语言,现在要求实现

PASCAL语言，你用什么办法做更好？（最 好不用汇编语言编写）编译的前端和后端如何划分?翻译(编译)和解释的区别是什么?各自的优、 缺点是什么？第36页，共102页。有关学习问题第37页，共102页。4

教学内容和学习目的4

学习要求和学习方法教学内容编译程序概述PL/0编译程序（读懂文本，扩充功能）语言和文法词法分析和有限自动机

(5)自顶向下语法分析方法*(6)自底向上算符优先分析法自底向上LR分析法语法制导翻译和中间代码生成目标程序运行时的存储空间组织*(10)代码优化第38页，共102页。学习目的4

近年来，信息技术的迅猛发展，对软件技术和软件工具的需求急剧增加，编译技术已大量应用于各种各样软件工具的研制和开发中。从各种语言的结构化编辑器、分析器和语言的解释系统到嵌入式软件，交叉编译器；从传统的强制式的程序设计语言到应用式、面向对象的语言的编译；从一般的批处理环境到交互环境及分布式环境等等；技术需求越来越大，涉及面越来越广。因而，广大从事计算机系统软件和应用软件研制及开发人员对编译技术深入了解的要求越来越高。第39页，共102页。学习要求和学习方法4

目前，编译系统的构造在理论上有较成熟的体

系支持，实现技术也很丰富多样。但要使学生

通过该课程的学习从理解原理、掌握技术到自

己设计和实现一个完整的编译程序，难度很大，因为课程内容广泛，涉及到数据结构、操作系

统、离散数学及语言理论，是综合性很强的一

门课程。从抽象形式语言与自动机的概念，到

具体构造实现的复杂性，学生都必须理解原理

掌握技术。第40页，共102页。学习要求和学习方法4

学时：课内48，课外804

学好原理和构造技术需做相当量作业，巩固课堂知识理论联系实际，做好实验第41页，共102页。实验要求必做题目第42页，共102页。65%扩充条件语句〈条件语句〉::=IF〈条件〉THEN〈语句〉[ELSE〈语句〉]扩充重复语句〈重复语句〉::=REPEAT〈语句〉{；〈语句〉}UNTIL〈条件〉选做题目用C语言改写PL/0编译程序；

80%用Java语言改写PL/0编译程序；80%实验要求对PL/0语言扩充整形数组（尽量做此题）。95%讨论 ：分成3人一组做扩充整形数组，开展讨论、相互学习，培养团队精神。其他选做①学完语法分析后可用LL（1）或LR语法分析方法改写PL/0编译程序的某些部分②用LEX、YACC编写一个小型的编译器（要求见编译原理实验2）③用LEX、YACC改写PL/0编译程序适当加分第43页，共102页。实验要求实验报告内容:对扩充部分用语法图和EBNF描述；对程序变动部分的说明；所用测试用例；实验体会和建议。第44页，共102页。参考书第45页，共102页。吕映芝，张素琴，蒋维杜.编译原理.清华大学出版社.1998

Tomas

Pittmn,

The

art

of

Compiler

Design

theory

andPractice,

Prentice-Hall

1992Charles

N.

Fischer,

Richard

J.

Leblanc,

Crafting

ACompiler,

The

Benjamin/Cummings

Publishing

Company1988ALFRED

V.

AHO,

RAVISETHI,

JEFFREY

D.

ULLMAN,Compilers

Principles,

Techniques

and

Tools

ADDISSON-WESLEY

1986教材后所列其它参考第2章

PL/0编译程序的实现4

本章目的：以PL/0语言的编译程序为实例,学习一个编译程序实现的基本步骤和相关技术“PL/0语言的编译程序”是世界著名计算机科学家

N.Wirth先生编写的。由于PL/0语言功能简单、

结构清晰、可读性强，而又具备了一般高级语言的必须部分，因而PL/0语言的编译程序能充分体现一个高级语言编译程序实现的基本技术和步骤。是一个非常合适的小型编译程序的教学模型。第46页，共102页。第2章

PL/0编译程序的实现通过本章的学习可达到：–对编译程序的构造得到一些感性认识和初步了解–对编译程序的实现建立起整体概念–为系统地学习本课程以下各章节打好基础为了读者能较好地阅读PL/0语言编译程序文本。本章将对PL/0语言编译程序的实现过程作概括的分析说明。对PL/0语言文法的表示只给出语法图和扩充的巴科斯-瑙尔范式(EBNF)的描述形式，不作文法理论上的讨论。第47页，共102页。第2章

PL/0编译程序的实现4

功能PL/0编译程序PL/0语言类pcode源语言(PL/0)目标语言(类pcode)实现语言（pascal)PL/0类pcodepascal类pcode是中间代码Pcode是适合pascal的中间代码第48页，共102页。PL/0源程序PL/0编译程序类pcode代码类

pcode解释程序输入输出PL/0编译程序功能的框架第49页，共102页。第2章

PL/0编译程序的实现步骤1. 认识源语言PL/0与目标代码类pcode及它们之间的映射步骤2.

PL/0编译程序的总体设计步骤3.

PL/0编译程序词法分析的设计与实现步骤4.

PL/0编译程序语法语义分析的设计与实现步骤5.

PL/0编译程序代码生成的实现*步骤6.

PL/0编译程序错误处理的实现步骤7.

类pcode代码解释器的设计与实现第50页，共102页。练习见教材26-27页1.

2.

3.

4.

5.6.

(2),

(3)第51页，共102页。第3章 文法和语言文法和语言概述文法和语言的形式定义文法的类型（重点是二型和三型）上下文无关文法及其语法树句型的分析有关文法实用中的一些说明第52页，共102页。3.1

语言文法概述4

本章目的4

语言概述4

语言的一般描述4

文法的直观概念第53页，共102页。本章目的本章目的是为语言的语法描述寻求工具，是本课程的理论基础。通过描述工具，可以：对源语言给出精确无二义的语法描述。（严谨、简洁、易读）根据语言文法的特点来指导语法分析的过程从描述语言的文法可以自动构造出可用的分析程序(如：第13章介绍的基于LALR(1)文法的yacc和基于LL(2)文法的SD&EBNF_LL(2))制导语义翻译第54页，共102页。语言概述4

语言是由句子组成的集合，是由一组记号所构成的集合。4

汉语--所有符合汉语语法的句子的全体4

英语--所有符合英语语法的句子的全体4

程序设计语言--所有该语言的程序的全体4每个句子构成的规律4

研究语言 每个句子的含义4每个句子和使用者的关系第55页，共102页。语言概述语言研究的三个方面:语法（

Syntax

）--表示构成语言句子的各个记号之间的组合规律语义（Semantics）--表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用（Pragmatics）--表示在各个记号所出现的行为中，它们的来源、使用和影响。（本章不做进一步的介绍）第56页，共102页。语言概述4

形式语言理论（formal

language

theory）：是一种从语法上研究语言的理论。它是抽象的数学系统，着重研究符号串集合的表示法、结构及其特性。是程序设计语言语法分析研

究的基础。（本章仅使用其与编译程序构造

有关的结论，而不做证明）4

形式语义（formal

semantics）：（本课程不介绍）。第57页，共102页。语言的一般描述4

语言可以看成在一个基本符号集上定义的，按一定规则构成的基本符号串组成的所有集合。4

一些基本概念第58页，共102页。文法的直观概念4

句子的产生4

<句子>::=<主语><谓语>4

<主语>::=<代词>|<名词>4

<代词>::=我|你|他4

<名词>::=王明|大学生|工人|英语4

<谓语>::=<动词><直接宾语>4

<动词>::=是|学习4

<直接宾语>::=<代词>|<名词>第59页，共102页。文法的直观概念（用“ ”表示推导）<句子>

<主语><谓语><代词><谓语>我<谓语>我<动词><直接宾语>我是<直接宾语>我是<名词>我是大学生第60页，共102页。练习教材45~46页5.7.9.11.13.

(3)14.

(1),(2)16.

(2),(3)第61页，共102页。第4章 词法分析设计词法分析程序单词的描述工具单词的识别系统词法分析程序正规表达式、*正规文法与正规集有穷自动机正规表达式和有穷自动机*

4.5有穷自动机和正规文法第62页，共102页。4.1

词法分析程序词法分析（lexical

analysis）词法分析是逐个读入源程序字符，并按照构词规则分割成一系列单词，再转换成词标流的过程。单词是语言中具有独立意义的最小单位，包括

保留字、标识符、常量、运算符和界符等。词标是单词的机内表示，其格式由实现系统规定。例如：PL/0语言的单词用户写的if

a=2...机内表示为ifsym

ident

eql

number…。第63页，共102页。4.1

词法分析程序词法分析是编译过程中的一个阶段，在语法分析前进行。可以作为单独的一遍，将源程序转换成词标流供下一遍使用。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序，获得当前词标,供语法分析程序使用。如PL/0语言编译程序的实现就是把词法分析和语法分析结合在一起作为一遍。第64页，共102页。4.1

词法分析程序在词法分析程序的实际实现中，首先需要描述和刻画语言中的最小单位—单词，其次需要识别单词和执行某些相关的动作。程序设计语言词法的描述和识别机制是：描述机制用3型文法和正规表达式；识别机制用有穷状态自动机。在词法分析过程中，与语法分析无关的符号应预先处理。如为提高易读性增加的注释，与语法语义分析无关，无需产生相应的词标，处理时应滤掉。第65页，共102页。4.1

词法分析程序源程序词法分析程序语法分析程序Tokenget

token主要任务：读源程序(字符流)，产生单词符号（词标流）其他任务：滤掉空格、跳过注释和换行符,追踪换行标志，复制出错源程序，宏展开等。第66页，共102页。4.1

词法分析程序单词符号一般可分为下列五种：基本字(关键字或保留字)标识符常数（常量）运算符界符第67页，共102页。4.1

词法分析程序输出表示（单词种别，单词自身的值）。词法分析工作独立的原因：简化设计提高编译效率增加编译系统的可移植性第68页，共102页。练习教材第66~67页4.7练习的

1.(1)3.4.(b)*5.*8.第69页，共102页。第5章 LL(1)文法及其分析程序4

5.1 语法分析（回顾）(自顶向下分析的一般过程和问题)4

5.2

LL(1)

文法的定义FIRST集和FOLLOW集的定义和计算LL(1)

文法的定义非LL(1)文法的改造4

5.3 LL(1)分析程序的实现第70页，共102页。5.1 语法分析（回顾）4

句型、句子和语言的定义4

句型:x，且x∈V*，则称x是文法GTx，且x∈V

*，则称x是文法G–有文法G[s]，若S的句型。4

句子:–有文法G[s]，若S的句子。00001111例：G[s]：S→0S1，S→01S

0S1

00S11

000S111仅有00001111是句子第71页，共102页。5.1 语法分析（回顾）4

最左（最右）推导：在推导的任何一步α

β(其中α、β是句型)，都是对α中的最左（右）非终结符进行替换。4

最右推导被称为规范推导。4

由规范推导所得的句型称为规范句型。第72页，共102页。句型的分析4

句型分析

就是识别一个符号串是否为某文法的句型，也就是某文法的某个推导的构造过程。4

在语言的编译实现中，把完成句型分析的程序称

为分析程序

或识别程序。分析算法又称识别算法。4

从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。第73页，共102页。句型的分析4

分析算法可分为：4

自顶向下（自上而下）分析法：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号串匹配的推导。4

自底向上（自下而上）分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。4

两种方法反映了两种不同的语法树的构造过程第74页，共102页。自顶向下（自上而下）的语法分析4

例：文法G：S

→

cAdA

→

abA

→

a识别输入串w=cabd是否该文法的句子ScSA

d

cSA

dab推导过程：S

cAd

cabd第75页，共102页。自底向上（自下而上）的语法分析4

例：文法G：S

→

cAdA

→

abA

→

a识别输入串w=cabd是否该文法的句子SAAc

a

b

dc

a

b

dc

a

b

d归约过程：

S

cAdcabd第76页，共102页。句型分析的有关问题1）如何选择使用哪个产生式进行推导？在自顶向下的分析方法中，假定要被替换的最左非终结符号是V，且V为左部有n条规则：V→A1|A2|…|An，那么如何确定用哪个右部去替换

V？如：前例中A→ab|

a

2）如何识别可归约的串？在自底向上的分析方法中，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到某个非终结符号，该子串称为“可归约串”，归约就是用非终结符号替换它。第77页，共102页。练习教材

90

页1.3.7.（2）,（3）第78页，共102页。第6章

自底向上的优先分析法4

自底向上语法分析概述4

*6.1 自下而上的优先分析法概述（不介绍）4

*6.2 简单优先分析（不介绍）4

6.3 算符优先分析（本章重点）第79页，共102页。自底向上语法分析概述自底向上语法分析是试图将一个输入符号串反向归约至语法的开始符号，在每一步中如何选择可归约子串进行归约？常用的两种方法是：–算符优先分析法–LR分析（第7章详细介绍）自底向上语法分析比自上而下语法分析更有效率，特别是某些LR分析法对语法的限制更少。第80页，共102页。6.3

算符优先分析4

某些文法具有“算符”特性表达式运算符（优先级、结合性）人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性4

只考虑算符之间的优先关系来确定可归约串（广义讲终结符为算符）第81页，共102页。练习教材116页1.(1)、（2）、（4）2.

（1）第82页，共102页。第7章

LR分析程序及其自动构造LR分析概述LR

(0)

分析SLR(1)

分析*7.4

LR（1）分析*7.5

LALR(1)分析7.6 二义性文法在LR分析中的应用7.7

LR分析程序的自动生成第83页，共102页。7.1

LR分析概述4

一般移进-归约分析过程4

LR分析器模型和分析算法4

LR分析特征讨论第84页，共102页。7.1

LR分析概述4

例6.

1

G[S]为：（1）S

aAcBe（2）A

b（3）A

Ab（4）B

d第85页，共102页。文法G[S]：S

→

aAcBeA

→

bA

→

AbB

→

dab

bc

d

e符号栈abbcde#输入符号串 动作移进A步骤1）

##a#ab#aAbbcde#bcde#bcde#移进归约(A→b)移进A归约(A→Ab)#aAb#aAcde#cde#移进de#移进Be#e##S#aAc#

aAcd#aAcB10）

#aAcBe11）

#S#归约(B→d)移进归约接受对输入串abbcde#的移进-归约分析过程第86页，共102页。S

aAcBe符号串abbcde是否是G[S]的句子aAcde

aAbcde

abbcde7.1

LR分析概述4

在步骤3中，用A→b归约4

在步骤5中，用A→Ab归约4

问题：何时移进？何时归约？用哪个产生式归约？第87页，共102页。LR分析器模型input

xxx···#总控程序outputSn

Xn·

··

·S1

X1S0

#状态栈

文法符号栈ACTION

GOTOLR分析表产生式表第88页，共102页。练习教材151~154中的

1.2.6.*8.16

.第89