编译原理笔记(一)

前言

不久之前在知乎看到一个问题计算机不同编程语言的差别本质是编译器的差别吗? 下边某个回答道:

正好说反了,编程语言规范的差别,导致了编译器实现的差别。

比如C89不能用变长数组,C99可以,那么 -std=c89编译有变长数组的代码就会失败,用-std=c99就可以编译通过。同一个编译器,行为却不一样,是因为语言的规范不一样。

....

编译器的行为,总是反应了对规范的实现。即使是新功能,也是先提出草案,再尝试实现,最后批准草案。

现代编译器由前端和后端组成

前端:

代码字符串->词法分析->tokens->语法分析->AST->语义分析->语言相关优化->IR

后端:

IR->平台无关优化->平台相关优化->汇编代码生成->ASM->汇编器->目标代码->链接->可执行文件

语言之间的差异,都在前端。词法不同,导致语言对字符的解释不通,词法的不同导致代码的表现不同。

​ ------ 韩朴宇

总结下来就是,语言的不同并不在于编译器的差别,词法和语法的差异也不是根本的差异,语言的差别最主要的是语义上的差异。

编译程序

翻译程序:把一种语言程序(源语言程序)等价地转化成另外一种语言程序(目标语言)的程序。
编译程序:特指把高级语言翻译成低级语言的程序。
解释程序: 不产生目标程序,边解释边执行。

例如下表:

功能工作结果实现技术差别
编辑程序源程序的一个转换系统源程序的目标代码把中间代码转化为目标程序
解释程序源程序的一个执行系统源程序的执行结果执行中间代码

部分语言处理系统组合了编译和解释两个过程,如下图

源程序->编译程序->中间程序->解释程序->计算结果

比如JAVA的语言处理器就包括编译和解释两部分

​ 首先将Java源程序编译成为字节码的中间表示形式。

​ 然后由JVM对得到的字节码加以解释执行。

汇编程序:源语言程序是汇编语言程序,目标语言程序是机器语言程序。

宿主机:运行编译程序的计算机。

目标机:运行编译程序所产生目标代码的计算机

编译过程概述

自然语言的翻译与编译过程,一共有五个步骤:此法分析 语法分析 语义分析、产生中间代码、优化、生成目标代码。

词法分析:

任务:输入源程序,对构成源程序的字符串进行扫描和分解,识别出一个个的单词。然后对单词进行分类,分成基本字符,标识符、常数、算符、界符等。依循语言词法的规则。

例如一个for循环: for k :=1 to 100 do

经过词法分析可以得到如下:

基本字: for 标识符 k 赋值号 := 常数 1 基本字 to 常数100 基本字 do

语法分析:

任务:在词法分析的基础上,根据语言的语法规则把单词符号串分解成各类语法单位通过语法分析,确定输入串是否构成语法上正确的程序。

语法单位: 短语、子句、句子、程序段等。

规则:依循语言的语法规则

规则描述规则:上下文无关文法

方法: 递归子程序法、LR分析法、优先分析法。

例如: Z:=X+0.618*Y

经过语法分析可以得到

算术表达式: 0.618*Y 、X+0.618*Y

词法分析与语法分析的区别: 词法分析是线性结构 语法分析是层次结构分析。

语义分析和中间代码产生

任务:对语法检查器识别出的各类语法单位,进行静态语义检查,如果正确初步翻译,产生中间代码

工作: 按照语法树的层次关系和先后次序,逐个语句进行语义处理。对每种语法范畴进行静态语义检查,变量是否定义,类型是否正确。

规则:语义规则

规则描述工具:属性文法

翻译方法:语义子程序、DAG图、语法制导翻译等。

中间代码:

​ 含义明确、便于处理的记号系统。

​ 独立于具体硬件

​ 更接近于计算机指令系统或容易变换为机器指令

​ 三元式、四元式,逆波兰式,树形表示等。

例如: id1 + id2*id3

三元表示:1、(*,id2,id3),2、(+,id1,(1))

四元表示:1、(*,id2,id3,T1) 2、(+,id1,T1,T2)

逆波兰: id1id2id3*+

优化

任务: 对中间代码进行加工变换,以期在最后阶段能产生出更高效的目标代码。

有两种优化:机器无关优化 机器有关优化。

原则: 等价交换规则。

方法:公共子表达式的提取、循环优化、删除无用代码、并行化处理等。

例如 C++的 O2 O3优化,我仅仅听说过,不知道具体里边是如何优化的。

目标代码生成

任务: 把中间代码变换成特定机器上的低级语言代码,实现最后的翻译。

