沒想到這一系列文件能得到csdn和大家的這么看好,首先要感謝大家的賞識(shí)和csdn的推薦.那么我就更沒有理由不寫好這下面的幾篇文章了.本來我的計(jì)劃是簡(jiǎn)單把lex和yacc介紹完后就直接進(jìn)入編譯器的構(gòu)造的技術(shù)細(xì)節(jié)問題討論,但是最近看了一些國(guó)外經(jīng)典教材后,發(fā)現(xiàn)文法的識(shí)別問題在編譯原理和技術(shù)中是個(gè)絕不能忽視的問題.即使現(xiàn)在有了yacc工具來幫助我來識(shí)別文法,但是有些時(shí)候還是需要我們自己來寫簡(jiǎn)單的語法分析器.
1.什么是文法識(shí)別(語法分析)
首先要告訴大家的是,這里的文法識(shí)別是指的上下文無關(guān)的文法,也就是上一節(jié)我們一直在討論的那些 BNF式.
比如說,我寫了一句
if (a>6+5) printf(“OK!”); else printf(“No!”);
那么它匹配的文法也就是
if-stmt -> if expr stmt
???????? | if expr stmt else stmt
我們通常要為一個(gè)程序語言寫出很多BNF式的文法,怎么知道這句話是匹配的哪個(gè)文法,這就是語法分析器(或者叫文法分析器要做的工作).知道了是那句文法后,我們才能對(duì)這句話做出正確的解釋,所以文法識(shí)別是個(gè)不可忽視的工作.下面我來看看我們常使用的文法識(shí)別的算法.
2.自頂向下的算法(LL算法)
自頂向下的語法分析算法是十分簡(jiǎn)單的.自頂向下的算法也叫LL算法.LL(k)就是向前預(yù)測(cè)k個(gè)符號(hào)的自頂向下的算法.不過無論是我們國(guó)內(nèi)的編譯教程還是國(guó)外的經(jīng)典教程都是只討論了LL(1)算法.因?yàn)橐话愕某绦蛘Z言,只使用LL(1)算法就已經(jīng)足夠了.這里我們同樣也只是討論LL(1)算法.
其中有種特殊的算法叫做遞歸下降的算法,在C語言中,由于函數(shù)本身是可以遞歸的,所以實(shí)現(xiàn)這種算法就只需要寫簡(jiǎn)單的幾個(gè)函數(shù)的遞歸過程就是了.
為什么叫自頂向下呢?因?yàn)樵诜治鲞^程中,我們是從語法樹的樹頂逐步向樹底分析的,所以叫自頂向下的算法.
為了方便說明自頂向下算法的簡(jiǎn)單性,我們來看一下<<Compilers Principles,Techniques,and Tools>>中的一個(gè)例子.(本系列文章經(jīng)常要引用國(guó)外經(jīng)典著作的范例,希望大家不要告我抄襲,我實(shí)在找不到比大師的范例更經(jīng)典的范例了)
例4.1
考慮一個(gè)Pascal中定義變量的文法.
特別說明,這里的dotdot表示”..”
type
-> simple | id | array [ simple ] oftype
simple ->
integer
|char| num dotdot num
在為array[ num dotdot num] of integer構(gòu)造一個(gè)分析數(shù)的時(shí)候,該算法就是從根結(jié)點(diǎn)開始.
下面我們通過其中主要的三個(gè)步驟來看看算法的實(shí)現(xiàn)原理.
第一步分析:
__________________________________________________________________________________
首先分析的是輸入的字符串第一個(gè)串”array”,判斷出它屬于type的First集合.所以在圖中的分析樹部分,我們的當(dāng)前分析就是樹根結(jié)點(diǎn)type.(圖中標(biāo)上箭頭,就表示是當(dāng)前正在分析的部分).
這里遇到一個(gè)新名詞:First集合.在大學(xué)里的編譯課程肯定是講過First集合的吧.不過我還是要在這里重復(fù)一次了.
名詞解釋First集合:
在對(duì)文法產(chǎn)生式進(jìn)行判斷的時(shí)候,每個(gè)產(chǎn)生式都是由好幾個(gè)終結(jié)符和非終結(jié)符構(gòu)成.比如
本例中的文法
type
-> simple
| id
| array [ simple ] oftype
simple ->
integer
|char
| num dotdot num
判斷type的產(chǎn)生式的時(shí)候,如果我們把每個(gè)產(chǎn)生式里面的simple,id,array, [ ,simple ,] , of , type這些終結(jié)符和非終結(jié)符都進(jìn)行判斷的話,那么就會(huì)涉及到”試驗(yàn)和錯(cuò)誤”的問題.當(dāng)一個(gè)文法產(chǎn)生式分析到最后,發(fā)現(xiàn)并不匹配,就必然會(huì)產(chǎn)生回溯的問題,就要回到頭,從新開始對(duì)第二個(gè)產(chǎn)生式逐步進(jìn)行判斷分析.我們知道,回溯的算法效率肯定是十分低效率的.但是實(shí)際上我們完全可以避免這種回溯算法,而完成同樣工作的文法分析.這就產(chǎn)生了計(jì)算First集合的理論和以及后面的左提公因式的問題.
First集合簡(jiǎn)單地說,就是一個(gè)非終結(jié)符的最開頭的字符串(終結(jié)符號(hào))的集合.比如說.
First(simple) = { integer, char, num }
First(type) = First(simple) U { id, array }
這里的type的一個(gè)產(chǎn)生式中有個(gè)simple非終結(jié)符在其開頭,那么simple的開頭字符串同時(shí)也可以是simple,所以First(simple)也是First(type)的一部分.
為什么我們只計(jì)算每個(gè)非終結(jié)符的最開頭的終結(jié)符? 因?yàn)槲覀冞@里是考慮的LL(1)算法,LL(1)算法只向前預(yù)測(cè)一個(gè)字符號(hào),所以我們只考慮一個(gè)First集合就可以判斷出是哪個(gè)文法產(chǎn)生式了.
這里聽起來似乎有些不太可能,一個(gè)產(chǎn)生式有那么千百萬化,如果單單只看第一個(gè)非終結(jié)符號(hào),如果就能說明一個(gè)輸入串到底是哪個(gè)產(chǎn)生式呢? 如果有兩個(gè)產(chǎn)生式的最開頭一樣怎么辦,比如像if語句,那怎么辦? 但其實(shí)我們幾乎所有的程序語言的文法都可以通過LL(1)來分析出來.原因是我們可以通過左提公因式來把最開頭的相同的產(chǎn)生式的公共終結(jié)符號(hào)提取出來,留下兩個(gè)子產(chǎn)生式,而他們的最開頭的非終結(jié)符號(hào)不相同.
左提公因式:
例4.2
考慮文法
A
-> ab
|ac
這里,A的兩個(gè)產(chǎn)生式中最開頭的終結(jié)符號(hào)都是’a’,那么就無法通過這個(gè)最開頭的終結(jié)符號(hào)來判斷一個(gè)輸入串到底該是哪個(gè)產(chǎn)生式了.那么我們可以修改文法成
A
-> aA’
A’
-> b | c
這樣一來,一個(gè)文法變成兩個(gè),但是無論A還是A’,它們的每個(gè)產(chǎn)生式的First集合都是不相交的.所以,他們能夠只通過最開頭的終結(jié)符號(hào)來判斷是哪個(gè)產(chǎn)生式.
這個(gè)變化過程有點(diǎn)想我們的代數(shù)里面的 ab + ac = a(b+c),所以叫它左提公因式.
這只是個(gè)簡(jiǎn)單的左提公因式的例子,實(shí)際當(dāng)中還會(huì)遇到一些復(fù)雜的問題.但是無論是哪個(gè)編譯教材,都會(huì)給出針對(duì)一切文法的左提公因式的算法.同樣,計(jì)算First集合的算法也在教材中詳細(xì)講解了.我就不在這里再描述了.
第二步分析:
__________________________________________________________________________________
經(jīng)過第一步的考察輸入串中的第一個(gè)串為”array”屬于非終結(jié)符號(hào)type第三個(gè)產(chǎn)生式的First集合,那么就可以確定這個(gè)串確實(shí)為type文法第三個(gè)產(chǎn)生式的串.所以在第二步中,展開出type的第三個(gè)產(chǎn)生式出來. type -> array[ simple ]of integer
那么接下來就是繼續(xù)分析構(gòu)造出來的type -> array[ simple] of integer產(chǎn)生式中的每個(gè)結(jié)點(diǎn).
所以箭頭又放到了分析樹中type的第一個(gè)孩結(jié)點(diǎn)array上.因?yàn)閍rray是終結(jié)符號(hào),如果它和輸入中的當(dāng)前箭頭所指的終結(jié)符號(hào)相同,那么箭頭都往下移動(dòng)一結(jié)點(diǎn)到’[‘符號(hào).同樣地,由于分析樹中的’[‘是終結(jié)符號(hào),那么只要看輸入中的串是否是’[‘就可以了.如果是,那么繼續(xù)往下分析.分析到分析數(shù)中的simple的時(shí)候,由于simple是非終結(jié)符號(hào),那么就需要考慮simple的產(chǎn)生式了.
第三步分析:
__________________________________________________________________________________
在第二步中,分析到分析數(shù)中的simple子結(jié)點(diǎn)的時(shí)候,由于simple是非終結(jié)符號(hào),那么就需要考慮simple的產(chǎn)生式.simple一共有三個(gè)產(chǎn)生式.通過輸入串當(dāng)前的串是”num”,是屬于simple產(chǎn)生式中第3個(gè)產(chǎn)生式的First集合,所以simple在分析數(shù)中就按第三個(gè)產(chǎn)生式simple -> num dotdot num 來展開.那么分析箭頭同樣,也自動(dòng)移動(dòng)到simple的第一個(gè)子結(jié)點(diǎn)num上繼續(xù)分析.
總體說來,這中自頂向下的分析原理就基本上是上面的過程.通過計(jì)算產(chǎn)生式的First集合,來逐步產(chǎn)生非終結(jié)符的產(chǎn)生式.最后的分析樹都會(huì)劃歸到終結(jié)符來進(jìn)行判斷(非終結(jié)符號(hào)是無法進(jìn)行直接判斷的,一定要展開過后才行).
看了原理,我們?cè)倏磳?shí)現(xiàn)的偽代碼.代碼很簡(jiǎn)單.
________________________________________________________________________
void
match(char token)
{
???
if lookahead == token)
lookahead = token;
???
else
???
?error(0);
}
void
type()
{
???
if( lookahead == integer || lookeahead == char || lookahead == num)
??????? simple();
???
else if( lookahead == id)
??????? match(id);
???
else if( lookahead == array)
??? {
??????? match(array); match(')'); simple(); match(')'); match(of); type();
??? }
???
else
??????? error(0);
}
void
simple()
{
???
if( lookahead == integar) match(integer);
???
else if( lookahead == char) match(char);
???
else if( lookahead == num)
??? {
??????? match(num); match(dotdot); match(num);
??? }
???
else
??????? error(0);
}
_________________________________________________________________________
注意:這里的代碼都是純的語法分析代碼,實(shí)際執(zhí)行過程中并沒有什么用處,但是我們構(gòu)造語法樹parse-tree的代碼就是鑲嵌在這些純的語法分析代碼中.