摘要：考慮這樣一個(gè)問(wèn)題，給定一個(gè)字符串，，如何將它轉(zhuǎn)化為如下形式換句話說(shuō)，就是如何將字符串按照四則運(yùn)算計(jì)算出來(lái)，如何寫(xiě)一個(gè)計(jì)算器。語(yǔ)義分析使用語(yǔ)法樹(shù)檢查源程序是否和語(yǔ)言定義的語(yǔ)義一致。

考慮這樣一個(gè)問(wèn)題，給定一個(gè)字符串，“1+1+(3+4)-2*3+8/2”，如何將它轉(zhuǎn)化為如下形式：

“1+1=2”

“3+4=7”

“2+7=9”

“2*3=6”

“9-6=3”

“8/2=4”

“3+4=7”

換句話說(shuō)，就是如何將字符串按照四則運(yùn)算計(jì)算出來(lái)，如何寫(xiě)一個(gè)計(jì)算器。

拿 java 來(lái)舉例，并且為了簡(jiǎn)單，我們只考慮個(gè)位數(shù)。這個(gè)過(guò)程大概分為這幾個(gè)步驟，首先需要掃描字符串去除空白字符，其次將各個(gè)字符轉(zhuǎn)換成對(duì)應(yīng)的操作符或操作數(shù)，然后按照四則運(yùn)算規(guī)則逐次計(jì)算并輸出。

好，我們首先構(gòu)造一個(gè) scanner，它主要功能是順序掃描字符串，返回字符并跳過(guò)其中的空白字符，如下

2015年就要結(jié)束了

public class Scanner {

    public Scanner(String source){
       this.source = source.toCharArray();
    }

    private char[] source;
    private int index = 0;
    private static char END = "
";
    public char getNext(){
        char result;

        do{
            if (index >= source.length){
                return END;
            }
            result = source[index];
            index += 1;
        }while (Character.isWhitespace(result));

        return result;
    }

}

在進(jìn)行下一步之前，讓我們思考一下這個(gè)算式的規(guī)律，算式中存在兩種對(duì)象，一種是數(shù)字，一種是操作符，由于存在運(yùn)算的優(yōu)先級(jí)，我們分成三種對(duì)象，并用下面的形式來(lái)說(shuō)明。

expr —> term + expr | term - expr | term
term —> factor * term | factor/term | factor
factor—> digit ｜(expr)

—>的意思是由...組成，｜ 代表或關(guān)系，expr 代表加減法運(yùn)算式，term 代表乘除法運(yùn)算式，factor 代表操作的最小元素，最后一句的意思就是 factor 由數(shù)字或者帶括號(hào)的 expr 組成。這三個(gè)定義式是遞歸的，它可以代表任意深度的算式。讓我們用樹(shù)的形式來(lái)觀察一下：

有了這三種抽象對(duì)象我們可以寫(xiě)出對(duì)應(yīng)方法了，我們?cè)趐arser類(lèi)里定義三個(gè)函數(shù)，來(lái)代表三種對(duì)象的產(chǎn)生過(guò)程，并且定義char類(lèi)型變量head代表正在被掃描的字符。

public class Parser {
    private Scanner scanner;
    public Parser(Scanner scanner){
        this.scanner = scanner;
    }

    private char head;

