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