Bright LGM's Blog

Code speaks.

0%

程序员需要知道的编译器知识

发表于 更新于 分类于 ， 阅读次数：
本文字数： 5.5k 阅读时长 ≈ 9 分钟

我们每天都在用某种编程语言写代码，但是我们真的了解它们是如何工作的吗？代码是如何转换为计算机可以识别的机器码的呢？

了解编程语言的工作原理，不仅可以让我们深入理解某一种编程语言，某些时候还可以帮助以一种更优雅的方式实现想要的功能。比如我们平时谈论很多的DSL（Domain Specific Language），在定义了DSL之后，我们如何做更进一步的支持呢？事实上我们还可以实现DSL的自动错误检查，还可以将其转化为某种可以执行的程序等等。还比如我们经常遇到的模式识别问题，状态机相关问题等等。对于这些问题，编程语言的实现原理可以给我们很多启示。

那么编程语言是如何工作的呢？详细的理论知识得回到我们大学时代的编译原理课程。下面我将主要从实例出发，辅以必备的几个概念介绍来帮助理解编程语言的工作原理，并介绍一些实用的工具帮助我们日常的开发。

一个例子

首先我们来看一个最简单的四则运算的例子。在这里我们想定义一种支持简单的 正整数四则运算 的语言。

首先是语言中的概念和符号：

  • 正整数： [0-9]+ (正则表达式定义)
  • 运算符号： + - * /

然后我们定义*和/的优先级一样，+和-的优先级一样，* /高于+ -，与我们一般的理解一致。

这个描述我们可以用一种更规范的形式来表示，如下：

1
2
3
4
5
6
7
8
9
tokens:
    NUMBER  : r'[0-9]'

expressions:
    expr    : NUMBER
            | expr + expr
            | expr - expr
            | expr * expr
            | expr / expr

expressions中的语句采用了递归的形式进行定义（|表示或者），这样可以满足任意长度的任意组合了。

像这样一种更规范的格式就是我们所谓的上下文无关文法了，其中著名的BNF范式就是其中一种。

几个概念

什么是上下文无关文法？

要理解这个概念，我们先得知道形式语言。形式语言是用 精确的 数学或机器可处理的 公式 定义的语言。这个概念是专门为计算机定义的，但仅仅从这句话来看，其实还是模糊的，什么样的公式才是数学和机器可处理的呢？

这就牵涉到形式文法的概念，文法用于构成语言，形式文法就是用于构成形式语言的。文法可以类比我们自然语言中的主谓宾、主系表这类语言结构规则。那么形式文法呢？形式文法就是数学和计算机可以处理的一种比较严谨的语言结构规则。事实上形式文法可以表示为一个四元组（非终结符N, 终结符Σ, 产生式规则P, 起始符S），这个四元组里面不仅仅有规则，还包括了规则的作用范围，符号等。这个四元组就是数学上的定义。有了这个定义，我们就可以用数学逻辑推导相关文法理论了。到这里大家应该有一点概念了，本文并不想过多涉及理论，详细的数学分析及示例可以参考wiki。

上下文无关文法，顾名思义，就是上下文无关的一种形式文法，这种文法虽然简单，但是非常重要，因为所有的编程语言都是基于它来设计的。BNF（Backus Normal Form），也就是巴克斯-诺尔范式（由他们最先引入），就是我们经常用来表达上下文无关文法的一种符号集。前面关于 正整数四则运算 语言的规范定义就是用BNF格式来定义的。

我们说某种BNF严格的定义了相应的语言，也可以说某种语言由其对应的BNF来严格定义。比如C语言由C语言的BNF来定义，JAVA语言由JAVA语言的BNF来定义。

理解语言

有了语言定义，我们可以做什么呢？一个直接的任务应该就是理解语言并将其转化为计算机可以执行的代码，以便在机器上运行。完成这个任务的东西我们叫编译器。

有时候其实我们并不一定要让计算机计算出一个结果，而是只要计算机能理解语言，然后在根据这些理解来做一些事情。如何才算理解了语言？对于某一行代码，事实上可以用一棵树结构来描述它，树结构一个节点代表语言定义的一个简单推导。比如1 + 2 + 3可以表示成：

1
2
3
4
5
expr   |-- NUMBER(3)
       +
       |-- expr   |-- NUMBER(1)
                  +
                  |-- NUMBER(2)

这里的树结构被称为语法树，有了这颗语法树，我们就可以说理解语言了。事实上从这颗语法树出发我们可以完成很多和这门语言相关的任务，比如我们可以做语法分析查错，可以做代码优化重构提示，可以做代码编写提示，当然还可以将其翻译为机器码等等。IDE的很多功能就是依赖于语法树来实现的。

理解四则运算语言

理解语言一般我们可以分为两个步骤，第一是理解词，第二是按照语法规则将词组织成语法树。比如四则运算的例子，我们在构造语法树的时候，输入一个字符串，然后需要依次提取字符串中的词（这里的词是指正整数和+-*/符号），最后根据词和规则来构造语法树。

在这个简单的例子中，识别词的过程我们可以用简单的正则匹配来实现。但是构造语法树的时候，我们需要构造一个有限状态机（finite-state machine）来实现，这看起来就好像并不是一件简单的事了。

