如何编写属于自己的C语言编译器

luochicun 技术 2017年12月14日发布

导语:本文为编写C语言编译器系列文章的第一篇,为此我先说明一下我要如此做的一些理由: 1.通过编写过程,你会对抽象语法树(AST)以及程序如何表示和操作其他程序有清晰地了解,并可以熟练地使用linters、静态分析器与各种各样的元编程。 2.

timg.jpg

本文为编写C语言编译器系列文章的第一篇,为此我先说明一下我要如此做的一些理由:

1.通过编写过程,你会对抽象语法树(AST)以及程序如何表示和操作其他程序有清晰地了解,并可以熟练地使用linters、静态分析器与各种各样的元编程。

2.你将对汇编,调用约定,以及所有相关的技术细节有个系统了解。

3.由于这是很困难的项目,所以整个过程我都在探索,有不对的地方请大家多指正。

在过去的几个星期里,我一直在借鉴Abdulaziz Ghuloum的“编译器构建的增量方法”,在自己的C语言编译器nqcc进行探索。Ghuloum的方法的大致是这样的:

第一,本文介绍的只是基本的X86汇编语言的一个子集,其中涉及汇编语言的最核心部分,包括寄存器结构,数据表示,基本的操作指令(包括数据传送指令、逻辑计算指令、算数运算指令),以及函数的调用规则。

第二,添加新的语言特性,整个添加过程可以一步一步地慢慢进行。一开始,只会返回常数,而随着步骤的增加,就要处理加减法了。

第三,虽然每一步的进展都很慢,但这保证了你对每一步进行充分的管理,在每一步的末尾,都有一个编译器。

我将在本文中,介绍算术运算,条件语句,局部变量,函数调用等概念。除此以外,我还编写了一些测试程序,以方便验证编译器的每个阶段是否在正常工作。

准备阶段

在编写C语言编译器之前,你还需要完成两件事:

1.决定使用哪种编译器的语言;

2.如何处理解析和词法分析。

对于编写语言,虽然我没有什么硬性规定,你可以用你喜欢的任何语言来编写编译器,但我的建议是使用具有和类型(sum types)和模式匹配的语言,比如OCaml,Haskell或者Rust。因为根据我的经验,这些语言在构建和遍历一个AST时会更加容易。其实最初,我也用的是Python,但是到最后,我还是选择了OCaml。

另外,你还需要决定是编写自己的解析和词法分析器,还是使用自动解析器和扫描生成器(例如flex和bison)。我会在本文中,向你展示如何手动去编写紫的词法分析器(或扫描器)以及递归下降语法分析器。虽然使用 解析生成器可能更容易编写,但我还没有尝试过该方法。你还可以使用扫描生成器来实现词法分析,但前提是要手动编写自己的解析器。

整数分析

一开始,我会编译一个可以返回单个整数的程序。另外,我还将为编译器设置三个基本的路径(pass)。这些被定义的体系结构将为以后添加更多的语言功能提供便利。

下面就是一个经过编译的程序,我将其称为return_2.c。

int main() {
    return 2;}

我只能用一个单一的函数来处理程序main,它由一个单一的return语句组成。唯一不同的是正在返回的整数值,不过我不会处理十六进制或八进制的整数。为了验证你的编译器运行是否正常,你需要编译一个程序,运行它,然后检查它的返回码。

$ ./YOUR_COMPILER return_2.c # compile the source file shown above
$ ./gcc -m32 return_2.s -o return_2 # assemble it into an executable
$ ./return_2 # run the executable you just compiled
$ echo $? # check the return code; it should be 2
2

此时,编译器将生成x86汇编。我不会将汇编程序转换成可执行文件,它们是独立的程序。为了了解这个汇编程序,我用gcc对它进行了编译。

$ gcc -S -O3 -fno-asynchronous-unwind-tables return_2.c
$ cat return_2.s
    .section __TEXT,__text_startup,regular,pure_instructions
    .align 4
    .globl _main
