《自制编译器》读书笔记Part1

作者: kolibreath | 来源:发表于2020-08-29 19:44 被阅读0次

前言

最近花了一个月时间读完了一本书《自制编译器》。首先对这本书给一个非常中肯的评价，这本书写的内容很充实，很丰富，确实正如作者所说的掌握了基础的Java、C等知识就可以看懂，后面的硬件知识，汇编知识会逐渐给你铺开，丝丝入扣平易近人。但是美中不足的地方也有很多，比如这本书中存在着一些错误（也可能是我理解上的问题），我读了很多遍还是觉得有问题，比如“push 和 pop指令操作了ebp寄存器”，这明显和前面介绍的”push和pop指令操作esp寄存器”冲突了，还有一些印刷错误等等。不过，如果想真正的完成和实现一个编译器，这本书并没有像很多例子一样手把手的教你，只是给出了一个大概的纲要，就算看完了GitHub仓库里面的Java实现，最后也会难倒在如何将编译器编译出来这个步骤上（比如我QAQ）。这本书的第三部分汇编代码可以单独拿出来作为汇编语言的基础手册进行参考。

本文是读完了《自制编译器》书之后做的一个读后感以及编译过程中的重难点分析并且提出我自己的一些理解。Part1 主要聚焦于编译器制作的三个部分，分别是语法分析和语义分析以及中间代码生成部分，这三个部分也被合称作编译器的前端部分。

Reference

文章参考：
《自制编译器》1-21章
《深入理解计算机系统》第7章链接

编译器概要

自从学习编程语言以来，通过点击IDE上面的run按钮就能获得所想即所得的代码结果仿佛是一件再正常不过的操作。但是整个编译的过程却非常复杂，在大体上可以分成语法分析-语义分析-中间代码生成-代码生成这样的四个阶段，下面我根据这本书中对于C语言的一个子集Cflat，以及每一个阶段我在读书的过程中所思考的问题和这些问题的回答进行一个列举。

自制编译器自制了什么？

《自制编译器》通过Java语言和JavaCC工具构建了一个Cflat编译器以及Cflat语言，即一种实现了部分C语言的功能特性的编程语言，相对于原来的C语言，Cflat省略了一些特性：

省略的特性

但是就算是省略了这些特性，也能从学习这本书的过程中管中窥豹似的了解编程语言的编译内容。

提出的问题

在看这本书之前以及我对编译过程的一些了解，我给自己提出了一些问题：

输入的代码文件如何从正则表达式解析生成了抽象语法树？
像 include import 这样的语句是如何导入外部模块、包的变量和函数的，这些变量以及函数是如何进行管理的？
对于代码中的函数的作用域是如何划分的，局部变量和全局变量如何区分?
抽象语法树如何变成汇编代码？汇编代码又如何变成机器代码并且执行的？
在代码编译的过程中，编译器如何进行代码的优化？
指针、数组、函数类型在整个函数编译过程中有无特殊的影响和作用？
在中缀表达式中，我们通过栈可以处理表达式的优先级，在编译器编译代码过程中，是不是也需要转换为中缀表达式呢？

以上的几个问题都是在写代码的过程中会思考的问题，实际上在分析编译器的制作的过程中，特别是从汇编语言到机器语言这一步涉及到了更多平常不会考虑的问题，后面都会详细说明！

Section1 ：语法分析

语法分析的目标是生成一棵抽象语法树(AST)，这样的抽象语法树只记录了节点之间的关联，但是对于节点之前语句的正确性没有进行判断。本书通过JavaCC这样的技术生成了一个扫描分析器，即通过扫描的过程进行正则表达式的匹配，进行很多单词的划分；并且通过解析器生成了抽象语法树。

广义的语法分析是包括了词法分析和语法分析（狭义的语法分析，狭义和广义的语法分析可以通过上下文来判断）的，因为Cflat编译器使用了JavaCC来制作扫描解析器，所以我直接把这一块都放在词法分析来说明了。

词法分析

