编译程序实验指导书讲解[共25页]

1、编译程序实验指导书实验目的：用C语言对一个C语言的子集编制一个一遍扫描的编译程序，以加深对编译原理的理解，掌握编译程序的实现方法和技术。1词法分析1.1 实验目的设计、编制并测试一个词法分析程序，加深对词法分析原理的理解。1.2 实验要求1.2.1 待分析的C语言子集的词法1. 关键字main if else int char for while 所有的关键字都是小写。2专用符号= + - * / = = != ; : , ( )3其他标记ID和NUM通过以下正规式定义其他标记：IDletter(letter|digit)*NUMdigit digit*lettera|z|A|Zdigit0|

2、94空格由空白、制表符和换行符组成空格一般用来分隔ID、NUM、专用符号和关键字，词法分析阶段通常被忽略。1.2.2 各种单词符号对应的种别码表1 各种单词符号的种别码单词符号 种别码 单词符号 种别码 单词符号 种别码main 1 = 21 , 32int 2 + 22 : 33char 3 - 23 ; 34if 4 * 24 35else 5 / 25 = 37while 7 ) 27 = 38ID 10 28 = 39MUN 20 29 != 40 30 0 1000 31 ERROR -11.2.3 词法分析程序的功能输入：所给文法的源程序字符串。输出：二元组（syn,token或s

3、um）构成的序列。其中，. syn为单词种别码。. Token为存放的单词自身字符串。. Sum为整型常量。具体实现时，可以将单词的二元组用结构进行处理。例如，对源程序main()int i=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 词法分析程序的主要算法思想算法的基本任务是从字符

4、串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到的单词符号的第一个字符的种类，拼出相应的单词符号。1. 主程序示意图 主程序示意图如图1所示。 置初值调用扫描子程序输出单词二元组输入串结束结束否是图1 词法分析主程序示意图其中初值包括如下两方面：(1) 关键字表初值关键字作为特殊标识符处理,把它们预先安排在一张表格中(称为关键字表),当扫描程序识别出标识符时,查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：char *KEY_WORDS8=“main”,”int”,”char”,”if”,”else”,”for”,”

5、while”；为分析方便，这里把main作关键字处理。(2) 程序中需要用到的主要变量：syn,token和sum。2. 扫描子程序的算法思想首先设置三个变量：token用来存放构成单词符号的字符串；sum用来存放整型单词；syn用来存放单词符号的种别编码。扫描子程序主要部分流程如图2所示。变量初始化 忽略空格是是否文件结束 返回否其他符号运算符,界符等符号字母数字否对不同符号给出相应的syn值是否关键字是Syn为对应关键字的单词种别码返回报错拼数拼字符串Syn=10Syn=11图2 词法分析程序流程2语法分析2.1 实验目的编制一个递归下降分析程序， 实现对词法分析程序所提供的单词序列进行语

6、法检查和结构分析。2.2 实验要求利用C语言编制递归下降分析程序，并对C语言的简单子集进行分析。2.2.1 待分析的C语言子集的语法用扩充的BNF表示如下：(1) =main( )(2) =(3) =;(4) =|(5) =ID=(6) =if()(7) =while(8) =(9) =+|-(10)=*|/(11)=ID|NUM|()(12)=|=|=|!=2.3 语法分析程序的算法思想(1) 主程序示意图如图3所示。置初值调用scaner读下一个单词符号调用lrparser结束图3 语法分析主程序示意图(2) 递归下降分析程序示意图如图4所示。lrparser否否是否单词串main()是调

7、用scaner出错处理调用语句块分析函数否源程序是否结束是打印分析成功图4递归下降分析程序示意图(3) 语句块分析过程示意图如图5所示。否是否是调用scaner出错处理调用语句串分析过程否是否是出口图5语句块分析示意图(4) 语句串分析过程示意图如图6所示。调用statement函数 否否是否；是调用scaner调用statement函数出错处理图6语句串分析示意图(5) statement (语句) 函数流程如图7所示；(6) expression（表达式）分析过程如图8所示；(7) term（项）分析过程如图9所示；(8) condition（条件）分析过程如图10所示；(9) facto

