概述

练习题

程序设计语言的基本成分

练习题

编译程序基本原理

名词解释

词法分析

词法分析（英语：lexical analysis）是计算机科学中将字符序列转换为单词（Token）序列的过程。进行词法分析的程序或者函数叫作词法分析器（Lexical analyzer，简称Lexer），也叫扫描器（Scanner）。词法分析器一般以函数的形式存在，供语法分析器调用。 完成词法分析任务的程序称为词法分析程序或词法分析器或扫描器。
完成词法分析任务的程序称为词法分析程序或词法分析器或扫描器。从左至右地对源程序进行扫描，按照语言的词法规则识别各类单词，并产生相应单词的属性字。

词法分析阶段是编译过程的第一个阶段，是编译的基础。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用Lex等工具自动生成。
词法分析是编译程序的第一个阶段且是必要阶段；词法分析的核心任务是扫描、识别单词且对识别出的单词给出定性、定长的处理；实现词法分析程序的常用途径:自动生成,手工生成。
词法分析器通常不会关心单词之间的关系（属于语法分析的范畴），举例来说：词法分析器能够将括号识别为单词，但并不保证括号是否匹配。
单词经常使用正则表达式进行定义，像lex一类的词法分析器生成器就支持使用正则表达式。语法分析器读取输入字符流、从中识别出语素、最后生成不同类型的单词。其间一旦发现无效单词，便会报错。

扫描器

词法分析的第一阶段即扫描器，通常基于有限状态自动机。扫描器能够识别其所能处理的单词中可能包含的所有字符序列（单个这样的字符序列即前面所说的“语素”）。例如“整数”单词可以包含所有数字字符序列。很多情况下，根据第一个非空白字符便可以推导出该单词的类型，于是便可逐个处理之后的字符，直到出现不属于该类型单词字符集中的字符（即最长一致原则）。

语法分析

语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.语法分析程序可以用YACC等工具自动生成。
完成语法分析任务的程序称为语法分析器，或语法分析程序。按照源语言的语法规则，从词法分析的结果中识别出相应的语法范畴，同时进行语法检查。
目前，已存在许多语法分析的方法。但就产生语法树的方向而言，可大致把他们分为自底向上和自顶向下两大类。目前比较流行LL分析法和LR分析法。

语义分析

语义分析是编译过程的一个逻辑阶段， 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查，进行类型审查。语义分析是审查源程序有无语义错误，为代码生成阶段收集类型信息。比如语义分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。如有的编译程序要对实数用作数组下标的情况报告错误。又比如某些程序规定运算对象可被强制，那么当二目运算施于一整型和一实型对象时，编译程序应将整型转换为实型而不能认为是源程序的错误。
语义分析的地位:编译程序最实质性的工作；第一次对源程序的语义作出解释，引起源程序质的变化。
地位：语义分析的地位:编译程序最实质性的工作；第一次对源程序的语义作出解释，引起源程序质的变化。
语义分析的任务：按照语法分析器识别的语法范畴进行语义检查和处理，产生相应的中间代码或目标代码。
什么叫中间代码：介于源语言和目标代码之间的一种代码。
引入中间代码的目的：1. 方便生成目标代码； 2. 便于优化；3. 便于移植。

中间代码生成

中间代码生成是产生中间代码的过程。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统复杂性介于源程序语言和机器语言之间，容易将它翻译成目标代码。另外，还可以在中间代码一级进行与机器无关的优化。
在进行了语法分析和语义分析阶段的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间表示或中间代码。

代码优化

所谓代码优化是指对程序代码进行等价（指不改变程序的运行结果）变换。程序代码可以是中间代码（如四元式代码），也可以是目标代码。等价的含义是使得变换后的代码运行结果与变换前代码运行结果相同。优化的含义是最终生成的目标代码短（运行时间更短、占用空间更小），时空效率优化。原则上，优化可以在编译的各个阶段进行，但最主要的一类是对中间代码进行优化，这类优化不依赖于具体的计算机。
在不改变程序运行效果的前提下，对被编译的程序进行等价变换，使之能生成更加高效的目标代码。

代码优化过程：

等价：不改变程序执行效果； 变换：引起程序形式上的变动。

改进、提高程序途径:

1） 改进算法；
2） 在源程序级上等价变换；
3） 充分利用系统提供的程序库；
4） 编译时优化等。

为什么要实施优化？

优化程度是编译器的一个重要技术、质量目标；
无法苛求用户对源语言的掌握，编程技巧.编写源程序的优化；
编译程序固有的缺陷：不是面对一个或一类具体问题的程序，而是统一处理该语言的各种源程序，无法尽善尽美。

优化所涉及的源程序的范围：

局部优化 — 基本块内优化；
循环优化 — 隐式、显式循环体内优化；
全局优化 — 一个源程序范围内优化；
优化相对于编译逻辑功能实现的阶段,中间代码级 — 目标代码生成前的优化；目标代码级 — 目标代码生成后的优化。

具优化功能编译器的组织

练习题

文法定义

闭包

文法

正规式

有限自动机

很简单