构建抽象语法树过程中好玩的例子

变量的声明

通过分析下面几个例子就可以对扫描解析器JavaCC从扫描源文件到生成抽象语法树有一个大体的认识：
example 1：

int a = 10;
char b = 10;
char c = 'a';
int  d;
static int e = 10;

对于变量的声明，定义在Parser.jj中的JavaCC代码是这样的:

List<DefinedVariable> defvars():
{
    List<DefinedVariable> defs = new ArrayList<DefinedVariable>();
    boolean priv;
    TypeNode type;
    String name;
    ExprNode init = null;
}
{
     //priv 是private的缩写，用于表示这个变量是否是一个static变量（C语言中的static用来区分模块的可见性）
    // type 表示类型，这里划一个重点，这里的类型和后面的类型消解有关 
    //name 是单纯的名称的识别，定义变量的标识符的规则和C语言中的是相同的
    // 后面的初始化表达式init可以省略 ，在普通情况下可能会更加复杂eg: int f = func(func1(c));
    priv=storage() type=type() name=name() ["=" init=expr()]
        {
            defs.add(new DefinedVariable(priv, type, name, init));
            init = null;
        }
    ( "," name=name() ["=" init=expr()]
        {
            defs.add(new DefinedVariable(priv, type, name, init));
            init = null;
        }
    )* ";"
        {
            return defs;
        }
}

按照上面的规则进行匹配，example1中的几个表达式可以被分解成：

分解过程

其中的storage() 就是扫描静态标识符的代码，关于静态标识符的问题在编译器中其实也比较麻烦，涉及到最后生成汇编代码的全局可见性的问题，还有一个是在机器栈上管理的问题。

所以JavaCC是一个非常好用的工具，通过JavaCC定义的一些语法规则，能够扫描出代码中的各种组成部分，并且这些部分会使用一种叫做JavaCC Action的代码帮助生成节点，从而构建整个抽象语法树。

其他的几个例子的分割和匹配过程是类似的，最后会生成一个这样的抽象语法树结构：通过缩进来表示语法树的层级：

int a = 10; 
----------------
    <<DefinedVariable>> (test.cb:1)
    name: "a"
    isPrivate: false
    typeNode: int
    initializer:
        <<IntegerLiteralNode>> (test.cb:1)
        typeNode: int
        value: 10
functions:

上面的例子中对于

char b = 10;

其实还涉及到一个类型转换的问题，在cflat编译器中是这样处理的：

TypeRef typeref_base():
{
    Token t, name;
}
{
      t=<VOID>          { return new VoidTypeRef(location(t)); }
    | t=<CHAR>          { return IntegerTypeRef.charRef(location(t)); }
//// .....
}

所以说至少在Cflat编译器中，char类型其实是被当成是 Integer类型的一种特殊情形处理的（我的理解是作为一种数值的字面量），其他的类型也是这样的，不过在涉及到内存相关的问题时，还是会按照固定的内存大小进行分配：

//the sizes of char short int long ptr
 public static TypeTable ilp32() { return newTable(1, 2, 4, 4, 4); }

example 2: 比较复杂import语句的例子

 import stdio;

int main(int argc, char **argv)
{
    printf("Hello, World!\n");
    return 0;
}

这个代码引入了外部的库中的一个函数printf,这个函数的代码是在编译器的最后的链接的过程中写入的，在生成语法树的时候这个节点其实其中的代码并不知道，之后再连接的过程中还需要做一个符号的消解过程，这里后面会提到。

 <<AST>> (hello.cb:1)
variables:
functions:
    <<DefinedFunction>> (hello.cb:3)
    name: "main"
    isPrivate: false
    params:
        parameters:
            <<CBCParameter>> (hello.cb:4)
            name: "argc"
            typeNode: int
            <<CBCParameter>> (hello.cb:4)
            name: "argv"
            typeNode: char**
    body:
        <<BlockNode>> (hello.cb:5)
        variables:
        stmts:
            <<ExprStmtNode>> (hello.cb:6)
            expr:
                <<FuncallNode>> (hello.cb:6)
                expr:
                    <<VariableNode>> (hello.cb:6)
                    name: "printf"
                args:
                    <<StringLiteralNode>> (hello.cb:6)
                    value: "Hello, World!\n"
            <<ReturnNode>> (hello.cb:7)
            expr:
                <<IntegerLiteralNode>> (hello.cb:7)
                typeNode: int
                value: 0

