低级和高级语言

程序设计语言根据硬件是否能识别区分为两类：

  • 低级语言：二进制机器指令、汇编语言。
  • 高级语言：面向各类应用的程序设计语言，更加接近自然语言。需要通过编译器或解释器（翻译）来让机器执行。

编译和解释

程序设计语言按照翻译的方式可分为：

  • 编译：需要通过编译器（编译程序）将源程序（源代码）编译为包含二进制指令的可执行文件（目标程序）。

    真正在机器上运行的是与源程序（逻辑）等价的目标程序。

    源程序和编译器都不再参与目标程序的运行过程。

    汇编程序也是属于编译执行。

  • 解释：需要通过解释器（解释程序）将源程序（源代码）中的指令解释为二进制指令后给机器执行。

    该过程不会产生独立的目标程序。

    并且解释器和源程序都会参与到程序的运行过程（运行控制）中。

    与编译方式相比，解释方式程序执行的速度慢，因为解释方式执行的程序，需要解释器在其中充当一个原程序与机器之前实时的翻译。

    脚本语言属于动态语言，其程序结构可以在运行中改变。

编译过程

编译程序的功能是把某高级语言书写的源程序翻译成与之等价的目标程序（汇编语言或机 器语言)。

编译程序的工作过程如下图所示：

编译过程

其中，以下几个阶段对于编译过程来说是必须的：

  1. 词法分析
  2. 语法分析
  3. 语义分析
  4. 目标代码生成

以下两个阶段对于编译过程来说不是必须的（可省略）：

  • 中间代码生成
  • （中间或目标）代码优化

词法分析

源程序可以简单地被看成是一个多行的字符串。词法分析阶段的任务是对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个“单词”符号。“单词”符号是程序设计语言的基本语法单位，如关键字（或称保留字）、标识符、常数、运算符和分隔符（如标点符号、左右括号）等。

词法分析程序输出的“单词”常以二元组的方式输出，即单词种别和单词自身的值。

词法分析过程依据的是语言的词法规则，即描述“单词”结构的规则。

词法规则

词法分析根据词法规则将构成源程序的字符串转换成单词符号序列。词法规则可用3型文法（正规文法）或正规表达式描述。

正规表达式

正规表达式（正规式）有以下符号：

符号 名称 含义
* 闭包 表示其前面链接的符号或集合可以出现$[0, +\infty]$次。
· 连接 可省略，将多个符号或集合连接起来。表示逻辑与
| 或 表示逻辑或。

Example：

设$U$、$V$和$W$均为正规式：

有限自动机

有限自动机是词法分析的一个工具（一种识别装置的抽象概念），它能正确地识别正规集。

  • 确定的有限自动机（Deterministic Finite Automata，DFA）：对每一个状态来说识别字符后转移的状态是唯一的。

    一个DFA是一个五元组$(S, \Sigma, f, s_0, Z)$：

    • $S$：包含状态的有限集（每个元素称为一个状态）。

    • $\Sigma$：有穷字母表，其每个元素称为一个输入字符。

    • $f$：$S \times \Sigma \to S$ 上的单值部分映像。

      $$ f(A,a)=Q \qquad A \in S, a \in \Sigma $$

      表示当前状态为$A$、输入为$a$时，将转换到下一状态$Q$，称$Q$为$A$的一个后继状态。

    • $s_0$：唯一的开始状态，$s_0 \in S$。

    • $Z$：非空的终止状态集合，$Z \subseteq S$。

    DFA可以用两种直观的方式表示：

    • 状态转换图：简称为转换图，是一个有向图。

      • DFA中的每个状态对应转换图中的一个结点。

      • DFA中的每个转换函数对应图中的一条有向弧。

      • 双圈表示的结点是终态结点。

        终态也可以是初态。

      若转换函数为$f(A,a)=Q$，则该有向弧从结点$A$出发，进入结点$Q$,字符$a$是弧上的标记。

    • 状态转换矩阵：用一个二位数组$M$表示。

      矩阵元素$M[A,a]$：

      • 行下标：表示状态。当前状态为$A$。
      • 列下标：表示输入的字符。当前输入为$a$。
      • $M[A,a]$的值：当前状态为$A$、输入为$a$时，应该转换到的下一状态。

  • 不确定的有限自动机（Nondeterministic Finite Automata，NFA）：对每一个状态来说识别字符后转移的状态是不唯一的。

    NFA也是一个五元组$(S, \Sigma, f, s_0, Z)$。与DFA的区别是：

    • $f$是$S \times \Sigma \to 2^S$ 上的映像。

      对于$S$中的一个给定状态及输入符号，返回一个状态的集合。即当前状态的后继状态不一定是唯一的。

    • 有向弧上的标记可以是 $\varepsilon$（$\varepsilon$ 表示空）。

    DFA是NFA的特例。

