编译原理教案

教案

2006-2007学年第1学期

课程名称：编译原理

课程编号:________________

学院、专业、年级:计算机科学与技术学院

任课教师：________________

教师所在单位：计算机科学与技术学院

泰山学院

《编译原理》教案

课程简介

编译原理是计算机科学与技术专业的一门重要专业课程。该课程的目的是让学生掌握程序设计语言编译

程序构造的一般原理、基本设计方法、主要实现技术和一些自动构造工具，从而让学生了解将高级程序设计

语言源程序翻译成计算机能处理的目标代码语言的整个过程。该课程是理论性很强的课程，对于计算机专业

学生的进一步深造有较大的促进作用。同时，该课程还可以提高学生计算机的专业素质，培养他们的软件开

发能力和抽象思维能力，为进一步深造打下基础。课程主要内容有：词法分析、自顶向下语法分析、自底向

上语法分析、属性文法和语法制导翻译、存储器管理、符号表的组织与管理、中间代码优化、代码生成等内

容。课程要求：了解编译程序的构造技术：理解编译原理的理论基础即文法与形式语言概念；掌握各种词法

分析、语法分析、语法制导翻译、代码优化、存储管理的方法和技巧；具备一定的设计相关语法分析器的能

力。

该课程是计算机专业中较难得一门专业课，有如下四个重点，也是难点：（1）自动机理论（2）语法分

析（3）语法制导的翻译（4）代码优化。

《编译原理》教案

教学大纲

《编译原理》教学大纲

课程名称：编译原理

英文名称：ThePrincipleofCompilerDesign

课程编号：

课程类别：专业课

学时数：80学时

学分数：4

先修课程：高级程序设计语言、数据结构、离散数学等

适用年级：四年级

适用专业：计算机科学与技术

一、内容简介

该课程的研究对象是编译程序构造的一般原理、基本设计方法、主要实现技术和一些自动构造工具，从

而让学生掌握将高级程序设计语言翻译成计算机能处理的目标代码语言的整个过程。该课程的主要内容为：

词法分析、自顶向下语法分析、自底向上语法分析、属性文法和语法制导翻译、存储器管理、符号表的组织

与管理、中间代码优化、代码生成等内容。

二、本课程的性质、目的和任务

编译原理是计算机科学与技术专业的一门重要专业课程，其研究对象是编译程序构造的一般原理、基本

设计方法、主要实现技术和一些自动构造工具，从而让学生掌握将高级程序设计语言翻译成计算机能处理的

目标代码语言的整个过程。

通过该课程的学习，使学生掌握编译原理的基本理论和编译程序的构造技术，为进一步学习和深造打下

基础。该课程的主要内容有：词法分析、自顶向下语法分析、自底向上语法分析、属性文法和语法制导翻译、

存储器管理、符号表的组织与管理、中间代码优化、代码生成等内容。

通过各个教学环节，逐步培养学生的抽象思维能力、程序设计能力和自学能力，培养学生运用所学知识、

独立解决较复杂问题的能力。

三、本课程与其它课程的关系

本课程是计算机科学与技术专业的重要专业课。其先行课有高级程序设计语言、数据结构、离散数学、

计算机系统结构、操作系统等。

课程基础性、理论性强，与相关课程的学习联系密切，是计算机科学与技术专业学生进一步提高的基本

课程。

四、本课程的基本要求

了解编译程序的构造技术；理解编译原理的理论基础即文法与形式语言概念；掌握各种词法分析、语法

分析、语法制导翻译、代码优化、存储管理的方法和技巧；具备一定的设计相关语法分析器的能力。

五、课程内容与学时分配

（一）编译原理概论2学时

1、教学内容：

什么是编译原理

编译过程概述

编译程序的结构

编译阶段的组合

编译技术和软件工具

2、教学要求：

了解：编译技术和软件工具。

掌握：什么是编译原理，编译程序的结构，编译过程和六个阶段的任务和组合。

（二）PL/O编译程序的实现4学时

1、教学内容：

PL/O语言描述：PL/O语言的语法描述图；PL/O语言文法的EBNF表示

PL/O编译程序的结构

PL/O编译程序的词法分析

PL/O编译程序的语法分析

PL/O编译程序的目标代码结构和代码生成

PL/O编译程序的语法错误处理

PL/O编译程序的目标代码解释执行时的存储分配

2、教学要求：

了解：PL/O编译程序的词法分析、语法分析、目标代码结构和代码生成、语法错误处理及目标代码解释

执行时的存储分配。

掌握：PL/O语言的语法描述图及文法的EBNF表示，PL/O编译程序的结构。

（三）文法和语言4学时

1、教学内容：

文法的直观概念