if-else的二义性问题

还有一个关于if-else很著名的二义性问题。对于常见的if语句代码，如果不加上大括号的话，默认情况下else是和最近一个没有else的if匹配，这是如何实现的呢？

if(cond)
  if(cond)
    f()
  else
    g()

对于匹配规则

//这里可以简单理解stmt()表示一个if语句或者是一个带有大括号的代码块
"if" "(" expr() ")" stmt() [ "else" stmt()]

上面的语句有这样的两种理解方式：

if (cond){
  if(cond){
    f()
  }else{
    g()
  }
}

if(cond){
  if(cond){
    f()
  } 
}else {
  g()
}

这两种理解方式都可以通过上面写的这样的表达式的。在这种情况发生的时候，同一种代码生成了两种不一样的语法树：

两棵语法树

解决这个问题的关键在于，如果一个if后面出现了一个else就立刻和它匹配到一起，不可以省略或者留给上一个else。因此，在这里可以加一个超前扫描符号LOOKAHEAD()

"if" "(" expr() ")" stmt() [ LOOKAHEAD(1) "else" stmt()]

运算符优先级的处理问题

最后的部分会谈一下如何在生成抽象语法树的过程中也兼顾运算符的优先级问题。

ExprNode expr():
{
    ExprNode lhs, rhs, expr;
    String op;
}
{
   /// .... 省略
    | expr=expr10()
        {
            return expr;
        }
}

Cflat编译器使用了一种非常讨巧的方式（其他的编译器使用的方式应该也是类似的），因为Cflat对于抽象语法树的访问顺序是从上至下的，所以Cflat会将优先级低的运算符放在靠近顶端的位置

表达式1+2*3

所以在上面的规则中，先会进行优先级低的表达式的处理：
example: int a = b > c ? 10 : 0;

ExprNode expr10():
{ ExprNode c, t, e; }
{
    c=expr9() ["?" t=expr() ":" e=expr10()
                    { return new CondExprNode(c, t, e); }]
        {
            return c;
        }
}

就这样按照C语言的顺序逐次处理向下：

ExprNode expr2():
{ ExprNode l, r; }
{
    l=expr1() ( "+" r=expr1() { l = new BinaryOpNode(l, "+", r); }
              | "-" r=expr1() { l = new BinaryOpNode(l, "-", r); }
              )*
        {
            return l;
        }
}
// #@@}

// #@@range/expr1{
ExprNode expr1():
{ ExprNode l, r; }
{
    l=term() ( "*" r=term() { l = new BinaryOpNode(l, "*", r); }
             | "/" r=term() { l = new BinaryOpNode(l, "/", r); }
             | "%" r=term() { l = new BinaryOpNode(l, "%", r); }
             )*
        {
            return l;
        }
}

Section2：语义分析

语义分析是要对通过词法分析和语法分析生成了的抽象语法树（AST）进行处理，主要是需要进行五个步骤的处理。具体来说是进行如下的几个步骤：

按照次序进行的几个步骤

操作	目的	涉及到的类型
变量引用的消解	判断同名变量i具体指向的是全局的还是局部的	LocalResolver,ToplevelScope,LocalScope
类型名称的消解	将TypeRef全部转换为Type类型	TypeRef,Type,TypeResolver
类型定义检查	检查是否存在错误定义的类型和循环定义的类型	TypeTable
表达式有效性检查	检查赋值，成员引用是否存在问题	DereferenceChecker
静态类型检查	检查如表达式两端的类型是否存在问题	TypeChecker

