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

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

“1+1=2”

“3+4=7”

“2+7=9”

“2*3=6”

“9-6=3”

“8/2=4”

“3+4=7”

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

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

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

2015年就要結束了

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

}

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

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

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

有了這三種抽象對象我們可以寫出對應方法了，我們在parser類里定義三個函數，來代表三種對象的產生過程，并且定義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可以轉換成對應的字面數字
            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();
}

}

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

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

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

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

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

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

代碼生成，將優化過對中間代碼生成機器代碼。

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

OneAPM Mobile Insight 以真實用戶體驗為度量標準進行 Crash 分析，監控網絡請求及網絡錯誤，提升用戶留存。訪問 OneAPM 官方網站感受更多應用性能優化體驗，想閱讀更多技術文章，請訪問 OneAPM 官方技術博客。
本文轉自 OneAPM 官方博客