java開發(fā)C語言編譯器：把C實(shí)現(xiàn)的快速排序算法編譯成jvm字節(jié)碼

有了前面一系列的鋪墊和準(zhǔn)備后，我們終于能走到至關(guān)重要的一刻。在本節(jié)超凳，我們將用C語言開發(fā)快速排序算法钞澳，然后利用我們的編譯器把它編譯成java字節(jié)碼怠惶，讓C語言編寫的快速排序算法能在java虛擬機(jī)上順利執(zhí)行，完成本節(jié)內(nèi)容后轧粟，編譯器可以正確的將下列代碼編譯成java字節(jié)碼：


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代碼是根據(jù)《算法導(dǎo)論》所編寫的實(shí)現(xiàn)快速排序的算法策治，主函數(shù)先初始化一個(gè)亂序的數(shù)組，然后通過調(diào)用quicksort函數(shù)實(shí)現(xiàn)排序兰吟。我一直把編譯器能夠解釋編譯C語言快速排序的代碼作為章節(jié)的終點(diǎn)通惫，一來快速排序算法的實(shí)現(xiàn)包含了循環(huán)，ifelse分支判斷混蔼，遞歸等編程語言的關(guān)鍵要素履腋，能正確解釋和編譯它意味著編譯器達(dá)到了一定的成熟度。而本節(jié)完成后，我們的編譯器能正確編譯快速排序的C語言實(shí)現(xiàn)后遵湖，整個(gè)編譯器實(shí)現(xiàn)課程經(jīng)歷兩年時(shí)光悔政，也該畫上句號(hào)了。

我們看看代碼的實(shí)現(xiàn)奄侠，這次代碼與前面代碼的一大不同之處就是函數(shù)的遞歸調(diào)用卓箫。quicksort函數(shù)中會(huì)調(diào)用它自己，因此編譯器在實(shí)現(xiàn)時(shí)垄潮，需要注意這個(gè)特點(diǎn)烹卒。原來我們實(shí)現(xiàn)函數(shù)的編譯時(shí)，編譯器會(huì)解讀代碼弯洗，直到函數(shù)第一次被調(diào)用時(shí)旅急，才會(huì)把被調(diào)函數(shù)編譯成字節(jié)碼，但這里牡整，被調(diào)函數(shù)在執(zhí)行時(shí)會(huì)調(diào)用它自己藐吮，如果對原來的邏輯不加處理，那么編譯器會(huì)反復(fù)的為quicksort函數(shù)生成代碼逃贝，陷入到一種死循環(huán)的狀態(tài)谣辞。負(fù)責(zé)函數(shù)調(diào)用的代碼處于UnaryNodeExecutor中，代碼修改如下：

