第一章 总论
1.1引言
这个“翻译”就是“编译程序”
编译原理 = 形式语言理论 + 编译技术
本书约定 程序设计语言即高级程序语言
编译程序构造原理包括(桉顺序)词法分析 语法分析 语义分析 目标代码生成 代码优化
本书中约定 用 ‘ := ’ 表示“定义为”
1.2程序设计语言与程序
程序指一系列指令或者语句
C语言的基本符号可以是字母 数字 与界限符。而界限符可分为 关键字 专用符号。
专用符号又可以是运算符(+ -),括号("([{"),分隔符(,;)
由C语言基本符号可以知道,不同程序设计语言有不同的基本符号集。
1.2.2
程序设计语言的四大方面
语法:如何由单词组成语法中的成分。单词是由基本符号集构成的单个具有意义的符号串。后者叫做词法规则。语法规则不仅可以用形式(可见形式是必要的,生活中依然如此)表示,还可以用语法树,语法图,口语表示。
语义:程序语句由语法分析完成后,交给语义定义分析。语义定义有动态和静态之分。静态是指在编译时就能确定语法成分的含义,而动态的是只能在程序运行的时候才能知道。
语用:其应用是注释,比如这个:/* 。。。。*/
语境:比如codeblocks,C的编译与运行环境,叫做语境。一种语言的可移植性将受到语境的影响。java的可移植性就很好,因为有JVM。
语法定义:
1.语法图书中P6(百度),优点是形象直观,不足是篇幅大。
2.BNF表示法P6(百度)
注意,其中“ | ” 表示为 “ 或者 ”其中“ ::= ”读作“ 定义为 ”
一种用来描述另外一种语言的语言称作为元语言。::=和|称作元符号,连接元语言成分。< >括起来的叫做元语言变量,后面管它叫非终结符,意思是还可以继续对他进行定义,所以非终结符必须在左边出现一次或者多次。
BNF的扩充:{x}表示x出现0次或者0次以上,[x]表示x可出现或者不出现。
3.口语
比如对C语言函数定义:函数定义由函数首部和函数体组成。
1.2.3程序的执行
解释执行和翻译执行,在调试的时候逐行执行,称作为解释执行,是模拟执行的,并没有生成最终代码,优点是查错,缺点是效率低下。而翻译执行则直接生成机器代码,在执行。编译程序优点是只需要分析翻译一次。
1.3编译程序构造及相关概念:
1.3.1构造
分为两大块,前端(与机器无关)是词法分析,语法分析,语义分析。后端(与机器有关)是目标代码生成与代码优化。
注意:注释的删除,文件包含与宏功能,条件编译等各部分是在词法分析时做的工作。
语义分析要确定数据结构类型是否正确,还有控制结构的正确性。
语义分析完成后生成中间代码,用于代码优化。最后才生成目标代码。
概括起来: 语义分析包括确定类型,类型检查,识别含义与相应的语义处理,并进行一些静态语义检查等四项功能。
注意:代码优化不会改变算法,只针对如a=2+3*pi 优化为a=11.42
优化分为机器无关优化和机器相关优化两类。
窥孔优化:代价不高(不复杂)的一类优化。
1.3.2遍的概念
一个编译程序的工作因为量太大(尤其是大型项目),可以分为若干阶段完成,每一个阶段都以上一段的输出作为输入,每个阶段读入并处理的过程叫做遍。(或趟)
SL源语言 TL目标语言 中间语言L1,L2,......Ln.
1.3.3编译程序的分类
诊断型:帮助与开发,初级阶段使用
优化型:产生高效率代码,缺电是增加了编译复杂性和时间。
可重定目标型:只改变后端(前面叙述的后端),不改变前端,因此移植性很好。
交叉性:在windows上生成了mac的可执行程序。在windows上开发apk文件。
增量型:比如在visulstudio中,调试程序时,如果发现错误,可以改正,并从改正处继续调试,这个就叫做增量型。它不必在改正错误后重新编译整个程序,可以节约大量时间。
应用并行技术的编译程序:一方面为多处理器机器专门研发,比如并发Pasical,Ada.另一方面,在顺序程序中,寻找并行计算,比如数组赋同样的值,可并行计算.
1.3.4实际应用中的编译程序:p13,p14.
1.4形式语言理论与编译实现技术
形式语言:一种符号语言,不考虑它的含义,其理论是研究组成它的符号串集合,还有研究它们的表示法,结构和某些特征。
乔姆斯基(chomsky)文法:
1.短语结构文法 2.上下文有关文法 3.上下文无关文法 4.正则文法
什么叫做上下文无关:我吃你,“我”,“你”都具有特定含义,称作无关。而比如:做爱做的事,就是上下文有关了。
编译程序不同阶段使用不同的分析技术,比如语义分析就是上下文相关的,词法分析上下文无关,程序是不能具有二义性的,但是人说话却可以有二义性的。