java开发C语言编译器：把C实现的快速排序算法编译成jvm字节码

Wesley13
• 阅读 694

有了前面一系列的铺垫和准备后，我们终于能走到至关重要的一刻。在本节，我们将用C语言开发快速排序算法，然后利用我们的编译器把它编译成java字节码，让C语言编写的快速排序算法能在java虚拟机上顺利执行，完成本节内容后，编译器可以正确的将下列代码编译成java字节码：

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]);
    }

}

上面的C代码是根据《算法导论》所编写的实现快速排序的算法，主函数先初始化一个乱序的数组，然后通过调用quicksort函数实现排序。我一直把编译器能够解释编译C语言快速排序的代码作为章节的终点，一来快速排序算法的实现包含了循环，ifelse分支判断，递归等编程语言的关键要素，能正确解释和编译它意味着编译器达到了一定的成熟度。而本节完成后，我们的编译器能正确编译快速排序的C语言实现后，整个编译器实现课程经历两年时光，也该画上句号了。

我们看看代码的实现，这次代码与前面代码的一大不同之处就是函数的递归调用。quicksort函数中会调用它自己，因此编译器在实现时，需要注意这个特点。原来我们实现函数的编译时，编译器会解读代码，直到函数第一次被调用时，才会把被调函数编译成字节码，但这里，被调函数在执行时会调用它自己，如果对原来的逻辑不加处理，那么编译器会反复的为quicksort函数生成代码，陷入到一种死循环的状态。负责函数调用的代码处于UnaryNodeExecutor中，代码修改如下：

case CGrammarInitializer.Unary_LP_RP_TO_Unary:
        case CGrammarInitializer.Unary_LP_ARGS_RP_TO_Unary:
            //先获得函数名
            boolean reEntry = false;
            String funcName = (String)root.getChildren().get(0).getAttribute(ICodeKey.TEXT);
            //change here
            /*
             * 如果函数名被记录过，那表明现在的函数调用其实是递归调用
             */
            if (funcName != "" && funcName.equals(BaseExecutor.funcName)) {
                reEntry = true;
            }


            ArrayList<Object> argList = null;
            ArrayList<Object> symList = null;

            if (production == CGrammarInitializer.Unary_LP_ARGS_RP_TO_Unary) {
                ICodeNode argsNode = root.getChildren().get(1);
                argList = (ArrayList<Object>)argsNode.getAttribute(ICodeKey.VALUE);
                symList = (ArrayList<Object>)argsNode.getAttribute(ICodeKey.SYMBOL);
                FunctionArgumentList.getFunctionArgumentList().setFuncArgList(argList);    
                FunctionArgumentList.getFunctionArgumentList().setFuncArgSymbolList(symList);
            }

            //找到函数执行树头节点
            ICodeNode func = CodeTreeBuilder.getCodeTreeBuilder().getFunctionNodeByName(funcName);
            if (func != null) {
                //change here push parameters before calling function 
                /*
                 * 函数调用时，把当前被调用的函数名记录下来，如果函数体内发送递归调用，那么编译器还会再次进入到
                 * 这里，如果进入时判断到函数名跟我们这里存储的函数名一致，那表明发生了递归调用。
                 */
                BaseExecutor.funcName = funcName;
                int count = 0;
                while (count < argList.size()) {
                    Object objVal = argList.get(count);
                    Object objSym = symList.get(count);
                    if (objSym != null) {
                        Symbol param = (Symbol)objSym;
                        int idx = generator.getLocalVariableIndex(param);
                        if (param.getDeclarator(Declarator.ARRAY) != null) {
                            generator.emit(Instruction.ALOAD, "" + idx);
                        } else {
                            generator.emit(Instruction.ILOAD, ""+idx);
                        }
                    } else {
                        int v = (int)objVal;
                        generator.emit(Instruction.SIPUSH, ""+v);
                    }

                    count++;
                }
                //problem here handle reentry
                if (BaseExecutor.isCompileMode == true && reEntry == false) {
                    /*
                     * 在编译状态下，遇到函数自我递归调用则不需要再次为函数生成代码，只需要生成invoke指令即可
                     */
                    Executor executor = ExecutorFactory.getExecutorFactory().getExecutor(func);
                    ProgramGenerator.getInstance().setInstructionBuffered(true);
                    executor.Execute(func);
                    symbol = (Symbol)root.getChildren().get(0).getAttribute(ICodeKey.SYMBOL);
                    emitReturnInstruction(symbol);
                    ProgramGenerator.getInstance().emitDirective(Directive.END_METHOD);
                    ProgramGenerator.getInstance().setInstructionBuffered(false);
                    ProgramGenerator.getInstance().popFuncName();
                }
                compileFunctionCall(funcName);


                Object returnVal = func.getAttribute(ICodeKey.VALUE);
                if (returnVal != null) {
                    System.out.println("function call with name " + funcName + " has return value that is " + returnVal.toString());
                    root.setAttribute(ICodeKey.VALUE, returnVal);
                }

            } else {
                ClibCall libCall = ClibCall.getInstance();
                if (libCall.isAPICall(funcName)) {
                    Object obj = libCall.invokeAPI(funcName);
                    root.setAttribute(ICodeKey.VALUE, obj);
                } 
            }


            break;

