第一章 引论

第一章 引论

第一章 引论

@东明 许 @软件工程@YA1714180

  • 参考链接及相关博客

编译原理[笔记] 第一章-绪论_Java_qq_39495105的博客-CSDN博客

一、各种语言历史

https://www.notion.so/xudongming/4369e0307c3a469eb194d77d8227bc49?v=55dbdbb3471949f89ddd61285bc089fe

[比较卡,可能打不开]

二、参考教材

  • Compilers: Principles, Techniques,and Tools (龙书)
  • Alfred V.Aho, Ravi Sethi, Jeffrey D.Ullman 第一版(1986),人民邮电版影印,2002.(机械工业版中译本,2003)
  • 第二版(2007),Addison Wesley(Alfred V.Aho, Monica S.Lam , Ravi Sethi, Jeffrey D.Ullman )
  • Modern Compiler Implementation in C (虎书)
  • Andrew W.Appel,人民邮电出版社影印,2005
  • Programming Language Pragmatics
  • Michaeil. Scott etc.,电子工业出版社中译本,2005
  • Elements of Compiler Design
  • Alexander Meduna,Taylor & Francis Group,2008
  • Advanced Compiler Design and Implementation (鲸书)
  • Steven S. Muchnick, 1997. 机械工业出版社影印,2003
  • Engineering a Compiler
  • Keith Cooper, Linda Torczon, Morgan Kaufmann, 2003

三、章节笔记

一. 基本概念

1.高级语言与低级语言

2.几种重要程序

3.源程序的翻译与运行

源程序通过翻译过程到最后运行得到结果要经过两个阶段:

翻译(编译或汇编)阶段:源程序 —> 翻译程序 —> 目标程序

运行阶段:输入数据 —> 目标程序+运行子程序 —> 输出数据

4.源程序的解释执行

解释程序:可以对源程序或编译得到的中间代码进行解释执行的程序

解释执行过程:源程序或中间代码+输入数据—>解释程序—>输出数据

相比于纯编译执行的优点与缺点

优点:

(1)动态响应性好:如果程序的某部分或输入数据在程序运行时还需要发生改变,因为解释执行是对源代码的语句(或指令)一条一条的执行,执行某条时其它语句(或指令)可以放心的进行修改。

(2)便于调试:解释执行产生的中间代码中,尚未解释执行的部分还保持着源代码的样子,这使得程序的调试变得更加容易

(3)简易性:相比于编译系统,解释执行的处理系统更容易研制

(4)节省空间:相比于编译执行,解释执行的中间代码占用的储存空间更小,因为还未执行的部分还保持着源代码的状态

(5)移植性更好:解释执行的中间语言与机器无关(与源语言有关),因此,便于将语言处理系统移植到其他机器上

缺点:因为需要一条一条地解释执行,因此程序的运行速度较慢

5.“编译-解释执行”系统

为了让翻译系统同时具备编译执行和解释执行的特点,通常解释程序往往和编译程序结合使用,采用“编译-解释执行”方式。比如Java语言就需要采用编译-解释执行方式运行Java源代码,这样既使得Java源代码拥有很好的移植性的同时,在运行效率上也得到了优化。

此外,我们也可以先对源程序进行解释执行,以便测试与调试,待调试完成后再用编译程序将正确的源程序进行编译,这样可以大大提高编程的效率。

二. 编译过程

编译过程是指将 高级语言程序 翻译为等价的 目标程序 的过程。习惯上将编译过程划分为5个基本阶段七个逻辑部分五个基本阶段:

①词法分析

②语法分析

③语义分析、生成中间代码

④代码优化

⑤生成目标程序

七个逻辑部分:

五个基本阶段的基础上加上各阶段需要做的

⑥符号表管理

⑦出错处理

1. 词法分析

1.任务:分析和识别源程序中的单词

2.过程:词法分析的输入是字符串形式的源程序,词法分析扫描源程序(字符串),根据语言的词法规则分析识别出具有独立语法意义的单词(token),并以某种编码形式输出。

