上篇文章記錄了一個簡單的計算器，但是只能計算一個表達式，比如計算8+3*5，得到值23.這次在其基礎上添加了支持語句的功能，並且支持表達式中存在變量。比如下面：
num1 := 5;
num2 := num1+3*5;
num3 := num1 * (num2 - 20/5);
最後計算並返回的值是num3的值80.
根據這個例子，可以看出相比於上次那個簡單的計算器，添加的特性包括1、支持賦值語句 2、支持變量 3、支持多條賦值語句，也就是語句塊。其中語句之間使用分號分隔，賦值符號為”:=”，變量名的規則和c語言規則一致，以字母或者下劃線開頭，能包含數字、字母、下劃線。
下面是新增的語法規則：
stmt -> id := expr;
stmts -> stmts stmt | stmt
id -> (letter｜_) (letter | num)*
其中stmt代表一條語句，目前的語句只有一種，就是賦值語句，id代表一個標識符，在這裡僅代表變量，id的定義使用正則表達式定義，letter代表字母。
另外一個值得關注的是新增了符號表，它是一個結構體數組，包含的結構體如下：
typedef struct sym
{
char *name; /*符號名字*/
int val; /*值*/
}Sym;
因為在這個簡單的計算器中，所有變量只有一種值，即32位正數。所以Sym結構體的值val就是int。在我們的計算器中，變量可以不用聲明而直接使用，如果事先沒有賦值的話，那麼變量的值將會是0。
符號表的填充是在生成了語法樹之後，對其進行求值時進行的。比如單條語句num1 := 5； 在生成語法樹
:=
/ \
num1 5
之後。開始調用calc函數對其遞歸求值。在對num1求值時，先檢查符號表中是否存在符號num1，如果不存在則將其加入到符號表，並對它賦值為0。最後對賦值操作符“:=”求值時，將其右邊表達式的值5賦給左邊標識符num1，並且返回num1的值作為賦值操作符的返回值。
對於多條語句的求值，比如num1 := 5; num2 := num1 + 10; 生成的語法樹如下：
:= —> :=
/ \ / \
num1 5 num2 +
/ \
num1 10
可見對於兩條語句分別生成了兩棵語法樹，其中第二棵語法樹是作為第一棵語法樹的兄弟節點存在的，下面是樹節點的結構體TreeNode：
typedef struct treenode
{
struct treenode *child[CHILDNUM];/*子結點*/
struct treenode *brother;/*兄弟節點*/
NodeKind kind;/*節點類型：1. 語句 2.表達式*/
union
{
ExpK e;/*表達式子類型：常數、變量、數學表達式*/
StmtK s;/*語句類型：目前只有賦值語句一種*/
}attr;
union
{
int num;
TokenType tt;
char *name;
}val;/*屬性對應的值*/
}TreeNode;
其中兄弟節點的存在就是為了將多條語句連接起來，以便在語法分析和求值的時候方便找到。
下面看下在代碼中所做的相應改變，首先是在語法規則中新增的stmt和stmts規則所對應的兩個函數：
TreeNode *stmt()
{
TreeNode *node;
TreeNode *lnode, *rnode;
/*目前就只有賦值語句這一種，以一個ID類型值開頭*/
switch (token)
{
case ID:
/*賦值左邊的值為左節點*/
lnode = newIdNode();
match(ID);
/*賦值號為根節點*/
node = newNode();
node->kind = Stmt;
node->attr.s = AssignK;
node->val.tt = ASSIGN;
match(ASSIGN);
/*賦值右邊的表達式為右節點*/
rnode = exp();
node->child[0] = lnode;
node->child[1] = rnode;
/*匹配分號*/
match(SEMI);
break;
default:
printf("stmt: Unknown token.\n");
exit(1);
break;
}
return node;
}
由於目前語句 只有賦值語句這一種，所以stmt函數就只需要解析語句就行了，賦值語句以一個ID類型的token開頭，接著是賦值操作符，最後是一個exp表達式，解析表達式的函數exp()與上一篇文章中的一致。
下面是解析語句塊的函數stmts()
TreeNode *stmts()
{
TreeNode *node, *brother;
TreeNode *head;
head = node = stmt();
while (ENDFILE != token)
{
brother = stmt();
node->brother = brother;
node = brother;
}
return head;
}
可以看到，stmts函數中先調用stmt解析一條語句，也就是說，源文件中至少得有一條語句。接著是一個while循環，不斷調用stmt函數進行語句的解析，直到文件結束就退出while循環。此時返回一棵語法樹，該樹對應第一條語句，語法樹的兄弟節點指向它後面的語句。
接下來需要關注的就是calc求值函數，
/*計算語法樹的值*/
int calc(TreeNode *node)
{
int val;
int val1, val2;
Sym *s;
if (NULL == node)
{
printf("calc: syntax error.\n");
exit(1);
}
/*根據節點的屬性返回相應的值，目前節點有兩種
屬性:數字或者操作符*/
switch (node->kind)
{
case Exp:
switch (node->attr.e)
{
/*數字屬性節點直接返回值*/
case ConstK:
return node->val.num;
break;
/*操作符屬性節點值需要先計算兩個操作數的值，
再根據操作符來計算最後的結果*/
case OpK:
val1 = calc(node->child[0]);
if (NULL != node->child[1])
{
val2 = calc(node->child[1]);
}
switch (node->val.tt)
{
case ADD:
val = val1 + val2;
break;
case MINUS:
val = val1 - val2;
break;
case MUL:
val = val1 * val2;
break;
case DIV:
val = val1 / val2;
break;
case NEGATIVE:
val = val1*(-1);
break;
default:
printf("cal: Unknown operation.\n");
exit(1);
break;
}
break;
case IdK:
s = findSym(node->val.name);
if (NULL == s)
{
/*未聲明的id默認值為0*/
addSym(node->val.name, 0);
val = 0;
}
else
{
val = s->val;
}
break;
default:
printf("calc: Unknown expression type.\n");
exit(1);
break;
}
break;
case Stmt: /*賦值語句的計算*/
switch (node->attr.s)
{
case AssignK:
val1 = val = calc(node->child[1]);
s = findSym(node->child[0]->val.name);
if (NULL == s)
{
addSym(node->child[0]->val.name, val1);
}
else
{
s->val = val1;
}
break;
default:
printf("calc: Unknown stmt kind.\n");
exit(1);
break;
}
break;
}
if (NULL != node->brother)
{
val = calc(node->brother);
}
return val;
}
可以看到該函數有兩層的switch嵌套，第一層switch判斷節點的類型是語句還是表達式，第二層switch判斷其子類型，比如表達式可以是常數、標識符、數學表達式，語句目前只有賦值語句一種，將來可以能有if語句、while語句等等。在計算計算賦值語句分支中，先計算賦值符號右邊表達式的值，這個值將會賦給左邊標識符，並且作為賦值符號的值而返回。對於左邊標識符，先判斷其是否在符號表中，如果不在就將其添加到符號表，並把右邊表達式的值賦給它，以便後面引用到該標識符時使用。
在計算switch的表達式標識符的分支中，也是先查找其是否在符號表中，如果在的話，就直接返回符號表中保存的該標識符的值。如果不在，那麼就將該標識符添加到符號表，並初始化為0。
另外的一些改變是getToken函數，添加了識別標識符的分支，下面僅列出其添加的代碼：
default:
/*首字符是字母或者下劃線*/
if (isalpha(c) || ('_' == c))
{
/*可以是下劃線字母或者數字*/
while (isalnum(c) || ('_' == c))
{
tval[index++] = c;
c = nextChar();
}
pushBack();
token = ID;
state = DONE;
}
else
{
printf("getToken: Unknown character.\n");
exit(1);
}
break;
下面是向符號表添加符號和查找符號的兩個函數：
void addSym(char *name, int val)
{
if (symidx >= SYMNUM)
{
printf("addSym: too much symbol.\n");
exit(1);
}
symTbl[symidx] = (Sym *)malloc(sizeof(Sym));
symTbl[symidx]->name = name;
symTbl[symidx]->val = val;
symidx++;
}
Sym *findSym(char *name)
{
int i;
for (i = 0; i < symidx; i++)
{
if (!strcmp(symTbl[i]->name, name))
{
return symTbl[i];
}
}
return NULL;
}
好了，這個帶變量，帶語句版本的計算器就完成了。下面看看效果。
建立一個測試文件test.txt，輸入以下內容：
num1 := 5;
num2 := num1 + 10;
num3 := num2 * num1 - 20 / num1;
接下來編譯計算器
gcc -fno-builtin mycomplier.c -o mycpl
執行
./mycpl test.txt
將會輸出 The result is 71.
看到這一條條帶變量的語句，還能計算出正確的結果，真是覺點有點像那麼回事 Y(^_^)Y。
源代碼下載路徑 http://download.csdn.net/detail/luo3532869/8039017
Email: [email protected]
有問題歡迎交流～～～～～
