下载掌阅APP，畅读海量书库
立即打开
第3章给出了编译器设计中基本的技术步骤和手段。必须指出的是，作为基础性的介绍，所给出的程序在设计和数据结构上进行了大幅度的简化和缩减。本章将介绍按C语言的语法进行完整定义，逐步构建编译器的过程。
在目前流行的编译性语言中，C语言的语法规则属于较为简单的。即便如此，C语言编译器的设计所涉及的数据结构、运行流程仍然非常复杂，和普通应用程序的设计在理念、方法上存在很大差异。由此可见，这对相当多的编程人员（尤其是非计算机专业的人员）在理解和设计上造成一定的困难。
编译过程设计涉及语法分析和语义分析两个方面。前者在语法解析过程中完成，相对比较直接和确定；而后者在语言转换过程中完成，经常在某种程度上存在某种可商榷性或不确定因素。
为了方便理解编译器的设计，本章各小节对支持的C语言语法范畴进行了逐步增扩。
工程项目路径：/cc_source_4.1。
词法解析器文本cc.l在开始部分给出了C语言各种常数类型的宏定义，具体如下。
·第20～22行：常数类型的枚举及转换函数。
·第38～41行：十进制、八进制、十六进制及二进制常数（正规表达式宏定义），涵盖数值为零的整数。
·第43～47行：转义字符集合（正规表达式宏定义）。
·第49～51行：字符常数（正规表达式宏定义）。
·第53～55行：字符串常数（正规表达式宏定义）。
词法解析器文本 cc.l的规则部分列出了对各类常数的识别规则（常规表达式+识别后的处理），其中包括不同进制常数的识别，以及单字符和字符串的识别，具体如下。
词法解析器文本cc.l的规则部分列出了C语言关键字识别规则，以及识别后的操作，具体如下。
·第90～123行：C语言中保留的关键字识别。
·第125行：为支持PIC16Fxxxx系列CPU所增设的_linear_关键字，表示内存的线性空间。
·第127行：对于标识符的识别必须排列在所有关键字之后（因为关键字都符合标识符的识别规则）。
词法解析器文本cc.l的规则部分最后列出了C语言各类操作运算符识别规则，以及识别后的操作，具体如下。
·第129～150行：C语言中各类运算操作符的识别。
·第152～157行：对单字符关键字的识别，必须排列在其他运算符关键字序列之后；大括号（{}）作为特殊字符不存入缓冲区中。
C语言源程序以纯文本形式输入并表示。除语句中的变量名、操作符之外，其描述的常数部分中所有字符也都在ASCII码的可显示字符集（十六进制数0x20～0x7E）范畴。对于使用非显示字符（0x00～0x1F），以及特殊场合，源代码中通常使用转换符方式进行描述。
编译处理过程中，转换符所表示的数据值必须被转译成实际的内容（值），以供随后的运算、处理和存储。ASCII字符数值举例如表4-1所示。
表4-1 ASCII字符数值举例
下面两个函数（ascii.c/ascii.h源程序文件中），将负责进行上述的转译：
char*parseRawStr（char*str）表示对字符串常数进行扫描处理。
int parseRawChr（char*str）表示对字符常数进行扫描处理。
小结
（1）词法解析扫描是按解析规则的排列顺序从始至终逐一扫描比较的。因此，在同一种解析状态下，各解析识别规则不能随意排列。
（2）词法识别后返回的各种token及其内涵宏定义在语法文本cc.y中定义，最终以枚举的方式导入cc.h中。
第3章中所列举的各种数据结构只是简化后的形式，便于理解。本章将给出完整的结构形式。
attrib用于描述变量、函数的本身特性及附加特征，包括与目标处理器有关的信息。为了能涵盖所有类型的数据特征，attrib定义需要扩充，其完整的结构如下。
（1）第25行和第26行定义的变量（ptrVect、dimVect）均为int数组指针，并各自对应一个动态生成的一维数组。其中，前者描述指针维度，而后者描述数组的维度。数组中的首个元素值为内涵长度（维度）。
例如：dimVect的内容为[2，10，5]，表示描述一个二维数组“[10][5]”。
例如：ptrVect的内容为[1，0]，表示描述一个简单指针“*”。
例如：ptrVect的内容为[2，CONST，0]，表示描述一个二重指针“*const*”。
（2）atAddr、newData、parList本该是node类型的指针，但因为定义先后关系而无法引用，只能使用通用形式“void*”。
在4.2.1节的基础上对各类node进行扩充，并给出它们完整的数据结构，具体如下。
（1）各类node中，除oprNode_t之外，含义都很单纯。而oprNode_t并非只表示通常意义上的运算操作，还可以借助oper成员变量的描述，应用于其他场景。
（2）oprNode_t的op和listNode_t的ptr成员均为node的指针数组，必须排列在结构的末尾。原因是这两类node在生成时，数组实际长度按需求而定，其中nops成员将指示其长度（参见common.c文件中的listNode（）和oprNode（）函数）。
语法解析器文本cc.y中宏定义部分的完善如下。
此部分列出（枚举）所有终节点token，并对部分token赋予数值类型（第49～52行）。此外：
·第20行：声明parListCheck（）函数。它将检测函数参数列表中的格式正确与否，并返回正确的列表长度。
例如：
在3个函数声明中，foo1（）和foo2（）函数均没有入口参数，而foo3（）函数有1个入口参数。
·第25行：表明语法解析自动机存在1处语法多义性（grammar ambiguity）。语法多义性给解析过程带来某种不确定性，理论上计算机语言的设计应该避免这一情况。这处语法多义是C语言if…else语法本身的一个缺陷，又因为bison/yacc属于LALR（1）-Look Ahead Left-to-Right 类型的解析工具，所以无法应付这类的语法多义解析。解决的方案为，当解析遇到这种多义性时，解析将按最邻近匹配原则处理。这也从另外的角度提醒编程人员在实践中应该警惕此类情形。
例如：
按C语言语法，此处else既可以被理解为与第一处if组成if…else…语句，也可以解析为第2处if的分支（邻近匹配）。在编译器的实际语法解析中，else将与第二处（最邻近）的if匹配。
语法解析器文本cc.y中的节点（非终节点）数据类型定义如下。
中间（归纳）节点及其类型必须具备某种数据类型，是构建编译树的纽带和基础，表示中间节点的数据属性。其中：
%type<n>表示节点数据yylval属性为node指针（它涵盖node中各类成员）。
%type<i>表示节点数据yylval属性为int。
%type<a>表示节点数据yylval属性为attribute指针。
%type<p>表示节点数据yylval属性为int指针。
语法解析器文本cc.y中对于函数声明及定义的识别如下。
·第419～422行：函数返回值类型为默认时的函数定义/声明情景，自动填补为int。
例如，foo（）{...}。
func_declarator为函数声明（包括函数名本身），其中数据类型为idNode_t*，由$1表示。
func_body为函数体，其中数据类型为idNode_t*，由$2表示。它有以下两种类型。
（1）空语句'；'为函数声明。
（2）复合语句为函数定义。
归纳结果由$$表示，数据类型为oprNode_t*，函数的返回值类型将添加到opr.attr中。
·第423～442行：完整的函数定义/声明情景。
declaration_specifiers为返回值类型及各种修饰，数据类型为attrib*。
func_declarator2为函数声明（包括函数名本身及指针修饰，涵盖func_declarator定义）。
·第443～448行：中断服务函数的定义（PIC16Fxxxx处理器只有一个中断入口，因此不需要定义入口地址）。
在语法解析器文本cc.y中，运算符的设计是通过产生式来确定的，从而确定了运算符的优先规则，具体如下。
例如，源程序的运算语句如下。
将其归纳为生成的编译树结构，如图4-1所示。
图4-1 编译树的运算符优先解析结构举例
图4-1中不仅显示了各类运算符处理的优先关系，还展示了语法解析过程。
C语言中变量定义的语法涉及很多因素，因而语法解析比较复杂。通常变量定义的语法形式如下。
变量类型及其修饰：declaration_specifiers。
变量名序列：init_declarator_list。
其中“变量名序列”部分是可省略项（并不产生歧义）。
·第93～105行：“变量名”部分省略，以支持enum语句。
·第106～111行：其中init_declarator_list表示变量名序列（表）。
init_declarator_list表序列中各元素可含有各自的初始化赋值表达式，具体如下。
所谓的direct_declarator，是变量名连同所属的某些修饰（数组）的语法识别范畴，其解析过程如下。
·第179～185行：非函数指针类变量，通过递归形成对多维数组的识别。
·第186～226行：函数指针类变量，只支持一维数组。
例如，对于变量定义语句：
其对应的完整解析、归纳后的编译树结构如图4-2所示。
图4-2 对于变量定义语句实例的完整解析、归纳后的编译树结构
小结
（1）通过上述语法解析实例，可以发现语法解析十分复杂，其中可能包括很深的递归过程。
（2）bison工具的功能非常强大和微妙。
（3）作为实验，读者可以试着编译下面的源程序作为本节的结束。
4.2节给出的语法/词法解析已经形成基本的解析模型，能应付C语言最基本的功能。本节在此基础上进行充实：
（1）支持预处理语句，如＃define、＃ifdef、＃if、＃else等预处理语句种类。
（2）支持汇编语言行插入。
上述两类语句不同于常规语句，并且有一定的上下文牵连关系，即上下语句间相互关联，因此在词法解析自动机中设置了不同的扫描状态。
工程项目路径：/cc_source_4.2。
词法解析中新增的变量将用于对预处理语句（由“＃”开头的语句）的识别，具体如下。
·第15～16行：新增变量，作为支持预处理语句的标志及类型。
同时，词法解析将新增预处理语句的识别状态，具体如下。
·第62～63行：为词法解析自动机新增状态（ASMCODE和PREPROC），分别对应增加的插入汇编语言及预处理语句功能。
当在解析中识别预处理语句时，解析自动机将进入新增的状态，直至预处理语句结束。此状态下，对于行终结字符的处理会有差异，解析识别如下。
·第70～78行：对于＃define、＃undef、＃pragma、＃ifdef、＃ifndef预处理（特殊）语句，将跟随相应的标识符，因此进入PREPROC状态。
·第94行：对于＃asm语句，将跟随一段汇编语言代码，因此进入ASMCODE状态。
·第98行：在ASMCODE状态下，识别＃endasm语句，表示汇编语言代码段结束，返回常规状态INITIAL。
·第100行：在ASMCODE状态下，所有源程序文件字符行将作为字符串数据，供语法解析处理。
·第196～209行：换行符的处理，每条预处理语句只能是单行语句。对于部分类型预处理语句，行结尾需返回特殊token，供语法解析yyparse（）函数使用。
汇编语言的插入方式主要有以下两种。
（1）片段式插入：使用＃asm...＃endasm语句作为始终。
（2）单句式插入：使用类似C语言函数形式的asm（"..."）；语句，其中asm（）函数作为内部函数，可以在以后语法分析时进行识别并处理。
相应地，在语法解析器文本cc.y中，增加有关对预处理语句的识别节点类型及规则，具体如下。
·第76行：增加对应预处理语句的产生式归纳节点（符号）。
·第93～99行：识别/支持变量定义并设定绝对地址的语法。
·第100～103行：识别/支持CPU寄存器中“位”的定义语法。
·第104～105行：识别/支持“＃undef 宏名”语句。
·第106～107行：识别/支持“＃define 宏名”语句（隐匿定义值）。
·第108～110行：识别/支持“＃define 宏名 表达式”语句（带定义值）。
·第111～115行：识别/支持“＃ifdef 宏名”语句。
·第116～120行：识别/支持“＃ifndef 宏名”语句。
·第121～125行：识别/支持“＃if...＃else...＃endif”预处理语句。其中，＃else...部分可保持默认设置。
·第126～129行：识别/支持“＃define 宏名（参数序列）表达式”语句。
·第130～133行：识别/支持“＃define 宏名（参数序列）”语句。
·第134～135行：识别/支持“＃pragma 标识符”语句。
·第136～138行：识别/支持“＃pragma 标识符 表达式”语句。
·第159～160行：识别/支持“＃asm…＃endasm”语句，即汇编语言片段的插入。
·第162～173行：对于“＃if...”及“＃else...”语句具有识别规则。其中，＃else...语句可以包含递归嵌套。
例如，对于预处理语句：
其对应的解析、归纳后的编译树结构如图4-3所示。
图4-3 对于预处理语句实例的解析、归纳后的编译树结构
在4.3节的基础上，增加以下功能。
（1）枚举语句（enum）。
（2）结构和联合（struct/union）数据定义功能。在C语言中，struct/union用于创建、设计新类型的数据，其用途广泛，也是高级语言的重要特征之一。
工程项目路径：/cc_source_4.3。
增加相应的节点及其类型
在语法解析器文本cc.y中，增加对enum和struct/union语句结构的解析功能，具体如下。
·第77～78行：新增有关enum语法归纳节点。
·第79～83行：新增有关struct/union语法归纳节点。
·第220～221行：在数据类型说明符的type_specifier 列表中，增加新类型 enum 和struct/union语句。注：它们均以数据类型attrib表示。
·第647～671行：enum_specifier的语法解析。
例如，enum语句实例解析后生成语法树结构，如图4-4所示。
图4-4 enum语句实例解析后生成语法树结构
·第672～709行：支持struct/union语句语法的产生式。注：本设计中不支持位域（bit-field）的使用。
在 C/C++语言的编程实践中（尤其是嵌入式应用场合），struct/union 结构中位域（bit-field）的使用很常见，因为能减少内存的消耗。但在实际应用中，使用位域可能会降低运行效率（视CPU结构而定），而且支持位域会使编译器设计难度明显增加。因此，为了便于理解，本设计不支持这一功能。
作为本章知识讲解的最后一节，此节增加C语言中typedef语句的支持。
C语言中typedef的语法及使用是为（已有的）变量类型（重新）命名。它为程序设计带来了某种便捷，并增加了可读性。此外，它给程序的移植也经常提供便利。也就是说，typedef实质上是为已经确定的数据类型增加新的名称。
typedef的语法在本质上是源程序在编译过程中动态地生成（新）关键字，即新数据类型名。关键字在词法解析/扫描规则上等同于常规的标识符，但它与标识符的概念和作用完全不同。
C语言本身已经定义了众多关键字（如if、else、char、int等），理论上这些关键字不得他用。若以此为据，则其他标识符均只能作为变量名、函数名等。而使用typedef 语句增加新变量类型名后，将语言的关键字（集）进行了动态扩充。因此，它势必影响（此后）关键字识别规则。
有必要指出的是，编译器设计在支持typedef的语法/功能上存在较大的难度，将在词法解析与语法解析的交互作用下完成。本节提出的手段未必是最佳方案。
工程项目路径：/cc_source_4.4。
在词法解析器文本cc.l中，新增相关的变量和支持函数，具体如下。
·第17行：增加新变量 ignoreTypedef，整数型变量最低位的bit0=0表示需要检测标识符是否为由typedef定义的变量类型名；bit0=1表示不需要检测（禁止检测）。
·第18行：增加新变量newNameList，用来存放由typedef定义的变量类型名链表（也被称为新类型名表）。
相应地，在common.h/common.c文件中，为newNameList提供添加、查找及删除链表的函数，具体如下。
根据ignoreTypedef变量最低位bit0的状态来判断标识符的性质（常规标识符名或新变量类型名），具体如下。
·第171～181行：对于符合标识符识别规则的字符（串），若该字符（串）没有在新类型名表中出现或禁止检测，则判断其为IDENTIFIER；否则，认定为由typedef定义过的变量类型名。
在语法解析器文本cc.y中，变量的声明和定义语句识别规则将对ignoreTypedef变量进行及时的修改，从而引导词法解析，具体如下。
·第158～164行：数据变量声明结束前，开启（允许）新类型名识别。
·第168～188行：完整的typedef定义语法解析。具体如下。
➢ 第168行：一旦识别typedef关键字本身，就开启（允许）新类型名识别。
➢ 第169行：类型确定后，关闭（禁止）新类型名识别。
➢ 第170行：init_declarator_list中只允许一个标识符出现。
➢ 第186行：整个typedef定义语法解析结束，再次开启（允许）新类型名识别。
struct/union语句中可以出现定义嵌套，因此需对ignoreTypedef变量进行移位（保存/复位），具体如下。
·第722行：开启（允许）新类型名识别，并保留先前的识别/禁止状态。
·第728行：恢复先前的识别/禁止状态。
在变量类型的识别序列中，增加新类型的识别，具体如下。需要注意的是，所有变量类型均使用attrib数据结构来描述，但其中的表示方式有所不同。
·第234～247行：增加新的数据类型说明。其中TYPEDEF_NAME的特征attrib在词法解析cc.l文件中构成并给出类型名（参见cc.l文件第171～181行）。
本章给出的语法解析器将作为编译器的前端词法/语法处理机构。
（1）由cc.l和cc.y文件组成的语法解析器在完成C语言源程序的处理后，将生成符合原意的数据构造——编译树，由progUnit指针指示，作为后续处理的物质基础。
（2）整棵编译树由5种节点结构通过有机链接构成。而这5种节点结构又全部可以通过综合手段归纳为一种通用节点，给表达和理解带来便利。此外，各种节点均可包含其他种类的节点。
（3）本章所介绍的语法解析处理需要在C语言标准内进行某些取舍，主要包括以下几点。
·不支持浮点数的表示和处理。
·只支持一维函数指针数组。
·不支持struct/union中位域的定义和使用。