单词通常分为4类:

① 关键字或保留字 ② 标识符 ③ 常量 ④ 运算符和分界符

比如: x1:= ( 2.0 + 0.8 ) * c3中,可识别出9个单词。(注意:其中 := 是二元赋值运算符)

2. 语法分析

1.任务:根据语法规则(即语言的文法),分析并识别出各种语法成分,如表达式、各种说明、各种语句、

过程、函数、程序等,并进行语法正确性检查。

2.过程:语法分析的输入是通过词法分析获得的单词串形式的源程序,语法分析识别出语言的各自语法成分(如:变量声明、表达式、语句、函数等),并进行语法检查。语法分析最后输出一棵语法树,它的叶子节点是单词(token),每一个非叶子节点代表一个语法成分

3. 语义分析、生成中间代码

1.任务:RT

2.过程:语义分析的输入是语法分析获得的语法成分,通过分析处理识别语法成分组合的含义,同时进行语义检查,最后生成中间代码

3.中间代码:中间代码介于源代码和目标代码之间,与目标机器无关,对代码优化和程序移植有很大的作用。

4.中间代码的形式:常用的中间代码形式有四元式、三元式、逆波兰表示和抽象语法树等。

例如:语句 x1 := ( 2.0 + 0.8 ) * c3 的中间代码 四元式 表示:

4. 代码优化

1.任务:在确保源代码功能不变的的前提下,使目标代码更加简短,以尽量减少储存空间和运行时间。

2.方法:例如,上面的四元式中第一个四元式是计算常量表达式值,该值在编译时就可以算出并存放在工作单元中,不必生成目标指令来计算,这样四元式可优化为:

编译时:2.0 + 0.8 → T1

中间代码(四元式):

5.生成目标程序

1.任务:通过中间代码生成(地址指令序列表示的)目标程序。

2.需要注意的问题:

①这部分工作与机器关系密切,所以要根据具体机器进行

②在做这部分工作时(要注意充分利用累加器),也可以进行优化处理。

③在翻译成目标程序的过程中,要切记保持 语义的等价性(翻译的根据)。

三. 编译程序构造

1. 逻辑结构

1.主体结构:由上可知,按逻辑功能不同,可将编译过程划分为五个基本阶段。与此相对应,我们将实现整个编译过程的编译程序划分为五个逻辑阶段(即五个逻辑子过程)。

2.辅助结构:符号表管理和出错处理。

①符号表管理:在整个编译过程中始终都要贯穿着填表和查表的工作。即要及时地把源程序中的信息和编译过程中所产生的信息登记在表格中,而在随后的编译过程中同时又要不断地查找这些表格中的信息。

②出错处理:规模较大的源程序难免有多种错误。编译程序必须要有出错处理的功能,即能诊察出错误,并向用户报告错误性质和位置,以便用户修改源程序。出错处理能力的优劣是衡量编译程序质量好坏的一个重要指标。

2. 编译程序的前端和后端

根据编译程序各部分功能,将编译程序分成前端和后端

①前端:包括的部分:词法分析、语法分析、语义分析、中间代码生成、代码优化以及相应部分的符号表管理和出错处理部分(语言处理系统的分析部分)

特点:与源语言有关,与目标机器无关。

②后端:包括的部分:目标程序生成、与目标机有关的优化以及相应部分的符号表管理和出错处理部分(语言处理系统的综合部分)

特点:与目标机器有关,依赖中间语言而与源语言无关。

③分成前端和后端开发的好处:

(1)不同目标机器的编译程序可能使用同一个前端部分,不同源语言可能使用同一个后端部分。

(2)前端、后端的开发人员可以并行工作,提高效率。

3. 遍

对源程序(包括源程序中间形式)从头到尾扫描一次,并做有关的加工处理,生成新的源程序中间形式或目标程序,通常称之为一遍。