8、r（因子）分析过程如图11所示。否是调用scaner是调用expression是否标识符否是否ifififfifififif标识符否是否while是是调用scaner调用scaner是否=否调用condition调用condition调用语句块调用语句块调用scaner出错处理图7 statement函数流程调用factor调用ffactor调用term出错处理调用factor调用scaner是否*、/是否否是否+、-是出错处理调用scaner调用term图8 expression分析过程示意图 图9 term分析过程示意图调用scaner调用expression否是否逻辑运算符是出错处理调用

9、expression图10 condition分析过程示意图是是否标识符否是是否数字否是否（否是调用expression调用scaner是否）否调用scaner是出错处理调用scaner图11 factor分析过程示意图 3语义分析产生中间代码3.1 实验目的通过上机实验，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法成分变换为中间代码的语义翻译方法。3.2 实验要求采用递归下降语法制导翻译法对算术表达式、赋值语句、条件语句、循环语句进行语义分析生成四元式序列。3.2.1 实验的输入和输出输入是语法分析提供的正确的单词串，输出是四元式序列。例如，对于语句串i=2*3+4;if (i1

10、0) j=3;while j10 k=1;输出的四元式序列如下：(1) (*,2,3,T1)(2) (+,2,T1,T2)(3) (=,T2, ,i)(4) (j,i,10,6)(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). int gen(op,arg1,arg2,result)该函数是将四元式(op,arg1,arg2,result)送到四元式表中。(2). char *newtemp( )该函数回送一个新的临时变量名

11、，临时变量名产生的顺序为T1,T2,.(3). int merg(p1,p2)该函数将以p1和p2为头指针的两条链合并为一，合并后的链首为返回值。(4). int bp(p,t)该函数的功能是把p所链接的每个四元式的第四区段都填为t。2. 主程序示意图置初值调用scaner调用lrparser打印四元式列表结束图12 语义分析主程序示意图3. 函数lrparser在原来语法分析的基础上插入相应的语义动作将输入串翻译成四元式序列。在实验中我们只对表达式、if语句和while语句进行翻译，其具体翻译程序见实验实例。4实验实例/*/*文件：globals.h */*定义分析器需要的一些数据结构、宏等

12、 */*本头文件必须在其他文件前引用 */*/# ifndef _GLOBALS_H# define _GLOBALS_H# include # include # include /*单词种别码*/# 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/*整数

13、的单词种别码*/# 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_LEFTBRACKET2

14、30/* */# define _SYN_RIGHTBRACKET231/* */# define _SYN_COMMA32/* , */# define _SYN_COLON33/* : */# define _SYN_SEMICOLON34/* ; */# define _SYN_LG35/* */# define _SYN_LT36/* = */# define _SYN_LE38/* ,= */void Do_EndOfLess(char *strSource);/* ,= */void Do_EndOfEnd(char *strSource);/* 用 0 作为源程序结束 */voi

15、d PrintError(int nColumn,int nRow,char chInput);/* 词法分析错误输出 */void Scaner(void)；/* 词法扫描函数 */extern char *strSource;/* 待分析的源程序 */extern FILE *fw;/* 结果输出文件 */int gnColumn,gnRow,/* 行列号 */ gnLocate,/* 下一个字符脚标 */ gnLocateStart;/* 下一个单词开始位置 */Word uWord;/* 扫描出的单词 */* 关键字表 */char *KEY_WORDS20=main,int,char

16、,if,else,for,while,void,_KEY_WORD_END;int IsDigit(char chInput)/* 判断扫描的字符是否数字 */ if (chInput=0) return 1; else return 0;int IsChar(char chInput)/* 判断扫描的字符是否字母 */ if (chInput=a) | (chInput=A) return 1; else return 0;void Do_Start(char *strSource)/* 开始识别最先一个单词 */ gnLocateStart=gnLocate; switch (strSou

17、rcegnLocate)/* 根据第一个字符判断 */ case +: Do_EndOfPlus(strSource);break; case -: Do_EndOfSubtraction(strSource);break; case *: Do_EndOfMultiply(strSource);break; case /: Do_EndOfDivide(strSource);break; case (: Do_EndOfLParen(strSource);break; case ): Do_EndOfRParen(strSource);break; case : Do_EndOfLeftBr