符号和符号串

文法和语言的形式定义

文法的类型

上下文无关文法及其语法树

句型的分析：自上而下的分析方法；自下而上的分析方法；句型分析的有关问题

有关文法实用中的一些说明：有关文法的实用限制；上下文无关文法中的e规则

2、教学要求：

了解：文法的直观概念，符号和符号串，上下文无关文法中的€规则。

掌握：文法和语言的形式定义。

熟练掌握：文法的类型，上下文无关文法及其语法树，句型的分析。

（四）词法分析8学时

1、教学内容：

词法分析程序的设计：词法分析程序与语法分析程序的接口方式；词法分析程序的输出；将词法分析工

作分离的考虑

单词的描述工具：正规文法；正规式；正规文法到正规式

有穷自动机：确定的有穷自动机(DFA)；不确定的有穷自动机(NFA)；DFA-NFA的转换；确定有

穷自动机的化简

正规式和有穷自动机的等价性

正规式和有穷自动机间的转换

词法分析程序的自动构造工具：LEX语言(选讲内容)

2、教学要求：

了解：词法分析程序与语法分析程序的接口方式和输出；词法分析工作分离的考虑，LEX语言。

掌握：正规文法；正规式；正规文法到正规式。

熟练掌握：确定的有穷自动机(DFA)；不确定的有穷自动机(NFA)；DFA-NFA的转换；确定有穷

自动机的化简，正规式和有穷自动机的等价性，正规式和有穷自动机间的转换。

(五)自顶向下语法分析方法6学时

1、教学内容：

确定的自顶向下分析思想

LL(1)文法的判别

某些非LL(1)文法到LL(1)文法的等价变换

不确定的自顶向下分析思想

确定的自顶向下分析方法：递归子程序法；预测分析法

2、教学要求：

了解：不确定的自顶向下分析思想。

掌握：确定的自顶向下分析思想，LL(1)文法的判别，递归子程序法，预测分析法。

熟练掌握：某些非LL(1)文法到LL(1)文法的等价变换。

(六)自底向上优先分析法6学时

1、教学内容：

自底向上优先分析法概述

简单优先分析法：优先关系；简单优先文法的定义；简单优先分析法

算符优先分析法：直观算符优先分析法；算符优先分析法的定义；算符优先关系表的构造；算符优先分

析法；优先函数；算符优先分析法的局限性

2、教学要求：

掌握：简单优先分析法。

熟练掌握：算符优先分析法。

(七)LR分析法10学时

1、教学内容：

LR分析概述

LR(0)分析：可归前缀和子前缀；识别活前缀的有限自动机；活前缀及其可归前缀的一般计算方法；LR(0)

项目集规范族的构造

SLR⑴分析

LR(1)分析：LR(1)项目集族的构造；LR(1)分析表的构造

LALR(l)分析

二义性文法在LR分析中的应用

2、教学要求：

掌握：SLR⑴分析，LALR⑴分析。

熟练掌握：LR（O）分析，LR（1）分析。

（八）语法制导翻译和中间代码生成10学时

1、教学内容：

属性文法

语法制导翻译概论

中间代码的形式：逆波兰记号；三元式和树形表示；四元式

简单赋值语句的翻译

布尔表达式的翻译：布尔表达式的翻译方法；控制语句中布尔表达式的翻译

控制结构的翻译：条件转移；开关语句；for循环语句；出口语句；goto语句；过程调用语句的四元式

产生。

说明语句的翻译：简单说明句的翻译；过程中的说明

数组和结构的翻译：数组说明和数组元素的引用；结构（记录）说明和引用的翻译

2、教学要求：

掌握：中间代码的形式逆波兰记号、三元式和树形表示、四元式。

熟练掌握：简单赋值语句、布尔表达式、控制结构、说明语句、数组和结构的翻译。

（九）符号表4学时

1、教学内容：

符号表的作用和地位

符号的主要属性机作用

符号表的组织：符号表的总体组织：符号表项的排列；关键字域的组织；其它域的组织；下推链域的组

织

符号表的管理：符号表的初始化；符号的登录；符号的查找；符号表中分程序结构层次的管理

2、教学要求：

掌握：符号的主要属性机作用。

熟练掌握：符号表的组织。

（十）目标程序运行时的存储组织6学时

1、教学内容：

数据空间的三种不同使用方法和管理方法：静态存储分配；动态存储分配；栈式动态存储分配；堆式动

态存储分配

栈式存储分配的实现：简单的栈式存储分配的实现；嵌套过程语言的栈式实现；分程序结构的存储管理

参数传递：传值；传地址；过程参数

2、教学要求：

了解：堆式动态存储分配、过程调用、过程进入和过程返回

