编译原理（一）编译程序、解释程序、程序设计语言范型

编译原理的地位

• 是软件技术的基础
• 是计算机专业的基础课程，是专业必修课

编译原理的作用

• 编译原理是介绍如何将高级语言程序变换成低级语言程序的方法。
• 其理论基础坚实，其形式化系统不仅用于编译程序，还大量用于人工智能、多媒体技术、数据库等领域。

程序设计语言

低级程序语言

• 特定的计算机系统所固有的语言
• 即：机器语言、汇编语言
• 特点：执行效率高、编制效率低

高级程序语言

• 与自然语言比较接近的语言
• 过程式语言：C, Pascal, Fortran,
• ADA 对象式语言：Java, C++ 等
• 函数式语言：LISP
• 逻辑式语言：Prolog
• 特点：执行效率低、编制效率高

1.1 什么是编译程序

一、编译程序（又称“编译器”）

• 是语言的翻译器
• 功能：高级语言的源程序低级语言的目标程序
• 重要性：使编程者不必考虑与机器有关的细节
• 本课程主要研究：顺序过程式语言的编译原理和技术

二、高级语言程序的处理过程

1 词法分析

任务：
从左到右读入源程序的每个字符，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也叫单词符号或符号）。
单词是具有独立意义的最小语法单位。
如：标识符、保留字（关键字或基本字）、算符、界符、常数等。

例. 某源程序片断如下：

• 保留字 begin
• 保留字 var
• 标识符 sum
• 逗号 ,
• 标识符 first
• 逗号 ,
• 标识符 count
• 冒号 :
• 保留字 real
• 分号 ;
• 标识符 sum
• 赋值号 :=
• 标识符 first
• 加号 +
• 标识符 count
• 乘号 *
• 整数 10
• 保留字 end
• 界符 .

2 语法分析

任务：

• 依据语言的语法规则，确定源程序的输入串是否构成一个语法上正确的程序。
• 最终将单词序列分解成各类语法短语（也叫语法单位），如“程序”、“语句”、“表达式”等。

语法：由程序语言基本符号组成程序中各个语法成分的一组规则。

• 一般语法规则 ：由单词符号构成语法成分的规则；
• 词法规则 ：由基本符号构成的符号书写规则。
  

程序结构的递归表示

表达式的表示：
1）任何标识符是表达式。
2）任何常数（整常数、实常数）是表达式。
3）若表达式1和表达式2都是表达式，那么
表达式1+表达式2
表达式1*表达式2
（表达式1）
都是表达式。
语句的表示：
1）标识符:=表达式 是语句
2）while (表达式) do 语句 是语句
3）if(表达式) then 语句 else 语句 是语句

3 语义分析

任务：审查源程序有无语义错误，为代码生成阶段收集类型信息。
主要功能：类型检查、报语义错误、类型转换等

语义：是程序设计语言中按语法规则构成的各个语法成分的意义。

• 静态语义：编译时刻即可确定的语法成分含义。
• 动态语义：运行时刻才能确定的语法成分含义。

5 代码优化

任务：对中间代码进行变换或改造，使之更为高效（时间、空间）。

表格管理

任务：用于保存源程序的各种信息。因为上述各阶段工作均需要查找、更新、构造表格。

出错处理

任务：报告源程序中错误的性质、地点，将错误所造成的影响限制在尽可能小的范围。有些编译程序还可以自动纠错。
一个程序是正确的，包括两层含义：
1）书写正确（合乎语法规则）
2）含义正确（合乎语义规则）

注意：
多数实用的编译程序都采用以上几个阶段的工作过程。
有些编译程序没有“中间代码生成”和“代码优化”。

二、编译程序的结构

二、解释程序与编译程序的比较

答案：ACAC

答案：BDAC

答案：CB

答案：（1）表格处理和出错处理
（2）中间代码生成（3） 代码优化
（4）单词 （5）语法错误

答案：ABCF
因为代码优化是为了提高目标程序的质量，不是必须的，没有优化源程序一样能够转化为目标代码。而中间代码生成是为代码优化服务的，没有代码优化的编译器可以直接生成目标代码。

答案：（1）B E (2) D (3) B

12、判断：“含有代码优化的编译器的执行效率高”。

答案：错。含有代码优化的编译器，其优化是指对生成的目标代码进行了优化，而不是编译器本身得到了优化，所以，它提高的是目标代码的执行效率，而不是编译器本身的执行效率。

13. 判断：“解释方式与编译方式的区别在于解释程序对源程序没有真正进行翻译”。
答案：错。编译方式和解释方式实际上都进行的翻译，只是编译相当于笔译，而解释相当于口译。 解释方式下，不将于源程序彻底翻译成目标代码，而是每读入一条语句，将其翻译成中间代码，解释其含义并执行，然后再读入下一条语句，再翻译执行。 编译方式和解释方式的根本区别在于“是否生成了目标代码”。

来源：王致列