图片来自https://blog.csdn.net/qq_39495105/article/details/83028685

遍与五个基本阶段的区别:

①五个基本阶段:将源程序翻译为目标程序在 逻辑上要完成的工作

②遍:为完成五个基本阶段的工作,实际对源程序(或其中间形式)进行扫描并加工处理的 动作单元

★一遍扫描的编译程序

我们在实验课中实现的PL/0编译器就是这一类型的编译程序,总共只用进行一次扫描就可以完成编译过程的各项任务。

工作原理

①以语法分析程序为核心。

②当语法分析程序需要读入新的单词时,调用词法分析程序,从源程序中依次读入字符并进行单词识别。当识别出单词时,将识别出的单词返回到语法分析程序。

③当语法分析程序根据词法分析返回的单词组成,识别出某语法成分时,调用语义分析程序对其进行分析并生成相应部分的目标程序片段,语义分析程序向语法分析程序返回分析结果。

④语法分析程序执行结束后,对产生的目标程序进行整合,得到完整的目标程序。

关于分遍

分遍扫描的编译程序与一遍扫描的编译程序相对,每一遍只完成一个或相连的几个逻辑部分的工作。第一遍的输入是源程序,最后一遍的输出是目标程序,其它每一遍的输入程序是上一遍的输出程序。

★优点与缺点

①优点:

(1)减少对内存的要求(主要):分遍后,编译时可以以遍为单位将程序调入内存进行加工。

(2)优化工作更充足:分遍使编译程序结构更清晰,相互联系更简单,更利于优化工作的进行(可以分部分进行优化,而不是要同时考虑所有部分)。

(3)实现前后端的分离

②缺点:

增加重复工作,文件读写频繁,降低编译效率。

四. 编译技术在软件工程中的应用

1.语法制导的结构化编辑器:提供自动格式缩进、实时语法检查、自动关键字匹配等辅助功能,提高编程效率。

2.程序格式化工具:优化源代码可读性

3.软件测试工具

(1)静态分析器:对源代码的分析,检测出无法执行到的代码部分、未定义或赋值就引用的变量等。

(2)动态结构测试器:使用样例对程序进行测试。

4.其它工具

五. 两类程序语言处理程序(翻译的两种方式)

  1. 编译程序(编译器):先将源程序翻译成汇编语言程序或机器语言程序(称为目标程序),然后再执行它。
  2. 解释程序(解释器):按解释方式进行翻译的翻译程序称为解释程序。解释程序的主要优点是便于对源程序进行调试和修改,但其加工处理过程的速度较慢。e.g. BASIC。

注:

(1)把汇编语言程序翻译成机器可执行的目标程序的工作是由汇编器完成的。

(2)编写一个计算机高级语言的源程序后,到正式上机运行之前,一般要经过编辑、编译、连接这三步。

(3)编译方式与解释方式的根本区别在于是否生成目标代码。

(4)与编译系统相比,解释系统比较简单,可移植性好,执行速度慢。

(5)编译程序生成的目标程序不一定是可执行的程序。

六. 编译程序的种类

  1. 可变目标编译程序:不需重写编译程序中与机器无关的部分就能改变目标机的编译程序。
  2. 交叉编译程序:能产生不同于其宿主机的机器代码的编译程序。
  3. 优化编译程序:着重于提高目标代码效率的编译程序。
  4. 诊断编译程序:专门用于帮助程序开发和调试的编译程序。

七. 编译程序的工作过程

  1. 词法分析:词法分析是编译过程的基础,其任务是扫描源程序,根据语言的词法规则,分解和识别出每个单词,并把单词翻译成相应的机内表示。
  2. 语法分析:语法分析是在词法分析的基础上进行的。其任务是根据语言的语法规则,把单词符号串分解成各类语法单位,如表达式、语句等。
  3. 语义分析:语义分析的任务是对源程序进行语义检查,其目的是保证标识符和常数的正确使用,把必要的信息收集、保存到符号表或者中间代码程序中,并进行相应的处理。
  4. 中间代码生成:对于编译程序而言并非必不可少的阶段。常用的中间代码有三元式、四元式和逆波兰式。
  5. 中间代码优化:也不是编译程序的必要阶段。优化的任务在于对前端产生的中间代码进行加工变换,以期在最后阶段能产生出更为高效(省时间和空间)的目标代码。
  6. 目标代码生成:编译程序的最后阶段。