_main:
    movl    $2, %eax
    ret
    .subsections_via_symbols

现在,你就可以看到汇编程序的全貌了。不过,我忽略了.section,.align和.subsections_via_symbols指令,如果你删除它们,你仍然可以组装并运行

return_2.s。 .globl _main表示_main符号应该对链接器可见,否则你无法找到程序的入口点。另外,其中还附有汇编指令:
_main:                  ; label for start of "main" function
    movl    $2, %eax    ; move constant "2" into the EAX register
    ret                 ; return from function

当函数返回时,EAX寄存器将包含它的返回值,而main函数的返回值将是程序的出口代码。

这个汇编程序代码中唯一可以改变的是返回值。因此,一个非常简单的方法就是使用正则表达式从源代码中提取返回值,然后将其插入汇编程序中,你可以利用以下这20行的Python脚本来实现。

import sys, os, re
#expected form of a C program, without line breaks
source_re = r"int mains*(s*)s*{s*returns+(?P<ret>[0-9]+)s*;s*}" 
assembly_format = """    
    .globl _main
_main:
    movl    ${}, %eax
    ret
"""
source_file = sys.argv[1]
assembly_file = os.path.splitext(source_file)[0] + ".s"
with open(source_file, 'r') as infile, open(assembly_file, 'w') as outfile:
    source = infile.read().strip()
    match = re.match(source_re, source)
    # extract the named "ret" group, containing the return value
    retval = match.group('ret') 
    outfile.write(assembly_format.format(retval))

由于用正则表达式来解析整个程序并不是一个长期可行的方法,所以我将编译器分成三个阶段:词法分析,解析和代码生成,这是一个非常标准的编译器结构。

词法分析

词法分析器(也称为扫描器或标记器)是编译器将字符串(源代码)分解为标记列表(list of token)的阶段。标记记号是词法分析器可以理解的最小单位,许多标记就是用空格分隔的单个单词。变量名,关键字和常量以及大括号等标点符号都是标记记号。以下是return_2.c中所有标记的列表:

int关键字
标识符“main”
左括号
右括号
前大括号
返回关键字
常量“2”
分号
后大括号

请注意,某些标记只有一个值(例如,常量标记的值为“2”),另外请注意,没有空格标记。在某些语言中,如Python,空格是很重要的,而且你需要对它进行标记。

以下是你的词法分析器需要识别的所有标记,以及定义每个标记的正则表达式:

前大括号{
后大括号}
左括号(
右括号)
分号
Int关键字int
返回关键字return
标识符[a-zA-Z]w*
整数值[0-9]+

如果你愿意,你可以只使用一个“关键字”标记,而不是为每个关键字都进行不同标记。

可以进行的编写

此时,我就可以编写一个接受文件的lex函数并返回一个标记列表。它应该适用于测试套件中的所有起始示例,包括无效的示例。 所谓无效的示例就是在解析器中引发错误,而不是词法分析器。为了简单起见,我只使用十进制整数。如果你喜欢,你可以扩展你的词法分析器来处理八进制和十六进制整数。不过要注意,没有负整数。

解析过程

现在将我的令牌列表转换为AST, AST是表示程序结构的一种方式。在大多数编程语言中,像条件语句和函数语句这样的语言结构是由简单的结构组成的,比如变量和常量。 而AST可以捕捉到这种关系,AST的根就是整个程序,每个节点都有代表其组成部分的子节点。比如下面这个示例:

if (a < b) {
    c = 2;
    return c;
} else {
    c = 3;
}

由于这个代码片段是一个if语句,所以我将AST的根标记为“if语句”。它将有三个节点:

条件部分(a <b);
if 部分(c = 2; return c;);
其它部分(c = 3;)。

其中每个部分都可以进一步分解。例如,条件部分就可以再拆分成两个:

