behindt

编译器前端介绍

Chenyuan Zhao's photo
Chenyuan Zhao
·

2 min read

前言

编译指的是将源程序翻译为等价的目标代码的过程。编译往往有五个阶段，即词法分析，语法分析，语义分析，中间代码优化与目标代码生成。编译器前端通常指生成中间代码之前的步骤。
高级语言的源程序在计算机的角度来看仅仅是一串字符串，并不能直接在计算机上执行。需要靠编译器去分析这些字符串，理解程序员的意图，并将其转化为机器能够执行的语言。

词法分析的任务是识别源码中的词素（Token），将源码分隔为不能再拆分的基本组成单元。这些单元往往是：

  1. 语言定义的关键字或保留字，e.g. 数据类型int, 流程控制while等
  2. 标志符，如变量名foo, bar, 函数名main等
  3. 常数，包含整形与浮点，以及可能有的前缀、后缀，如(0xdeadbeef, 3.14159L)
  4. 运算符，如+-/% 比如 x = (2.0+0.8)C1 就可被拆成
    |x |= | (| 2.0| +|0.8|)|*| C1|

如何拆分完全是由该每个词素中允许出现的字符决定的，而不是靠格式（如空格等）。比如，数字2.0与后续的+运算符之间没有空格，却一定会被拆开；而2.0虽然有三个字符，却会被看作是一个连续的整体。

语法分析是根据语言的文法，分析并识别出各种语法成分，如表达式、语句、过程、函数等。一门编程语言的SPEC中定义了允许的语法，这些语法是程序员在使用这门语言时能表达算法意图的能力。程序员必须按规定动作书写程序，这样写出来的程序才能被编译器“看懂”并进一步转化成目标代码。就好比两个航海员在公海上使用摩斯电码交谈一般，纵使有万千话语，也得按部就班地使用“点”与“划”交流。为了正确传达自己的意思，可能两人需要对原始语句进行修改使之更容易被对方的译码人员听懂；而译码人员也要不断精进自己的译码技术，破译越来越复杂的电码组合。
语法举例：

  1. <赋值语句>:= <变量><赋值操作符><表达式>
  2. <变量>:= <简单标识符> ｜ <嵌套标识符>
  3. <赋值操作符>:= '='
  4. <表达式>:= ...

语义分析是将各种语法成分转化成中间代码，便于优化处理和编译程序的移植。中间代码有多种形式，不拘一格，有些抽象程序高，便于作程序优化，有些贴近底层语言，方便生成目标代码。有的编译器会同时使用多种中间代码来做不同层次的优化。
常见的中间代码形式有：四元式（三地址指令）、三元式、逆波兰表示等。 比如在赋值语句中，语义分析需要分析表达式两端的数据类型是否一致。
语句 x = (2.0+0.8)*C1 经过转化可以生成类似这样的中间代码（四元式形式）:

2.0+0.8 -> T1
T1 * C1 -> T2
T2 -> x1

除此之外，在语义分析过程中还需要明确同名变量的作用域，因此会维护一个变量表。

手动编写前端——递归下降法

用任何一种编程语言都可以手写一个编译器的词法分析器（lexer）和语法分析器(parser)，和将语法树转化为中间代码表示的遍历工具(visitor)。

手写的词法、语法分析器往往采用LL语法，即从当前输入的头部也就是最左侧（当然，假设正常的书写顺序是从左到右，可能只有阿拉伯人不同意这个命名）读入一个字符，并按此字符的类型与之前缓存的字符一起判定，当前读到的字符是否属于当前词素。

如从开始状态开始，如果读到一个字母，就进入标识符分析程序；如果读到一个数字，就进入数字常量分析程序。

image.png

看到这个图可能会让人联想到自动状态机，事实上也的确就是。而基于LL文法的词法分析器在日常编程中有一个更广泛的用途：正则表达式。所以实现一个词法分析器也可以使用现成的正则表达式库来完成。

语法分析也与词法分析类似，但这回分析的基本单位变成了词素而不是单个字符。举一个例子： 文法： statement:= var=expression | IF expression THEN statement | IF expression THEN statement ELSE statement var:= ID | ID [ expression ] expression:= item | expression + item item:= factor | item*factor factor:= var | ( expression ) 那么statement的分析程序就可以如此实现：

