第三章 程序设计语言

1. 基本概念

  • 解释器：

    • 解释程序不生成可执行文件，可以遂条解释执行，用于调试模式，可以控制源程序，因为还需要控制程 序，因此执行速度慢，效率低。

  • 编译器：

    • 编译程序生成独立的可执行文件，直接运行，运行时无法控制源程序，效率高。

  • 许多程序设计语言规定，程序中的数据必须具有类型，其作用是：

    • 便于为数据合理分配存储单元

    • 便于对参与表达式计算的数据对象进行检查

    • 便于规定数据对象的取值范围及能够进行的运算

各程序设计语言特点：

  • Fortran语言（科学计算，执行效率高）
  • Pascal语言（为教学而开发的，表达能力强，Delphi）
  • C语言（指针操作能力强，高效）
  • Lisp语言（函数式程序语言，符号处理，人工智能）
  • C++语言（面向对象，高效)
  • Java语言（面向对象，中间代码，跨平台）
  • C#语言（面向对象，中间代码，.Net）
  • Prolog语言（逻辑推理，简洁性，表达能力，数据库和专家系统）

2. 基本成分

  • 数据：常量和变量、全局量和局部量、数据类型
  • 运算：算式运算、关系运算、逻辑运算
  • 控制：顺序结构、选择结构、循环结构
  • 传输：赋值、输入、输出 函数：定义、声明、调用：传值(值调用)、传地址(引用调用)
    • 传值调用：将实参的值传递给形参，实参可以是变量、常量和表达式。不可以实现形参和实参间双向传 递数据的效果。
    • 传引用（地址）调用：将实参的地址传递给形参，形参必须有地址，实参不能是常量（值）、表达式。 可以实现形参和实参间双向传递数据的效果，即改变形参的值同时也改变了实参的值。

3. 编译程序基本原理

  • 编译方式：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成

  • 解释方式：词法分析、语法分析、语义分析

  • 编译器和解释器都不可省略词法分析、语法分析、语义分析且顺序不可交换

  • 即词法分析、语法分析、语义分析是必须的。

  • 编译器方式中中间代码生成和代码优化不是必要，可省略。

  • 即编译器方式可以在词法分析、语法分析、语义分析阶段后直接生成目标代码

符号表：不断收集、记录和使用源程序中一些相关符号的类型和特征等信息，并将其存入符号表中。记录源程序中各个字符的必要信息，以辅助语义的正确性检查和代码生成。

1）词法分析

  • 输入：源程序
  • 输出：记号流
  • 词法分析阶段的主要作用是：分析构成程序的字符及由字符按照构造规则构成的符号，是否符合程序语言的规定。

2）语法分析

  • 输入：记号流
  • 输出：语法树（分析树）
  • 语法分析阶段的主要作用是：对各条语句的结构进行合法性分析，分析程序中的句子结构是否正确。
  • 语法分析阶段可以发现程序中所有的语法错误

3）语义分析

  • 输入：语法树（分析树）
  • 语义分析阶段的主要作用是进行类型分析和检查
  • 语义分析阶段可以发现程序中所有的语法错误
  • 语义分析阶段不能发现程序中所有的语义错误

语义分析阶段可以发现静态语义错误，不能发现动态语义错误，动态语义错误运行时才能发现（eg：除数为0时只能在运行阶段检查出来）

4）中间代码生成

常见的中间代码有：后缀式、三地址码、三元式、四元式和树（图）等形式。

中间代码与具体的机器无关（不依赖具体的机器）,可以将不同的高级程序语言翻译成同一种中间代码。

中间代码可以跨平台。

因为与具体的机器无关，使用中间代码有利于进行与机器无关的优化处理和提高编译程序的可移植性。

6）目标代码生成

目标代码生成阶段的工作与具体的机器密切相关,寄存器的分配工作处于目标代码生成阶段

4. 正规式

有限自动机

  • 有限自动机是词法分析的一个工具，它能正确地识别正规集
  • 确定的有限自动机（ DFA )：对每一个状态来说识别字符后转移的状态是唯一的
  • 不确定的有限自动机（ NFA )：对每一个状态来说识别字符后转移的状态是不唯一的

5. 文法

G={Vt,Vn,S,P}G=\lbrace Vt,Vn,S,P\rbrace

  • Vt：非空有限集合的符号，它的每个元素称为终结符号

  • Vn：非空有限集合的符号，它的每个元素称为非终结符号

  • S：文法G的开始符号

  • P：非空有限集合，它的元素称为产生式

    正则闭包：A + = A 1 U A 2 U A 3 U … U A n U … (也就是所有幂的组合)

    闭包：A * = A 0 U A +(在正则闭包的基础上，加上A 0 = { })

    例如：ab* = {ab,abab,ababab,…, }

类型对应的自动机

别称 对应自动机
短语文法 图灵机
上下文有 关文法 线性界限自动 机
上下文无 关文法 非确定的下推 自动机
正规文法 有限自动机

6. 中缀后缀表达式

中缀式：a ？ b ===> 后缀式：ab？ 后缀式转中缀式可以用：栈

中间代码有多种形式，其中树与后缀表示形式适用于解释器，而编译器多采用与机器指令格式较接近的四元式形式。

根据生成的语法树，按照不同的方式遍历即可生成形式不同的表达式：

  • 中缀表达式：中序遍历（左-根-右）；
  • 后缀表达式：后序便利（左-右-根）。

逆波兰式其实就是后缀式。