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