掌握：静态存储分配，参数的传值、传地址和过程参数

熟练掌握：简单的栈式存储分配的实现；嵌套过程语言的栈式实现；分程序结构的存储管理

（+-）代码优化8学时

1、教学内容：

优化技术简介

局部优化：基本块的划分；基本块的变换；基本块的DAG表示；DAG的应用；DAG构造算法讨论

控制流分析和循环优化：出现域循环；循环；循环的查找；可规约流图；循环优化

数据流的分析与全局优化：一些主要的概念；数据流方程的一般形式；到达一定值数据流方程；可用表

达式及其数据流方程；活跃变量数据流方法；复写传播

2、教学要求：

了解：数据流的分析与全局优化。

掌握：局部优化、控制流分析和循环优化。

十二、代码生成6学时

1、教学内容：

代码生成概述

一个计算机模型

一个简单的代码生成器：寄存器分配的原则；待用信息链表法；代码生成算法

代码生成研究现状：中间语言的选择；代码生成的自动化研究

2、教学要求：

了解：代码生成研究现状。

掌握：寄存器分配的原则；待用信息链表法；代码生成算法。

五、主要参考书目

考试教材：《编译原理》，吕映芝、张素琴等编著清华大学出版社。

主要参考书目有；

《Compilers:Principles,Techniques,andTools/编译原理技术与工具（英文版）》ALFREDV.AHO,

RAVISETHI,JEFFREYD.ULLMAN.

《程序设计语言编译原理》陈火旺，国防工业出版社，2000

《编译原理及编译程序构造》高仲仪、金茂忠，北京航空学院出版社，1990.12

《编译原理》胡伦骏、徐兰芳、刘建农编，电子工业出版社.2002年

《编译程序原理与技术》李赣生、王华民编著，清华大学出版社

《编译原理技术》陈意云，中国科技大学出版社

《编译原理习题精选》陈意云、张昱著，中国科技大学出版社

《编译原理》教案

授课时间第一周第1次课

课程的性质与任务

第1章引论

1.1什么是编译程序

任课教师

授课章节1.2编译过程、编译程序的结构冯玲讲师

及职称

1.3编译程序和软件工具

1.4程序设计语言范型

教学方法

多媒体课堂教学课时安排节课

与手段2

《编译原理》（第2版）张素琴，吕映芝等著，清华大学出版社

《Compilers:Principles,Techniques,andTools/编译原理技术与工具（英文版）》

ALFREDV.AHO.RAVISETHI,JEFFREYD.ULLMAN.

《程序设计语言编译原理》陈火旺，国防工业出版社，2000

使用教材和

《编译原理及编译程序构造》高仲仪、金茂忠，北京航空学院出版社，1990.12

主要参考书

《编译原理》胡伦骏、徐兰芳、刘建农编，电子工业出版社.2002年

《编译程序原理与技术》李赣生、王华民编著，清华大学出版社

《编译原理技术》陈意云，中国科技大学出版社

《编译原理习题精选》陈意云、张昱著，中国科技大学出版社

教学目的与要求：

本章重点对编译程序的功能和结构做了综合概述，要求学生了解编译程序各个成分在编译阶段的逻辑关系以

及它们怎样作为一个整体完成编译任务的。

1了解课程的性质与任务

2理解什么是编译程序

3了解编译过程和编译程序的结构

4为什么要学习编译程序

教学重点，难点：

1.理解理解什么是编译程序

2.了解编译过程和编译程序的结构

教学内容:

课程的性质与任务

•本课程地位属于计算机科学与技术专业的一门重要的专业必修课。

•本课程的学习有助于对语言的执行系统、程序语言的理解。

•通过本课程的学习，要掌握编译程序的一般构造原理，包括语言基础知识、词法分析程序设计原理和构造

方法。各种语法分析技术和中间代码生成符号表的构造、代码优化、并行编译技术常识及运行时存储空间的

组织等基本方法和主要实现技术。

语言的发展

•机器语言

•汇编语言

•高级语言

•查询语言、标注语言

第1章编译程序概论

1.1什么是编译程序

1.1.1语言处理程序

语言处理程序：把较高级语言编写的程序语义等价地变换成较低级语言程序的程序。

/汇编程序

语言处理程序《解释程序

、编译程序

(0)语言的执行方式

解释方式(Basic)口译

编译方式(C,pascal)笔译

(1)汇编程序

汇编程序：把用汇编语言编写的程序翻译成机器语言的程序。

汇编语言是为特定的计算机或计算机系统设计的面向机器的语言。如8086/8088PC、Z-80、VAX汇编语言。

汇编的过程就是对汇编指令逐行进行处理，最终得到机器代码的过程。