注:

(1)编译程序的工作过程一般可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化等几个基本阶段,同时还伴有表格处理出错处理

(2)编译程序绝大多数时间花在表格管理上。

(3)编译程序中包括词法分析、语法分析、语义分析和中间代码产生等主要与源程序有关但与目标机无关的那些部分叫编译前端;编译程序中包括目标代码生成、目标代码优化等与目标机有关而与源语言无关的那些部分叫编译后端。编译后端通常不依赖于源语言而仅仅依赖于中间语言。可以取编译程序的前端,改写其后端以生成不同目标机上的相同语言的编译程序。

(4)从编译程序的角度说,源程序中的错误通常分为语法错误和语义错误两大类。在使用高级语言编程时,首先可通过编译程序发现源程序的全部语法错误和部分语义错误。语法错误是指源程序中不符合语法(或词法)规则的错误,它们可在词法分析或语法分析时检测出来。例如,词法分析阶段能够检测出“非法字符”之类的错误;语法分析阶段能够检测出诸如“括号不匹配”、“缺少 ; ”之类的错误。语义错误是指源程序中不符合语义规则的错误,这些错误一般在语义分析时检测出来,有的语义错误要在运行时才能检测出来。语义错误通常包括:说明错误、作用域错误、类型不一致等。

(5)现代多数实用编译程序所产生的目标代码都是一种可重定位的指令代码,在运行前必须借助于一个连接装配程序把各个目标模块,包括系统提供的库模块连接在一起,确定程序变量或常数在主存中的位置,装入内存中制定的起始地址,使之成为一个可运行的绝对指令代码的程序。

(6)目标代码生成阶段所生成的目标代码的形式可以是绝对指令代码、可重定位的指令代码或汇编指令代码。

(7)编译过程可采用分遍的形式,即编译过程可以由一遍或多遍编译程序来完成。对于源程序或中间代码程序,从头到尾扫描一次并完成所规定的工作称为一遍。将编译程序分成若干个“遍”是为了使程序的结构更加清晰。

八. 编译程序的结构

  1. 词法分析器(扫描器):输入源程序,进行词法分析,输出单词符号。
  2. 语法分析器(分析器):对单词符号串进行语法分析(根据语法规则进行推导或归约),识别出各类语法单位,最终判断输入串是否构成语法上正确的“程序”。
  3. 语义分析及中间代码产生器:按照语义规则对语法分析器归约出(或推导出)的语法单位进行语义分析并把它们翻译成一定形式的中间代码。有的编译程序在识别出各类语法单位后,构造并输出一棵表示语法结构的语法树,然后,根据语法树进行语义分析和中间代码产生。还有许多编译程序在识别出语法单位后并不真正构造语法树,而是调用相应的语义子程序。在这种编译程序中,扫描器、分析器和中间代码生成器三者并非是截然分开的,而是相互穿插的。
  4. 优化器:对中间代码进行优化处理。
  5. 目标代码生成器:把中间代码翻译成目标程序。

九. 其他

1. 为了使编译后的Java程序从一个平台移到另外一个平台上执行,Java定义了一种称为ByteCode的虚拟机代码。只要实际使用的操作平台上实现了执行ByteCode的Java解释器,这个操作平台就可以执行各种Java程序。这就是所谓Java语言的操作平台无关性。

  1. 编译程序的自动化
  • LEX:词法分析程序生成器(输入:正规表达式;输出:词法分析程序)
  • YACC:语法分析程序生成器(输入:LALR(1)文法;输出:LALR(1)分析表和LALR(1)分析器)

