程序设计语言基础(2)

3. 编译程序基本原理

编译程序的功能是把某高级语言书写的源程序翻译成与之等价的目标程序（汇编语 言或机器语言)。编译程序工作过程分为6个阶段，如下图所示：

词法分析：是编译过程的第一个阶 段。这个阶段的任务是从左到右 个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然 后根据构词规则识别单词（也称单 词符号或符号)。

语法分析：是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类 语法短语，如“程序”，“语句”， “表达式”等等.语法分析程序判断源 程序在结构上是否正确

语义分析：是编译过程的一个逻辑阶段.语义分析的任务是对结构上正确的源程序 进行上下文有关性质的审查，进行类型审查。如类型匹配、除法除数不为0等。又分为静态语义错误（在编译阶段能够查找出来）和动态语义错误（只能在运行时发 现)。

中间代码和目标代码生成：中间代码是根据语义分析产生的，需要经过优化链接， 最终生成可执行的目标代码。引入中间代码的目的是进行与机器无关的代码优化处理。常用的中间代码有后缀式（逆波兰式）、三元式（三地址码）、四元式和树等形式。需要考虑三个问题（一是如何生成较短的目标代码；二是如何充分利用计算 机中的寄存器，减少目标代码访问存储单元的次数；三是如何充分利用计算机指令 系统的特点，以提高目标代码的质量)。

要掌握上述三种表达式即可，其实就是树的三种遍历，一般正常的表达式是中序遍历 即中缀表达式，根据其构造出树，再按题目要求求出前缀或后缀式。

简单求法：后缀表达式是从左到右开始，先把表达式加上括号，再依次把运算符加到本层次的括号后面。

3. 文法定义

一个形式文法是一个有序四元组G=(V,T,S,P),其中：

1)V:非终结符。不是语言组成部分，不是最终结果，可理解为占位符。

2)T:终结符。是语言的组成部分，是最终结果。V⌒T=θ

3)S:起始符。是语言的开始符号。

4)P:产生式。用终结符替代非终结符的规则。形如α->β

终结符：最终结果，不能推导出其他元素。

非终结符：能够推导出其他元素。

产生式：即非终结符推导出终结符的公式。

闭包，概念如下图，一般考察闭包可以为0个的情况代入运算：

正则闭包：A+=A1UA2UA3U…UAn U…（也就是所有幂的组合)。

闭包：A*=A0UA+(在正则闭包的基础上，加上A0={ε})。

例如a={a,aa,aaa,…,ε},而(ab)*={ab,abab,ababab,.,ε}

4. 文法类型

5.正规式

对于字母表∑，其上的正规式及其表示的正规集可以递归定义如下。

（1） ε 是一个正规式，它表示集合L( ε）={ ε}。

（2）若a是∑上的字符，则a是一个正规式，它所表示的正规集为{a}。

（3）若正规式r和s分别表示正规集L和L(s），则：

①r|s是正规式，表示集合L U L(s)。

②r·s是正规式，表示集合LL(s)。

③r’是正规式，表示集合（L(r））。

④是正规式，表示集合L。

6. 有限自动机

确定的有限自动机和不确定的有限自动机：输入一个字符，看是 否能得出唯一的后继，若能，则是确定的，否则若得出多个后继则是不确定的

7.语法分析方法

自上而下语法分析：最左推导，从左至右。给定文法G和源程序串r。从G的开始符号S出发，通过反 复使用产生式对句型中的非终结符进行替换（推导），逐步推导出r。

递归下降思想：原理是利用函数之间的递归调用模拟语法树自上而下的构造过程，是一种自上而下 的语法分析方法。

自下而上语法分析：最右推导，从右至左。从给定的输入串开始，不断寻找子串与文法G中某个产 生式P的候选式进行匹配，并用P的左部代替（归约)之，逐步归约到开始符号S。

移进规约思想：设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式的右部时，就用左部去 代替，称为归约。很明显，这个思想是通过右部来推导出左部，因此是自下而上语法分析的核心思.