编译原理--引论

编译原理--引论 引论

设计和实现编译器的方法
编译器的编写涉及程序设计语言，计算机体系结构，形式语言理论，算法和软件工程。

语言处理器

编译器是一个程序，可以阅读以某一种语言编写的程序，把它翻译为一个等价的，
用另一种语言编写的程序。
解释器，直接利用用户提供的输入执行源程序中指定的 *** 作。逐个语言地执行源程序。

1.源程序可能被划分为多个模块，放于独立的文件中。
把源程序聚合在一起的任务有时会由一个称为预处理器的程序独立完成。
预处理器还负责把那些称为宏的缩写形式转换为源语言的语句。
2.将经过预处理的源程序作为输入传递给一个编译器。
编译器可能产生一个汇编语言程序作为输出。
3.汇编语言程序由称为汇编器的程序进行处理，生成可重定位的机器代码。
4.大型程序常被分为多个部分进行编译。
可重定位的机器代码有必要和其他可重定位的目标文件及库文件连接到一起，
形成一个真正在机器上运行的代码。
一个文件中的代码可能指向另一个文件中的位置。链接器能够解决外部内存地址的问题。
5.加载器把所有的可执行目标文件放到内存中执行。

一个编译器的结构

分析部分
1.分析部分把源程序分解成多个组成要素，并在这些要素上加上语法结构。
2.它使用这个结构来创建该源程序的一个中间表示。
如分析部分检查出源程序没按照正确的语法构成，或语义不一致，
它就必须提供有用的信息，使得用户可按此进行改正。
分析部分还会收集有关源程序的信息，把信息存放在一个称为符号表的数据结构中。
符号表和中间表示形式一起传送给综合部分。
综合部分
根据中间表示和符号表中的信息构造用户期待的目标程序。

详细地研究编译过程，会发现它顺序执行了一组步骤。
每个步骤把源程序的一种表示方式转换成另一种表示方式。
多个步骤可能被组合在一起，组合在一起的步骤之间的中间表示不需被明确地构造出来。
存放整个源程序的信息的符号表可由编译器的各个步骤使用。

典型的各个步骤：
字符流–语法分析器–>符号流–语法分析–>语法树–语义分析–>语法树
–中间代码生成器–>中间表示形式–机器无关代码优化器–>中间表示形式
–代码生成器–>目标机器语言–机器相关代码优化器–>目标机器语言

语法分析

语法分析器读入组成源程序的字符流，将它们组织为有意义的词素序列。
对每个词素，语法分析器产生如下形式的词法单元作为输出。

这个词法单元被传送给下一个步骤，即语法分析。
在此词法单元中，
token-name为一个由语法分析步骤使用的抽象符号。
attribute-value指向符号表中关于这个词法单元的条目。
符号表条目的信息会被语义分析和代码生成步骤使用。

如：
position = initial + rate * 60
上述赋值语句中的字符可组合成如下词素，
并映射为如下词法单元，这些词法单元将被传递给语法分析阶段。
1.position是一个词素，被映射为词法单元，
id是表示标识符的抽象符号。1，指向符号表中position对应的条目。
一个标识符对应的符号表条目存放该标识符有关的信息，如它的名字和类型。
2.赋值符号=是一个词素，被映射成词法单元<=>。
因为这个词法单元不需属性值，所以省略了第二个分量。
也可用assign这样的抽象符号作为词法单元的名字。
3.initial是一个词素，被映射成词法单元
4.+是一个词素，被映射成词法单元<+>
5.rate是一个词素，被映射成词法单元
6.*是一个词素，被映射成词法单元<*>
7.60是一个词素，被映射成词法单元<60>
分隔词素的空格会被词法分析器忽略掉。
上述赋值语句将表示为如下的词法单元序列：
 <=>  <+>  <*> <60>
上述表示中，词法单元名=，+，*分别是表示赋值，加法，乘法运算符的抽象符号

语法分析