—A|汇编程序]―定藐))

⑵解释程序

解释程序：对用高级语言编写的程序进行逐句分析并立即得到结果。

解释程序按源程序中语句的动态顺序逐句进行分析翻译，并立即予以执行，它不产生目标代码。

BASICAPLLISPJava等语言就是采用解释方法实现的。

高级语言解释系统(interpreter)

功能：让计算机执行高级语言(basic,lisp,prolog)

与编译程序的不同：1)不生成目标代码2)能支持交互环境(同增量式编译系统)

源程序|解释程序

计算结果

初始数据

解释系统

直接对源程序中的语句进行分析，执行其隐含的操作。

《编译原理》教案

如：....

b:=2;

lnt2

a：=b+2;i-------y编译程刃-----〉

Stb

writea;

Ldb

add2

Sta

解释程序直接将4的值输出(显示)

⑶编译程序

编译程序：把用高级语言编写的源程序翻译成等价的低级语言(称作目标语言)程序。

编译系统是编译程序和运行系统的合称。

一个编译程序把一个高级语言源程序翻译成目标程序的工作可分为前后衔接的六个阶段：词法分析、语

法分析、语义分析、中间代码生成、代码优化及目标代码生成。大多数高级语言是采用编译的方法实现的。

如：PASCAL>FORTRAN.ADA、C、C++、PL/1、ALGOL60、ALGOL68,等等。

1.1.2什么是编译程序(compiler)

编译程序是现代计算机系统的基本组成部分.

从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言(称作源语言)书写的程序翻译成另--种语言

(称作目标语言)的等价的程序.

编译程序的功能

术语：编译程序的源语言(源程序)；

编译程序的目标语言(目标程序)；

编译程序的实现语言；

软件：计算机系统中的程序及其文档；

系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。他和具体

的应用领域无关，如编译系统和操作系统等。

处理系统：把软件语言书写的各种程序处理成可在计算机上执行的程序。

软件语言：用于书写软件的语言。它主要包括需求定义语言，功能性语言，设计性语言，程序设计语

言以及文档语言

编译程序(compiler);

编译程序的源语言(源程序)(sourcelanguage)(sourceprogram);

编译程序的目标语言(目标程序)(objectortargetlanguage)(objectortargetprogram);

编译程序的实现语言(implementationlanguage);

语言处理程序(languageprocessor);

语言转(变)换(languagetransformation)

—源程序一

©

I预处理器I

《编译原理》教案

1.2编译过程和结构

1.2.1编译逻辑过程

（1）词法分析这个阶段的任务是从左至右、从上到下一个字符一个字符地读入源程序，对构成源程序的字符

流进行扫描和分解，从而识别出一个个单词。

词法分析后可能返回：

单词类型单词值

保留字int

标识符（变量名）a

界符；

标识符（变量名）a

算符（赋值）=

标识符（变量名）a

算符（加）+

整数2

界符；

有关术语

词法分析--从左到右读字符流的源程序、识别（拼）单词。

单词--具有独立意义的基本语法单位。

保留字-一具有特殊规定的意义，不允许用户将它们作为别用，是用户定义标识符的禁区。

标识符--用来表示程序、过程、函数、类型、常量和变量等名称的符号。

（2）语法分析

在词法分析的基础上，根据语言的语法规则（文法规则）,把单词符号串分解成各类语法单位，如“短语”、

“句子”、“程序段”和“程序”。通过语法分解，确定整个输入串是否构成一个语法上正确的程序.

例：符号串X+0.168*Y,经语法分析就可识别出这个字符串属于算术表达式。

Y:=X+0.168*Y;

语法分析所依循的是语言的语法规则，用产生式描述。语法分析器读入单词，将它们组合成按产生式规

定的各类语法单位。

sum:=first+count*10

规则

〈赋值语句＞：:=＜标识符＞"：=”〈表达式》

〈表达式》:=〈表达式＞“+”（表达式〉

〈表达式》:=＜表达式＞“*”〈表达式》

〈表达式》:=“（”〈表达式》“）”

（表达式》:=〈标识符＞

〈表达式》:=〈整数》

〈表达式》:=＜实数＞

《编译原理》教案

赋值语句

表达式

标识符

术语

语法：定义语言各语法成分的形式或结构。

语法分析：依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树)。

语法树(推导树)：表示句型推导(或归约)的树型结构。语法树有助于理解一个句子语法结构的层次0

(3)语义分析

语义审查(静态语义)

类型匹配

类型转换

例:Programp();

Varrate:real;

procedureinitial;

position:=initial+rate*60

/*error*//*error*//*warning*/;

语义分析的一个重要内容是类型检查，对表达式及语句中的各语法成分作类型检查和分析.

