转载

从零写一个编译器（十三）：代码生成之遍历AST

在上一篇完成对JVM指令的生成，下面就可以真正进入代码生成部分了。通常现代编译器都是先把生成IR，再经过代码优化等等，最后才编译成目标平台代码。但是时间水平有限，我们没有IR也没有代码优化，就直接利用AST生成Java字节码

入口

进行代码生成的入口在CodeGen，和之前解释器一样：先获取main函数的头节点，从这个节点开始，先进入函数定义，再进入代码块

函数定义节点

在进入函数定义节点的时候，就要生成一个函数定义对应的Java字节码，即一个静态方法（因为我们对整个C语言文件生成为一个类，main方法为public static main，其它的则是对应的静态方法，结构体则是另外的类）

  • 对于函数定义先从节点中拿到对应的函数命和参数
  • emitArgs是用来处理参数的，根据参数生成相应的Java字节码
  • 如果这个函数是main的话已经是交由前面处理了，逻辑差不多（具体在start.Start中）
case SyntaxProductionInit.NewName_LP_RP_TO_FunctDecl:
    root.reverseChildren();
    AstNode n = root.getChildren().get(0);
    String name = (String) n.getAttribute(NodeKey.TEXT);
    symbol = (Symbol) root.getAttribute(NodeKey.SYMBOL);
    generator.setCurrentFuncName(name);
    if (name != null && !name.equals("main")) {
        String declaration = name + emitArgs(symbol);
        generator.emitDirective(Directive.METHOD_PUBBLIC_STATIC, declaration);
        generator.setNameAndDeclaration(name, declaration);
    }
    copyChild(root, root.getChildren().get(0));
    break;

case SyntaxProductionInit.NewName_LP_VarList_RP_TO_FunctDecl:
    n = root.getChildren().get(0);
    name = (String) n.getAttribute(NodeKey.TEXT);
    symbol = (Symbol) root.getAttribute(NodeKey.SYMBOL);
    generator.setCurrentFuncName(name);
    if (name != null && !name.equals("main")) {
        String declaration = name + emitArgs(symbol);
        generator.emitDirective(Directive.METHOD_PUBBLIC_STATIC, declaration);
        generator.setNameAndDeclaration(name, declaration);
    }

    Symbol args = symbol.getArgList();

    if (args == null || argsList == null || argsList.isEmpty()) {
        System.err.println("generate function with arg list but arg list is null");
        System.exit(1);
    }
    break;

创建结构体和数组

数组

创建结构体和数组的节点在DefGenerate里，可以看到在这里只处理了数组和普通变量，有关结构体的处理是在对结构体第一次使用的时候。顺便提一下代码生成对于赋初值操作是没有进行处理的。

  • 如果是个数组，酒直接调用ProgramGenerator直接生成创建数组的指令
  • 如果是个普通变量，就直接找到它并且赋值为0（这里变量在队列里的位置是根据符号表来计算的，具体可以看上一篇的getLocalVariableIndex方法）
public class DefGenerate extends BaseGenerate {
    @Override
    public Object generate(AstNode root) {
        int production = (int) root.getAttribute(NodeKey.PRODUCTION);
        ProgramGenerator generator = ProgramGenerator.getInstance();
        Symbol symbol = (Symbol) root.getAttribute(NodeKey.SYMBOL);

        switch (production) {
            case SyntaxProductionInit.Specifiers_DeclList_Semi_TO_Def:
                Declarator declarator = symbol.getDeclarator(Declarator.ARRAY);
                if (declarator != null) {
                    if (symbol.getSpecifierByType(Specifier.STRUCTURE) == null) {
                        generator.createArray(symbol);
                    }
                } else {
                    int i = generator.getLocalVariableIndex(symbol);
                    generator.emit(Instruction.SIPUSH, "" + 0);
                    generator.emit(Instruction.ISTORE, "" + i);
                }

                break;

            default:
                break;
        }

        return root;
    }
}

结构体

