编译原理

2026-01-21

学校课程复习

写在前面：

本篇blog参考于程序设计语言编译原理第3版陈火旺等编著
能看到前序当中指出，这本书参加的是九五计划，超级无比老的一本书。
知识永远不会过时，但是其中的例子略显陈旧。例如书中举例使用了上古人工智能编程语言 Lisp prolog fortran pascal 举例分析。

1 高级语言及其语法描述

1.1 程序语言的定义

1.1.1 语法

1.1.1.1 字母表

什么是高级语言 ：任何语言程序都可看成是一定字符集（字母表）上的一字符串。
对于下面这样一个运算式
```
0.5 * X1 + C
```
在这个运算式当中，单词符号 包括“0.5” “*” “ X1” “ + ” “C” 。而表达式 “0.5 * X1+ C ” 称之为语言的一个 语法范畴 或 语法单位
一个程序语言只使用一个有限字符集作为字母表
语法包括 语法规则（产生规则） 以及 词法规则。

1.1.1.2 词法规则

词法规则 ：词法规则规定了字母表中什么样的字符串是一个 单词符号。
单词符号 一般包括：各类型的常数、标识符、基本字、算符、和界符。

1.1.1.3 语法规则

语法规则 ：语法规则规定了如何从 单词符号 形成更大的结构（ **语法单位 ** ）
工具：有限自动机、上下文无关文法
额外限定
- 书写格式：fortran规定每行最多80列
- 空白字符：多数情况下无意义。有时用作间隔符。

1.1.2 语义

语义规则 ：对于一个语言，除了前文所述的词法规则和语法规则，需要对于前文的 单词符号 和 语法单位 的意义做出规定。
工具：基于属性文法的语法制导翻译方法，虽然这还不是一种形式系统，但它还是比较接近形式化的。
程序：描述一定数据的处理过程。

一个语言的层次可以大致如下：

flowchart TD
A["程序"] 
B["子程序 或 分程序"]
C["语句"]
D["表达式"]
E["数据引用"]
F["算符"]
G["函数调用"]
   
A --> B
B --> C
C --> D
D --> E
D --> F
D --> G

1.2 高级语言的一般特性

1.2.1 高级语言的分类

请关注这样一个函数的实现，以区分不同类别语言的特性。

int fibonacci (int n)
{
    if (n == 1 ) return 1;
    if (n == 2 ) return 1 ;
    else return fibonacci ( n-1 )+ fibonacci ( n - 2 ) ;
}

1.2.1.1 强制式语言

被称为过程式语言例如 Fortran C Ada Pascal 都属于这类语言，前面的内容就是这个范畴。

1.2.1.2 应用式语言

使用函数式的嵌套调用。

LISP ML 属于这个类别。

(defun fibonacci (n)
  (cond ((= n 1) 1)
        ((= n 2) 1)
        (t (+ (fibonacci (- n 1))
              (fibonacci (- n 2))))))

其实能够看到，这个语言当中的运算符是被提前的，曾经在 形式语言与自动机 **这门课当中有一道作业题已经证明了这个语言是 **无歧义的 。

下面的文法生成的是具有x和y操作数、二元运算符+、-和* 的前缀表达式:E→+EE|* EE|-EE|x|y

b) 证明这个文法是无歧义的。

要证明文法 $G$ 是无歧义的，只需说明每个由 $G$ 生成的串 $w$ 都对应唯一的语法分析树。我们采用如下引理，并基于其进行证明。

引理设 $w$ 是 $G$ 生成的任一串，定义函数 $f(i, w) = (\text{前 } i \text{ 个字符中操作符的个数}) - (\text{前 } i \text{ 个字符中运算数的个数}) + 1$，$0 \le i \le |w|$。则对所有 $i$ 有：

若 $0 \le i < w $，则 $f(i, w) \ge 0$；
$f( w , w) = 0$。

引理的证明 对 $w$ 的长度进行归纳。

基始：当 $ w =1$ 时，$w$ 只能是 $x$ 或 $y$。此时 $f(0,w)=1$，$f(1,w)=0$，结论成立。

归纳步骤：设 $

>1$，则 $w$ 必以某个操作符 $op \in {+, -, *}$ 开头，且可写为 $w = op\;w_1 w_2$，其中 $w_1, w_2$ 也是 $G$ 生成的串（且长度均小于 $

$）。根据归纳假设，引理对 $w_1, w_2$ 成立。

考虑 $f(i,w)$ 的分段行为：

当 $i = 0$ 时，$f(0,w) = 1$。
当 $1 \le i \le 1+|w_1|$ 时，$f(i,w) = f(i-1, w_1) + 1$。由归纳假设，$f(i-1, w_1) \ge 0$，故此时 $f(i,w) \ge 1 > 0$。

当 $1+	w_1	< i \le	w	$ 时，$f(i,w) = f\bigl(i - 1 -	w_1	, \; w_2\bigr)$。
由归纳假设，该值在 $i <	w	$ 时 $\ge 0$，且在 $i =	w	$ 时为 $0$。

综上，在 $i <

$ 时 $f(i,w) \ge 0$，且仅在 $i =

$ 时取 $0$。归纳完成。

利用引理证明文法无歧义 对任意由 $G$ 生成的串 $w$：

若 $ w =1$，则 $w$ 只能是 $x$ 或 $y$，其语法分析树唯一。
若 $|w|>1$，则 $w$ 必以操作符 $op$ 开头，故可写为 $w = op\,w’$。根据引理，函数 $f(i,w)$ 在 $i=1$ 时值为 $2$，且随着 $i$ 增大，首次下降到 $1$ 的位置即为 $w_1$ 结束的位置（因为下降到 $1$ 意味着已读完一个完整的子表达式）。该位置由 $f(i,w)$ 的唯一性保证是唯一的，从而 $w$ 可被唯一地分解为 $op\,w_1 w_2$，其中 $w_1, w_2$ 均为 $G$ 生成的表达式。由归纳假设，$w_1$ 与 $w_2$ 的语法分析树唯一，故整个串 $w$ 的语法分析树也唯一。

因此，文法 $G$ 是无歧义的。

1.2.1.3 基于规则的语言

例如 prolog 语言（上古人工智能编程语言）

实际上这个语言很像那个switch-case 分支语句，针对每一个条件给出一个输出。很适合写决策树噢！！！

% 规则：fibonacci(N, F) - N 是位置，F 是对应的斐波那契数
fibonacci(1, 1).
fibonacci(2, 1).
fibonacci(N, F) :-
    N > 2,
    N1 is N - 1,
    N2 is N - 2,
    fib(N1, F1),
    fib(N2, F2),
    F is F1 + F2.
    
% 调用示例
?- fibonacci(1, Result).  % Result = 1
?- fibonacci(2, Result).  % Result = 1  
?- fibonacci(5, Result).  % Result = 5
?- fibonacci(10, Result). % Result = 55

1.2.1.4 面向对象语言（牢坚！！！）

这个很熟悉了，给出一个足够面向对象的java语言。

public class fibonacci_obj {
    public static int fibonacci (int n){
        if (n <= 0) throw new IllegalArgumentException("n必须为正整数");
        else if (n == 1 || n == 2) return 1;
        else return fibonacci (n - 1) + fibonacci (n - 2);
    }
}

嗯，这很面向对象，哈哈我有对象啦！