语法分析器完成的功能：

 处理源文件生成基本的语法树 

 对于符号表没有造成影响，末了符号表是空的，在语义分析阶段才开始向符号表中添加

语法树的变化：

1. 确定语法树的枝杈关系
2. 语法树上节点的属性 

对于一些需要登记名字的字符串，存放到一些系统的堆中。如 初始字符串放在了 StringHeap 堆中，其他一些标识符放在了 NameBuckets 哈希表中。

对于一些有初始值信息的变量，其初始值若是字符串或变量名则通过上述方式，以指针管理。若是int ,char,float 等类型则直接存放到节点的数据结构中。

3.  因为这时候的语法树是忠于源代码的，所以可以通过这个语法树逆向生成源代码。

源代码的实现：

• 数据结构

树节点的结构：

#define AST_NODE_COMMON   \
    int kind;             \     // 节点类型 enum nodeKind 类型( NK_前缀 )
    struct astNode *next; \     // 指向下一个节点，用于实现枝杈关系
    struct coord coord;         // 源文件定位信息，用于报错

typedef struct astNode
{
	AST_NODE_COMMON
} *AstNode;

这是"基类"，C语言不能实现继承关系，故而将 "基类" 的成员做到宏 AST_NODE_COMMON 中,子类中直接写一个宏就可以了。这也是 UCC 中实现继承的一个用的较多的方式：

1. 将 "基类" 公共成员做成宏，在 "子类" 中添加宏即可。

2. 宏中有一个 kind 指定当前对象的类型。

若 kind 为 NK_Function 时，这个节点就表示 astFunction 类型的，需要将 AstNode 转化成 AstFunction 来处理了。

•  处理流程

 注： UCL 在语法分析的函数是 Parse类函数，而词法分析是 Scan类函数。

UCL的词法分析是混在语法分析中的，主要是为了提高效率。当然绝对的分开也有些困难。对于编译器完全可以不用这些东西分开，一口器词法分析，语法分析，语义检查等一块儿进行更好，过度的拆解只是为了可维护性和重用性而已。

先看一下代码的主要流程吧： 

/**
 *  translation-unit:
 *		external-declaration
 *		translation-unit external-declaration
 *
 */
AstTranslationUnit ParseTranslationUnit(char *filename)
{
	AstTranslationUnit transUnit;
	AstNode *tail;

        // 文件读入内存
	ReadSourceFile(filename);

	TokenCoord.filename = filename;
	TokenCoord.line = TokenCoord.col = TokenCoord.ppline = 1;
	TypedefNames = CreateVector(8);
	OverloadNames = CreateVector(8);

        // 创建语法树根节点
	CREATE_AST_NODE(transUnit, TranslationUnit);
	tail = &transUnit->extDecls;

        // 开始添加枝叶了
	NEXT_TOKEN;
	while (CurrentToken != TK_END)
	{
		*tail = ParseExternalDeclaration();
		tail = &(*tail)->next;
		SkipTo(FIRST_ExternalDeclaration, "the beginning of external declaration");
	}

        // 关闭文件
	CloseSourceFile();

	return transUnit;
}

还好，代码注释都很全，在每一个 Parse类语法分析的函数前都有相应的BNF 式，在代码理解上省去了大半的力。在这个函数调用完之后，一个基本的 AST语法树就建立起来了，这个树的枝杈关系已经很确定了。

代码采用 LL 解析（ 自上向下）方式。ParseExternalDeclaration()  处理函数和全局的声明， ParseCompoundStatement() 处理函数体的执行语句部分。。。

• 词法分析器

在Parse 的过程中，经常会调用 NEXT_TOKEN 来获得下一个符号，这里面就藏着词法处理器了：

#define NEXT_TOKEN  CurrentToken = GetNextToken();


int GetNextToken(void)
{
	int tok;

	PrevCoord = TokenCoord;
	SkipWhiteSpace();
	TokenCoord.line = LINE;
	TokenCoord.col  = (int)(CURSOR - LINEHEAD + 1);

	tok = (*Scanners[*CURSOR])();
	return tok;
}

 Scanners 是一个词法处理函数的数组，对每个ASCII码表中的字符，都有一个函数映射，这样，在读入一个字符时候，通过查表法直接转到相应的处理函数中进行处理就行了： 

typedef int (*Scanner)(void);

static Scanner        Scanners[256];

 

查表法也是 UCC 代码中比较常用的技法，像操作符的名字、标识符的名字都是依次实现的。

在词法处理过程中影响的物件有一下几个,这几个是呈现给语法分析器，供其使用的，在Parse里经常看到：

1. CurrentToken 类型 int，记录下一个符号的类型 (token类型的值，如TK_ID)。

2. TokenCoord 类型 coor, 记录当前的行，列，文件名信息等。

3. TokenValue 类型 value, 记录一些具体的值信息，如变量的值，字符的值，字符串的值，浮点型的值等等。value 类型值得一提：

union value
{
	int i[2];    // 记录整型的数值
	float f;     // 记录浮点型的数值
	double d;    // 记录双精度浮点型的数值
	void *p;     // ◎CurrentToken为 TK_STRING或 TK_WIDESTRING 时，记录的是字符串的值， ◎CurrentToken为 TK_ID 时记录的是当前标识符的名字
};

注意的是，当 TokenValue 的 p 成员有两种含义，通过 CurrentToken 的值来区分的。

当是 TK_STRING或 TK_WIDESTRING 时，字符串的值是分配在全局的字符串堆 StringHeap 中。

当是 TK_ID 时,会先检查是否是预设的关键字（ union, typedef 等），如果不是会确定是 TK_ID, 然后会将标识符放到一个盛放字符串的内存池 NameBuckets (通过哈希方式管理)中 ：

static int ScanIdentifier(void)
{

        // ....
        ...
	
        // 判断是否是预设关键字 ( register, return 等)
        tok = FindKeyword((char *)start, (int)(CURSOR - start)); 
	if (tok == TK_ID)
	{
		  // 不是关键字则将此标识符插入到一个字符串的表中
                  TokenValue.p = InternName((char *)start, (int)(CURSOR - start));
	}

	return tok;
}

 【TODO】  typedef 和全局变量的处理过程

• 相关文章