作者:tangl_99
QQ:8664220
msn:[email protected]
email:[email protected]
沒想到這一系列檔案能得到csdn和大家的這麼看好,首先要感謝大家的賞識和csdn的推薦.那麼我就更沒有理由不寫好這下面的幾篇文章了.本來我的計劃是簡單把lex和yacc介紹完後就直接進入編譯器的構造的技術細節問題讨論,但是最近看了一些國外經典教材後,發現文法的識别問題在編譯原理和技術中是個絕不能忽視的問題.即使現在有了yacc工具來幫助我來識别文法,但是有些時候還是需要我們自己來寫簡單的文法分析器.
1.什麼是文法識别(文法分析)首先要告訴大家的是,這裡的文法識别是指的上下文無關的文法,也就是上一節我們一直在讨論的那些 BNF式.
比如說,我寫了一句
if (a>6+5) printf(“OK!”); else printf(“No!”);
那麼它比對的文法也就是
if-stmt ->
ifexpr stmt
|
ifexpr stmt
elsestmt
我們通常要為一個程式語言寫出很多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的代碼就是鑲嵌在這些純的文法分析代碼中.
2003-10-23
成都,四川大學