编译原理

实现一门脚本语言-原理篇

理解代码：编译器的前端技术

  • 前端（Front End）: 编译器对程序代码的分析和理解过程
    • 词法分析（Lexical Analysis）
      • 程序分割成一个个 Token 的过程，可以通过构造有限自动机来实现
      • 识别一个个的单词
      • 词法记号（Token）
      • Lex（或其 GNU 版本，Flex）
        • 正则文法（Regular Grammar）
          • 符合正则文法的表达式
        • 有限自动机（Finite-state Automaton，FSA，or Finite Automaton） 算法
    • 语法分析 （Syntactic Analysis, or Parsing）
      • 把程序的结构识别出来，并形成一棵便于由计算机处理的抽象语法树。可以用递归下降的算法来实现。*`
      • 别出程序的语法结构
      • Yacc（或 GNU 的版本，Bison）、Antlr、JavaCC
      • 抽象语法树（Abstract Syntax Tree，AST）
      • clang -cc1 -ast-dump hello.c
      • 递归下降算法（Recursive Descent Parsing）
    • 语义分析（Semantic Analysis）
      • 消除语义模糊，生成一些属性信息，让计算机能够依据这些信息生成目标代码。
  • 后端（Back End）: 生成目标代码的过程，跟目标机器有关

正则文法和有限自动机：纯手工打造词法分析器

  • 关键字: 语言设计中作为语法要素的词汇
  • 保留字: 当前的语言设计中还没用到，但是保留下来，因为将来会用到

关键字和保留字跟标识符区分开呢？

  • 识别普通的 标识符 之前，是否 关键字 / 保留字

语法分析

纯手工打造公式计算器

推导（Derivation）过程

  • 左边：非终结符（Non-terminal）
  • 右边：产生式（Production Rule）
  • 语法解析的过程中，左边会被右边替代
  • 如果替代之后还有非终结符，那么继续这个替代过程，直到最后全部都是终结符（Terminal），也就是 Token。
1
intDeclaration : Int Identifier ('=' additiveExpression)?;

伪代码

1
2
3
4
5
6
MatchIntDeclare() {
  MatchToken(Int)；        // 匹配Int关键字
  MatchIdentifier();       // 匹配标识符
  MatchToken(equal);       // 匹配等号
  MatchExpression();       // 匹配表达式
}

“下降”的含义

  1. 上级文法嵌套下级文法
  2. 上级的算法调用下级的算法
  • 上下文无关文法
  • 正则文法(不允许递归调用)

小结

  • 初步了解上下文无关文法，知道它能表达主流的计算机语言，以及与正则文法的区别。
  • 理解递归下降算法中的 下降 和 递归 两个特点。
  • 它跟文法规则基本上是同构的，通过文法一定能写出算法。通过遍历 AST 对表达式求值，加深对计算机程序执行机制的理解。

解决二元表达式中的难点

左递归（Left Recursive）：产生式的第一个元素是它自身，那么程序就会无限地递归下去

  • 优先级（Priority）
  • 结合性（Associativity）
  • 产生式: 一组替换规则

巴科斯范（BNF):

1
2
3
add ::= mul | add + mul
mul ::= pri | mul * pri
pri ::= Id | Num | (add)

扩展巴科斯范式 (EBNF)

1
add -> mul (+ mul)*

确保正确的优先级

  • 括号

确保正确的结合性

  • 左结合的运算符，递归项放在左边
  • 右结合的运算符，递归项放在右边

消除左递归

左递归文法 -> 非左递归的文法

1
2
add -> mul add'
add' -> + mul add' | ε
  • ε（读作 epsilon）:空集

小结

  • 优先级 是通过在语法推导中的层次来决定的，优先级越低的，越先尝试推导。
  • 结合性 是跟左递归还是右递归有关的，左递归导致左结合，右递归导致右结合。
  • 左递归 可以通过改写语法规则来避免，而改写后的语法又可以表达成简洁的 EBNF 格式，从而启发我们用循环代替右递归。

实现一门简单的脚本语言

回溯: 尝试一个规则不成功之后，恢复到原样，再去尝试另外的规则
REPL（Read-Eval-Print Loop）: 输入、执行、打印的循环过程

编译器前端工具

用Antlr生成词法、语法分析器

Antlr: Antlr 是一个开源的工具，支持根据规则文件生成词法分析器和语法分析器，它自身是用 Java 实现的。

https://github.com/antlr/antlr4/blob/master/doc/getting-started.md

用 Antlr 生成词法分析器

Hello.g4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
lexer grammar Hello;  // lexer关键字意味着这是一个词法规则文件，名称是Hello，要与文件名相同

// 关键字
If :               'if';
Int :              'int';

// 字面量
IntLiteral:        [0-9]+;
StringLiteral:      '"' .*? '"' ;  // 字符串字面量

// 操作符
AssignmentOP:       '=' ;   
RelationalOP:       '>'|'>='|'<' |'<=' ;   
Star:               '*';
Plus:               '+';
Sharp:              '#';
SemiColon:          ';';
Dot:                '.';
Comm:               ',';
LeftBracket :       '[';
RightBracket:       ']';
LeftBrace:          '{';
RightBrace:         '}';
LeftParen:          '(';
RightParen:         ')';

// 标识符
Id :                [a-zA-Z_] ([a-zA-Z_] | [0-9])*;

// 空白字符，抛弃
Whitespace:         [ \t]+ -> skip;
Newline:            ( '\r' '\n'?|'\n')-> skip;
编译词法规则
1
antlr Hello.g4
编译 Hello.java
1
javac *.java
测试

hello.play

1
2
3
4
int age = 45;
if (age >= 17+8+20) {
    printf("Hello old man!");
}

词法分析

1
grun Hello tokens -tokens hello.play
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
[@0,0:2='int',<'int'>,1:0]
[@1,4:6='age',<Id>,1:4]
[@2,8:8='=',<'='>,1:8]
[@3,10:11='45',<IntLiteral>,1:10]
[@4,12:12=';',<';'>,1:12]
[@5,14:15='if',<'if'>,2:0]
[@6,17:17='(',<'('>,2:3]
[@7,18:20='age',<Id>,2:4]
[@8,22:23='>=',<RelationalOP>,2:8]
[@9,25:26='17',<IntLiteral>,2:11]
[@10,27:27='+',<'+'>,2:13]
[@11,28:28='8',<IntLiteral>,2:14]
[@12,29:29='+',<'+'>,2:15]
[@13,30:31='20',<IntLiteral>,2:16]
[@14,32:32=')',<')'>,2:18]
[@15,34:34='{',<'{'>,2:20]
[@16,40:45='printf',<Id>,3:4]
[@17,46:46='(',<'('>,3:10]
[@18,47:62='"Hello old man!"',<StringLiteral>,3:11]
[@19,63:63=')',<')'>,3:27]
[@20,64:64=';',<';'>,3:28]
[@21,66:66='}',<'}'>,4:0]
[@22,68:67='<EOF>',<EOF>,5:0]

用 Antlr 生成语法分析器

PlayScript.g4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
grammar PlayScript;
import CommonLexer;   //导入词法定义

/*下面的内容加到所生成的Java源文件的头部，如包名称，import语句等。*/
@header {
package antlrtest;
}

expression
    :   assignmentExpression
    |   expression ',' assignmentExpression
    ;

assignmentExpression
    :   additiveExpression
    |   Identifier assignmentOperator additiveExpression
    ;

assignmentOperator
    :   '='
    |   '*='
    |  '/='
    |   '%='
    |   '+='
    |   '-='
    ;

additiveExpression
    :   multiplicativeExpression
    |   additiveExpression '+' multiplicativeExpression
    |   additiveExpression '-' multiplicativeExpression
    ;

multiplicativeExpression
    :   primaryExpression
    |   multiplicativeExpression '*' primaryExpression
    |   multiplicativeExpression '/' primaryExpression
    |   multiplicativeExpression '%' primaryExpression
    ;
生成语法分析器
1
2
antlr PlayScript.g4
javac antlrtest/*.java
测试
1
grun antlrtest.PlayScript expression -gui

Console

1
2
age + 10 * 2  + 10
^D

懂得基础原理，会让你站得更高

用Antlr重构脚本语言

  • 完善表达式（Expression）的语法

  • 完善各类语句（Statement）的语法

  • 语句

    • 条件语句
      • if 语句
      • switch 语句
    • 循环语句
      • for 循环语句
      • while 循环语句
    • return 语句

  • 表达式语句

    • 表达式后面加一个分号

用 Vistor 模式升级脚本解释器

1
antlr -visitor PlayScript.g4

作用域和生存期：实现块作用域和函数

作用域（Scope）: 计算机语言中变量、函数、类等起作用的范围
生存期（Extent）: 变量可以访问的时间段，也就是从分配内存给它，到收回它的内存之间的时间

  1. 实现作用域和栈
  2. 实现块作用域
  3. 实现函数功能: 参数
    • 建立一个栈桢
    • 计算所有参数的值，并放入栈桢
    • 执行函数声明中的函数体。

面向对象：实现数据和方法的封装

语法规则

  • 类声明以 class 关键字开头，有一个标识符是类型名称，后面跟着类的主体。
  • 类的主体里要声明类的成员。在简化的情况下，可以只关注类的属性和方法两种成员。
  • 类的方法也叫做 function，而不是 method，是想把对象方法和函数做一些统一的设计。
  • 函数声明现在的角色是类的方法。类的成员变量的声明和普通变量声明在语法上没什么区别。

如何在内存里管理对象的数据

把对象的数据像其他数据一样，保存在栈

访问对象的属性和方法

点操作符来

闭包： 理解了原理，它就不反直觉了

对于初学者来讲是一个挑战。其实，闭包就是把函数在静态作用域中所访问的变量的生存期拉长，形成一份可以由这个函数单独访问的数据。正因为这些数据只能被闭包函数访问，所以也就具备了对信息进行封装、隐藏内部细节的特性。

语义分析

如何建立一个完善的类型系统？

  • 静态类型语言: 全部或者几乎全部的类型检查是在编译期进行的
  • 动态类型语言: 类型的检查是在运行期进行的
  • 强类型语言: 变量的类型一旦声明就不能改变
  • 弱类型语言: 变量类型在运行期时可以改变

如何做类型检查、类型推导和类型转换

  • 类型推导（Type Inference）
  • 类型检查（Type Checking）
    • 赋值语句（检查赋值操作左边和右边的类型是否匹配）
    • 变量声明语句（因为变量声明语句中也会有初始化部分，所以也需要类型匹配）
    • 函数传参（调用函数的时候，传入的参数要符合形参的要求）
    • 函数返回值（从函数中返回一个值的时候，要符合函数返回值的规定）。
  • 类型转换（Type Conversion）

如何做上下文相关情况的处理？

语义分析的本质，就是针对上下文相关的情况做处理。

语义分析场景：引用的消解

语义分析场景：左值和右值

  • 左值（L-value）：最早是在 C 语言中提出的，通常出现在表达式的左边，如赋值语句的左边。左值取的是变量的地址（或者说变量的引用），获得地址以后，我们就可以把新值写进去了。
  • 右值（R-value）：通常所说的值，不是地址。

语义分析过程

  1. 类型和作用域解析（TypeAndScopeScanner.java）
  2. 类型的消解（TypeResolver.java
  3. 引用的消解和 S 属性的类型的推导（RefResolver.java）
  4. 做类型检查（TypeChecker.java）
  5. 做一些语义合法性的检查（SematicValidator.java）

继承和多态：面向对象运行期的动态特性

从类型体系的角度理解继承和多态

  • 继承: 一个类的子类，自动具备了父类的属性和方法，除非被父类声明为私有的。
  • 多态: 同一个类的不同子类，在调用同一个方法时会执行不同的动作。

子类型: is-a 的操作

  • 名义子类型（Nominal Subtyping）
    • 像 Java 和 C++ 语言，需要显式声明继承了什么类，或者实现了什么接口
  • 结构化子类型（Structural Subtyping），又叫鸭子类型（Duck Type）
    • 一个类不需要显式地说自己是什么类型，只要它实现了某个类型的所有方法，那就属于这个类型

如何对继承和多态的特性做语义分析

  1. 识别出新的类型
  2. 设置正确的作用域
  3. 变量和函数做类型的引用消解

小结

  1. 从类型的角度，面向对象的继承和多态是一种叫做子类型的现象，子类型能够放宽对类型的检查，从而支持多态。
  2. 在编译期，无法准确地完成对象方法和属性的消解，因为无法确切知道对象的子类型。在运行期，我们能够获得对象的确切的子类型信息，从而绑定正确的方法和属性，实现继承和多态。
  3. 另一个需要注意的运行期的特征，是对象的逐级初始化过程。

参考：编译原理之美