void statement( )
{
  if (sym == IFTK) {        // 如果读到一个if token
    getsym( );                  // 读下一个符号
      expr( );                      // 剩下的一定是表达式部分，进入表达式分析程序
    if (sym != THENTK) error(); // 读完表达式后一定是一个then token
      else {                        // ...下略
        getsym ();
                statement ( );
            if (sym == ELSETK)
                getsym ();
                statment () ;

        }

    else {
      var ();
      if (sym ! = ASSIGN)
            error ( );
      else {
        getsym ();
                expr ();
       }
    }
}

从中可以看到，LL文法实现的语法分析器总是在作“预测”，它通过读入的当前词素来猜测现在处于哪一条语法规则中，并跳转到对应的语法分析规则中。而这个过程是从最上层的语法成分逐渐分解到下层细碎的语法成分，故名为“下降”；而规则的跳转可能会调用自己，比如expression的一个操作数又是一个expression,故名为“递归”。

自动化工具——Flex与Bison

使用手写的方法固然简单，但有些太过繁琐。由其是，现代编译器根本不关注前端parser的部分，只要能生成中间代码就好。真正的编译技术是从中间代码的优化开始的，以及指令选择、寄存器分配等。
如果要深入学习编译器技术，前端部分的学习要尽量快。这时自动化生成工具就能帮上忙了！这些工具是词法、语法分析器的“生成器”。它们的输入通常是一个文本形式的文件，而文件内容就是语言SPEC所提供的语法规则。只要一比一地将语法规则按生成器能读取的格式写下来，生成器就能自动帮忙生成parser。 这种工具有flex&bison, yacc, antlr等。其中flex与bison的组合是最经典的。
Flex是词法分析器的生成工具，而bison是语法分析器的生成工具。

一个flex文档的样例： scanner.flex

%{
#include "token.h"
%}
DIGIT [0-9]
LETTER [a-zA-Z]
%%
(" "|\t|\n) / * skip whitespace
* /
\+ { return TOKEN_ADD; }
while { return TOKEN_WHILE; }
{LETTER}+ { return TOKEN_IDENT; }
{DIGIT}+ { return TOKEN_NUMBER; }
. { return TOKEN_ERROR; }
%%
int yywrap() { return 1; }

它由四个部分组成，从上到下依次是头文件，token助记符，正则表达式规则，和附加代码。其中只有助记符和正则表达式规则真正用于词法分析，其它都是辅助。 比如头文件部分，通常就是一个token的enum表，同时被lexer和main文件include, 这样lexer每次读到一个token就可以告知parser当前token的类型。
附加代码部分则是会被无条件地（哪怕这部分代码中有语法错误！）添加到parser中。flex规定必须实现一个名为yywarp的函数，其作用是处理lexer异常，最小的实现就是直接返回1，不作其它任何处理。 token.h

typedef enum {
TOKEN_EOF=0,
TOKEN_WHILE,
TOKEN_ADD,
TOKEN_IDENT,
TOKEN_NUMBER,
TOKEN_ERROR
} token_t;

main.c

#include "token.h"
#include <stdio.h>

extern FILE +yyin;
extern int yylex();
extern char syytext;

int main() {
    yyin = fopen("program.c","r");
    LE (lyyin |
        printf ("could not open program.c!\n");
        return 1;

    while (1) {
        token_t t = yylex();
        if (   OKEN_EOF) break;
        printf ("token: %d text: %s\n",t,yytext);
    }
}

而bison文件的格式与flex如出一辙

%{
#include <stdio.h>
%}
%token TOKEN_INT
%token TOKEN_PLUS
%token TOKEN_MINUS
%token TOKEN_MUL
%token TOKEN_DIV
%token TOKEN_LPAREN
%token TOKEN_RPAREN
%token TOKEN_SEMI
%token TOKEN_ERROR
%%
program : expr TOKEN_SEMI;
expr : expr TOKEN_PLUS term
| expr TOKEN_MINUS term
| term
;
term : term TOKEN_MUL factor
| term TOKEN_DIV factor
| factor
;
factor: TOKEN_MINUS factor
| TOKEN_LPAREN expr TOKEN_RPAREN
| TOKEN_INT
;
%%
int yywrap() { return 0; }

强大的全自动化工具ANTLR