如：

Varcount:real;

Varfirst:real;

Varsum:real;

sum:=first+count*10

术语

语法：用来定义语言中各语法成份的形式或结构。

语义：用来规格各语法成份的含义和功能，即规定它们的属性或在执行时应进行的运算或操作。

语义分析：检查源程序是否包含语义错误，并搜集类型，供后面的代码生成阶段使用，只有语法和语义正确

的源程序才可被翻译成目标代码。语义分析程序需要进行频繁的造表和查表工作。

(4)中间代码生成

语义分析之后生成一种介于源语言和目标语言之间的中间语言代码。中间代码有多种形式：三元式、四

元式、逆波兰表示、树型结构

《编译原理》教案

例：a:=b*c

三元式：逆波兰表示式：abc*:=

(1)(*,b,c)树：,:=

(2)(:=,a,⑴)a*

四元式：bc

(*,b,c,a)

idl:=id2+id3*10

因运算需要，需设置临时变量tl,t2,t3来存放中间运算结果。

四元式(算符第一运算量第二运算量运算结果)

(1)(inttoreal,10,tl)

(2)(*,id3,tl,t2)

(3)(+,id2,t2,t3)

(4)(:=,t3,idl)

中间代码的几种形式

逆波兰表示：运算符在其运算量之后的表达式。

三元式：(OP,ARG1,ARG2)

四元式：(OP,ARG1,ARG2,RESULT)

树：根结点0P,左子树ARG1,右子树ARG2

(5)代码优化

对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效(省时间和省空间)的目标代码

tl=b*ctl=b*c

t2=tl+0t2=tl+tl

t3=b*ca-t2

t4=t2+t3

a=t4

在本例中，b、c的值没有改变，故tl=t3,由第二个表达式知道t2=tl。

(6)目标代码生成

将前阶段产生的中间代码翻译为机器语言或汇编语言形式的目标程序。目标程序总是按某一具体计算机的机

器语言或汇编语言来产生的。

目标代码生成

(*,id310.0tl)

(+,id2tlidl)

1

I

movfid3,R2

mulf#10.0,R2

movfid2,R1

addfR2,R1

movfRI,idl

《编译原理》教案

(7)符号表管理

符号表管理：记录源程序中使用的名字，收集每个名字的各种属性信息:类型、作用域、分配存储信息

在编译过程中，源程序中的标识符及其各种属性都要记录在符号表中，这些属性可以提供标识符的存储分配

信息、类型信息、作用域信息等等。对于过程标识符，还要有参数信息，包括参数的个数和类型、实参和形

参的结合方式等等。

符号表结构

符号表是一种含记录的数据结构，通常一个标识符在符号表中占一个记录，记录中除了标识符的名字域

之外，还有记录该标识符属性的域。

(8)出错处理

编译的每一个阶段都会发现源程序的错误，在发现错误之后，一•般要对其有一定的处理措施，因而编译

还可继续执行，不会一有错误就停止编译工作。

出错处理(errorhandling)(errorreportinganderrorrecovery)

在词法分析中，能发现单词拼写错误。

在语法分析中，检查单词串是否符合语法的结构规则。

在语义分析中，编译程序进一步查出语法上虽正确但含有无意义的操作部分，如两个标识符相加，一个是数

组名，一个是过程名，虽然语法上允许，但语义上不允许，各种错误，都应在相应的阶段进

行处理。

检查错误

报告出错信息(错误种类及位置)

校错及排错

恢复编译工作

1.2.2编译程序的结构(components)

A词法分析程序k

出

错

处

理

】目标代码生成程序r

1.2.3编译阶段的组合

分析，综合(synthesis)

源程序的分析

线性分析

层次分析

语义分析

目标程序的综合

编译的前端(frontend):这些阶段以来于源语言、与目标机无关。

编译的后端(backend)：依赖于目标机器的阶段。

遍(趟)从头到尾扫描源程序(各种形式)一遍(pass)

编译阶段和运行阶段存储结构

《编译原理》教案

1.3编译技术和软件工具

编译程序实现方式:手工,机器语言,汇编,系统程序设计语言，自动构造工具lexyaccgcc

1.3.1编译程序的发展

riented--------'编译।,,Computer-

oriented

1,...---

计算模式，语言冯诺曼机体系

范式结构并行体系

结构嵌入系统

编译程序的发展

(1)语言范型(支持的计算模式)

命令式(imperativelanguage)

应用式(applicative),也成函数式

基于规则的(rule-based)

面向对象的(object-oriented)

(2)编译程序执行环境

批处理

交互环境

嵌入系统环境

1.3.2编译技术和软件工具

结构化编辑器