处理结构体定义的代码在UnaryNodeGenerate，也就是只有在使用到结构体定义时才会进行定义

  • 先拿到当前UNARY的符号，如果instanceof ArrayValueSetter就说明是一个结构体数组，就进入getStructSymbolFromStructArray方法创建一个结构体数组，并返回当前下标的结构体对象
  • 设置当前结构体的作用域范围
  • 对结构体作为类进行定义
  • 然后对读取结构体的域
  • 其实可以忽略指针部分，因为代码生成并没有对指针进行模拟
case SyntaxProductionInit.Unary_StructOP_Name_TO_Unary:
    child = root.getChildren().get(0);
    String fieldName = (String) root.getAttribute(NodeKey.TEXT);
    Object object = child.getAttribute(NodeKey.SYMBOL);
    boolean isStructArray = false;

    if (object instanceof ArrayValueSetter) {
        symbol = getStructSymbolFromStructArray(object);
        symbol.addValueSetter(object);
        isStructArray = true;
    } else {
        symbol = (Symbol) child.getAttribute(NodeKey.SYMBOL);
    }

    if (isStructArray) {
        ArrayValueSetter vs = (ArrayValueSetter) object;
        Symbol structArray = vs.getSymbol();
        structArray.addScope(ProgramGenerator.getInstance().getCurrentFuncName());
    } else {
        symbol.addScope(ProgramGenerator.getInstance().getCurrentFuncName());
    }

    ProgramGenerator.getInstance().putStructToClassDeclaration(symbol);

    if (isSymbolStructPointer(symbol)) {
        copyBetweenStructAndMem(symbol, false);
    }

    Symbol args = symbol.getArgList();
    while (args != null) {
        if (args.getName().equals(fieldName)) {
            args.setStructParent(symbol);
            break;
        }

        args = args.getNextSymbol();
    }

    if (args == null) {
        System.err.println("access a filed not in struct object!");
        System.exit(1);
    }

    if (args.getValue() != null) {
        ProgramGenerator.getInstance().readValueFromStructMember(symbol, args);
    }

    root.setAttribute(NodeKey.SYMBOL, args);
    root.setAttribute(NodeKey.VALUE, args.getValue());

    if (isSymbolStructPointer(symbol)) {
        checkValidPointer(symbol);
        structObjSymbol = symbol;
        monitorSymbol = args;

        GenerateBrocasterImpl.getInstance().registerReceiverForAfterExe(this);
    } else {
        structObjSymbol = null;
    }
    break;

一元操作节点

这个节点和在解释器的有很多相同，除了有对结构体的操作，其它的也是有非常重要的作用

  • 像数字、字符串或者是变量和之前的操作都是把信息传递到父节点，交由父节点处理
case SyntaxProductionInit.Number_TO_Unary:
    text = (String) root.getAttribute(NodeKey.TEXT);
    boolean isFloat = text.indexOf('.') != -1;
    if (isFloat) {
        value = Float.valueOf(text);
        root.setAttribute(NodeKey.VALUE, value);
    } else {
        value = Integer.valueOf(text);
        root.setAttribute(NodeKey.VALUE, value);
    }
    break;

case SyntaxProductionInit.Name_TO_Unary:
    symbol = (Symbol) root.getAttribute(NodeKey.SYMBOL);
    if (symbol != null) {
        root.setAttribute(NodeKey.VALUE, symbol.getValue());
        root.setAttribute(NodeKey.TEXT, symbol.getName());
    }
    break;

case SyntaxProductionInit.String_TO_Unary:
    text = (String) root.getAttribute(NodeKey.TEXT);
    root.setAttribute(NodeKey.VALUE, text);
    break;