第一个操作数(变量a);
第二个操作数(变量b)。

赋值语句(如c = 2;)也能再分两部分:被更新的变量(c)和分配给它的表达式(2)。

除此之外,if 部分可以有任意数量的子节点,因为每个语句都是一个子节点。在这种情况下,因为有两个语句,也能再分两部分c = 2; 和return c;。

下面是这个代码片段的完整AST:

360截图161908256273113.jpg

下面是构建这个AST的伪代码:

//create if condition
cond = BinaryOp(op='>', operand_1=Var(a), operand_2=Var(b))
//create if body
assign = Assignment(var=Var(c), rhs=Const(2))
return = Return(val=Var(c))
if_body = [assign, return]
//create else body
assign_else = Assignment(var=Var(c), rhs=Const(3))
else_body = [assign_else]
//construct if statement
if = If(condition=cond, body=if_body, else=else_body)

但现在,我不需要担心条件,变量赋值或二元运算符。现在,我需要支持的唯一AST节点是程序,函数语句,语句和表达式。以下是我将如何定义它们的方法:

program = Program(function_declaration)
function_declaration = Function(string, statement) //string is the function name
statement = Return(exp)
exp = Constant(int)

现在,一个程序由一个单一的函数main组成,稍后我会将一个程序定义为函数列表。一开始,每个函数只有一个名称和一个主体。后来,又多了一个参数列表。对于投入运行的C编译器来说,我也需要存储函数的返回类型,不过现在我只有整数类型。函数体是一个单独的语句,稍后我会将它变成语句列表(list of statements)。现在,它只有一种类型的语句——返回语句。稍后我将添加其他类型的语句,如条件和变量语句。返回语句有一个子节点,一个表达式即返回的值。现在表达式只能是一个整数常量。稍后我将让表达式包含算术运算,这将允许我解析像return 2+2这样的语句。

当我添加新的语言结构时,我将更新我的AST节点的定义。例如,当我添加一个新类型的语句——变量赋值,我会在statement定义中添加一个新的范式(form ):

statement = Return(exp) | Assign(variable, exp)

以下是return_2.c的AST图:

360截图16200716116129103.jpg

最后,我需要一个正式的语法,它负责定义如何将一系列的标记组合起来形成完整的语言结构。我将在巴科斯范式中定义它:

<program> ::= <function>
<function> ::= "int" <id> "(" ")" "{" <statement> "}"
<statement> ::= "return" <exp> ";"
<exp> ::= <int>

上面的每一行都表示一个运行规则,定义了如何从其他语言结构和标记构建语言结构。运行规则左侧出现的每个符号(例如,<program>,<function>,<statement>)都是非终结符号。而单个标记(例如,关键字,标点符等)则是终端符号。需要注意的是,虽然这个语法让我可以构建一个有效的C程序,但它并没有告诉我如何将这个程序转换成一个AST,例如,在AST中没有对应于常量节点的运行规则。当重写我的语法来为常量创建一个运行规则后,

我发现语法就变得非常简单,起初,每个非终端符号只需一个运行规则。例如,如果我添加了对变量语句的支持,则可以用以下规则来派生语句:

<statement> ::= "return" <int> ";" | "int" <id> "=" <int> ";"

为了将令牌列表转换成AST,我将使用一种称为递归下降解析的技术。我将定义一个函数来解析语法中的每个非终结符号,并返回相应的AST节点。解析符号S的函数应该从列表的开始处删除标记,直到形成S. If的有效派生。如果在解析完成之前,就碰到了一个不在S的运行规则中的标记,将会派生失败。如果S的规则包含其它非终结符,则应该调用其他函数来解析它们。

以下是解析语句的伪代码:

def parse_statement(tokens):
    tok = tokens.next()
    if tok.type != "RETURN_KEYWORD":
        fail()
    tok = tokens.next()
    if tok.type != "INT"
        fail()
    exp = parse_exp(tokens) //parse_exp will pop off more tokens
    statement = Return(exp)
    tok = tokens.next()
    if tok.type != "SEMICOLON":
        fail()
    return statement