有限自动机识别成功的依据是路跑的通并且跑完后的终点是终态。

有向弧中出现如 $a,b$，代表该有向弧输入的值可以为$a$或$b$。即,代表或。

语法分析

语法分析的任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如“表达式”“语句”和“程序”等。

如果源程序中没有语法错误，语法分析后就能正确地构造出其语法树；否则指出语法错误，并给出相应的诊断信息。

例如对id1 := id2 + id3 * 60进行语法分析后形成的语法树：

一般来说，根据表达式生成的语法树，运算符在表达式种优先级越高，它在语法树中的层次就越低，反之亦然。

词法分析和语法分析在本质上都是对源程序的结构进行分析。

到达语法分析阶段可以发现程序中所有的语法错误。例如：

  • 变量的值是否正确；
  • 语句的形式是否正确；
  • 语句的结构是否合法；
  • 检查括号是否匹配；
  • ……

语法分析方法有多种，根据产生语法树的方向，可分为自底向上和自顶向下两类。

上下文无关文法

程序设计语言的绝大多数语法规则可以采用上下文无关文法进行描述。

上下文无关文法属于乔姆斯基定义的2型文法。

对于上下文无关文法，$G[S] = (V_N, V_T, P, S)$，其产生式的形式都是 $A \to \beta$，其中 $A \in V_n$，$\beta \in (V_N \cup V_T)^*$。即：

  • $V_N$：非终结符号集合，
  • $V_T$：终结符号集合，
  • $P$：产生式集合，
  • $S$：开始符号。

上下文无关文法的推导过程可用树型结构描述：

由上下文无关文法的推导过程也可以看出它是自顶向下推导。

对于上下文无关文法中的集合，有以下对应关系：

  • $S \to P$
  • $P \to V_N$
  • $V_N \to V_T$

语义分析

语义分析阶段分析各语法结构的含义，检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。只有语法和语义都正确的源程序才能翻译成正确的目标代码。

语义分析的一个主要工作是进行类型分析和检查。程序设计语言中的一个数据类型一般包含两个方面的内容：类型的载体及其上的运算。

语义分析阶段的输入是上一个阶段（语法分析）所构造的语法树。

语义分析后语法树中可能会出现一些语义处理结点。例如inttoreal，表示将一个整型数转换为浮点数。

语义分析不能发现程序中所有的语义错误。语义分析只能发现静态语义错误，动态语义错误需要在生成目标程序后运行时才能发现。

有语义错误是可以编译成功的。例如a/0，符合语法，也符合静态语义，编译器检验不出来这个是错的，只有运行才会报错，也就是动态语义，动态语义错误常见的还有死循环。

PS：现在有些IDE会对一些常见的动态语义错误进行检查，在程序编译前提示给用户。

中间代码生成

中间代码生成阶段的工作是根据语义分析的输出生成中间代码。

“中间代码”是一种简单且含义明确的记号系统，可以有若干种形式，它们的共同特征是与具体的机器无关。最常用的一种中间代码是与汇编语言的指令非常相似的三地址码，其实现方式常采用四元式。四元式的形式为：

(运算符, 运算对象1, 运算对象2, 运算结果)

语义分析和中间代码生成所依据的是语言的语义规则。

中间代码生成阶段对于编译过程来说是可省略的。但是前面的三个阶段词法分析、语法分析和语义分析还有最后的目标代码生成是不可省略的。

编译器前后端

对于编译过程的各个阶段，在逻辑上可以把它们划分为：

  • 前端：
    • 词法分析
    • 语法分析
    • 语义分析
    • 中间代码生成
  • 后端：
    • 中间代码优化
    • 目标代码生成

以中间代码为分水岭（中间代码作为前端的输出，然后再作为后端的输入来连接前后端），把编译器分成了与机器有关的部分（后端）和与机器无关的部分（前端）。如此一来，对于同一种程序设计语言的编译器，开发出一个前端之后，就可以针对不同的机器开发相应的后端，前、后端有机结合后就形成了该语言的一个编译器。当语言有改动时，只会涉及前端部分的维护。

对于不同的程序设计语言，分别设计出相应的前端，然后将各个语言的前端与同一个后端相结合，就可以得到各个语言在某种机器上的编译器。

使用中间代码，将编译器分为前后端的好处是，有利于编译程序的可移植性。

编译程序的可移植性提高了，那么相应的源程序（源代码）的可移植也会提高。

中缀和后缀表达式

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

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

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

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

    后缀转中缀用到了栈。

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

代码优化

由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进行的，因此，生成的中间代码往往在时间上和空间上有较大的浪费。当需要生成高效的目标代码时，必须进行优化。优化过程可以在中间代码生成阶段进行，也可以在目标代码生成阶段进行。