程序调试工具

程序测试工具：1静态分析2动态分析3度量工具(结构度量)

4分析工具(sourceinsight)

高级语言转换工具

广泛的语言领域

1.3.3研究领域

(1)并行化编译技术

目的：提高并行计算机体系结构的性能

(2)交叉编译器

由于目标机指令系统与宿主机的指令系统不同，编译时将应用程序的源程序在宿主机上生成目标机代码，称

为交叉编译。简单地说，就是在一个平台上生成另一个平台上的可执行代码。

嵌入式

(3)自展编译技术用被编译的语言来书写该语言自身的编译程序。

小结

《编译原理》教案

复习思考题、作业题：

1.什么是编译程序？

2.简要介绍编译过程的六个阶段，并给出编译程序的结构。

下次课预习要点

预习第二章PL/O编译程序的结构与词法分析等内容

实施情况及教学效果分析

授课时间分配合理；

编译过程、编译基本概念重点突出，

学生能够掌握基本内容；

教学效果良好。

学院审核意见

同意实施

学院负责人签字

年月日

《编译原理》教案

授课时间第一周__________第2次课

第2章PL/O编译程序的实现

2.1PL/O语言描述

任课教师

授课章节2.2PL/O编译程序的结构冯玲讲师

及职称

2.3PL/O编译程序的词法分析

教学方法

多媒体课堂教学课时安排2节课

与手段

《编译原理》（第2版）张素琴，吕映芝等著，清华大学出版社

《Compilers:Principles,Techniques,andTools/编译原理技术与工具（英文版）》

ALFREDV.AHO,RAVISETHI,JEFFREYD.ULLMAN.

《程序设计语言编译原理》陈火旺，国防工业出版社，2000

使用教材和

《编译原理及编译程序构造》高仲仪、金茂忠，北京航空学院出版社，1990.12

主要参考书

《编译原理》胡伦骏、徐兰芳、刘建农编，电子工业出版社.2002年

《编译程序原理与技术》李赣生、王华民编著，清华大学出版社

《编译原理技术》陈意云，中国科技大学出版社

《编译原理习题精选》陈意云、张昱著，中国科技大学出版社

教学目的与要求:

以PL/O为实例，学习编译程序实现的基本步骤和相关技术。

教学重点，难点:

PL/O编译程序的结构与词法分析

教学内容:第2章PL/O编译程序的实现

PL/O编译系统的结构框架

PL/O源程序

PL/O编译程庠

类pcode代码

类pcode解释程序/

输入▲输出

2.1PL/0语言

⑴PL/0程序示例

CONSTA=10;(*常量说明部分*)

VARB,C;(*变量说明部分*)

PROCEDUREP;(*过程说明部分*)

VARD;

PROCEDUREQ;

VARX;

BEGIN

READ(X);

D:二X;

WHILEX#()

DOCALLP;

END;

BEGIN

WRITE(D);

CALLQ;

END;

BEGIN

CALLP;

END.

(2)PL/0的语法描述图

程序一►分序口

口内的文字表示非终结符v

O或O内的文字或符号表示终结符

条件语法描述图

表达式和项的语法描述图

因子的语法图

⑶PL/0语言文法的EBNF表示

EBNF引入的符号（元符号）：

＜＞用左右尖括号括起来的语法成分为非终结符

::=（一）'定义为‘：：=（一）的左部由右部定义

I喊，

｛）表示花括号内的语法成分可重复任意次或限定次数

[]表示方括号内的语法成分为任选项

（）表示圆括号内的成分优先

例：用EBNF描述〈整数〉的定义：

〈整数＞：：=[+■＜数字＞｛＜数字＞｝

〈数字＞：：=0|1|2|3|4|5|6|7|8|9

或更好的写法

〈整数＞：：=[+卜]＜非零数字〉｛〈数字〉｝10

〈非零数字＞：：=1|2|3|4|5|6|7|8|9

〈数字＞：：=0|〈非零数字〉

PL/0余言的文法表示见P15.

（4）PL/0语言是PASCAL语言的子集

同PASCAL作用域规则（内层可引用包围它的外层定义的标识符），上下文约束，过程可嵌套定义，可递归调

用

子集

数据类型，只有整型

数据结构，只有简变和常数

数字最多为14位

标识符的有效长度是10

语句种类

过程最多可嵌套三层

⑸目标代码类pcode

目标代码类pcode是一种假想栈式计算机的汇编语言。指令格式：

目标程序

《编译原理》教案

(2)PL/O编译程序的总体设计

其编译过程采用一趟扫描方式，以语法、语义分析程序为核心

词法分析程序和代码生成程序都作为一个过程，当语法分析需要读单词时就调用词法分析程序，而当语

法、语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。

表格管理程序实现变量，常量和过程标识符的信息的登录与查找。

出错处理程序，对词法和语法、语义分析遇到的错误给出在源程序中出错的位置和与错误性质有关的编

号，并进行错误恢复。

(3)编译程序总体流程图

(4)PL/O编译程序过程一览表(P17)

2.3PL/O编译程序的词法分析

(1)PI/O词法分析程序Getsym

识别的单词：(类别，值)

保留字：如：BEGIN,END、IF、THEN等

运算符：如：+、-、*、/、：=、#、>=、<=等

标识符：用户定义的变量名、常数名、过程名

常数：如：10、25、100等整数

界符：如—」、‘；‘、'('、)等

