前言
文法分析中最重要算法是
LL自頂向下和LR自底向上算法.前面幾篇文章主要講解的是LL算法的理論和一個LL算法的文法分析器javacc.本文以LL(1)算法中最簡單的一種形式遞歸下降算法來分析常規算法問題中的數學表達式問題.同時,本文也介紹手工構造EBNF文法的分析器代碼普遍方法.希望本文的實踐能對大家實現自己的語法分析器帶來幫助.
數學表達式問題
在學習算法的時候,四則混合運算的表達式處理是個很經典的算法問題.
比如這里有個數學表達式”122+2*(11-1)/(3-(2-0))”.我們需要根據這個字符串的描述,然后計算出其結果.
Input:
122+2*(11-1)/(3-(2-0))
Output:
142
四則混合運算中還需要考慮到括號,乘除號與加減號的優先運算問題,通常的解決辦法就是使用堆棧.那種常規的算法和LL算法有異曲同工之處,更或者說,那么的算法其實是一樣的.
傳統數學表達式處理算法簡介
這個傳統算法其實不知不覺地使用LL(1)算法的精髓.它就是主要依靠棧式的數據結構分別保存數和符號,然后根據運算符號的優先級別進行數學計算,并將結果保存在棧里面.
傳統算法中使用了兩個棧.一個是保存數值,暫時就叫值棧. 另一個是保存符號的,叫符號棧.我們規定一個記號#,來表示棧底.下面我們就來看看如何計算一個簡單的表達式11+2-8*(5-3).
為了顯示整個計算過程,我們以下面這個棧的變化圖來表示.
符號棧和值棧的變化是根據輸入串來進行的
.基本上棧的操作可以簡單用下面幾句話來說.
Start:
1.
????
如果當前輸入串中得到的是數字,則直接壓入值棧.然后轉到Start.
2.
????
如果當前輸入串中得到的是符號
,那么對符號進行判斷.
1)如果符號是’+’或者’-‘,則依次彈出符號棧的符號,計算棧中數值,直到彈出的符號不是*,/,+,-.
2)如果符號是’*’或者’/’,則壓入符號棧
3)如果符號是’(‘,則直接壓’(‘入符號棧
4)如果符號是’)’,則依照符號棧的順序彈出符號,計算棧中數值,把結果壓入值棧,直到符號棧頂是’(‘,最后再彈出’(‘ .
最后轉到Start.
3.????
如果當前輸入串得到的是EOF(字符串結束符號),則計算棧中數值,知道符號棧沒有符號.
語法分析數學表達式
或者可能你以前運用過自己的辦法來解決過這個程序問題,不過下面我們將通過編譯原理建立的一套文法分析理論,來十分精彩地解決這個算法問題.
首先是建立數學表達式的文法EBNF.EBNF文法可以更靈活地表示BNF,是BNF范式文法的一種擴展.下面是上一篇javacc的介紹中使用到的計算表達式的文法.
Expression
-> Term{ Addop Term }
Addop -> "+" | "-"
Term -> Factor { Mulop Factor }
Mulop -> "*" | "/"
Factor -> ID | NUM | "("Expression")"
我們來看看如何根據這個EBNF文法實現一個遞歸下降的分析程序.大致上來說要分那么幾步來實現.(注意,下面的幾個步驟不光是針對本節的數學表達式問題,而是包含所有通常的遞歸下降文法分析器的實現)
語法分析實現
1.
???
Step 建立詞法分析
本系列文章開篇第一節就是講的詞法分析相關問題.因為詞法分析是語法分析的前提,那么我們在實現遞歸下降算法的時候,同樣應該把詞法分析的實現考慮進去.
本文要處理只是個數學表達式的問題,那么通過上面的文法,可以看到需要識別的詞法無非就是2個ID,NUM和4個運算符號’+’’-‘‘*’’/’以及2個括號’(‘‘(‘.本文沒有對詞法分析的自動機原理進行講解,這部分內容應該在編譯原理中講得比較透徹.所謂自動機,就是按一定步驟識別每個字符的算法.可以用下面的幾個圖來表示ID和NUM的識別自動機(識別步驟或算法)
NUM:
基本算法就是,如果輸入的字符是digit(‘0’-‘9’),那么進入check循環,如果輸入還是digit,那么再跳回循環查看,如果輸入是other(不是’0’-‘9’),那么就直接accept,接收這個串為NUM類型的TOKEN.
ID:
同NUM一樣,當輸入的是letter,那么進入ID的有限自動機.只是在進入check循環后,有兩種可能都繼續留在循環,那就是digit和letter(‘a’-‘Z’).當輸入既不是digit,也不是letter的時候,就跳出check循環,進入accept,把接收到的字符歸結成ID類型的TOKEN.
通過這個有限自動機的圖示,我們就很容易寫出詞法分析程序
.
不過在此之前,我們得寫出識別letter和digit的代碼.我們建立兩個函數IsLetter和IsDigit來完成這個功能.
int IsLetter(char ch)
{
??? if(ch >= 'A' && ch <= 'Z')
??????? return 1;
??? if(ch >='a' && ch <='z')
??????? return 1;
??? return 0;
}
int IsDigit(char ch)
{
??? if(ch >= '0' && ch <='9')
??????? return 1;
??? return 0;
}
有個這兩個輔助函數,那么接下來,我們就直接寫gettoken詞法分析函數,它的功能就是從輸入中分析,得到一個一個的token.我們首先定義token的類型.
#define
ID ?1
#define
NUM 2
#define
PLUS ??3 // ‘+’
#define
MINUS ?4 // ‘-‘
#define
TIMERS 5 // ‘*’
#define
OVER ??6 // ‘/’
#define
LPAREN 7 // ‘(‘
#define
RPAREN 8 // ‘)’
#define
ERROR 255
上面注釋已經說符號token代表的意思,我也不再多說.不過需要注意的是,這里我們定義了個ERROR的常量,但是我們這里并沒有ERROR的token,它只是為我們后面處理結果時候的一個錯誤處理信息的定義.
char token[10];
char *nextchar;
const char g_strCalculate[]="122+2*(11-1)/(3-(2-0))";
我們需要定義token記號和一個指到輸入串的指針.token記錄的就是當前gettoken()得到的token的text(字符串).nextchar是當前指到輸入串的指針.最后,我們隨便定義一個要分析的數學表達式的輸入串g_strCalculate.
int gettoken()
{
??? char *ptoken =token;
??? while(*nextchar == ' ' || *nextchar=='\n' || *nextchar=='\t')
??????? nextchar++;
??? switch(*nextchar)
??? {
??? case '+': nextchar++; return PLUS;
??? case '-': nextchar++; return MINUS;
??? case '*': nextchar++; return TIMERS;
??? case '/': nextchar++; return OVER;
??? case '(': nextchar++; return LPAREN;
??? case ')': nextchar++; return RPAREN;
??? default: break;
??? }
???
// ID的詞法識別分析
??? if(IsLetter(*nextchar))
??? {
???????? while(IsLetter(*nextchar) || IsDigit(*nextchar))
???????? {
????????????????? *ptoken = *nextchar;
????????????????? nextchar++;
????????????????? ptoken++;
???????? }
???????? *ptoken ='\0';
???????? printf("gettoken: token = %s\n",token);
???????? return ID;
}
// NUM的詞法識別分析
??? if(IsDigit(*nextchar))
??? {
??????? while(IsDigit(*nextchar))
??????? {
?????????????? *ptoken = *nextchar;
?????????????? nextchar++;
?????????????? ptoken++;
??????? }
??????? *ptoken ='\0';
??????? printf("gettoken: token = %s\n",token);
??????? return NUM;
??? }
??? return ERROR;
}
代碼很簡單,我沒有寫多少任何注釋.函數中,首先使用了char *ptoken記錄token的首地址,它為后面的字符串復制(構造token)所用.同時,在處理代碼的第一部分是過濾掉空格,制表符和換行符.然后是計算符號的詞法分析.計算符號就是一個固定的字符號,所以它的識別很簡單,直接用switch來判斷*nextchar.而后面的ID,NUM的識別就是完全按照前面的有限自動機表示圖表來進行編寫的.以ID的圖表來說,ID的自動機首先是要識別出第一個字符是letter,那么我就寫了第一行if(IsLetter(*nextchar)),如果滿足,則進入check循環,也就是while(IsLetter(*nextchar) || IsDigit(*nextchar))循環.循環中我們記錄了*nextchar到token符號中.最后跳出check循環,進入accept,在代碼中return ID.對于NUM的詞法識別也是如此的,我就不多說了.
2.
???
根據EBNF文法建立文法識別函數
首先看到第一條非終結產生式
Expression
-> Term{ Addop Term }
Expression
也是我們總的輸入結果函數
.
我們先定義函數
int Expression(),
其返回值就是我們要處理的表達式的值
.
右邊的產生式中
,
第一個是
Term,
我們就直接調用
Term
函數完成
.
然后是
0
到無限次的
Addop Term,
那么用一個循環即可
.
文法中使用非終結符號
Addop.
程序代碼中我沒有特別為此非終結符號創建函數
.
我們直接在代碼以
’+’ || ‘-‘
代替
Addop.
代碼如下
.
int expression()
{
??? int temp = term(); // 對應文法中的第一個Term
int tokentype;
??? while(*nextchar == '+' || *nextchar == '-') // 對應文法中的{ Addop Term }
??? {
??????? tokentype = gettoken();
??????? switch(tokentype)
??????? {
??????? case PLUS:
??????????????? temp +=term();
??????????????? break;
??????? case MINUS:
??????????????? temp -=term();
??????????????? break;
??????? default:
??????????????? break;
??????? }
??? }
??? return temp;
}
然后是第二條文法.同樣,我也沒有特別為Mulop特別寫一個文法函數,而是直接以’*’|| ‘\’代替.
Term
-> Factor { Mulop Factor }
同理
,
建立如下函數
int term()
{
??? int temp;
??? int tokentype;
??? temp = factor(); // 對應文法中的Factor