个人认为这五个问题以及延伸出来的相关问题的解释和回答是编译器前端中最有意思的地方所在，下面将挨个简要概括一下。

变量引用的消解 LocalResolver

example：

int i = 10;

void fun(){
  int i = 100;
  printf("%d", i);
}

全局变量和函数内部的变量名称相同的时候往往会选取局部变量。编译器在这个地方做的操作其实非常巧妙：
一个源代码文件在全局声明的变量会被放到ToplevelScope中，在局部作用域，比如函数内部，流程控制语句内部声明的变量会放到LocalScope中，而且Scope之间的关系是通过一个Scope栈进行管理的，而且作用域（LocalScope 和 ToplevelScope相互引用，也形成了一棵树的结构），如果要找变量名称为t的变量，直接先找当前的scope中，如果没有的话会沿着Scope树向上寻找。

类型名称的消解

在最开始分析代码的解析的时候，这里的划了一个重点：

  priv=storage() type=type() name=name() ["=" init=expr()]

对于type()的规则的分析可以向下深挖：

TypeNode type():
{ TypeRef ref; }
{
    ref=typeref() { return new TypeNode(ref); }
}

TypeRef typeref():
{
    TypeRef ref;
    Token t;
    ParamTypeRefs params;
}
{
    ref=typeref_base()
    ( LOOKAHEAD(2)
      "[" "]"
        {
            ref = new ArrayTypeRef(ref);
        }
    | "[" t=<INTEGER> "]"
        {
            ref = new ArrayTypeRef(ref, integerValue(t.image));
        }
    | "*"
        {
            ref = new PointerTypeRef(ref);
        }
    | "(" params=param_typerefs() ")"
        {
            ref = new FunctionTypeRef(ref, params);
        }
    )*
        {
            return ref;
        }
}

编译器中使用了Type作为变量应该有的类型，使用了TypeRef做了变量的名称。之所以引入这样的区别主要是满足类型的“向前引用的问题”：

import stdio;

int t = 10;
int main(int argc, char ** argv) {
  printf("%d", fun(t));
}

int fun(int t){
 return t;
}

这样的代码在C语言中是无法过编译的，因为函数fun没有在调用之前进行函数声明。还有这个例子:

import stdio;

int main(int argc, char ** argv) {
 struct Point point;
 point.x = 10;
 point.y = 10;
 printf("%d", point.x);
}

struct Point {
 int x;
 int y;
};

结构体Point 没有在调用处之间声明，这样的代码在C语言中也无法过编译。
在Cflat编译器中，问题的解决思路比较简单，首先通过TypeRef在扫描的时候记录一下类型的名字（函数也算是一个类型，函数的类型由返回值和参数共同决定），然后再语义分析中进行消解，也就是建立真正的类型Type和类型名称TypeRef的一个映射关系。

类型定义检查

类型定义检查主要要处理三个方面的问题：

包含void类型的数组、结构体、联合体
成员重复的结构、联合体
循环定义的结构体、联合体

在这三个问题中前两个问题比较容易解决，

如图

第三个问题可以使用图算法中的DFS算法检查环路

检查环路

如果存在着循环定义一定会构成一个环路，使用DFS算法就可以找到是否环路存在。

表达式有效性检查 DereferenceChecker

对于可能出现问题的表达式进行了一个枚举：

表达式有效性检查需要处理的各类有问题的表达式

其中这些有问题的表达式可以大体上分成两种：

检查表达式是否可以被赋值（自增自减、取地址运算符等等）
检查操作数和类型（其他的情况）

左边右边左值右值

左边（left hand side）的内容只能是编程语言中的能赋值的表达式，右边（right hand side ）可以是任意表达式。左边表达式的共性都是能取地址（因为赋值其实上是将右边的内容写入地址）。

赋值符号将等式划分成左边和右边两个部分。
因此，当同样的一个表达式出现在赋值语句的两端，所表示的内容一定是不相同的，如上图中的 * ptr 出现在左边的时候表示的是* ptr的指向的地址，即&n；当* ptr出现在右侧的时候表示的是*ptr表示的值。