Getsym用到三个单元：

SYM:存放单词类别

ID:存放标识符的值

NUM:存放整数的值

(2)词法分析过程GETSYM

流程图(P19)

所要完成的任务：

滤空格

识别保留字

识别标识符

拼数

识别单字符单词(<,>等)

拼双字符单词(<=,<>等)

输出源程序

读字符子程序(getch)(p20)

(3)进一步的说明

z如何识别标识符

y先查保留字表，建立保留字表

保留字内部表示

beginbeginsym

callcallsym

writewritesym

查到时找到相应的内部表示

若不是保留字，则是用户定义的标识符，应建立标识符表。

类似地可以建立运算符、常数、界符表

词法分析程序的实现见附录

《编译原理》教案

复习思考题、作业题：P30,练习2

2.2若pl/O编译程序运行时的存储分配策略采用栈式动态分配，并用动态链和静态链的方式分别解决递归调用和非局部变量的

引用问题，试写出下列程序执行到赋值语句b:=10时运行栈的布局示意图。Varx,y;

Procedurep;

Vara;

Procedureq;

Varb;

Begin(q)

B:=10;

End(q);

Procedures;

Varc,d;

Procedurer;

Vare,f;

Begin(r)

Callq;

End(r);

Begin(s)

Callr;

End⑸；

Begin(p);

Calls;

End(p);

Begin(main)

Callp;

End(main).

下次课预习要点

复习PL/O编译程序的结构与词法分析，预习2.4—2.7小节

实施情况及教学效果分析

授课时间分配合理；

PL/O语言、编译各阶段的功能为教学重点，也是难点;

学生能够掌握基本内容；

教学效果良好。

学院审核意见

同意实施

学院负责人签字

年月日

《编译原理》教案

授课时间第二周第2次课

第2章PL/O编译程序的实现

2.4PL/O编译程序的语法语义分析

2.5PL/O编译程序的目标代码结构和代码生成

任课教师

授课章节2.6PL/O编译程序的语法错误处理冯玲讲师

及职称

2.7PL/O编译程序的目标代码解释执行时的存

储分配

教学方法

多媒体课堂教学课时安排2节课

与手段

《编译原理》（第2版）张素琴，吕映芝等著，清华大学出版社

《Compilers:Principles,Techniques,andTools/编译原理技术与工具（英文版）》

ALFREDV.AHO,RAVISETHI,JEFFREYD.ULLMAN.

《程序设计语言编译原理》陈火旺，国防工业出版社，2000

使用教材和

《编译原理及编译程序构造》高仲仪、金茂忠，北京航空学院出版社，1990.12

主要参考书

《编译原理》胡伦骏、徐兰芳、刘建农编，电子工业出版社.2002年

《编译程序原理与技术》李赣生、王华民编著，清华大学出版社

《编译原理技术》陈意云，中国科技大学出版社

《编译原理习题精选》陈意云、张昱著，中国科技大学出版社

教学目的与要求：

以PL/O为实例，学习编译程序实现的基本步骤和相关技术。

教学重点，难点：

1掌握PL/O编译程序的语法语义分析与目标代码结构和代码生成

2了解PL/O编译程序的语法错误处理

3理解PL/O编译程序的目标代码解释执行时的存储分配

《编译原理》教案

教学内容：

2.4PL/O编译程序语法语义分析

2.4.1PL/O编译程序语法分析的设计与实现

自顶向下的语法分析

递归子程序法：对于每个非终结符，编写一个子程序，由该子程序负责识别该语法单位是否正确。

先回忆PL/O的语法规定。

递归子程序法：对应每个非终结符语法单元，编一个独立的处理过程（或子程序），识别该终结符对应的

句子。

语法分析从读入第一个单词开始，由非终结符（程序>（即开始符）出发，沿语法描述图箭头所指出的方

向进行分析。当遇到非终结符时，则调用相应的处理过程，从语法描述图看，也就进入了一个语法单元,