    public void parse(){
        if (Scanner.END != (head = scanner.getNext())){
            expr();
        }
        if (head != Scanner.END){
            throw new RuntimeException(“syntax error at "+head);
        }
    }

    public int expr(){
        int result = term();
        int tempResult;
        char operate;
        while ((operate = head) == "+" || operate == "-") {
            head = scanner.getNext();
            tempResult = term();
            switch (operate) {
                case "+":
                    System.out.println(result + "+" + tempResult + "=" + (result + tempResult));
                    result += tempResult;
                    break;
                case "-":
                    System.out.println(result + "-" + tempResult + "=" + (result - tempResult));
                    result -= tempResult;
            }
        }
        return result;
    }
    public int term(){
        int result = factor();
        int tempResult;
        char operate ;
        while ((operate=head) == "*" ||operate == "/") {
            head = scanner.getNext();
            tempResult = factor();
            switch (operate) {
                case "*":
                    System.out.println(result + "*" + tempResult + "=" + (result * tempResult));
                    result *= tempResult;
                    break;
                case "/":
                    System.out.println(result + "/" + tempResult + "=" + (result / tempResult));
                    result /= tempResult;
            }
        }
        return result;
    }

    public int factor(){
        int factor;

        if (Character.isDigit(head)){
            factor = head - 48; //字符變量－48可以轉(zhuǎn)換成對(duì)應(yīng)的字面數(shù)字
            head = scanner.getNext();
        } else {
            match("(");
            factor = expr();
            match(")");

        }
        return factor;
    }

//match 方法用來(lái)斷言 head 是什么字符，如果為真，將讀取下一個(gè)字符賦值給 head

public boolean match(char symbol){
    if (symbol == head){
        head = scanner.getNext();
        return true;
    }
    throw new  RuntimeException("syntax error at "+head);
}

public static void main(String... args){
    Scanner scanner = new Scanner("1+1+(3+4)-2*3+8/2");
    Parser parser = new Parser(scanner);
    parser.parse();
}

}

如果回過(guò)頭來(lái)重新考慮這件事情，你會(huì)發(fā)現(xiàn)我們這個(gè)小程序的本質(zhì)是將一段文本轉(zhuǎn)化成可以執(zhí)行的程序，正如我們的編譯器一樣。而實(shí)際上編譯器要復(fù)雜的多，它的基本工作過(guò)程可以分為幾個(gè)步驟：

詞法分析 (scanning)，讀入源程序字符流，將字符轉(zhuǎn)換成有意義的詞素 (lexeme) 的序列，并生成對(duì)應(yīng)的詞法單元 (token)

語(yǔ)法分析 (parsing)，主要目的是生成詞法單元的語(yǔ)法結(jié)構(gòu),一般會(huì)使用樹(shù)形結(jié)構(gòu)來(lái)表示，稱(chēng)為語(yǔ)法樹(shù)。

語(yǔ)義分析 (semantic analysis),使用語(yǔ)法樹(shù)檢查源程序是否和語(yǔ)言定義的語(yǔ)義一致。其中一個(gè)重要部分是類(lèi)型檢查。

生成中間代碼，語(yǔ)義分析完成后，編譯器會(huì)將語(yǔ)法樹(shù)生成為一種接近機(jī)器語(yǔ)言的中間代碼。我們程序最后產(chǎn)生的一系列小的表達(dá)式與之類(lèi)似。

代碼優(yōu)化，編譯器會(huì)嘗試改進(jìn)中間代碼，用以生成更高效的機(jī)器代碼。

代碼生成，將優(yōu)化過(guò)對(duì)中間代碼生成機(jī)器代碼。

在這些過(guò)程中，遞歸的方法起到了非常重要的作用，有一句話說(shuō)明了編譯器的本質(zhì)，編譯器就是讓你的源程序變成可執(zhí)行程序的另一個(gè)程序。你會(huì)發(fā)現(xiàn)這個(gè)定義本身就是遞歸的。透過(guò)這些編譯原理，可以讓我們更加深入的理解編程語(yǔ)言，甚至發(fā)明一種編程語(yǔ)言。

OneAPM Mobile Insight 以真實(shí)用戶(hù)體驗(yàn)為度量標(biāo)準(zhǔn)進(jìn)行 Crash 分析，監(jiān)控網(wǎng)絡(luò)請(qǐng)求及網(wǎng)絡(luò)錯(cuò)誤，提升用戶(hù)留存。訪問(wèn) OneAPM 官方網(wǎng)站感受更多應(yīng)用性能優(yōu)化體驗(yàn)，想閱讀更多技術(shù)文章，請(qǐng)?jiān)L問(wèn) OneAPM 官方技術(shù)博客。
本文轉(zhuǎn)自 OneAPM 官方博客