检查非指针取值操作

example:

int pointer = 10;
*pointer = 20;

这个操作其实就是对抽象语法树上对于DereferenceNode的访问，如果被访问的节点不是指针的话，是不能够解引用的（undereferable）。

获取非左值的表达式

根据上面介绍的左值和右值的定义可知，在Cflat编译器中只有部分的节点可以作为表达式的左值（可以取地址的节点）：

所以代码流程如图所示。

对于类型的处理和处理隐式地址

因为在C（Cflat）语言中数组和函数都是一个隐式的地址（指针）。对于函数puts和&put都应该是指向函数的指针，他们两个的类型应该是相同的，并且他们的值也是相同的，举书中讲过的一个冷笑话：

因此，在visit(AddressNode node) 的代码中需要特殊处理

 public Void visit(AddressNode node) {
        super.visit(node);
        if (! node.expr().isLvalue()) {
            semanticError(node.location(), "invalid expression for &");
        }
        Type base = node.expr().type();
         //如果node.expr()是函数或者是数组类型进行特殊处理
        if (! node.expr().isLoadable()) {
            // node.expr.type is already pointer.
            node.setType(base);
        }
        else {
            //如果不是 还是要指向取地址之后的类型 比如：
            // int * a 的类型应该是 PointerType 包装了一个int的类型
            node.setType(typeTable.pointerTo(base));
        }
        return null;
    }

同理，handleImplicitAddress的原理也是类似的：

 private void handleImplicitAddress(LHSNode node) {
        if (! node.isLoadable()) {
            Type t = node.type();
            if (t.isArray()) {
                // int[4] ary; ary; should generate int*
                node.setType(typeTable.pointerTo(t.baseType()));
            }
            else {
               //如果是函数类型 直接处理成函数的指针 不需要进行套娃
                node.setType(typeTable.pointerTo(t));
            }
        }
    }

静态类型检查 TypeChecker

静态类型检查就是在表达式中对某一个操作符号使用的部分进行检查，比如 * 操作只能支持两边都是相同类型的数值（Cflat没有支持浮点数运算），同时对于有些操作也可以进行隐式类型转换(char和int进行运算时会按照一定的规则转换成相同的类型)。

静态类型检查其实相对容易，按照操作符规定的类型进行检查即可：

类型检查1

类型检查2

具体的代码:

public Void visit(BinaryOpNode node) {
        super.visit(node);
        switch (node.operator()) {
            case "+":
            case "-":
                expectsSameIntegerOrPointerDiff(node);
                break;
            case "*":
            case "/":
            case "%":
            case "&":
            case "|":
            case "^":
            case "<<":
            case ">>":
                expectsSameInteger(node);
                break;
            case "==":
            case "!=":
            case "<":
            case "<=":
            case ">":
            case ">=":
                expectsComparableScalars(node);
                break;
            default:
                throw new Error("unknown binary operator: " + node.operator());
        }
        return null;
    }

函数名称和具体的操作符通过一种枚举的方式已经写的比较清楚了，其中在expect相关的的函数中其实进行了隐式类型转换。

 private void arithmeticImplicitCast(BinaryOpNode node) {
        Type r = integralPromotion(node.right().type());
        Type l = integralPromotion(node.left().type());
//都需要转换成目标的类型 ，如果不同的话就进行转换cast
        Type target = usualArithmeticConversion(l, r);
        if (! l.isSameType(target)) {
            // insert cast on left expr
            node.setLeft(new CastNode(target, node.left()));
        }
        if (! r.isSameType(target)) {
            // insert cast on right expr
            node.setRight(new CastNode(target, node.right()));
        }
        node.setType(target);
    }

Section3：中间代码生成 IRGenerator

中间代码是依据抽象语法树生成的，说明这个问题之前有必要说明一下Cflat编译器中是如何进行树节点的访问的。Cflat编译器中使用了设计模式中的Visitor模式来设计节点的访问过程，本文就不介绍Visitor模式了，下面展示一下除了最后一个汇编代码生成阶段之外的几个部分的联系，Part2中会对这个图在进行补充。