由于中间代码不依赖于具体机器，此时所做的优化一般建立在对程序的控制流和数据流分析的基础之上，与具体的机器无关。优化所依据的原则是程序的等价变换规则。

目标代码生成

目标代码生成阶段的任务是把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码，这个阶段的工作与具体的机器密切相关。

寄存器的分配：寄存器访问速度快，但数量有限，所以如何分配及使用寄存器是目标代码生成时需要着重考虑的。

编译过程中为变量分配的存储单元所用的地址是逻辑地址，程序运行时再将逻辑地址映射为物理地址。

符号表管理

符号表的作用是：

  • 记录源程序中各个符号的必要信息；
  • 辅助语义的正确性检查和代码生成。

在编译过程中需要对符号表进行快速有效地查找、插入、修改和删除等操作。

  • 符号表在前三个阶段构建：可以始于词法分析阶段，也可以放到语法分析和语义分析阶段
  • 符号表的使用有时会延续到目标代码的运行阶段。

编译过程中翻译主要考虑声明语句和可执行语句。对声明语句，主要是将所需的信息正确地填入符号表；对可执行语句，则是将其翻译成中间代码或目标代码。

出错处理

编写的源程序中出现的错误分为：

  • 静态错误：

    编译阶段发现的程序错误，又可分为：

    • 语法错误：有关语言结构上的错误。

    如单词拼写错误、标点符号错误、表达式中缺少操作数、括号不匹配等。

    • 静态语义错误：运算符与运算对象类型不合法等错误。

  • 动态错误（动态语义错误）：发生在程序运行时。

    常见的动态错误例如除数为0。

在编译时发现程序中的错误后，编译程序应采用适当的策略修复它们，使得分析过程能够继续下去，以便在一次编译过程中尽可能多地找出程序中的错误。

程序设计语言的基本成分

程序设计语言的基本成分包括：

  • 数据
  • 运算
  • 控制
  • 传输
  • （函数）

数据成分

数据成分包含以下内容：

  • 标识符：标识符通常是由字母、数字和下划线_组成，并且不能由数字开头。

    一般有如下种类标识符：

    • 关键字。
    • 变量名。
    • 函数名。

    现在，某些高级语言已经支持中文等字符来当作变量名。

  • 常量：一般有字面量（例如123、"abc"）和不可变变量（在某些语言中也称其为常量）。

    • 常量也具有类型；
    • 常量也有对应的存储单元。

  • 变量：用来存储数据或对象。有存储类别、类型、名称（变量名）、作用域和生存周期等属性（这些也是数据的属性）。

  • 全局量：在程序代码中的作用域（作用范围）为整个文件或程序的数据。

  • 局部量：在程序代码中的作用域（作用范围）为定义它的函数或语句块中的数据。

  • 数据类型：按照数据组织形式的不同可将数据分为基本类型、用户定义类型、构造类型（C和C++）及其他类型等。

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

    • 分配存储单元：便于为数据合理分配存储单元；
    • 检查数据对象：便于对参与表达式计算的数据对象进行（合法性）检查；
    • 取值范围：便于规定数据对象的取值范围及能够进行的运算

动态数据结构，其数据的结构会在程序运行过程中改变，例如链表、二叉树等。

动态数据结构的数据空间必须采用堆存储分配策略，数据存放在堆区。

在C/C++中，全局变量的存储空间在静态数据区分配。

运算成分

大多数高级程序设计语言的基本运算可以分为：

  • 算术运算。
  • 关系运算。
  • 逻辑运算。
  • 位运算。
  • …

控制结构

有以下三种结构来构造程序中的控制逻辑：

  • 顺序结构。
  • 选择结构。
  • 循环结构。

大多数高级语言都针对循环结构提供了break、continue等控制流跳转语句。

传输成分

程序设计语言的传输成分指明语言允许的数据传输方式，如赋值处理、数据的输入和输出等。

函数

函数定义：

  • 函数首部：
    • 返回值类型
    • 函数名
    • 形参表
  • 函数体：定义函数所实现的功能。

函数声明：在C（C++）中，函数需要先声明后引用。

函数调用：在调用函数中使用被调函数实现的功能。函数调用的一般形式为：

函数名(实参表)

调用函数与被调函数之间参数的传递有两种形式：

  • 值调用（Call by Value）：形参是实参的一份拷贝。即实参将值传递给形参，对形参值的更改并不会作用到实参上。

  • 引用调用（Call by Reference）：形参是实参的一个别名。即函数中对形参的访问和修改实际上是对其相应实参所做的访问和修改。

    引用调用下，可以实现形参和实参之间数据的双向传递。

在进行函数调用和返回时，由系统使用栈区来进行控制和管理。