编译原理

2026-01-21

学校课程复习

写在前面：

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

2 高级语言及其语法描述

2.1 程序语言的定义

2.1.1 语法

2.1.1.1 字母表

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

2.1.1.2 词法规则

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

2.1.1.3 语法规则

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

2.1.2 语义

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

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

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

2.2 高级语言的一般特性

2.2.1 高级语言的分类

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

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

2.2.1.1 强制式语言

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

2.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$ 是无歧义的。

2.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

2.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);
    }
}

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

2.2.2 程序结构

一个程序往往通过若干子程序段构造，书本采用了很多种语言讲述，我转述为c++完成。

2.2.2.1 多子程序结构

书本上用了fortran语言完成

void learn_in_tongji()
{
    learn_gaocheng();
    learn_oop();
}
int main ()
{
    learn_in_tongji();
    return 0;
}

2.2.2.2 子程序嵌套定义

原书用pascal举例

int main()
{
    double gpa = 5.0;
    if (gpa < 4.0){
        cout << "failed to get in school of computer science and technology" <<endl;
    } else {
        if (gpa <=5.0){
            cout << " sorry ,you can't graduate from tongji university!!!" << endl;
        }
        else {
            if (gpa <= 6.0){
                cout << "Not eligible for graduate school admission through recommendation" <<endl;
            } else{
                cout << "congradulations !"
            }
        }
    }
}

2.2.2.3 按包封装

原书用ada举例。其实是类似于结构体。

typedef struct tongji{
    int people = 3;
    int boat = 1;
    int oars = 3;
}; //不用怀疑，这是校徽

2.2.2.4 面向对象

原书用java举例

这样的语言真正实现了类之间的继承、多态、动态绑定等特征。

class six{};
class five{};
class four{};
class seven{};
class two{};
class tongji:class six, class five, class four ,class seven ,class two{
};

2.2.3 数据类型与操作

一个数据类型通常包括以下三种要素：

属性
值
可以对这个数据对象的操作

2.2.3.1 初等数据类型

数值数据 ：整数、实数、复数
逻辑数据 ：逻辑型数据
字符数据 ：字符、字符串
指针类型 ：地址

2.2.3.2 标识符与变量名

标识符：由字母或数字组成的以字母为开头的一个字符串。在程序语言当中的各种名字都是由各种标识符表示的。
变量名：变量名相当于是标识符的一种，用于辅助程序员标记这个变量。
- 类型：决定了能够取什么样的值，在计算机内的表示方式，以及能够施加什么运算
- 作用域：规定了值的存在范围。

2.2.3.3 基本数据结构

数组：从0开始或者从1开始的数组。一个数组所需的存储空间的大小在编译的时候就知道，这叫做确定数组，否则称之为可变数组。
结构体
字符串
表格
栈
队列
抽象数据类型，允许抽象运算。特征在于可以完成运算符重载。

2.2.4 语句与控制结构

2.2.4.1 表达式的形成规则

变量、常数是表达式
若$E_1,E_2$是表达式，$\theta$ 是一个二元运算符，则$E_1 \ \theta \ E_2$是表达式。

事实上，这个表达式可以采用前缀表达式或者后缀表达式。
若E 是表达式，$\theta$ 是一个一元运算符，则 $\theta \ E$ 或者 $E \ \theta$ 是表达式
若E 是表达式，则 $ ( E )$ 也是表达式。

一般情况下，运算符结合的优先性与按照常识所学来。

2.2.4.2 语句

赋值语句 a := b （这个叫海象运算符）。
- 左值一个名字所指代变量的地址
- 右值一个名字所指代变量的实际值
控制语句
- 无条件转移语句 goto
- 条件语句 if then
- 循环语句 while repeat for
- 过程调用语句 call
- 返回语句 return

说明句

其实这个就是类似于函数提前声明。

// 1. 变量说明句：声明变量类型
int age;          // 声明int型变量age
float score = 90.5; // 声明+初始化float型变量score
   
// 2. 函数说明句（函数原型）：声明函数的参数、返回值
int add(int a, int b); 
   
// 3. 类型说明句：自定义类型
typedef int Integer; // 声明Integer是int的别名
struct Student {     // 声明结构体类型Student
    char name[20];
    int id;
};