事实上，关于计算机语言的分析早在上世纪50年代就有了比较系统的研究了，相关工具当然也是非常成熟和丰富。最早的工具莫过于lex(lexical analyser)和yacc(yet another compiler-compiler)了。lex就是用来做词法分析的，yacc可以用lex的词法分析结果来生成语法树。这两个工具可以帮我们生成理解语言的源代码。但是这两个工具是unix系统下的工具，而我们现在用的一般都是GNU的系统。在GNU的系统下的两个类似实现是flex和bison，ubuntu系统下我们可以用sudo apt-get install flex bison来安装。

由于这两个工具是生成c语言的语法分析器代码。为了简单的在python下做一些实验，我们使用ply这个工具，它的全称是python lex-yacc，也就是python版本的lex和yacc。参考ply的文档，要实现上述四则运算，我们可以编写代码如下：

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
tokens = ('NAME', 'NUMBER', )
literals = '+-*/'

t_NAME = r'[a-zA-Z_][a-zA-Z0-9_]*'

def t_NUMBER(t):
    r'\d+'
    t.value = int(t.value)
    return t

precedence = (('left', '+', '-'), ('left', '*', '/'), )

def p_statement_expr(t):
    """statement : expression"""
    print(t[1])

def p_expression_binop(p):
    """expression : expression '+' expression
                  | expression '-' expression
                  | expression '*' expression
                  | expression '/' expression
    """
    if p[2] == '+': p[0] = p[1] + p[3]
    elif p[2] == '-': p[0] = p[1] - p[3]
    elif p[2] == '*': p[0] = p[1] * p[3]
    elif p[2] == '/': p[0] = p[1] / p[3]

def p_expression_number(p):
    """expression : NUMBER"""
    p[0] = p[1]

def test_lex_yacc():
    import ply.lex as lex
    import ply.yacc as yacc
    lexer = lex.lex()
    parser = yacc.yacc()

    while True:
        try:
            s = input('calc > ')
            lexer.input(s)
            while True:
                tok = lexer.token()
                if not tok:
                    break
                print(tok)
            parser.parse(s, lexer=lexer)
        except EOFError:
            break


if __name__ == '__main__':
    test_lex_yacc()

运行这个程序，输入我们的表达式，将能得到正确的结果，如下：

1
2
3
4
5
6
7
calc > 1+2*3
LexToken(NUMBER,1,1,0)
LexToken(+,'+',1,1)
LexToken(NUMBER,2,1,2)
LexToken(*,'*',1,3)
LexToken(NUMBER,3,1,4)
7

一个更复杂的例子

正整数四则运算的例子看起来过于简单，实际上我们可以用ply实现非常复杂的语法分析器。比如我们可以实现一个用于识别python的函数定义的语法分析器。有了这个分析器，我们就可以从识别结果中获取函数名，参数名，类型信息等，从而完成一些类似代码质量分析，自动代码格式化等工作。

初步看这个问题，似乎正则表达式可以解决一定的问题，但是仅仅有正则表达式是不够的，因为python的很多语法规则过于复杂，难以通过正则表达式来表达。

为识别python的函数定义，我们可以编写测试如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def test_yacc_for_python_func_def():
    test_code_lines = [
        'def abc(a,):',
        'def abc(a,):',
        'def abc(a,#xxx()[]\n):',
        'def abc(a: List[int],):',
        'def abc() -> int:',
        'def abc(a, b) -> List[int]:',
        'def abc(a, b: Union[int, List[float]],) -> Union[int, float]:',
        'def abc(a,) -> Union[int, List[float]]:',
        'def abc(a,) -> Union[int, List[float], float]:',
        'def abc(a,) #xxx()[]\n -> Union[int, List[float], float]:'
    ]
    for line in test_code_lines:
        yacc.parse(line, lexer=lexer)

有兴趣的小伙伴可以自己尝试实现，或者参考这里我实现的一个版本。

实用的工具

上面的工具已经可以帮我们做很多了，看起来甚至自己定义一门编程语言也是可能的。然而这件事的难度在于，对于一门好用的编程语言，语法定义要足够丰富好用，性能要足够高，相关生态要能做得起来。这就不是单纯的技术活了。

在日常的开发活动中，我们可能接触最多的还是对于当前流行的编程语言的处理。比如，某一天我们可能想要实现一个工具将一个java实现的库，转换为python实现，这里就有一个不错的尝试。又比如，某一天我们想要改进我们的IDE，尝试做更多特殊的自动代码格式化支持。还比如，某一天我们想要自动化生成一些代码，就像IDE里面的重构一样。这个时候有没有什么工具可以帮助我们呢？

当然是有的，这里想要提一下 ANTLR。代码库在这里。这是一个java实现的类似工具，支持的语言非常广泛，我们可以在这里找到一个列表。可以看到这里支持了go python3 java9等等非常多的语言，基本上我们日常用到的语言都有覆盖了。而且这个工具可以生成各种目标语言的语法分析器。比如我们想得到一个python语言实现的go语言分析器，这个工具可以很容易实现。类似的工具还有很多，我们可以参考wiki上面的一个比较。

如果我们只想用一种编程语言去分析该语言自身，这个时候更简单的方式是直接用语言本身提供的语法分析器。一般提供了JIT(just in time的缩写, 也就是即时编译编译器)功能的语言，都有相应的接口去做语法分析。比如这里有python的ast库，调用ast.parse，输入一段源代码，就得到一颗语法树。javascript有一个第三方库esprima(这里)也可以做类似的事情。

到这里我们是不是对日常使用的编程语言有了更深入的了解呢？编译技术是一门强大的技术，灵活运用将能实现不少平时看起来很难的功能。希望当我们遇到这些问题的时候能有一些新的思路。

参考：

相关文章

欢迎关注我的其它发布渠道