语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示，
该中间表示给出了词法分析产生的词法单元流的语法结构。
一个常用的表示方法是语法树，
树中的每个内部结点表示一个运算，
而该结点的子结点表示该运算的分量。

图1-7显示了赋值语句
position = initial + rate * 60
中各个运算的执行顺序。
编译器的后续步骤使用这个语法结构来帮助分析源程序，并生成目标程序。

语义分析

语义分析器使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。
它同时也收集类型信息，并把这些信息存放在语法树或符号表中，
以便在随后的中间代码生成过程中使用。
语义分析一个重要部分是类型检查。
如数组下标得是整数，否则，编译器需报告错误。
程序设计语言可能允许某些类型转换，称为自动类型转换。
图1-7的语义分析器的类型检查程序发现运算符*被用于一个浮点数和一个整数。
此时，这个整数可被转换为一个浮点数。
图1-7中，语义分析器输出中有一个inttofloat，
inttofloat明确地把它的整数参数转换为一个浮点数。

中间代码生成

把一个源程序翻译成目标代码过程中，
一个编译器可能构造出一个或多个中间表示。
这些中间表示可有多种形式。
语法树是一种中间表示形式，通常在语法分析和语义分析中使用。
源程序的语法分析和语义分析完成后，很多编译器生成一个明确的低级或类机器语言的中间表示。
中间表示应具有两个重要的性质：易于生成，且能被轻松地翻译为目标机器上的语言。

代码优化

机器无关的代码优化步骤试图改进中间代码，以便生成更好的目标代码。

代码生成

代码生成器以源程序的中间表示形式作为输入，并把它映射到目标语言。
如目标语言是机器代码，就需为程序使用的每个变量选择寄存器或内存位置。
然后，中间指令被翻译成能完成相同任务的机器指令序列。
代码生成的一个重要方面是合理分配寄存器及存放变量的值。

运行时刻的存储组织方法依赖于被编译的语言。
编译器在中间代码生成或代码生成阶段作出有关存储分配的决定。

符号表管理

编译器重要功能之一是记录程序中使用的变量的名字，并收集和每个名字的各种属性有关的信息。
这些属性可提供一个名字的存储分配，它的类型，作用域等信息。
对于过程名字，这些信息还包括：它的参数数量，类型，
每个参数的传递方法【如传值或传引用】及返回类型。
符号表数据结构为每个变量名字创建了一个记录条目，记录的字段就是名字的各个属性。

将多个步骤组合成趟

在一个特定的实现中，多个步骤的活动可被组合成一趟。
每趟读入一个输入文件并产生一个输出文件。
如前端步骤的词法分析，语法分析，语义分析，及中间代码生成可被组合在一起成为一趟。
代码优化可作为一个可选的趟，
然后可以有一个为特定目标机生成代码的后端趟。
有些编译器围绕一组精心设计的中间表示形式创建，
这些中间表示形式使我们可把特定语言的前端和特定目标机的后端相结合。

编译器构造工具

写编译器的人，可充分利用现代的软件开发环境。
一些常用的编译器的构造工具包括：
1.语法分析器的生成器：
可根据一个程序设计语言的语法描述自动生成语法分析器
2.扫描器的生成器
可根据一个语言的语法单元的正则表达式描述生成词法分析器
3.语法制导的翻译引擎
可生成一组用于遍历分析树并生成中间代码的例程
4.代码生成器的生成器
依据一组关于如何把中间语言的每个运算翻译成目标机上的机器语言的规则，生成一个代码生成器。
5.数据流分析引擎
可帮助收集数据流信息，即程序中的值如何从程序的一个部分传递到另一部分。
6.编译器构造工具集
提供了可用于构造编译器不同阶段的例程的完整集合

构建一个编译器的相关科学 编译器设计和实现中的建模

如何设计正确的数学模型和选择正确算法。
最基本的数学模型包括有穷状态自动机，正则表达式，上下文无关法。

代码优化的科学