18、acket1(strSource);break; case : Do_EndOfRightBracket1(strSource);break; case : Do_EndOfLeftBracket2(strSource);break; case : Do_EndOfRightBracket2(strSource);break; case : Do_EndOfColon(strSource);break; case ,: Do_EndOfComma(strSource);break; case ;: Do_EndOfSemicolon(strSource);break; case : Do_En

19、dOfMore(strSource);break; case ,= */ if (strSourcegnLocate+1!=) /* */ uWord.syn=_SYN_LG; uWord.value.T3=strSourcegnLocate; else /*= */gnLocate+;gnRow+;uWord.syn=_SYN_ME;strcpy(uWord.value.T1,=); gnLocate+; gnRow+; return;void Do_EndOfLess(char *strSource)/* ,= */ if (strSourcegnLocate+1!=) /* */ uWo

20、rd.syn=_SYN_LT; uWord.value.T3=strSourcegnLocate; else /*= */gnLocate+;gnRow+;uWord.syn=_SYN_LE;strcpy(uWord.value.T1,=); gnLocate+; gnRow+; return;void Do_EndOfEnd(char *strSource)/* 读到0,源程序结束 */ uWord.syn=_SYN_END; uWord.value.T3=strSourcegnLocate; gnLocate+; gnRow+; return;void PrintWord(Word uWo

21、rd)/* 打印二元组 */ if (uWord.syn= */ | uWord.syn=_SYN_LE/* Col:%dtRow:%dtChar:%c,nColumn,nRow,chInput); return;/*/*文件：semanteme.h */*定义语法（语义）分析器的接口 */*/# ifndef _SEMANTEME_H# define _SEMANTEME_H/* 四元组的结构 */typedef struct QUAD char opMAXLENGTH;/* 操作符 */ char argv1MAXLENGTH;/* 第一个操作数 */ char argv2MAXLENGT

22、H;/* 第二个操作数 */ char resultMAXLENGTH;/* 运算结果 */QUATERNION;void lrparse(void);/* 语法语义分析主函数 */# endif/*/*文件：semanteme.c */*分析器的语法语义扫描部分 */*/# include globals.h# include scan.h# include semanteme.hQUATERNION *pQuad;/* 存放四元组的元组 */int nSuffix,nNXQ,/* 临时变量的编号 */ntc,nfc;extern Word uWord;/* 扫描得到的单词 */extern

23、 int gnColumn,gnRow;/* 行列号 */FILE *fw;/* 打印结果的文件指针 */char *strFileName;/* 打印结果的文件名 */char *strSource;/* 源程序 */char *Expression(void);char *Term(void);char *Factor(void);void Statement_Block(int *nChain);void LocateError(int nColumn,int nRow)/* 定位语法错误 */ fprintf(fw,nCol:%dtRow:%d-,nColumn+1,nRow);voi

24、d error(char *strError)/* 输出扫描发现的错误 */ LocateError(gnColumn,gnRow); fprintf(fw,%s,strError); return;void Match(int syn,char *strError)/* 判断当前识别出的单词是否需要的单词， 如果不是则报错，否则扫描下一个单词 */ if (syn=uWod.syn) Scaner( ); else error(strError); return;void gen(char *op,char *argv1,char *argv2,char *result)/* 生成一个四元式

25、 */ sprintf(pQuadnNXQ.op,op); sprintf(pQuadnNXQ.argv1,argv1); sprintf(pQuadnNXQ.argv2,argv2); sprintf(pQuadnNXQ.result,result); nNXQ+; return;void PrintQuaternion(void)/* 打印一个四元式 */ int nLoop; for (nLoop=1;nLoopnNXQ;nLoop+) fprintf(fw,n%d:%s,t%s,t%s, nLoop,pQuadnLoop.op,pQuadnLoop.argv1, pQuadnLoop.argv2,pQuadnLoop.result); char *Newtemp(void)/* 产生一个临时变量 */ char *strTempID=(char *) malloc(MAXLENGTH); sprintf(strTempID,T%d,+nSuffix); return strTempID;int merg(i