稍后,运行规则将是递归的(例如,一个算术表达式可以包含其他表达式),这意味着解析函数也将是递归的,因此此方法就顺理地被称为递归下降解析。

编写一个解析函数,从而接受一个标记列表并返回一个基于程序节点的AST。该函数应该为所有有效的示例构建正确的AST,并在所有无效的示例中引发错误。

有许多表示AST的代码,具体取决于编译器所使用的语言。例如,可以将AST节点定义为OCaml数据类型:

type exp = Const(int)
type statement = Return(exp)
type fun_decl = Fun(string, statement)
type prog = Prog(fun_decl)

代码的生成

现在我已经构建了一个AST,并准备生成一些汇编程序,我只需要发送四行汇编即可。为了发送,我将遍历AST,这意味着我将按以下顺序访问:

1.函数名称(不是一个真正的节点,而是函数定义中的第一项);

2.返回值;

3.返回语句。

这个遍历可以确保在使用汇编程序之前预定义一个值,例如,我在返回语句中引用之前生成的返回值。

以下就是我需要的汇编程序:

1.生成一个函数(例如函数“foo”):

 .globl _foo
_foo:
 <FUNCTION BODY GOES HERE>

2.生成返回语句(例如,return 3;):

 movl    $3, %eax
 ret

可以进行的编写

编写一个接受AST并生成汇编程序的生成函数。它可以将程序集作为字符串返回,也可以直接将其写入文件。它应该为所有有效示例生成正确的汇编程序。

输出

此时,你可能需要一个实用程序函数来打印出AST,以帮助进行调试。你可以现在就编写或者等到你需要的时候再写。下面是使用nqcc输出的return_2.c。

FUN INT main:
    params: ()
    body:
        RETURN Int<2>

这个示例包含了AST不需要的一些信息,比如返回类型和函数参数列表。

可以进行的编写

用一种可读的方式写一个预打印的函数,它以AST的形式打印出来。

编写一个接受C源文件并输出可执行文件的程序,该程序要实现的功能如下:

1.阅读文件;

2.词法分析;

3.解析;

4.生成汇编程序;

5.将汇编程序写入文件;

6.调用GCC命令将汇编程序转换为可执行文件:

gcc -m32 assembly.s -o out

在此命令中,“assembly.s”是汇编程序文件的名称,“out”是要生成的可执行文件的名称。 -m32选项会调用GCC命令构建一个32位的二进制文件。如果需要,可以省略该选项并构建64位二进制文件,但稍后需要对代码生成步骤进行一些更改(例如,使用64位寄存器)。

7.删除汇编程序文件。

测试

你可以通过测试你的编译器查看是否正确地使用了测试脚本,正常情况下,它会使用你的编译器编译一组测试程序,然后执行它们,并确保它们返回正确的值。

调用过程如下:

./test_compiler.sh /path/to/your/compiler

要用脚本测试,你的编译器就需要遵循下面这3个标准:

1.可以从命令行调用一个C源文件作为参数,例如:./YOUR_COMPILER /path/to/program.c。

2.当通过program.c时,它会在同一个目录下生成可执行程序。

3.如果解析失败,它不会生成程序集或可执行文件,因为这是测试脚本检查无效测试程序的方法。

要注意的是,虽然该脚本不负责检查编译器是否输出了合理的错误信息,但可以使用无效的测试程序来手动测试。

本文翻译自:https://norasandler.com/2017/11/29/Write-a-Compiler.html,如若转载,请注明原文地址: http://www.4hou.com/technology/9124.html
点赞 5
  • 分享至
取消

感谢您的支持,我会继续努力的!

扫码支持

打开微信扫一扫后点击右上角即可分享哟

发表评论