联系关系

如图所示，Parser.jj（其实是JavaCC生成了的Parser类）输出了AST，这就完成了语法分析部分。抽象语法树AST可以说是前三个部分的核心，抽象语法树中间的节点Node有很多子类型，这些节点定义在ast包中，配合着Visitor模式，在节点的基类型Node定义了一个抽象方法accept(ASTVisitor vistor)，接受一个ASTVisitor参数。在语义分析中的DereferenceChecker等等都进行了ASTVistor，来进行节点的访问过程，最后输出处理了的AST（处理：类型消解等等，检查：各种checker过程），或者报错终止编译流程，这就完成了语义分析部分。这个AST又被implements ASTVisitor的IRGenerator处理，最后输出中间代码树IR tree。这个部分就是我们要展开的中间代码生成过程。

中间代码的意义

因为在最后的汇编代码中是没有像编程语言中的if，while等等流程控制语句的，在运算符方面也和我们高级语言的感觉是不一样的，而且我们希望代码树能尽量地贴近汇编代码的结构所以需要通过中间代码进行处理。在很多变成语言中因为底层的指令集等等的差异，往往也用中间代码做一个缓冲层，比如GCC将很多语言变成相同的中间语言就没有必要设计诸如C++专用的Intel编译器等等了。

不使用中间代码

使用中间代码的情况

一言以蔽之，就是一个解耦合的思想。

中间代码的运算符号

中间代码和之前的AST类似，其实都是对代码结构的一个表现，它实际上不会计算结果，不会求值。因为需要贴近汇编代码，所以在中间代码的层面上直接通过运算符号来表现变量的符号（signed unsigned）。

int main (int argc, char **argv) {
 int a = 10;
 unsigned int b = 20;
}

在AST的层面上是通过节点的类型进行表示的，like this：

 <<DefinedVariable>> (signed.cb:2)
            name: "a"
            isPrivate: false
            typeNode: int
            initializer:
                <<IntegerLiteralNode>> (signed.cb:2)
                typeNode: int
                value: 10
            <<DefinedVariable>> (signed.cb:3)
            name: "b"
            isPrivate: false
            typeNode: unsigned int
            initializer:
                <<IntegerLiteralNode>> (signed.cb:3)
                typeNode: int
                value: 20

举几个定义的操作符的例子：

例子

函数体和流程控制语句转换的算法

流程控制语句只能定义在函数体中。在大体上将这些流程控制语句转化成中间代码的模式和goto语句是相同的。所以了解了其中一种流程控制语句的转换算法，其他的也可以举一反三了。

对于控制语句的节点命令行打印输出的流程我放在了这里。

IfNode WhileNode 转换成中间代码

IfNode 转换成中间代码

 public Void visit(IfNode node) {
        Label thenLabel = new Label();
        Label elseLabel = new Label();
        Label endLabel = new Label();

        Expr cond = transformExpr(node.cond());
        if (node.elseBody() == null) {
            cjump(node.location(), cond, thenLabel, endLabel);
            label(thenLabel);
            transformStmt(node.thenBody());
        } else {
            cjump(node.location(), cond, thenLabel, elseLabel);
            label(thenLabel);
            transformStmt(node.thenBody());
            jump(endLabel);
            label(elseLabel);
            transformStmt(node.elseBody());
        }
        label(endLabel);
        return null;
    }

通过一个if分支分成了带有else语句和不带有else语句的两种情况，其中比较复杂的带有else语句的情况就是这个意思：

IfNode

WhileNode的访问

相比较于IfNode WhileNode 还有ForNode 对应的while，for语句等等是可以break的，也就是break可以结束循环体，同时可以通过continue进行下一次循环。不过依葫芦画瓢，while的转换应该是这样子：

WhileNode

如果是涉及到有嵌套的for while语句，可能会更加复杂：

