编译原理第二章一个微小编译器

1、2021-11-4北京化工大学信息科学与技术学院计算机系22021-11-4北京化工大学信息科学与技术学院计算机系2第 1 章 编译简介1.11.1 编译器编译器 1.21.2 源程序的结构源程序的结构 1.31.3 编译器的实例编译器的实例 1.41.4 与编译相关的数据结构与编译相关的数据结构 1.51.5 编译器各阶段的分组编译器各阶段的分组 2021-11-4北京化工大学信息科学与技术学院计算机系32021-11-4北京化工大学信息科学与技术学院计算机系31.1 编译器2021-11-4北京化工大学信息科学与技术学院计算机系42021-11-4北京化工大学信息科学与技术学院计算机系4t

2、hephaseofacompiler编译程序的结构编译程序的结构2021-11-4北京化工大学信息科学与技术学院计算机系5 5编译器的分析/综合模式 编译器分析（前端） 综合（后端）语法/语义分析代码生成/优化源程序中间代码目标代码编译器基础架构（infrastructure）源代码的中间表示c+ parserada parserjava parserc+源程序 ada源程序 java源程序 .x86 a86/a386.2021-11-4北京化工大学信息科学与技术学院计算机系6q and a javajava程序编译执行过程程序编译执行过程java 语言能够跨平台执行，在不同平台上有不同的 j

3、ava 虚拟机，可以使 java 的执行代码即统一的中间代码与平台无关。2021-11-4北京化工大学信息科学与技术学院计算机系7 7例例1. 1. pascal源程序语句如下： var x, y, z : real; x := y + z * 60;词 法 分 析（记号流）(id,1),(:=),(id,2),(+),(id,3),(*) ,(60)依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树).语法分析1.3 编译器的实例2021-11-4北京化工大学信息科学与技术学院计算机系82021-11-4北京化工大学信息科学与技术学院计算机系8赋值语句标识符表达式表达式+表达式

4、表达式标识符整数标识符:=表达式*:=id1 +id2 *id3 60语法树x := y + z * 60;2021-11-4北京化工大学信息科学与技术学院计算机系9 9语义分析中间代码的形式与作用：(序号) (op， arg1, arg2, result)result := arg1 op arg2 (1) (itr, 60, , t1)(2) (*, id3, t1, t2)(3) (+, id2, t2, t3)(4) (:=, t3, , id1) :=id1 +id2 *id3 itr601234y real 4z real 8. .符号表部分内容x real 0中间代码生成x :=

5、 y + z * 60;2021-11-4北京化工大学信息科学与技术学院计算机系1010中间代码优化目标代码生成(1) (itr, 60, , t1)(2) (*, id3, t1, t2)(3) (+, id2, t2, t3)(4) (:=, t3, , id1) (1) (*, id3, 60, t1)(2) (+, id2, t1, id1) movf r2, id3mulf r2, #60movf r1, id2 addf r1, r2movf id1, r1x := y + z * 60;r2 := id3r2 := r2 * 60r1 := id2r1 := r1 + r2id1

6、 := r1id1 := id2 + id3 * 602021-11-4北京化工大学信息科学与技术学院计算机系1111编译器各阶段工作的归纳 词法分析：识别单词，至少分以下几大类：关键字（保留字）、标识符、特殊符号； 语法分析：得到语言结构并以树的形式表示； 语义分析：考察结构正确的句子是否语义合法，可修改树结构； 中间代码生成（可选）：生成一种既接近目标语言，又与具体机器无关的表示，便于优化与代码生成； 中间代码优化（可选）：局部优化、循环优化、全局优化等；优化实际上是一个等价变换，变换前后的指令序列完成同样的功能，但是，在占用的空间上和程序执行的时间上都更省、更有效。 目标代码生成：不同形