再沿当前所进入的语法单元所指箭头方向继续进行分析。当遇到描述图中是终结符时，则判断当前读入

的单词是否与图中的终结符相匹配，若匹配，再读取下一个单词继续分析。遇到分支点时，将当前的单

词与分支点上多个终结符逐个相比较，若都不匹配时可能是进入下一个非终结符语法单位或是出错。

表达式的EBNF

〈表达式〉：：=[+■〈项〉｛（+I-）〈项〉｝

〈项〉：：=〈因子〉｛（*|/）〈因子〉）

〈因子〉：：=〈标识符〉|〈无符号整数〉「（，〈表达式〉9'

〈表达式〉的递归子程序实现

procedureexpr;

begin

ifsymin[plus,minus]then

begin

getsym;term;

end

elseterm;

whilesymin[plus,minus]do

begin

getsym;term;

end

end;

〈项〉的递归子程序实现

〈项〉：：=〈因子〉｛（*|/）〈因子〉）

procedureterm;

begin

factor;

whilesymin[times,slash]do

begin

getsym;factor;

end

end;

〈因子〉的递归子程序实现

procedurefactor;

begin

ifsym<>identthen

《编译原理》教案

ifsym＜＞numberthen

ifsym='（'then

begin

getsym;

expr;

ifsym='）'thengetsym

elseerror

end

elseerror

elsegetsym

elsegetsym

end;

（程序＞::=＜分程序＞

begin（*main*）

…（*initialize*）

…（*r/wfileset*）

getsym;

block（）;

ifsym＜＞periodthenerror...

end.

2.4.2PL/0编译程序语义分析的设计与实现

PL/O编译程序语法、语义分析的的核心程序是BLOCK过程

（1）说明部分的分析与处理

对每个过程（含主程序）说明的对象（变量，常量和过程）造符号表，登录标识符的属性。

标识符的属性:种类，所在层次,值和分配的相对位置。

登录信息由ENTER过程完成。

注意：所有标识符保存在Table中，TX表示索引表的指针

LEV表示层次

Dx表示局部变量分配的位置

常量说明语句的处理

语法：（常量说明部分〉：：=const〈常量定义＞{,〈常量定义＞}；

〈常量定义〉：：=〈标识符＞=〈无符号整数》

〈无符号整数）：：=〈数字＞{〈数字＞}

ifsym=constsymthen

begin

getsym;（*获取下一个token,正常应为用作常量名的标识符*）

repeat（*反复进行常量声明*）

constdeclaration;（*声明以当前token为标识符的常量*）

whilesym=commado（*如果遇到了逗号则反复声明下一常量*）

begin

getsym;（*获取下一个token,这里正好应该是标识符*）

constdeclaration（*声明以当前token为标识符的常量*）

end;

《编译原理》教案

ifsym=semicolonthen（*如果常量声明结束，应遇到分号*）

getsym（*获取下一个token,为下一轮循环做好准备*）

else

error（5）（*提示5号错误*）

untilsym<>ident（*如果遇到非标识符,则常量声明结束*）

end;

常量说明处理

procedureconstdeclaration;

begin

ifsym=identthen

begin

getsym;

ifsymin[eql,becomes]then（*如果是等号或赋值号*）

ifsym=becomesthen（*如果是赋值号（常量生明中应该是等号）*）

error（1）;（*提示1号错误*）

getsym;（*获取下一个token,等号或赋值号后应接上数字*）

ifsym=numberthen（*如果的确是数字*）

begin

enter（constant）;（*把这个常量登陆到符号表*）

getsym（*获取下一个token,为后面作准备*）

end

elseerror（2）（*如果等号后接的不是数字，提示2号错误*）

elseerror（3）（*如常量标识符后不是等号或赋值号，提示3号错误*）

end

elseerror（4）

end（*constdeclaration*）;

变量定义语句的处理

语法：〈变量说明部分》：：二var〈标识符>{,〈标识符>}；

程序：

ifsym=varsynithen

begin

getsym;

repeat

vardeclaration;（*变量说明处理*）

whilesym=commado

begin

getsym;

vardeclaration

end;

ifsym=semicolonthen

getsym

elseerror（5）

untilsymOident;

end;

《编译原理》教案一

变量说明处理

procedureardeclaration;

begin

ifsym=identthen

begin

enter(variable);

getsym

end

elseerror(4)

end(*vardeclaration*);

过程定义语句的处理

程序：

whilesym=procsymdo(*循环声明各子过程*)

begin

getsym;(*获取下一个token,此处正常应为作为过程名的标识符*)

ifsym=identthen(*如果token确为标识符*)

begin

enter(procedur);(*把这个过程登录到名字表中*)

getsym(