应用严格的数学基础，使我们可证明一个优化是正确的，且它对所有可能的输入都产生预期的效果。
很多现实世界的问题没有完美的答案，编译器优化中提出的很多问题都是不可判定的。
编译器优化目标：
1.优化需正确的，不改变被编译程序含义
2.优化需能改善很多程序的性能
3.优化所需时间需保持在合理范围
4.所需的工程方面的工作需可管理

编译技术的应用 高级程序设计语言的实现 针对计算机体系结构的优化

高性能系统：并行，内存层次结构

新计算机体系结构的设计 程序翻译 软件生产率工具 程序设计语言基础 静态和动态的区别

如果一个语言使用的策略支持编译器静态决定某个问题，则说这个语言使用了一个静态策略。
或者说这个问题可在编译时刻决定。
一个只允许在运行程序的时候作出决定的策略称为动态策略，或被认为需在运行时刻作出决定。

声明的作用域，
x的一个声明的作用域指程序的一个区域，在其中对x的使用都指向这个声明。
如仅通过阅读程序就可确定一个声明的作用域，则此语言使用的是静态作用域或词法作用域。
否则，此语言使用的是动态作用域。

环境与状态

程序运行时发生的改变是否影响数据元素的值，还是影响对那个数据的名字的解释。
名字和内存【存储】位置的关联，及之后和值的关联可用两个映射来描述。
这两个映射随着程序的运行而改变。

1.环境是一个从名字到存储位置的映射。因为变量就是指内存位置【c中左值】，
还可换一种方法，可以把环境定义为从名字到变量的映射。
2.状态是一个从内存位置到他们的值的映射。以c的术语，状态把左值映射为它们的右值。

环境和状态映射是动态的，但也有一些例外。
1.名字到位置的静态绑定与动态绑定。
大部分名字到位置的绑定是动态的。
某些声明可以在编译器生成目标代码时一劳永逸地分配一个存储位置。
2.从位置到值的静态绑定与动态绑定。
一般来说，位置到值的绑定也是动态的。
被声明的常量是一个例外。

静态作用域和块结构

c使用静态作用域。
c的作用域规则是基于程序结构的。
一个声明的作用域由该声明在程序中出现的位置隐含地决定。
c++通过诸如public，private，protected等关键字的使用，提供了对作用域的明确控制。
本节，我们考虑块结构语言的静态作用域规则。
其中，块是声明和语句的一个组合。c用{}来界定一个块。

显式访问控制

类和结构为它们的成员引入了新的作用域。
如p是一个具有字段x的类的对象，
则p.x中对x的使用指的是这个类定义中的字段x。
通过public，private，protected，
像c++或java提供了对超类中的成员名字的显式访问控制。

声明是告诉我们事务的类型。
定义告诉我们它们的值。

动态作用域

动态作用域通常指的是下面的策略：
对一个名字x的使用指向的是最近被调用但还没终止且声明了x的过程中的这个声明。
考虑两个动态作用域的例子：C预处理器中的宏扩展，面向对象编程中的方法解析。

动态作用域解析对多态过程必不可少。
所谓多态过程是指对同一个名字根据参数类型具有两个或多个定义的过程。

参数传递机制

实参和形参关联。
值调用：
会对实参求值【针对表达式】或拷贝【针对变量】。
这些值被放在属于被调用过程的相应形参的内存位置上。
值调用的效果是，被调用过程所做的所有有关形参的计算都局限于这个过程，
相应的实参本身不会被改变。

引用调用：
实参的地址作为相应的形参的值被传递给被调用者。
在被调用者的代码中使用形参时，实现方法是沿着这个指针找到调用者指明的内存位置。
改变形参看起来像是改变了实参一样。

但如实参是一个表达式，则在调用前会对表达式求值。
然后它的值被存放在一个该值自己的位置上。
改变形参会改变这个位置上的值，但对调用者的数据没影响。

别名

引用调用或其他类似的方法，有可能两个形参指向同一个位置，
这样的变量称为另一个变量的别名。