依赖于硬件系统结构和机器指令含义。

硬件系统功能部件的运用,机器指令的选择,数据存储空间分配,寄存器的调度等。

目标指令代码: 绝对指令代码、汇编指令代码、可重定位的指令代码。

编译程序的结构

先看这样的图:

编译程序总框

编译程序的流程图
编译程序输入操作输出
词法分析器(扫描器)源程序词法分析单词符号
语法分析器(分析器)单词符号语法分析识别出语法单位判断输入串语法是否正确语法单位或语法树
语义分析产生中间代码语法单位或语法树语义分析并翻译成中间代码中间代码
中间代码优化中间代码优化优化后的中间代码
生成目标代码优化后的中间代码翻译目标代码
表格与表格管理

任务: 保存一系列的表格,登记源程序的各类信息和编译各阶段的进展状况。

表格种类: 符号名表、常数表、标号表、入口名表、过程引用表等。

符号表:登记源程序中出现的每个名字(标识符),名字的各种属性:类型、作用域、分配存储信息。

符号表

扫描识别名字之后,将名字添加到符号表中。但此时不能确定其属性,在后续各个阶段填入,比如名字的类型在语义分析时才能确定,名字的地址可能到目标代码才能确定。编译的各个阶段均涉及到构造、查找或更新有关的表格。

出错处理

程序中的错误可分为语法错误语义错误两类。语法错误可在词法分析和语法分析阶段查出来。

词法分析阶段:非法字符等 语法分析阶段:括号不匹配,缺少标点符号等。

语义错误

语义错误有些可以在编译时查出来,有些则需要在运行时才能查出来。

典型的语义错误:标识符没有说明就使用;标号有引用而无定义;说明错误,作用域类型不一致等;

这些错误可在编译时查出来,而另一些错误如下标越界、运算溢出、调用某些标准函数的值不符合要求等,需要在程序运行时才能查出来。

遍(Pass)

对源程序或源程序的中间结果从头到尾扫描一次,并做相关处理,生成新的中间结果或目标程序的过程。

遍是处理数据的一个完 是处理数据的一个完 整周期,每遍工作从外存上 整周期,每遍工作从外存上 获得前一遍的中间结果(源 获得前一遍的中间结果(源 程序),完成它所含的有关 程序),完成它所含的有关 工作之后,再把结果记录于外存。

一个编译程序可由一遍、两遍、或多遍完成。每一遍可完成不同的阶段或多个阶段的工作。

编译程序的生成

设计目标

目标程序小,执行速度快。

编译程序小,执行速度快。

诊断能力强,可靠性强。

可移植性,可扩充性。

实现基础

构造一个编译程序时 ,需要掌握以下内容:
源语言:深刻理解其 结构和含义 。
目标语言 :深刻理解其 结构和含义 。
操作系统和硬件结构:有些情况,比如目标语言是机器语言,还要熟悉硬件的系统结构和OS的特性。
编译方法:把一种语言程序翻译为另一种语言程序的方法很多,选择合适的算法。

定义源语言是相对容易的,难得是如何将高级语言中的新的特性用目标语言高效合理的表示。

编译程序的生成技术

自编译:用某种高级语言书写自己的编译程序称为自编译。比如已有一个编译程序,假定A机器上已有一个PASCAL语言编译程序,则可用PASCAL语言编写一个功能更强的PASCAL语言编译程序,然后借助于原有的编译程序对新编成的PASCAL编译程序进行编译,从而得到一个能在A机器上运行功能更强的PASCAL编译程序。

自展:用低级语言先实现一个基础功能的编译器,然后用这个编译器再去编写一个功能更复杂的编译器,这个新编译器是旧编译器扩展的过程。

交叉编译:用x机器上的编译程序产生可在y机器上运行的目标代码成为交叉编译。也就是生成不同机器上可运行的目标代码。

移植:A机器上的某种高级语言的编译程序稍加改动或不改动后能直接在B机器上运行。

关于更加详细的编译程序生成技术参见知乎:点击这里

参考资料:老师上课所用PPT 还有知乎某些回答。
本章PPT上传至附件-编译原理引论

文章名: 《编译原理笔记(一)》
文章链接:https://blog.hrhr7.cn/index.php/archives/4/
联系方式:tensor7@163.com
除特别注明外,文章均为Cupidr原创,转载时请注明本文出处及文章链接
Last modification:November 22nd, 2019 at 08:01 pm
如果觉得我的文章对你有用,请随意赞赏

3 comments

  1. ( ๑´•ω•) "(ㆆᴗㆆ)

Leave a Comment