简单句和复合句

就是把上面的语句复合起来用。例如
```
if (...) goto ...
```

2.3 程序语言的语法描述

2.3.1 上下文无关文法

嗯，这是你形式语言当中学过的内容。不过我们来回顾一些概念吧。

终结符号
非终结符号
开始符号
产生式
如果一个产生式，其中有如下这么多种情况的话，那么其中a、b、c、d分别称之为一个 候选式

P -> a|b|c|d

其中 -> 读作 “定义为”，“ | ” 读作或，他们是 元语言符号
若a -> b-> c -> d 那么这一串过程叫做从a到d的推导。
$\alpha \overset{+}{\Rightarrow} \beta$ 表示至少经过1步推导。
$\alpha \overset{*}{\Rightarrow} \beta$ 表示至少经过0步推导。

$S \overset{*}{\Rightarrow} \alpha$ 其中$\alpha$称之为一个句型，如果$\alpha$当中仅含终结符号，那么这称之为一个句子。文法G产生的所有句子是一个语言。记作 $L(G)$ 。$$ L(G) = { \alpha

S \overset{+}{\Rightarrow} \alpha \& \alpha \in V^*}$$

最左推导 每一步都对最左侧的非终结符推导，也即最右规约。

2.3.2 语法分析树和歧义性

嗯，这里没有什么需要过多指出的。都是你学过的！\ o /

2.3.3 形式语言鸟瞰

乔姆斯基
0 型文法，即图灵机。
1 型文法，上下文有关文法。$ \alpha A \beta \rightarrow \alpha \gamma \beta $ 也就是说，对于A的替换必须要考虑A的上下文。
2 型文法，上下文无关文法。不用考虑呗。
3 型文法，右线性文法（左线性文法），也即正则文法。

3 词法分析

3.1 对于词法分析器的要求

3.1.1 词法分析器的要求

程序语言的单词符号一般分为以下几种：

关键字 也就是c++当中的保留字。例如：if while do protected
标识符 int float 之类的
常数包括整数、实型、布尔型、文字型等等
运算符 + - * /
界符逗号，分号，括号

一个词法分析器输出的单词符号常常表示成如下的二元式：

(单词种别，单词符号的属性值)

其中：

单词种别 通常用整数编码。如何确定分种的方式，分种的数量，分种的编码方式，是重要且困难的技术性问题。
- 关键字：可以共同一种，也可以一符一种，一符一种更为方便
- 标识符：一般统共一种
- 常数：按照自己的类型分种
- 运算符：可以一符一种，也可以进行分类，按照相似属性的运算符进行分类。
- 界符：一般一符一种。

对于以下的c++代码，会被解析为：

while (i >=j ) i-- ;

单词种别	单词符号的属性值
while	-
(	-
id	&i
>=	-
id	&j
)	-
i	&i
;	-

3.1.2 词法分析器应当作为一个独立的子程序

这样的程序能够让程序变得更加调理
有两种方式应用这个程序
- 将代码转化成为一个中间文件保存。
- 每次需要解析的时候调用这个子程序。

3.2 词法分析器的设计

输入：程序文本、字符串+词法单元（token）的规约
输出：词法单元流
词法分析器生成器（antlr）/手写词法分析器/自动化词法分析器（自己实现一个词法分析器生成器）
手写的工作量并不大，词法分析器对于错误处理并不友好

3.2.1输入预处理

预处理谁？空白符，跳格符，回车符，换行符

3.2.2 超前搜索

将需要处理的内容预先读入缓存区当中，在缓冲区中对于一个个的字段进行超前搜索。

需要识别：关键字，标识符，常数，算符和界符。

3.3 正规表达式与有限自动机

3.4 词法分析器的自动产生

3.4.1 语言lex的一般表述

使用antlr4 语言完成了如下内容

grammar CLexer ;

prog : stat* EOF;

stat : expr SEMI
     | ID ASSIGN expr SEMI
     | PRINT  expr SEMI
     ;
ASSIGN : '=' ;
MUL : '*' ;
DIV : '/' ;
ADD : '+' ;
SUB : '-' ;
LPAREN : '(' ;
RPAREN : ')' ;
PRINT : 'print' ;
SEMI : ';' ;
expr : expr MUL expr
    | expr DIV expr
    | expr ADD expr
    | expr SUB expr
    | LPAREN expr RPAREN
    | ID
    | INT
    ;