case CGrammarInitializer.Unary_LP_RP_TO_Unary:
        case CGrammarInitializer.Unary_LP_ARGS_RP_TO_Unary:
            //先獲得函數(shù)名
            boolean reEntry = false;
            String funcName = (String)root.getChildren().get(0).getAttribute(ICodeKey.TEXT);
            //change here
            /*
             * 如果函數(shù)名被記錄過沐扳，那表明現(xiàn)在的函數(shù)調(diào)用其實(shí)是遞歸調(diào)用
             */
            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);
            }
            
            //找到函數(shù)執(zhí)行樹頭節(jié)點(diǎn)
            ICodeNode func = CodeTreeBuilder.getCodeTreeBuilder().getFunctionNodeByName(funcName);
            if (func != null) {
                //change here push parameters before calling function 
                /*
                 * 函數(shù)調(diào)用時(shí)泥从，把當(dāng)前被調(diào)用的函數(shù)名記錄下來，如果函數(shù)體內(nèi)發(fā)送遞歸調(diào)用沪摄，那么編譯器還會(huì)再次進(jìn)入到
                 * 這里躯嫉，如果進(jìn)入時(shí)判斷到函數(shù)名跟我們這里存儲(chǔ)的函數(shù)名一致，那表明發(fā)生了遞歸調(diào)用杨拐。
                 */
                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) {
                    /*
                     * 在編譯狀態(tài)下祈餐，遇到函數(shù)自我遞歸調(diào)用則不需要再次為函數(shù)生成代碼，只需要生成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;

當(dāng)編譯器解析到代碼中發(fā)生函數(shù)調(diào)用時(shí)哄陶，它會(huì)把被調(diào)函數(shù)的名字記錄下來帆阳，然后判斷這個(gè)名字是否被記錄過，如果前面有過記錄屋吨，那么這次進(jìn)入表明函數(shù)發(fā)生了遞歸調(diào)用蜒谤，于是就不再執(zhí)行函數(shù)對應(yīng)的執(zhí)行樹，如果函數(shù)是第一次被調(diào)用离赫，那么就執(zhí)行函數(shù)對應(yīng)的執(zhí)行樹芭逝，在執(zhí)行過程中就可以把函數(shù)編譯成字節(jié)碼。

除了上面的改動(dòng)之后渊胸，還有不少地方需要相應(yīng)的修改旬盯，具體的調(diào)試演示過程請參看視頻用java開發(fā)C語言編譯器。上面代碼完成后，運(yùn)行編譯器胖翰，給定的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

上面的代碼轉(zhuǎn)換成jvm字節(jié)碼運(yùn)行后結(jié)果如下：

這里寫圖片描述

編譯原理幾乎是計(jì)算機(jī)專業(yè)中最晦澀難懂的課程接剩。很多學(xué)生學(xué)這門課只不過是為了通過考試，學(xué)完后對編譯原理之精妙仍然是摸不著頭腦萨咳。而很多教這門課的老師懊缺，也只不過是混口飯吃，他自己未必對編譯原理有多少深入的了解和把握培他，于是與其昏昏鹃两，使人昭昭。畢業(yè)多年后舀凛，回過頭來反省我所承受的教育俊扳，我發(fā)現(xiàn)我們的教育總是流于表面的膚淺，給學(xué)生展示的始終是冰山的一角猛遍，對冰山下的巨大形體去置若罔聞馋记，于是整個(gè)系統(tǒng)雖然培養(yǎng)出大量的計(jì)算機(jī)專業(yè)人員，但有能力對計(jì)算機(jī)知識(shí)具備深入見解的人鳳毛麟角懊烤，很多人其實(shí)是走上工作崗位后梯醒，通過大量的生產(chǎn)實(shí)踐才開始對計(jì)算機(jī)知識(shí)有了一定程度的深入窺探的，我就是其中之一腌紧。

計(jì)算機(jī)始終是一門理論結(jié)合實(shí)踐的科學(xué)茸习。光有理論卻不能實(shí)踐，那么理論看起來晦澀難懂寄啼，聽起來虛兒巴腦逮光，于是美妙的智慧結(jié)晶在應(yīng)試教育體制下變成了虛張聲勢的怪獸代箭，讓學(xué)習(xí)它的人驚恐不慌墩划，以為自己要被這只巨大的怪獸所吞滅。我是過來人嗡综，知道這種關(guān)說不練假把式的巨大危害乙帮，那種理論講起來頭頭是道，搞得我暈頭轉(zhuǎn)向极景，處處受挫的煎熬感真是不忍回憶察净，我真心希望通過動(dòng)手實(shí)踐，能夠讓那些有志于在科技行業(yè)大展身手的年輕人不要再走我的老路盼樟。

如果人類只會(huì)談情說愛氢卡，那么早就滅絕了。因此愛的核心在做不在說晨缴，科學(xué)技術(shù)的理解和掌握更是如此译秦，動(dòng)手吧！Just Fuck It!

更多技術(shù)信息，包括操作系統(tǒng)筑悴，編譯器们拙，面試算法，機(jī)器學(xué)習(xí)阁吝，人工智能砚婆，請關(guān)照我的公眾號(hào)：

這里寫圖片描述

最后編輯于：2017.12.11 06:53:43

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市突勇，隨后出現(xiàn)的幾起案子装盯，更是在濱河造成了極大的恐慌，老刑警劉巖甲馋，帶你破解...
沈念sama閱讀 211,948評論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件验夯，死亡現(xiàn)場離奇詭異，居然都是意外死亡摔刁，警方通過查閱死者的電腦和手機(jī)挥转，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,371評論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來共屈，“玉大人绑谣，你說我怎么就攤上這事∞忠” “怎么了借宵？”我有些...
開封第一講書人閱讀 157,490評論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長矾削。經(jīng)常有香客問我壤玫，道長，這世上最難降的妖魔是什么哼凯？我笑而不...
開封第一講書人閱讀 56,521評論 1贊 284
?港島之戀（遺憾婚禮）
正文為了忘掉前任欲间，我火速辦了婚禮，結(jié)果婚禮上断部，老公的妹妹穿的比我還像新娘猎贴。我一直安慰自己，他們只是感情好蝴光，可當(dāng)我...
茶點(diǎn)故事閱讀 65,627評論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布她渴。她就那樣靜靜地躺著，像睡著了一般蔑祟。火紅的嫁衣襯著肌膚如雪趁耗。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,842評論 1贊 290
城市分裂傳說
那天疆虚，我揣著相機(jī)與錄音苛败，去河邊找鬼右冻。笑死，一個(gè)胖子當(dāng)著我的面吹牛著拭，可吹牛的內(nèi)容都是我干的纱扭。我是一名探鬼主播，決...
沈念sama閱讀 38,997評論 3贊 408
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼儡遮，長吁一口氣：“原來是場噩夢啊……” “哼乳蛾！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起鄙币，我...
開封第一講書人閱讀 37,741評論 0贊 268
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤肃叶，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后十嘿，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體因惭，經(jīng)...
沈念sama閱讀 44,203評論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,534評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年绩衷，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了蹦魔。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,673評論 1贊 341
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡咳燕，死狀恐怖勿决，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情招盲，我是刑警寧澤低缩，帶...
沈念sama閱讀 34,339評論 4贊 330
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站曹货，受9級特大地震影響咆繁，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜顶籽，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,955評論 3贊 313
男人毒藥：我在死后第九天來索命
文/蒙蒙一玩般、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧蜕衡，春花似錦壤短、人聲如沸设拟。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,770評論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽纳胧。三九已至镰吆，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間跑慕，已是汗流浹背万皿。一陣腳步聲響...
開封第一講書人閱讀 32,000評論 1贊 266
情欲美人皮
我被黑心中介騙來泰國打工摧找，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人牢硅。一個(gè)月前我還...
沈念sama閱讀 46,394評論 2贊 360
代替公主和親
正文我出身青樓蹬耘，卻偏偏與公主長得像，于是被迫代替她去往敵國和親减余。傳聞我的和親對象是個(gè)殘疾皇子综苔，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,562評論 2贊 349

java開發(fā)C語言編譯器：把C實(shí)現(xiàn)的快速排序算法編譯成jvm字節(jié)碼

推薦閱讀更多精彩內(nèi)容