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

考慮這樣一個問題，給定一個字符串，“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”

換句話說，就是如何將字符串按照四則運算計算出來，如何寫一個計算器。

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

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

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

}

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

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

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

有了這三種抽象對象我們可以寫出對應(yīng)方法了，我們在parser類里定義三個函數(shù)，來代表三種對象的產(chǎn)生過程，并且定義char類型變量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)換成對應(yīng)的字面數(shù)字
            head = scanner.getNext();
        } else {
            match("(");
            factor = expr();
            match(")");

        }
        return factor;
    }

//match 方法用來斷言 head 是什么字符，如果為真，將讀取下一個字符賦值給 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();
}

}

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

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

語法分析 (parsing)，主要目的是生成詞法單元的語法結(jié)構(gòu),一般會使用樹形結(jié)構(gòu)來表示，稱為語法樹。

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

生成中間代碼，語義分析完成后，編譯器會將語法樹生成為一種接近機器語言的中間代碼。我們程序最后產(chǎn)生的一系列小的表達式與之類似。

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

代碼生成，將優(yōu)化過對中間代碼生成機器代碼。

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

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