while(a < 10){
            while( b > 10) {
                if(a == b) break;
            }
            if(a > b) continue;
        }

这涉及到一个对应关系的问题，continue这条语句对应的是哪一个while？break应该跳转到哪里呢？Cflat编译器通过引入了一个和栈相关的算法处理了这个问题：

WhileNode

如果在扫描的过程中发现了可以break的节点，生成一个标签（跳转目标），并且压栈，如果发现了break，就将栈顶的标签和break语句进行绑定，当这个可以break的节点代码块结束之后就将标签弹出。

当break即将执行的时候，由于跳转目标已经制定好了，所以可以直接跳转到跳转目标的endLabel；如果是continue的话可以跳转到目标的begLabel进行下一次判定。
具体的代码如下：

  public Void visit(WhileNode node) {
        Label begLabel = new Label();
        Label bodyLabel = new Label();
        Label endLabel = new Label();

        label(begLabel);
        cjump(node.location(), transformExpr(node.cond()), bodyLabel, endLabel);
        label(bodyLabel);
        pushContinue(begLabel);
        pushBreak(endLabel);
        transformStmt(node.body());
        popBreak();
        popContinue();
        jump(begLabel);
        label(endLabel);
        return null;
    }

表达式的转换

表达式的转换要分成两种，区分依据是是否有副作用。这个副作用是指除了纯粹的计算出结果之外，还要其他的值在内存的改变，比如

a += 1;

除了返回值a之外，a的结果在内存中也改变了。再比如函数调用中经常会让编写者考虑副作用对于全局变量或者是参数的影响。
一般来说变成语言中的副作用一个就是赋值语句，另外一个就是函数调用。这个地方就跟着副作用的定义理解就好，不要多想（比如：a+=1 的结果不就是要改变a吗，为什么这个有副作用，感受它，别尝试理解它）。

没有副作用的表达式转换

比如

+a
-a

这些是一定没有副作用的，因为只是将变量a当成了工具人，提取内存中的结果。这样的处理往往比较单纯

 public Expr visit(UnaryOpNode node) {
        if (node.operator().equals("+")) {
            // +expr -> expr
            return transformExpr(node.expr());
        } else {
            return new Uni(asmType(node.type()),
                    Op.internUnary(node.operator()),
                    transformExpr(node.expr()));
        }
    }

带有副作用的表达式的处理

之所以要处理副作用，是因为带有副作用的表达式的执行顺序不能改变，在优化的时候有些优化方式没法执行，而且需要根据上下文来谨慎处理副作用的影响。

对于变量赋值引起的副作用对应的AssignNode，可以通过添加临时变量的方式来分开副作用和赋值两者：

public Expr visit(AssignNode node) {
        //先进行右表达式的计算 和编程语言的规范相同
        Location lloc = node.lhs().location();
        Location rloc = node.rhs().location();

        if (isStatement()) {
            //普通的表达式 a = a + 1
            Expr rhs = transformExpr(node.rhs());
            assign(lloc, transformExpr(node.lhs()), rhs);
            //这样的表达式不需要返回值
            return null;
        } else {
           //带有返回值的表达式如:具有返回值的节点,return 语句等等
           // cond(lhs = rhs) 这样的表达式
            DefinedVariable tmp = tmpVar(node.rhs().type());
            assign(rloc, ref(tmp), transformExpr(node.rhs()));
            assign(lloc, transformExpr(node.lhs()), ref(tmp));
            return ref(tmp);
        }
    }

直接看可能有点抽象，针对这样的情况才需要加入临时变量处理：

int i ;
f(i = g(10));

// 转换成
temp = g(10);
i = temp;
f(temp);

大体的思路是这样没错，在实际编译成中间代码的时候考虑到函数调用可能也带来的副作用影响，实际编译成代码可能是这样：

temp1 = g(10);
temp0 = temp1;
i = temp0;
f(temp0);

