author: Kevin Lynx email: zmhn320#163.com date: 3.9.2009
語(yǔ)法分析
語(yǔ)法分析接收詞法分析階段的token集合為輸入，將這些沒(méi)有關(guān)系的tokens整理為相互
之間有關(guān)系的結(jié)構(gòu)。書面點(diǎn)的說(shuō)法叫語(yǔ)法樹。
每一次讓我寫這些文縐縐的概念真讓我受不了:D。
語(yǔ)法樹
語(yǔ)法樹簡(jiǎn)單來(lái)說(shuō)就是一個(gè)以token作為每個(gè)節(jié)點(diǎn)的樹型結(jié)構(gòu)。例如我們有表達(dá)式age =
age + 1;，在詞法階段它被整理為token集合：age, =, age, +, 1。那么在經(jīng)過(guò)語(yǔ)法分析后
，這些tokens將被整理為大致如下的樹形結(jié)構(gòu)：
=
/ \
age +
/ \
age 1
整理成這樣的結(jié)構(gòu)有什么好處？就kl解釋器而言，最直接的好處就是我可以遞歸地解釋
這棵樹執(zhí)行。例如：
value compute( TreeNode *root )
{
/* child[0]保存結(jié)果值age，child[1]是那個(gè)+表達(dá)式 */
return op_exp( root->child[1] );
}
value op_exp( TreeNode *node )
{
switch( node->op )
{
case '+':
{
/* + 表達(dá)式必然有左右操作數(shù) */
value left = factor( node->child[0] );
value right = factor( node->child[1] );
return left + right;
}
}
}
value factor( TreeNode *node )
{
switch( node->type )
{
case ID:
/* 查找age的值 */
return age;
case CONST:
/* 1 是常量 */
return node->cvalue;
}
}
如你所見(jiàn)，當(dāng)我們完成了語(yǔ)法分析階段，我們就可以完成我們的解釋器了。后面我會(huì)單
獨(dú)講解下整個(gè)解釋過(guò)程，包括每個(gè)模塊是如何協(xié)作的。我不知道其他解釋器是怎么做的，但
是我這樣做，起碼結(jié)果是對(duì)的。
如何整理出語(yǔ)法樹？
這里不得不提到所謂的BNF文法，很明顯你還是無(wú)法從我這里獲取編譯原理里某個(gè)概念
的講解。我這里提這個(gè)概念完全是方便我提到這個(gè)東西。
每一種語(yǔ)言都有其自己的BNF文法，因?yàn)槿f(wàn)惡的先知告訴我們，每一門語(yǔ)言都需要建立
其語(yǔ)法樹。- -!
就像詞法分析一樣，因?yàn)榇蟛糠终Z(yǔ)言的結(jié)構(gòu)都差不多，所以我覺(jué)得詞法分析和語(yǔ)法分析
基本上都沒(méi)有任何特別之處。也就是說(shuō)，別的語(yǔ)言的BNF你可以直接拿來(lái)改改用。
抄個(gè)BNF如下：
exp -> exp adop term | term
addop -> + | -
term -> term mulop factor | factor
mulop -> *
factor -> (exp) | number
這個(gè)BNF用來(lái)描述一般的算數(shù)表達(dá)式(+-*/)。簡(jiǎn)單來(lái)說(shuō)，一門語(yǔ)言的BNF就是用于描述該
語(yǔ)言所有語(yǔ)句的東西，包括if、while、函數(shù)定義之類。建議你google一下C語(yǔ)言的BNF，并
改造之用于你自己的語(yǔ)言。
那么有了BNF之后，該如何整理出語(yǔ)法樹呢？
通常，我們的代碼里都會(huì)直接有對(duì)應(yīng)exp、term、addop之類的函數(shù)。按照我這句話的意
思，上面抄的BNF被翻譯為程序代碼后，就可能為：
exp()
{
if( ... ) left = exp()
right = term();
left addop right;
}
term()
{
if( ... ) left = term()
right = factor();
left mulop right;
}
factor()
{
if( ... ) return exp();
else return number;
}
(可能還會(huì)涉及到EBNF，用于處理重復(fù)和選擇的一些情況---不用管這句話)
每一個(gè)函數(shù)基本上都會(huì)返回一個(gè)樹節(jié)點(diǎn)，當(dāng)然，該節(jié)點(diǎn)下可能會(huì)有很多子節(jié)點(diǎn)。
總結(jié)
語(yǔ)法分析基本上就是以上信息。它將詞法分析輸出的token集合整理成一顆語(yǔ)法樹。為
了整理出這棵語(yǔ)法樹，你需要找一份用于描述你語(yǔ)言的BNF，然后根據(jù)BNF翻譯成處理代碼。
代碼導(dǎo)讀
kl中的整個(gè)語(yǔ)法分析代碼位于klparser.c/klparser.h中，其BNF基本上取自<編譯原理與
實(shí)踐>附錄中的C_語(yǔ)言。