编译原理第一章复习记录

第一章  总论

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.正则文法

 

        什么叫做上下文无关：我吃你，“我”，“你”都具有特定含义，称作无关。而比如：做爱做的事，就是上下文有关了。

            编译程序不同阶段使用不同的分析技术，比如语义分析就是上下文相关的，词法分析上下文无关，程序是不能具有二义性的，但是人说话却可以有二义性的。