因为处理FuncallNode 函数调用的时候也引入了中间变量:

 public Expr visit(FuncallNode node) {
        List<Expr> args = new ArrayList<>();
        List<ExprNode> reversedParams = new ArrayList<>(node.args());
        Collections.reverse(reversedParams);

        for (ExprNode arg : reversedParams) {
            args.add(0, transformExpr(arg));
        }

        Expr call = new Call(asmType(node.type()), transformExpr(node.expr()), args);
        if (isStatement()) {
            stmts.add(new ExprStmt(node.location(), call));
            return null;
        } else {
           //这里
            DefinedVariable tmp = tmpVar(node.type());
            assign(node.location(), ref(tmp), call);
            return ref(tmp);
        }
    }

问题的回答

输入的代码文件如何从正则表达式解析生成了抽象语法树？
通过Parser.jj生成的Parser一边扫描以便确定了抽象语法树。
像 include import 这样的语句是如何导入外部模块、包的变量和函数的，这些变量以及函数是如何进行管理的？
这个问题涉及到链接，下一章回答。
对于代码中的函数的作用域是如何划分的，局部变量和全局变量如何区分?
在LocalResolver中构建了Scope栈ToplevelScope和LocalScope，先从LocalScope往上找变量。
抽象语法树如何变成汇编代码？汇编代码又如何变成机器代码并且执行的？
变成汇编代码的过程会在CodeGenerator中，下一章会说明。
在代码编译的过程中，编译器如何进行代码的优化？
Cflat编译器使用了窥孔优化，但是我们可以做的更多，这个也会在下一章中说明。
指针、数组、函数类型在整个函数编译过程中有无特殊的影响和作用？
根据我们目前的了解来看，因为函数和数组类型在C（Cflat）语言中会被当成指针，所以在类型消解的时候要做隐式的类型转换，而不能指针类型套娃。基本可以看做是一种特殊的类型，特殊对待一下就好了。
在中缀表达式中，我们通过栈可以处理表达式的优先级，在编译器编译代码过程中，是不是也需要转换为中缀表达式呢？
变换成中缀表达式会影响抽象语法树，或者影响编译效率，直接在构建语法树的时候就处理了运算优先级。

《自制编译器》读书笔记Part1

前言

Reference

编译器概要

自制编译器自制了什么？

提出的问题

Section1 ：语法分析

词法分析

构建抽象语法树过程中好玩的例子

变量的声明

if-else的二义性问题

运算符优先级的处理问题

Section2：语义分析

变量引用的消解 LocalResolver

类型名称的消解

类型定义检查

表达式有效性检查 DereferenceChecker

左边右边左值右值

检查非指针取值操作

获取非左值的表达式

对于类型的处理和处理隐式地址

静态类型检查 TypeChecker

Section3：中间代码生成 IRGenerator

中间代码的意义

中间代码的运算符号

函数体和流程控制语句转换的算法

IfNode WhileNode 转换成中间代码

IfNode 转换成中间代码

WhileNode的访问

表达式的转换

没有副作用的表达式转换

带有副作用的表达式的处理

问题的回答

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

程序员

《自制编译器》读书笔记Part1

前言

Reference

编译器概要

自制编译器自制了什么？

提出的问题

Section1 ： 语法分析

词法分析

构建抽象语法树过程中好玩的例子

变量的声明

if-else的二义性问题

运算符优先级的处理问题

Section2：语义分析

变量引用的消解 LocalResolver

类型名称的消解

类型定义检查

表达式有效性检查 DereferenceChecker

左边右边 左值右值

检查非指针取值操作

获取非左值的表达式

对于类型的处理和处理隐式地址

静态类型检查 TypeChecker

Section3：中间代码生成 IRGenerator

中间代码的意义

中间代码的运算符号

函数体和流程控制语句转换的算法

IfNode WhileNode 转换成中间代码

IfNode 转换成中间代码

WhileNode的访问

表达式的转换

没有副作用的表达式转换

带有副作用的表达式的处理

问题的回答

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

程序员

Section1 ：语法分析

左边右边左值右值