品评TINY-C源码

编译原理上机，无聊，看了教育在线老师传上去的TINY-C的源码，用半节上机课写了如下内容。在此特别特别感谢热心的桑同学！！如果不是你，我的这些文字现在还在机房的充满病毒的随时可能被格式化的机器上！
－－－－－－－－－－－
TINY-C是一个自定义的超级小型的语言，实在是小得可以了，类似PASCAL。才8个关键字。
TYNY-C语言的相关描述：
1，只能处理整型数，且只能处理10进制数。
2，标识符只能由字母组成。
3，只有8个关键字：if,then,else,end,repeat,until,read,write。从字面上就可以知道这些东西是干嘛的了。
4，只有10个运算符：:=,=,<,+,-,*,/,(,),;
5，语法规则从那8个关键字就大概知道了。

老师提供的TINY-C源文件有两种实现：
1，LEX + YACC实现。这个实现还没有MAIN函数。只能构造出syntax tree而已。
2，完全C语言，手工，活生生写出来！这个能生成“汇编”代码（其实是作者自己定义的一种代码，是作者自己规定的一种“机器”的代码。其实这种机器也是一程序，是种不虚拟机八）

LEX+YACC实现的实在没劲，简单极了。看看C语言活生生写出的东西吧。
--------------------------------
一：共有16个文件。
MAIN.C: 主函数
GLOBALS.H:全局定义的文件
SCAN.C/SCAN.H: 词法分析
PARSE.C/PARSE.H:语法分析
UTIL.C/UTIL.H:构造树
SYMTAB.C/SYMTAB.H:符号表
CGEN.C/CGEN.H:生成"汇编代码"
CODE.C/CODE.H:这个只是用来把分析过程输出到屏幕的.

二：各个文件的分析。
1，MAIN.C:
主要有三个FILE*句柄:
source--源代码文件。
listing--显示分析过程的文件，这里重定向到stdout，也就是屏幕。
code--目标汇编代码文件。

从该文件中可知程序运行的流程：
检查参数正确否(tiny.exe filename)->构造语法树（调用parse函数）->根据语法树生成代码（调用codeGen函数，该函数又调用cGen函数）。

2，GLOBALS.H:
定义了关键字个数8个。
定义了关键字，运算符等内容的枚举值。
定义了语句类型的枚举值，这个决定树的结点。
定义了变量类型（也就三种，void, integer, boolean）。
定义了树的节点--这个最重要了！！其结构如下所示：
typedef struct treeNode
{
struct treeNode * child[MAXCHILDREN];
struct treeNode * sibling;
int lineno;
NodeKind nodekind;
union { StmtKind stmt; ExpKind exp;} kind;
union { TokenType op;
int val;
char * name; } attr;
ExpType type; /* for type checking of exps */
} TreeNode;

从字面就知道意思了。因为关键字少，语法简单，所以孩子结点不多，他这里定义最多3个，所以直接用数组就可以了，不动态分配。

剩下的定义了一些条件编译的变量，对整个编译的核心内容无关紧要。不说了。

3，SCAN.c/SCAN.H
主要有这么几个函数：
static int getNextChar(void);
static void ungetNextChar(void);
static TokenType reservedLookup (char * s);
TokenType getToken(void);

从字面也知道意思了。那个reservedLookup函数是查找关键字的，在符号表中找。这里还定义了一个保存关键字的结构：
static struct
{ char* str;
TokenType tok;
} reservedWords[MAXRESERVED]
=
{{"if",IF},{"then",THEN},{"else",ELSE},{"end",END},
{"repeat",REPEAT},{"until",UNTIL},{"read",READ},
{"write",WRITE}};

最重要的是getToken(void)函数。这个相当于lex的功能，进行词法分析。也就是一个DFA，switch后面跟了一堆的case。

其中，我比较欣赏他getNextChar(void)函数的思路，完整给出，让大家鉴赏一下：
static int getNextChar(void)
{
if (!(linepos < bufsize))
{
lineno++;
if (fgets(lineBuf,BUFLEN-1,source))
{
if (EchoSource) fprintf(listing,"%4d: %s",lineno,lineBuf);
bufsize = strlen(lineBuf);
linepos = 0;
return lineBuf[linepos++];
}
else
{
EOF_flag = TRUE;
return EOF;
}
}
else return lineBuf[linepos++];
}

4，PARSE.C/PARSE.H
有这么几个函数：
TreeNode * parse(void)
static TreeNode * stmt_sequence(void);
static TreeNode * statement(void);
static TreeNode * if_stmt(void);
static TreeNode * repeat_stmt(void);
static TreeNode * assign_stmt(void);
static TreeNode * read_stmt(void);
static TreeNode * write_stmt(void);
static TreeNode * exp(void);
static TreeNode * simple_exp(void);
static TreeNode * term(void);
static TreeNode * factor(void);

最重要的是parse这个函数，就是用来构造整个程序的语法树的。下面的一堆私有函数看名字就知道了，，它们构造相应语法的语法树，然后parse最后把它们这些子树整合成一个大树。

5，SYMTAB.C/SYMTAB.H
这个是符号表操作的，也就是词法分析的时候查找表，看该token是不是关键字。如果不是，就当作表识符添加进去。在语法分析的时候也要用到，看变量有没有声明的时候用的。

这里用到了HASH的技术，现在HASH的思想用得挺广的，也不希奇了。他HASH的算法是这样的：
static int hash ( char * key )
{ int temp = 0;
int i = 0;
while (key[i] != '