從這一節(jié)開始,我們就算進入編譯器構(gòu)造的正題了.不得不說,前面的詞法掃描器在整個編譯器部分只是個很小很小的組成,而這兩節(jié)講述的語言構(gòu)造器才能真正為我們的編譯工作起到重要的作用.這些東西相信大家在大學的編譯原理的課程已經(jīng)學了不少,那么本文我也只是大致地帶過,讓大家回憶起大學的知識,重要的yacc使用技巧等等,我將在后面的內(nèi)容講出.
例3.1
exp -> exp op exp | (exp) | number
op -> + | - | *
這里就是一個定義的帶有加法,減法,乘法的簡單整數(shù)算術(shù)表達式的文法.其中粗體表示的是終結(jié)符號,也就是不能有產(chǎn)生式生成的符號.而exp,op就是非終結(jié)符,它們都是由一個”->”符號來產(chǎn)生的.
比如100 + 222 *123123 –(888+11)就是符合上述文法的具體的表達式.
注意,在文法定義中,是可以遞歸的.所以exp產(chǎn)生式右邊的式子中可以再次出現(xiàn)exp.
這里的|和正則表達式一樣,表示的選擇的意思,也就是說,exp可以是exp op exp或者(exp)再或者number.
下面讓我們看看<<編譯原理及實踐>>書中的一個關(guān)于BNF文法的介紹.
比如說我們有個數(shù)學表達式(34-3)*42,然后我們來看看上面的exp文法怎么來推導識別它.
(1) exp => exp op exp?????????????? [exp ->exp op exp]
(2)???? => exp op number??????????? [exp ->number??? ]
(3)???? => exp * number???????????? [op -> *???????? ]
(4)???? => (exp) * number?????????? [exp ->(exp)???? ]
(5)???? => (exp op exp) * number??? [exp ->exp op exp]
(6)???? => (exp op number)* number? [exp -> number?? ]
(7)???? => (exp – number) * number [op -> -???????? ]
(8)???? => (number–number)* number [exp -> number?? ]
最終,exp里面全部的非終結(jié)符號全部變成了終結(jié)符號.那么推導完成.
這種推導十分像我們在離散數(shù)學中講到的命題推理.其實形式語言的推導的數(shù)學基礎(chǔ)就是我們離散數(shù)學的命題推理.
在推導過程中,其實就是把原來的文法中的遞歸展開.那么我們在推導的過程,也就很容易實現(xiàn)分析樹的生成.而分析樹就是我們編譯程序中十分重要的信息源.我們之所以前面又做詞法分析,又做語法分析的目標就是為了生成分析樹.有了它,我們編譯程序在后面的代碼生成過程中將變得容易百倍.
?請看:
例3.2
同樣是<<編譯原理及實踐>>書上的例子.
設E -> E+a | a 表示的文法為G,那么考慮它生成的表達L(G)
如果由標準的數(shù)學定義,那么我們用公式L(G)={s | exp =>* s }表示一種文法G.
s代表記號符號的任意數(shù)組串,也就是我們的終結(jié)符號.而exp代表非終結(jié)符號,=>*表示一系列的從非終結(jié)符到終結(jié)符號的推導過程.這里*有點像我們在講述正則表達式中的*符號一樣,它表示0到無限次的重復.所以=>*就是表示0次到無限次的推導過程.
L(G) = {a,a+a,a+a+a,a+a+a+a,…}
E => E+a => E+a+a => E+a+a+a
同時,在我們的編譯課本上,又經(jīng)常講述另一種數(shù)學表達方式來闡述文法的定義.
G=(T,N,P,S)
注意,這里的T,N,P,S都是集合.
T表示終結(jié)符號(terminal),也就是這里{a,+}
N表示非終結(jié)符號(nonterminal),也就是這里{E},但是N不能與T相交.
P表示產(chǎn)生式(production)或者文法規(guī)則(grammar rule)的集合,這里它只有一個元素: E -> E+a
S表示集合N的開始符號(start symbol).關(guān)于S,本人也搞不清楚它的用處,所以很抱歉!
例3.3
這是我們C程序語言中經(jīng)常使用if else文法
statement -> if-stmt | other
if-stmt -> if(exp) statement | if (exp) statement else statement
exp -> 0|1
statement就是我們C語言中使用語句,它的產(chǎn)生式包括了兩種可能,一是if-stmt語句,二是other.然后我們又另外定義if-stmt語句的產(chǎn)生式.這里有兩種情況,一是沒有else的,另外就是有else的.里面我們又使用了遞歸.if-stmt本來是包含在statement里面的,可是我們又在if-stmt的產(chǎn)生式中使用statement.正是因為文法中允許遞歸,所以它比起我們前面講的正則表達式有更廣泛的表示能力,但同時,文法的推導識別也更加法復雜.按照編譯原理的書籍,一般講完BNF文法后,就要重點講解文法的推導算法.一共有兩種,一是LL算法,自頂向下的算法,二是LR算法,自底向上的算法.LL算法比較簡單,其中還有一種特殊的情況,就是我們下一節(jié)要講的遞歸下降的算法.由于C語言中的函數(shù)本來就可以遞歸,那么實現(xiàn)這中遞歸下降的算法是十分簡單的,而且對于我們一般的程序設計語言來說,雖然它的算法能力很弱,但是已經(jīng)是足夠用了.而關(guān)于LR的算法,那么就是一個大難題了.它的算法能力最強,但是實現(xiàn)起來十分困難,還好,已經(jīng)有科學家為我們提供了yacc(或者叫bison)這個工具,可以來自動生成LR的文法推導算法.這就是我們一直在提到的yacc工具了.
回過頭來,我們看看下面的程序
if(0) other else other
的分析樹
思考: 為什么要把文法最終分析成樹結(jié)構(gòu)?
因為文法本身是遞歸的,而表示的遞歸的最好數(shù)據(jù)結(jié)構(gòu)就是樹,所以我們把文法弄成樹結(jié)構(gòu)后,后面在處理代碼生成等問題上,也可以用遞歸來很容易地完成.
例3.4
這里我給出microsoft在msdn中對于C語言的statement的文法
注意,這里用:符號替代了我們前面產(chǎn)生式的->
statement
:
labeled-statement
compound-statement
expression-statement
selection-statement
iteration-statement
jump-statement
try-except-statement???/* Microsoft Specific */
try-finally-statement???/* Microsoft Specific */
jump-statement
:
goto
identifier
;
continue;
break;
return
expression
opt
;
compound-statement
:
{
declaration-list
opt
statement-list
opt
}
declaration-list
:
declaration
declaration-list declaration
statement-list
:
statement
statement-list statement
expression-statement
:
expression
opt
;
iteration-statement
:
while (
expression
)
statement
do
statement
while (
expression
);
for (
expression
opt
;
expression
opt
;
expression
opt
)
statement
selection-statement
:
if (
expression
)
statement
if (
expression
)
statement
else
statement
switch (
expression
)
statement
labeled-statement
:
identifier
:
statement
case
constant-expression
:
statement
default :
statement
try-except-statement
:???/* Microsoft Specific */
__try
compound-statement
__except
(
expression
)
compound-statement
try-finally-statement
:???/* Microsoft Specific */
__try
compound-statement
__finally
compound-statement