// 显然的， 如果不出现这样的递归调用的话， 将会产生一个有穷语言
ID : ('_' |LETTER)('_' | LETTER | DIGIT )*;

INT : '0' | ('+' | '-' )? [1-9]DIGIT *;
//                      ^ 此处问号表示前面的符号可有可无， 也就是说整数可以以正负号开头， 也可以没有符号开头

WS : [ \t\r\n]+ -> skip; //white space

DOCS_COMMENT : '/**' .*? '\n' -> skip; // documentation comment

SL_COMMENT : '//' .*? '\n' -> skip; // single line comment
                 // ^ ? 代表贪婪匹配后面的内容，也就是遇到第一个后面的内容就结束

SL_COMMENT_2 : '//' (~[\n]*) '\n' -> skip; // single line comment alternative
                 //  ^ ~ 表示匹配除了\n 以外的所有内容，直到遇到 \n
ML_COMMENT : '/*' .*? '*/' -> skip; // multi-line comment
                 // ^ ? 起到了同样的作用

fragment LETTER : [a-zA-Z] ;
fragment DIGIT : [0-9] ;

语法规则以小写字母开头，词法规则以大写字母开头

antlr4 有如下几种特殊的匹配规则：

最前优先匹配——更靠前的语法规则会被匹配
最长优先匹配——更长的词法规则会被匹配
非贪婪匹配——（）？？（） * ？，（）+ ？

测试内容：

//a= a + b;

//a = a * b;

a = 3;
print a;

/* 12\
3 */
/** 123 **/

1+ 2 * 3 / 4 ;

一个期望的结果如下

parseTree

3.4.2 超前搜索

所谓超前搜索，就是在文档中找到匹配当前词法单元最长的字符串

3.4.3 LEX 的实现

在课程中遇到了一个java关键字 final 。这里特别说明

特性	C++ const	C++ constexpr	Java final（对比参考）
核心语义	只读（运行时 / 编译期常量均可）	编译期常量（必须编译期确定值）	不可重赋值（编译期 / 运行时常量均可）
初始化要求	可以用运行时的值初始化（如函数返回值）。例：`int getNum() { return 10; }const int a = getNum(); // 合法，运行时常量`	必须用编译期可计算的值初始化，不能用运行时数据。例：`constexpr int a = getNum(); // 编译错误（getNum 不是 constexpr 函数）constexpr int b = 10 + 20; // 合法（编译期计算）`	可以用运行时的值初始化（如构造器中赋值）。例：`final int a = new Random().nextInt(); // 合法`
适用场景	修饰运行时只读的变量（如函数参数、类成员）。	修饰必须编译期确定的常量（如数组大小、模板参数）。	修饰运行时不可重赋值的变量，仅 `static final 基本类型+字面量` 是编译期常量。

  public Token(TokenType type, String text) {
    this.type = type;
    this.text = text;
  }

这里体现了前文所述，一个词法单元可以解析为类型和内容

类型大致如下

package dragon;

/**
 * Types of tokens
 * Grouped by hardness of recognition
 */
public enum TokenType {
  // Group 0
  EOF,  // end of file
  UNKNOWN,  // for error

  // Group 1
  // lookhead = 1 (LA(1))
  DOT, POS, NEG,
  IF, ELSE,
  ID,
  INT,
  WS,

  // Group 2
  // =, <>, <, <=, >, >=
  // LA(2) lookahead = 2 2位超前搜索
  EQ, NE, LT, LE, GT, GE,

  // Group 3
  // arbitrary LA 需要向前看任意长度的文本
  REAL,// integer double
  SCI,// scientific notation 科学计数法
}

对于这样一个语法单元123Ex，前面读取到E之后猜测这是一个词法单元，但是这是一个错误的猜测，就要回退到上一个正确的地方。

一个正确的lexer 应该做到 记录来时最长匹配，无路可走便回头

3.4.3.1int id ws

对于这三类词法单元，需要不断重复直到遇到第一个错误

3.4.3.2 运算符号

需要一个有限DFA便可识别出所有需要的内容。