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