case SyntaxProductionInit.Unary_LB_Expr_RB_TO_Unary:
    child = root.getChildren().get(0);
    symbol = (Symbol) child.getAttribute(NodeKey.SYMBOL);

    child = root.getChildren().get(1);
    int index = 0;
    if (child.getAttribute(NodeKey.VALUE) != null) {
        index = (Integer) child.getAttribute(NodeKey.VALUE);
    }
    Object idxObj = child.getAttribute(NodeKey.SYMBOL);

    try {
        Declarator declarator = symbol.getDeclarator(Declarator.ARRAY);
        if (declarator != null) {
            Object val = declarator.getElement((int) index);
            root.setAttribute(NodeKey.VALUE, val);
            ArrayValueSetter setter;
            if (idxObj == null) {
                setter = new ArrayValueSetter(symbol, index);
            } else {
                setter = new ArrayValueSetter(symbol, idxObj);
            }

            root.setAttribute(NodeKey.SYMBOL, setter);
            root.setAttribute(NodeKey.TEXT, symbol.getName());

        }
        Declarator pointer = symbol.getDeclarator(Declarator.POINTER);
        if (pointer != null) {
            setPointerValue(root, symbol, index);
            PointerValueSetter pv = new PointerValueSetter(symbol, index);
            root.setAttribute(NodeKey.SYMBOL, pv);
            root.setAttribute(NodeKey.TEXT, symbol.getName());
        }
    } catch (Exception e) {
        e.printStackTrace();
        System.exit(1);
    }
    break;

赋值操作

  • 如果当前是一个数组，先拿到它的符号和下标
  • 如果不是结构体数组，那么拿到下标直接用readArrayElement生成读取数组元素的指令
  • 如果是一个符号则用getLocalVariableIndex读取这个符号的值
  • 如果是一个常数，则直接生成IPUSH指令
  • 最后进行赋值操作，如果不是对结构体的域进行赋值就直接用getLocalVariableIndex拿到队列位置然后生成ISTORE
  • 如果是对结构体数组的元素的域的赋值，就调用assignValueToStructMemberFromArray生成代码，如果只是结构体就直接调用assignValueToStructMember生成代码
ProgramGenerator generator = ProgramGenerator.getInstance();