3. 一个Lex源程序主要包括两部分,一部分是正规定义式,另一部分是识别规则

  1. 语言处理程序是一类系统软件的总称,而不是一种应用软件。语言处理程序可分为三种:汇编程序、编译程序和解释程序。

5. 甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。

6. 支持程序设计人员进行程序计开发的工具,除了编译程序以外,还需要编辑程序、链接程序和调试程序等其他一些工具。

四、直播课笔记

相关参考链接波兰式、逆波兰式与表达式求值前缀、中缀、后缀表达式转换详解二叉树的前,中,后序遍历详解
int a,*p;
p = &a; //p = a; 语义错误 赋值语句 <变量>=<表达式>
b = a + *p; //语法错误,变量未定义; //语义错,类型不匹配
-----------------------------------------------------------------------------------------------
int a[10],*p; //语法错
p = &a; //p = a; 语义错误 赋值语句 <变量>=<表达式>
b = a + *p; //语法错误,变量未定义; //语义错,类型不匹配
a[10]=9; //编译器会报错吗?
a[3.4]=7; //语义错误
-----------------------------------------------------------------------------------------------
x=(a+b)*c-(d-f)/e x a b + c * d f - e / - =
(op,n1,n2)
(1) (+,a,b)
(2) (*,(1),c)
(3) (-,d,f)
(4) (/,(3),e)
(5) (-,(2),(4)) (5)=(2)-(4)
(6) (=,(5),x) (6)=(5)=x //(=,x,(5)) 不便优化,间接三元式 三元式+执行表
-----------------------------------------------------------------------------------------------
(1) (+,a,b)
(2) (*,(1),c)
(3) (+,a,b)
(4) (/,(1),e)
(5) (-,(2),(4))
-----------------------------------------------------------------------------------------------
四元式: (op,n1,n2,R) R=n1 op n2
x=(a+b)*c-(d-f)/e
四元式 三地址式
(+,a,b,t1) t1=a+b
(*t1,c,t2) t2=t1*c
(-,d,f,t3) t3=d-f
(/,t3,e,t4) t4=t3/e
(-,t2,t4,t5) t5=t2-t4
(=,t5, ,x) x=t5
 

1.预处理

2.ASCII码,二进制表示

3.逆波兰式

4.T型图了解就好

五、课堂作业

六、课本习题

编译程序:

源程序:

目标程序:

编译程序的前端:

编译程序的后端:

编译程序的主要构成成分:

各自主要功能:

解释程序:

与编译程序的不同:

七、修改意见

一、你调研了历史上几种的主流语言,比较详细地描述了它们的发展进程和主要特点。

改进建议:

1) 面向对象和函数式风格的重要语言可以再增加几种(如,Smalltalk,Modula-2, Haskell, Caml)。

2)有兴趣的话,可简述一下近几年比较受关注的一些语言,如Python,Scala,Go,Rust,Dart。

3)学完编译课之后再从语言特性实现和语用的角度进行综述。

二、关于编译与解释的区别

(3)编译方式与解释方式的根本区别在于是否生成目标代码。 (这仅仅是表象,你落掉了更加本质的差异——内存管理 可以在学完编译后再回过头来思考这个问题)

三、编译程序的分类问题 不同的角度,分类的结果会不一样的。

如果不区分角度进行分类的话,其实这个列表可以比较长。我个人倾向于从不同的角度分类, 这样的话,每个角度的类别之间是互补的。

四、语言处理程序

4.语言处理程序是一类系统软件的总称,而不是一种应用软件。

语言处理程序可分为三种:汇编程序、编译程序和解释程序。

(这样说也可以, 主要看如何理解这里的“语言处理程序”。比如后面第6条提到的编辑程序、链接程序,以及还有预处理程序都属于这个范畴。)

© 版权声明
THE END
喜欢就支持以下吧
点赞0赞赏
分享
评论 抢沙发

请登录后发表评论