当编译器解析到代码中发生函数调用时，它会把被调函数的名字记录下来，然后判断这个名字是否被记录过，如果前面有过记录，那么这次进入表明函数发生了递归调用，于是就不再执行函数对应的执行树，如果函数是第一次被调用，那么就执行函数对应的执行树，在执行过程中就可以把函数编译成字节码。

除了上面的改动之后，还有不少地方需要相应的修改，具体的调试演示过程请点击‘阅读额原文'查看视频。上面代码完成后，运行编译器，给定的C语言代码编译出的java汇编代码如下：

.class public CSourceToJava
.super java/lang/Object

.method public static main([Ljava/lang/String;)V
    sipush    10
    newarray    int
    astore    1
    sipush    0
    istore    2
    sipush    0
    istore    0
    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    2

loop0:
    iload    2
    sipush    10
if_icmpge branch0
    sipush    10
    iload    2
    isub
    istore    0
    aload    1
    iload    2
    iload    0
    iastore
    aload    1
    iload    2
    iaload
    istore    3
    iload    2
    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    2
    sipush    1
    iadd
    istore    2
goto loop0
branch0:
    aload    1
    sipush    0
    sipush    9
    invokestatic    CSourceToJava/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    2

loop2:
    iload    2
    sipush    10
if_icmpge branch4
    aload    1
    iload    2
    iaload
    istore    3
    iload    2
    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    2
    sipush    1
    iadd
    istore    2
goto loop2
branch4:
    return
.end method
.method public static quicksort([III)V
    sipush    0
    istore    7
    sipush    0
    istore    6
    iload    1
    sipush    1
    isub
    istore    6
    sipush    0
    istore    5
    sipush    0
    istore    4
    sipush    0
    istore    3
    iload    2
    sipush    1
    isub
    istore    3
    iload    1
    iload    2
if_icmpge branch1

    aload    0
    iload    2
    iaload
    istore    7
    iload    1
    istore    5

loop1:

    iload    5
    iload    3
if_icmpgt ibranch1

    aload    0
    iload    5
    iaload
    iload    7
if_icmpgt ibranch2

    iload    6
    sipush    1
    iadd
    istore    6
    aload    0
    iload    6
    iaload
    istore    4
    aload    0
    iload    6
    aload    0
    iload    5
    iaload
    iastore
    aload    0
    iload    5
    iload    4
    iastore
ibranch2:

    iload    5
    sipush    1
    iadd
    istore    5
goto loop1

ibranch1:

    iload    6
    sipush    1
    iadd
    istore    3
    aload    0
    iload    3
    iaload
    istore    4
    aload    0
    iload    3
    aload    0
    iload    2
    iaload
    iastore
    aload    0
    iload    2
    iload    4
    iastore
    iload    3
    sipush    1
    isub
    istore    4
    aload    0
    iload    1
    iload    4
    invokestatic    CSourceToJava/quicksort([III)V
    iload    3
    sipush    1
    iadd
    istore    4
    aload    0
    iload    4
    iload    2
    invokestatic    CSourceToJava/quicksort([III)V
branch1:

    return
.end method

.end class

上面的代码转换成jvm字节码运行后结果如下：
java开发C语言编译器：把C实现的快速排序算法编译成jvm字节码

编译原理几乎是计算机专业中最晦涩难懂的课程。很多学生学这门课只不过是为了通过考试，学完后对编译原理之精妙仍然是摸不着头脑。而很多教这门课的老师，也只不过是混口饭吃，他自己未必对编译原理有多少深入的了解和把握，于是与其昏昏，使人昭昭。毕业多年后，回过头来反省我所承受的教育，我发现我们的教育总是流于表面的肤浅，给学生展示的始终是冰山的一角，对冰山下的巨大形体去置若罔闻，于是整个系统虽然培养出大量的计算机专业人员，但有能力对计算机知识具备深入见解的人凤毛麟角，很多人其实是走上工作岗位后，通过大量的生产实践才开始对计算机知识有了一定程度的深入窥探的，我就是其中之一。

计算机始终是一门理论结合实践的科学。光有理论却不能实践，那么理论看起来晦涩难懂，听起来虚儿巴脑，于是美妙的智慧结晶在应试教育体制下变成了虚张声势的怪兽，让学习它的人惊恐不慌，以为自己要被这只巨大的怪兽所吞灭。我是过来人，知道这种关说不练假把式的巨大危害，那种理论讲起来头头是道，搞得我晕头转向，处处受挫的煎熬感真是不忍回忆，我真心希望通过动手实践，能够让那些有志于在科技行业大展身手的年轻人不要再走我的老路。

如果人类只会谈情说爱，那么早就灭绝了。因此爱的核心在做不在说，科学技术的理解和掌握更是如此，动手吧！Just Fuck It!

java开发C语言编译器：把C实现的快速排序算法编译成jvm字节码

本文分享自微信公众号 - Coding迪斯尼（gh_c9f933e7765d）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。

c语言编译器快速排序字节码stringjvmJavaJava
点赞
收藏
评论区
推荐文章
blmius blmius
•
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时，报错：原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等，这样可以更容易地在不同的环境中使用MySQL。全局s
4133
0
0
helloworld_34035044 helloworld_34035044
•
2年前
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时，如何在新增行里自动增加id呢？能新增整数排序id吗？目前可以在新增行里自动增加id，但只能用uuid函数增加UUID编码，不能新增整数排序id。uuid函数说明：获取一个UUID，可以在填报表中用来创建数据ID语法：uuid()或uuid(sep)参数说明：sep布尔值，生成的uuid中是否包含分隔符''，缺省为
1149
0
0
待兔 待兔
•
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
1072
0
0
Jacquelyn38 Jacquelyn38
•
3年前
2020年前端实用代码段，为你的工作保驾护航
有空的时候，自己总结了几个代码段，在开发中也经常使用，谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
2389
0
0
Stella981 Stella981
•
3年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签，将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
1348
0
0
Easter79 Easter79
•
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中，有一些需要使用全局唯一ID的场景，这种时候为了防止ID冲突可以使用36位的UUID，但是UUID有一些缺点，首先他相对比较长，另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID，并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求，最初Twitter把存储系统从MySQL迁移
1182
0
0
Wesley13 Wesley13
•
3年前
00：Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork)，斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟，已经成为Web应用程序的首选开发语言。Java是简单易学，完全面向对象，安全可靠，与平台无关的编程语言。
1257
0
0
Stella981 Stella981
•
3年前
Docker 部署SpringBoot项目不香吗？
　　公众号改版后文章乱序推荐，希望你可以点击上方“Java进阶架构师”，点击右上角，将我们设为★“星标”！这样才不会错过每日进阶架构文章呀。　　!(http://dingyue.ws.126.net/2020/0920/b00fbfc7j00qgy5xy002kd200qo00hsg00it00cj.jpg)　　2
1077
0
0
Wesley13 Wesley13
•
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
1523
0
0
Python进阶者 Python进阶者
•
10个月前
Excel中这日期老是出来00：00：00，怎么用Pandas把这个去除
大家好，我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下：这日期老是出来00：00：00，怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下：pd.toexcel之前把这
510
0
0
Wesley13
Wesley13
Lv1
最大的安心是自律温柔和爱自己。
文章
1.2w
粉丝
20
获赞
1.7k
热门文章
JavPlayer：AI破坏马赛克，大量马赛克破坏版影片流出
2020年最新可用的磁力搜索引擎&种子搜索网站，持续整理分享
8个在线接收手机短信验证码的免费网络服务整理
IDM 激活破解工具
java.net.ConnectException：Connection timed out：connect 出现连接超时的问题？