编译程序实验指导书讲解

编译程序实验指导书实验目的：用C语言对一个C语言的子集编制一个一遍扫描的编译程序，以加深对编译原理的理解，掌握编译程序的实现方法和技术。1．词法分析1.1实验目的设计、编制并测试一个词法分析程序，加深对词法分析原理的理解。1.2实验要求1.2.1待分析的C语言子集的词法1.关键字mainifelseintcharforwhile所有的关键字都是小写。2．专用符号=+-*/====!=;:,{}[]()3．其他标记ID和NUM通过以下正规式定义其他标记：ID→letter(letter|digit)*NUM→digitdigit*letter→a|…|z|A|…|Zdigit→0|…|9…4．空格由空白、制表符和换行符组成空格一般用来分隔ID、NUM、专用符号和关键字，词法分析阶段通常被忽略。1.2.2各种单词符号对应的种别码表1各种单词符号的种别码单词符号种别码单词符号种别码单词符号种别码main1=21,32int2+22:33char3-23;34if4*2435else5/2536for6(26=37while7)27=38ID10[28==39MUN20]29!=40{30‘\0’1000}31ERROR-11.2.3词法分析程序的功能输入：所给文法的源程序字符串。输出：二元组（syn,token或sum）构成的序列。其中，.syn为单词种别码。.Token为存放的单词自身字符串。.Sum为整型常量。具体实现时，可以将单词的二元组用结构进行处理。例如，对源程序main(){inti=10;while(i)i=i-1;}的源文件，经词法分析后输出如下序列：(1,main)(26,()(27,))(30,{}(2,int)(10,i)(21,=)(20,10)(34,;)(7,while)(26,()(10,i)(27,))(10,i)(21,=)(10,i)(23,-)(20,1)(34,;)(31,))1.3词法分析程序的主要算法思想算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到的单词符号的第一个字符的种类，拼出相应的单词符号。1.主程序示意图主程序示意图如图1所示。图1词法分析主程序示意图其中初值包括如下两方面：(1)关键字表初值关键字作为特殊标识符处理,把它们预先安排在一张表格中(称为关键字表),当扫描程序识别出标识符时,查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：char*KEY_WORDS[8]={“main”,”int”,”char”,”if”,”else”,”for”,”while”}；为分析方便，这里把main作关键字处理。(2)程序中需要用到的主要变量：syn,token和sum。是否输入串结束置初值调用扫描子程序输出单词二元组结束2.扫描子程序的算法思想首先设置三个变量：token用来存放构成单词符号的字符串；sum用来存放整型单词；syn用来存放单词符号的种别编码。扫描子程序主要部分流程如图2所示。图2词法分析程序流程2．语法分析2.1实验目的编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析。2.2实验要求利用C语言编制递归下降分析程序，并对C语言的简单子集进行分析。2.2.1待分析的C语言子集的语法用扩充的BNF表示如下：(1)程序∷=main()语句块(2)语句块∷=’{’语句串’}’(3)语句串∷=语句{;语句};(4)语句∷=赋值语句|条件语句|循环语句否是其他符号运算符,界符等符号字母数字否是返回变量初始化忽略空格是否文件结束拼字符串是否关键字拼数Syn=10Syn为对应关键字的单词种别码Syn=11对不同符号给出相应的syn值报错返回(5)赋值语句∷=ID=表达式(6)条件语句∷=if(条件)语句块(7)循环语句∷=while条件语句块(8)条件∷=表达式关系运算符表达式(9)表达式∷=项{+项|-项}(10)项∷=因子{*因子|/因子}(11)因子∷=ID|NUM|(表达式)(12)关系运算符∷=|=||=|==|!=2.3语法分析程序的算法思想(1)主程序示意图如图3所示。图3语法分析主程序示意图(2)递归下降分析程序示意图如图4所示。图4递归下降分析程序示意图是否否否是lrparser置初值调用scaner读下一个单词符号调用lrparser结束调用scaner调用语句块分析函数是否单词串main()源程序是否结束打印分析成功出错处理(3)语句块分析过程示意图如图5所示。图5语句块分析示意图(4)语句串分析过程示意图如图6所示。图6语句串分析示意图(5)statement(语句)函数流程如图7所示；(6)expression（表达式）分析过程如图8所示；(7)term（项）分析过程如图9所示；(8)condition（条件）分析过程如图10所示；(9)factor（因子）分析过程如图11所示。是否是否否是调用scaner调用语句串分析过程是否{是否}出错处理出口调用statement函数调用scaner调用statement函数是否；出错处理否图7statement函数流程图8expression分析过程示意图图9term分析过程示意图否是是是是是否否否是否标识符否调用scaner是否=调用scaner调用expression调用scaner调用condition调用语句块出错处理调用scaner调用condition调用语句块是否ifififfifififif是否标识符是否标识符标识符是否while调用term是否+、-调用scaner调用term出错处理否是调用factor调用ffactor是否*、/调用scaner调用factor出错处理否是调用expression是否逻辑运算符调用scaner调用expression出错处理图10condition分析过程示意图图11factor分析过程示意图3．语义分析产生中间代码3.1实验目的通过上机实验，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法成分变换为中间代码的语义翻译方法。3.2实验要求采用递归下降语法制导翻译法对算术表达式、赋值语句、条件语句、循环语句进行语义分析生成四元式序列。3.2.1实验的输入和输出输入是语法分析提供的正确的单词串，输出是四元式序列。例如，对于语句串i=2*3+4;if(i10)j=3;whilej10k=1;输出的四元式序列如下：(1)(*,2,3,T1)(2)(+,2,T1,T2)(3)(=,T2,,i)(4)(j,i,10,6)否是否是是否否是是否数字调用scaner调用expression出错处理是否标识符是否（是否）调用scaner调用scaner(5)(j,,,7))(6)(=,3,,j)(7)(j,j,10,9)(8)(j,,,11)(9)(=,1,,k)(10)(j,,,7)(11)......3.2.2算法思想1.设置语义过程(1).intgen(op,arg1,arg2,result)该函数是将四元式(op,arg1,arg2,result)送到四元式表中。(2).char*newtemp()该函数回送一个新的临时变量名，临时变量名产生的顺序为T1,T2,....(3).intmerg(p1,p2)该函数将以p1和p2为头指针的两条链合并为一，合并后的链首为返回值。(4).intbp(p,t)该函数的功能是把p所链接的每个四元式的第四区段都填为t。2.主程序示意图图12语义分析主程序示意图3.函数lrparser在原来语法分析的基础上插入相应的语义动作将输入串翻译成四元式序列。在实验中我们只对表达式、if语句和while语句进行翻译，其具体翻译程序见实验实例。4．实验实例/****************************************************//*文件：globals.h*//*定义分析器需要的一些数据结构、宏等*//*本头文件必须在其他文件前引用*/置初值调用scaner调用lrparser打印四元式列表结束…/***************************************************/#ifndef_GLOBALS_H#define_GLOBALS_H#includestdio.h#includestdlib.h#includestring.h/*单词种别码*/#define_SYN_MAIN1#define_SYN_INT2#define_SYN_CHAR3#define_SYN_IF4#define_SYN_ELSE5#define_SYN_FOR6#define_SYN_WHILE7/*以上为关键字的单词种别码*/#define_SYN_ID10/*标识符的单词种别码*/#define_SYN_NUM20/*整数的单词种别码*/#define_SYN_ASSIGN21/*=*/#define_SYN_PLUS22/*+*/#define_SYN_MINUS23/*-*/#define_SYN_TIMES24/***/#define_SYN_DIVIDE25/*/*/#define_SYN_LPAREN26/*(*/#define_SYN_RPAREN27/*)*/#define_SYN_LEFTBRACKET128/*[*/#define_SYN_RIGHTBRACKET129/*]*/#define_SYN_LEFTBRACKET230/*{*/#define_SYN_RIGHTBRACKET231/*}*/#define_SYN_COMMA32/*,*/#define_SYN_COLON33/*:*/#define_SYN_SEMICOLON34/*;*/#define_SYN_LG35/**/#define_SYN_LT36/**/#define_SYN_ME37/*=*/#define_SYN_LE38/*=*/#define_SYN_EQ39/*==*/#define_SYN_NE40/*!=*/#define_SYN_END1000/*源程序结束标志*/#define_SYN_ERROR-1/*error*/#defineMAXLENGTH255/*一行允许的字符个数*/unionWORDCONTENT{/*存放单词内容的联合*/charT1[MAXLENGTH];intT2;charT3;};typedefstructWORD{/*单词二元组*/intsyn;unionWORDCONTENTvalue;}WORD;#endif/**************************************************//*文件：scan.h*//*定义词法分析器的接口*//**************************************************/#ifndef_SCAN_H#define_SCAN_H/*一个TAB占用的空格数*/#define_TAB_LENGTH4/*关键字结束标记*/#define_KEY_WORD_ENDwaitingforyourexpanding/*函数Scaner得到源程序里的下一个单词符号*/voidScaner(void);#endif/**************************************************//*文件：scan.c*//*分析器的词法扫描部分*//**************************************************/#includeglobals.h#Includescan.hvoidDo_Tag(