7、式的目标代码汇编、可重定位、内存形式; 符号表管理：合理组织符号，便于各阶段查找、填写等； 出错处理：错误的种类词法错、语法错、静态语义错、动态语义错。2021-11-4北京化工大学信息科学与技术学院计算机系122021-11-4北京化工大学信息科学与技术学院计算机系13 2021-11-4北京化工大学信息科学与技术学院计算机系14pbeginvdl;slend.vdlvd|vd;vdlvdvarid:tsls|s;slsid:=e|write(e)|read(id)tint|realeid|num|e+e|e*e|(e)2021-11-4北京化工大学信息科学与技术学院计算机系152021-1

8、1-4北京化工大学信息科学与技术学院计算机系16micro语言中单词的种类：语言中单词的种类：2.2 micro2.2 micro语言的词法分析语言的词法分析 以字母开头：以字母开头：保留字：保留字：begin,end,var,read,write,int,real标识符：字母标识符：字母/数字串数字串以数字开头：以数字开头：整常数：数字开头的数字串整常数：数字开头的数字串实常数：整数实常数：整数.整数整数符号词：符号词：+，-，*，/，(，)，:，:=，;，.控制词：控制词： ( (换行符）换行符） 2021-11-4北京化工大学信息科学与技术学院计算机系17输出. .任务：任务：token

9、定义：定义：二元组（单词种类，单词自身值）二元组（单词种类，单词自身值） 标识符标识符:($id,标识符）如标识符）如($id,x) 整常数整常数:($intc,整常数）如（整常数）如（$intc,5) 实常数实常数:($realc,实常数）如实常数）如($realc,0.5) 保留字保留字:($begin,-),($end,-),($var,-) 符号词符号词:($plus,-),($mult,-),($lparen,-), 换行符换行符:($line,-)2021-11-4北京化工大学信息科学与技术学院计算机系18micromicro的词法分析的词法分析图 源程序在文件中的表示空格2021

10、-11-4北京化工大学信息科学与技术学院计算机系19micromicro的词法分析的词法分析图图 词法分析后的词法分析后的tokentoken表示表示2021-11-4北京化工大学信息科学与技术学院计算机系20micro的词法分析的词法分析 读当前字符流，直至文件结束。读当前字符流，直至文件结束。如果是：如果是： (1)(1)标识符标识符时判断是保留字还是变量标识时判断是保留字还是变量标识 符，构造符，构造tokentoken表示；表示； (2)(2)数字数字时判断是整型还是实型，构造时判断是整型还是实型，构造 tokentoken表示；表示； (3)(3)构造其它合法的符号的构造其它合法的符

11、号的tokentoken表示；表示； (4)(4)遇到非法符号则报错。遇到非法符号则报错。2.2 micro2.2 micro语言的词法分析语言的词法分析3.词法分析过程词法分析过程2021-11-4北京化工大学信息科学与技术学院计算机系21micro语言的词法分析程序语言的词法分析程序例：例：beginvarx1:real;varz1:real;x1:=0.5;z1:=x1+56;write(z1+2.3);read(x1)end.2021-11-4北京化工大学信息科学与技术学院计算机系22micro语言的词法分析程序语言的词法分析程序从输入流把当前标识符从输入流把当前标识符名读到名读到na

12、mename中（它可能中（它可能是保留字）。在调用时，是保留字）。在调用时，当前字符一定是字母，当前字符一定是字母，且已被读到且已被读到chch中。中。gentoken(token)将将token送入送入token区。区。例：例：beginvarx1:real;varz1:real;x1:=0.5;z1:=x1+56;write(z1+2.3);read(x1)end.2021-11-4北京化工大学信息科学与技术学院计算机系23 词法错误词法错误2021-11-4北京化工大学信息科学与技术学院计算机系242021-11-4北京化工大学信息科学与技术学院计算机系252021-11-4北京化工大学

13、信息科学与技术学院计算机系26micromicro语言的词法分析程序的相关子程序语言的词法分析程序的相关子程序(3)(3)intconst(n,l):从输入流读当前整常数，并在从输入流读当前整常数，并在n中给出所中给出所读常数的二读常数的二(十十)进制值，在进制值，在l中给出整常数的位数。中给出整常数的位数。调用时当前字符应是数字。调用时当前字符应是数字。procedureintconst(n,l);beginn:=num(ch);l:=1;read(ch);whileisdigit(ch)don:=n*10+num(ch);l:=l+1;read(ch)end读整常数读整常数num(ch):

14、数字字符数字字符ch对应的二对应的二(十十)进制值。进制值。2021-11-4北京化工大学信息科学与技术学院计算机系27 例：例：beginvarx1:real;varz1:real;x1:=0.5;z1:=x1+56;write(z1+2.3);read(x1)end.2021-11-4北京化工大学信息科学与技术学院计算机系28任务：任务：2.2 micro2.2 micro语言的词法分析语言的词法分析2021-11-4北京化工大学信息科学与技术学院计算机系29说明：说明：语法分析只用到单词的语法分析只用到单词的token表示，表示，并不改变单词的并不改变单词的token表示表示。2021-

15、11-4北京化工大学信息科学与技术学院计算机系30 ，2021-11-4北京化工大学信息科学与技术学院计算机系31procedureparser();beginmatch($begin,1);match($var,2);ld:match($id,3);match($colon,4);match($intc/$reac,5);match($semi,6);readtoken(token);iftoken=$linethenreadtoken(token);iftoken=$varthengotold;match(kind,n)：读当前：读当前token，并检查并检查token.lh=kind？若

16、若不等不等，则打出，则打出错误编号错误编号n。token.lh：token的左半部。的左半部。token.rh：token的右半部。的右半部。readtoken(token):把当前把当前token读到读到token中。中。 micro语言的语法分析程序语言的语法分析程序声明列声明列处理处理2021-11-4北京化工大学信息科学与技术学院计算机系32ls:casetokenof($write,-）match($lparen,7);expr();match($rparen,8);($read,-)match($lparen,9);match($id,10);match($rparen,11);(

17、$id,-)match($assig,12);expr();othererror(13)end;readtoken(token);/读语句的后继符读语句的后继符单词单词后继符后继符expr():表达式的表达式的语法分析程序语法分析程序procedureparser();beginmatch($begin,1);match($var,2);ld:match($id,3);match($colon,4);match($intc/$reac,5);match($semi,6);readtoken(token);iftoken=$linethenreadtoken(token);iftoken=$va

18、rthengotold;2021-11-4北京化工大学信息科学与技术学院计算机系33readtoken(token);/读语句的后继符读语句的后继符2021-11-4北京化工大学信息科学与技术学院计算机系342021-11-4北京化工大学信息科学与技术学院计算机系352021-11-4北京化工大学信息科学与技术学院计算机系36procedureparser();beginmatch($begin,1);match($var,2);ld:match($id,3);match($colon,4);match($intc/$reac,5);match($semi,6);readtoken(token

19、);iftoken=$linethenreadtoken(token);iftoken=$varthengotold;ls:casetokenof($write,-）match($lparen,7);expr();match($rparen,8);($read,-)match($lparen,9);match($id,10);match($rparen,11);($id,-)match($assig,12);expr();othererror(13)end;readtoken(token);2021-11-4北京化工大学信息科学与技术学院计算机系37检查语义错误：没有声明；重复声明；类型不相容

20、检查语义错误：没有声明；重复声明；类型不相容entry表示标识符在符号表中的地址表示标识符在符号表中的地址2021-11-4北京化工大学信息科学与技术学院计算机系38语义分析过程语义分析过程 读入读入token遇到遇到标识符声明标识符声明时，检查是否已声明，是则报错，时，检查是否已声明，是则报错，否则构造标识符的符号表；否则构造标识符的符号表；遇到遇到标识符定义和使用标识符定义和使用时，检查是否声明过。时，检查是否声明过。将变量的将变量的token改为（改为（$id,entry)形式。形式。2021-11-4北京化工大学信息科学与技术学院计算机系392021-11-4北京化工大学信息科学与技术学院计算机系402021-11-4北京化工大学信息科学与技术学院计算机系412021-11-4北京化工大学信息科学与技术学院计算机系422021-11-4北京化工大学信息科学与技术学院计算机系432021-11-4北京化工大学信息科