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