表達式的計算問題

問題：編寫一個函數，要求輸入一個由０..9, +, -, *, / 和()組成的表達式字元串，計算結果，　如:　(1 + 2 )* 3 , 為簡單起見，不考慮大于１０的整數。

這是一個典型的語言識别問題。１０年前，我有一位同僚，他是IBM AS/400的專家，擅長RPG, CL程式的編寫與維護；他認為“能處理程式的程式”是最高深的程式；當然在AS/400環境下，用RPG來編寫這樣的程式的确是很困難的。但即便是用C, 如果沒有一點編譯理論知識，也會覺得無從入手。

有一種很經典的語言分析方法，叫做遞歸下降法。解決這個問題首先需要把“表達式”精确地定義出來，這些定義稱為文法規則：

表達式(exp)定義為　兩個項(item)的加減，或者帶括号的表達式

　　　　exp : item + item

             ｜item – item

              | item

　　　　　　　     ;

項定義為　因子的乘除

       Item : factor * factor

              | factor / factor

              ｜factor

       Factor : 0..9 | ( exp )

現在為每個規則配上一段解釋代碼(為了簡單起見，部分局部變量及錯誤處理未定義：

　　　int exp()

      {

 i1 = item();

       op_char = current_char();

       next_char();

        if (op_char == ‘+’)

           return i1 + exp();

       else if (op_char == ‘-‘)

           return i1 – exp();

       else

           return i1;

}

item()

{

    f = factor();

op_char = current_char();

next_char();

if (op_char == ‘*’)

    Return f * factor();

Else if (op_char == ‘/’)

Else

    Return f;

factor()

    c = current_char();

    next_char();

    If (c == ‘(‘)

        return exp();

    else

       return c – ‘0’;

這裡由３個函數，分别是exp(), item()與factor(), 分别對應上面的３個文法規則。還有兩個輔助函數，　current_char表示目前的字元，　next_char把指針向下撥一次。這裡忽略了實際應用中必須的錯誤檢查。

看上去很簡單，但是對于SQL這樣的語言，遞歸下降分析法并不适用。對文法的任何修改，都需要小心地修改分析函數，更讓人頭疼的是，有些文法規則并不能消除左遞歸，進而寫不出簡單的遞歸函數。