if (BaseGenerate.resultOnStack) {
    this.value = obj;
    BaseGenerate.resultOnStack = false;
} else if (obj instanceof ArrayValueSetter) {
    ArrayValueSetter setter = (ArrayValueSetter) obj;
    Symbol symbol = setter.getSymbol();
    Object index = setter.getIndex();
    if (symbol.getSpecifierByType(Specifier.STRUCTURE) == null) {
        if (index instanceof Symbol) {
            ProgramGenerator.getInstance().readArrayElement(symbol, index);
            if (((Symbol) index).getValue() != null) {
                int i = (int) ((Symbol) index).getValue();
                try {
                    this.value = symbol.getDeclarator(Declarator.ARRAY).getElement(i);
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        } else {
            int i = (int) index;
            try {
                this.value = symbol.getDeclarator(Declarator.ARRAY).getElement(i);
            } catch (Exception e) {
                e.printStackTrace();
            }

            ProgramGenerator.getInstance().readArrayElement(symbol, index);
        }
    }
} else if (obj instanceof Symbol) {
    Symbol symbol = (Symbol) obj;
    this.value = symbol.value;
    int i = generator.getLocalVariableIndex(symbol);
    generator.emit(Instruction.ILOAD, "" + i);
} else if (obj instanceof Integer) {
    Integer val = (Integer) obj;
    generator.emit(Instruction.SIPUSH, "" + val);
    this.value = obj;
}

if (!this.isStructMember()) {
    int idx = generator.getLocalVariableIndex(this);
    if (!generator.isPassingArguments()) {
        generator.emit(Instruction.ISTORE, "" + idx);
    }
} else {
    if (this.getStructSymbol().getValueSetter() != null) {
        generator.assignValueToStructMemberFromArray(this.getStructSymbol().getValueSetter(), this, this.value);
    } else {
        generator.assignValueToStructMember(this.getStructSymbol(), this, this.value);
    }
}

最后

完成这部分后，对下面的代码

void quicksort(int A[10], int p, int r) {
    int x;
    int i;
    i = p - 1;
    int j;
    int t;
    int v;
    v = r - 1;
    if (p < r) {
        x = A[r];
        for (j = p; j <= v; j++) {
            if (A[j] <= x) {
                i++;
                t = A[i];
                A[i] = A[j];
                A[j] = t;
            }
        }
        v = i + 1;
        t = A[v];
        A[v] = A[r];
        A[r] = t;
        t = v - 1;
        quicksort(A, p, t);
        t = v + 1;
        quicksort(A, t, r);
    }
}

void main () {
    int a[10];
    int i;
    int t;
    printf("before quick sort:");
    for(i = 0; i < 10; i++) {
        t = (10 - i);
        a[i] = t;
        printf("value of a[%d] is %d", i, a[i]);
    }
    quicksort(a, 0, 9);
    printf("after quick sort:");
    for (i = 0; i < 10; i++) {
        printf("value of a[%d] is %d", i, a[i]);
    }
}

则会生成下面的Java字节码

.class public C2Bytecode
.super java/lang/Object

.method public static main([Ljava/lang/String;)V
	sipush	10
	newarray	int
	astore	0
	sipush	0
	istore	1
	sipush	0
	istore	2
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	ldc	"before quick sort:"
	invokevirtual	java/io/PrintStream/print(Ljava/lang/String;)V
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	ldc	"
"
	invokevirtual	java/io/PrintStream/print(Ljava/lang/String;)V
	sipush	0
	istore	1

loop0:
	iload	1
	sipush	10
if_icmpge branch0
	sipush	10
	iload	1
	isub
	istore	2
	aload	0
	iload	1
	iload	2
	iastore
	aload	0
	iload	1
	iaload
	istore	3
	iload	1
	istore	4
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	ldc	"value of a["
	invokevirtual	java/io/PrintStream/print(Ljava/lang/String;)V
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	iload	4
	invokevirtual	java/io/PrintStream/print(I)V
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	ldc	"] is "
	invokevirtual	java/io/PrintStream/print(Ljava/lang/String;)V
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	iload	3
	invokevirtual	java/io/PrintStream/print(I)V
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	ldc	"
"
	invokevirtual	java/io/PrintStream/print(Ljava/lang/String;)V
	iload	1
	sipush	1
	iadd
	istore	1
goto loop0
branch0:
	aload	0
	sipush	0
	sipush	9
	invokestatic	C2Bytecode/quicksort([III)V
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	ldc	"after quick sort:"
	invokevirtual	java/io/PrintStream/print(Ljava/lang/String;)V
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	ldc	"
"
	invokevirtual	java/io/PrintStream/print(Ljava/lang/String;)V
	sipush	0
	istore	1

loop2:
	iload	1
	sipush	10
if_icmpge branch4
	aload	0
	iload	1
	iaload
	istore	3
	iload	1
	istore	4
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	ldc	"value of a["
	invokevirtual	java/io/PrintStream/print(Ljava/lang/String;)V
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	iload	4
	invokevirtual	java/io/PrintStream/print(I)V
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	ldc	"] is "
	invokevirtual	java/io/PrintStream/print(Ljava/lang/String;)V
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	iload	3
	invokevirtual	java/io/PrintStream/print(I)V
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	ldc	"
"
	invokevirtual	java/io/PrintStream/print(Ljava/lang/String;)V
	iload	1
	sipush	1
	iadd
	istore	1
goto loop2
branch4:
	return
.end method
.method public static quicksort([III)V
	sipush	2
	newarray	int
	astore	6
	sipush	0
	istore	5
	sipush	1
	istore	5
	aload	6
	iload	5
	sipush	1
	iastore
	aload	6
	sipush	1
	iaload
	istore	10
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	ldc	"before quick sort: "
	invokevirtual	java/io/PrintStream/print(Ljava/lang/String;)V
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	iload	10
	invokevirtual	java/io/PrintStream/print(I)V
	getstatic	java/lang/System/out Ljava/io/PrintStream;
	ldc	"
"
	invokevirtual	java/io/PrintStream/print(Ljava/lang/String;)V
	sipush	0
	istore	9
	sipush	0
	istore	3
	iload	1
	sipush	1
	isub
	istore	3
	sipush	0
	istore	4
	sipush	0
	istore	7
	sipush	0
	istore	8
	iload	2
	sipush	1
	isub
	istore	8
	iload	1
	iload	2
if_icmpge branch1

	aload	0
	iload	2
	iaload
	istore	9
	iload	1
	istore	4

loop1:

	iload	4
	iload	8
if_icmpgt ibranch1

	aload	0
	iload	4
	iaload
	iload	9
if_icmpgt ibranch2

	iload	3
	sipush	1
	iadd
	istore	3
	aload	0
	iload	3
	iaload
	istore	7
	aload	0
	iload	3
	aload	0
	iload	4
	iaload
	iastore
	aload	0
	iload	4
	iload	7
	iastore
ibranch2:

	iload	4
	sipush	1
	iadd
	istore	4
goto loop1

ibranch1:

	iload	3
	sipush	1
	iadd
	istore	8
	aload	0
	iload	8
	iaload
	istore	7
	aload	0
	iload	8
	aload	0
	iload	2
	iaload
	iastore
	aload	0
	iload	2
	iload	7
	iastore
	iload	8
	sipush	1
	isub
	istore	7
	aload	0
	iload	1
	iload	7
	invokestatic	C2Bytecode/quicksort([III)V
	iload	8
	sipush	1
	iadd
	istore	7
	aload	0
	iload	7
	iload	2
	invokestatic	C2Bytecode/quicksort([III)V
branch1:

	return
.end method

.end class

小结

这篇的代码生成和之前解释器的思路很相似，都是根据AST和对应的产生式来执行或者生成代码。

其实主要的思路是很清晰的，只是其中有太多细节容易让人太过纠结。这个系列算作是我自己的学习笔记，到这也有十三篇了，下一篇可能写写总结就正式结束了。

原文  https://dejavudwh.cn/compiler/从零写一个编译器（十三）.html
正文到此结束
所属分类： 编程技术 Java

热门推荐

相关文章

阿里云首购8折
说给你听

本文目录
随机标签
书籍教程
springboot-demo Java入门教程 bootstrap3 CSS Apache基础教程 php ionic 教程 Python mysql教程 eclipse Ubuntu VPS系统配置 AngularJS 教程 MongoDB教程 Struts2教程 Redis教程 Spring教程 Git教程 Jenkins进阶系列 openfire参考指南 Java设计模式 HBase教程 Maven教程 hibernate教程 Docker 教程 memcached教程 Quartz指南 Hive教程 Ant教程 ANTLR教程 SpringCloud java实例教程 springcloud-demo XStream教程 Hazelcast教程 Elastic-Job-Lite 深入浅出MyBatis SVN教程 ibaties教程 rabittmq教程 solr教程 Hadoop教程 WebService CXF学习 JPA教程 ActiveMQ中文指南 java-demo Java内存模型 dubbo教程 python3-demo Linux入门视频教程
近期评论
  1. 1 Spring Cloud Consul实现选举机制
  2. 2 Spring Boot集成ShedLock实现分布式定时任务
  3. 3 利用oss进行数据库和网站图片备份
  4. 4 Spring Cloud Stream实现数据流处理
  5. 5 Python3访问MySQL数据库快速入门Demo
  6. 6 Github开源项目作者可以免费申请 JetBrains 全家桶
  7. 7 Spring Cloud Vault快速入门Demo
  8. 8 Spring Cloud Gateway快速入门Demo
  9. 9 Spring Cloud Contract快速入门Demo
  10. 10 Spring Cloud Consul快速入门Demo
网站信息
  • 文章总数：82,714 篇
  • 文件总数：284,287 个
  • 标签总数：2,393 个
  • 分类总数：85 个
  • 留言数量：2,560 条
  • 在线人数：640 人
  • 运行天数：4,408天
  • 最后更新：2024年11月21日23点
Loading...

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

[HBLOG]公众号 HBLOG HBLOG