编译原理第一章复习记录

第一章  总论

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

 

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

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

相关文章
相关标签/搜索