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