编译原理实验指导书

16089296369051《编译原理》课程实验指导书计算机学院编２００７年９月16089296369052实验一C语言子集编译程序一、实验目的用C语言对一个C语言的子集编制一个一遍扫描的编译程序，以加深对编译原理的理解，掌握编译程序的实现方法和技术。1．设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。2．编制一个递归下降分析程序，并对C语言的简单子集进行分析。3．通过上机实习，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法成分变换中间代码的语义翻译方法。二、实验要求、内容及学时词法分析部分：2学时（一）待分析的C语言子集的词法：1．关键字mainifelseintreturnvoidwhile所有关键字都是小写。2．专用符号=+-*/====!=;:,{}[]()3.其他标记ID和NUM通过以下正规式定义其他标记：ID→letter(letter|digit)*NUM→digit(digit)*letter→a|…|z|A|…|Zdigit→0|…|94.空格由空白、制表符和换行符组成空格一般用来分隔ID、NUM、专用符号和关键字，词法分析阶段空格通常被忽略。各种单词符号对应的类别码：（采用一符一类别码,见下表）单词符号类别码单词符号类别码单词符号类别码main1-23;34int2*2435char3/2536if4(26=37else5)27=38for6[28==3916089296369053while7]29!=40ID10{30‘\0’1000NUM20}31ERROR-1=21，32+22：33（二）词法分析程序的功能：输入：所给文法的源程序字符串。输出：二元组（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．主程序示意结构图（如下）：置初值调用扫描子程序输出单词二元组直至输入串结束注：16089296369054①关键字表初值关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表可处理为一个字符串数组（实际为指向字符数组的指针数组），其描述如下：char*KEY_WORDS[8]={“main”,”int”,”char”,”if”,”else”,”for”,”while”};为分析方便,这里把main作关键字处理。②程序中需要用到的主要变量：syn,token和sum。2．扫描子程序（scaner）的算法思想首先设置三个变量：token用来存放构成单词符号的字符串；sum用来存放整型单词；syn用来存放单词的类别码。扫描子程序主要部分N—S图如下：变量初始化忽略空格文件是否结束TF是否字母TF拼字符串是否数字是否关键字TFTF拼数是否运算符、界符等符号syn为对应关键字的类别码syn=10syn=20TF给出相应的syn值报错语法分析部分：2学时（一）待分析的C语言子集的语法用扩充的BNF表示如下：1．程序→main()语句块2.语句块→’{‘语句串’}’3.语句串→语句{;语句};4.语句→赋值语句|条件语句|循环语句5.赋值语句→ID=表达式6.条件语句→if(条件表达式)语句块160892963690557.循环语句→while(条件表达式)语句块8.条件表达式→表达式关系运算符表达式9.表达式→项{+项|-项}10.项→项{*因子|/因子}11.因子→ID|NUM|(表达式)12.关系运算符→|=||=|==|!=（二）语法分析程序的主要算法思想1．主程序结构示意图如下：置初值调用scaner读下一个单词符号调用lrparser结束2．递归下降分析程序结构示意图如下：注：上接lrparser是否单词串main()TF调用scaner出错处理调用语句块分析函数源程序是否结束TF输出分析成功出错处理3．语句块分析结构示意图。是否{TF调用scaner出错处理调用语句串分析函数（过程）是否}TF出错处理4．语句串分析结构示意图如下：16089296369056调用statement函数当为；时调用scaner调用statement函数出错处理5．statement函数N—S图如下：是否标识符TF调用scaner是否if是否=TFTF调用scaner是否while调用scaner出错处理调用conditionTF调用expression调用语句块调用scaner出错处理调用condition调用语句块6．expression函数结构示意图如下：调用term是否+、-TF调用scaner出错处理调用term7．term函数结构示意图如下：调用factor是否*、/TF调用scaner出错处理调用factor8.condition函数结构示意图如下：16089296369057调用expression是否逻辑运算符TF调用scaner出错处理调用expression9．factor函数结构示意图如下：是否标识符TF调用scaner是否数字TF调用scaner是否（TF调用scaner出错处理调用expression是否）TF调用scaner出错处理语义分析部分：2学时（一）实验的输入和输出输入是语法分析提供的正确的单词串，输出是四元式序列。例如，对于语句串i=2*3+4;if(i10){j=3;}while(j0)k=1;输出的四元式序列如下：1:*,2,3,T12:+,T1,4,T23:=,T2,,i4:j,i,10,65:j,,,76:=,3,,j160892963690587:j,j,0,98:j,,,119:=,1,,k10:j,,,7（二）算法思想1．设置语义过程①intgen(op,arg1,arg2,result)该函数是将四元式(op,arg1,arg2,result)送到四元式表中。②char*newtemp()该函数回送一个新的临时变量名，临时变量名产生的顺序为：T1，T2，……③intmerg(p1,p2)该函数将以p1和p2为头指针的两条链合并为一，合并后的链表首为返回值。④intbp(p,t)该函数的功能是把p所链接的每个四元式的第四区段都填为t。2．主程序示意图如下：置初值调用scaner……调用lrparser打印四元式列表结束3．函数lrparse在原来语法分析的基础上插入相应的语义动作。将输入串翻译成四元式序列。在实验中我们只对表达式、if语句和while语句进行翻译，其具体翻译程序见实例。算符优先分析法部分：（选作）算符优先分析法特别有利于表达式的处理，宜于手工实现。算符优先分析过程是自下而上的归约过程，但这种归约未必是严格的规范归约。因此，所谓算符优先分析法就是定义算符之间的某种优先关系，并借助这种关系寻找句型的最左素短语进行归约。算符优先分析法通常有两种：优先矩阵法和优先函数法。前者是提供一张算符优先关系表，后者提供两个优先函数（入栈优先函数f和比较优先函数g），优先函数法比优先矩阵法节约存储空间，所以较为普遍。下面介绍使用优先函数法的分析过程。16089296369059分析过程：先在算符栈置“$”，然后开始顺序扫描表达式。若读来的单词符号是操作数，则直接进操作数栈，然后继续下一个单词符号。分析过程从头开始，并重复进行；若读来的单词符号是运算符2，则将当前处于运算符栈顶的运算符1的入栈优先函数f与2的比较优先函数g进行比较。1．若12()()fg，则2进算符栈，并继续顺序往下扫描，分析过程重复进行。2．若12()()fg，则产生对操作数栈顶的若干项进行1运算的中间代码，并从运算符栈顶移去1，且从操作数栈顶移去相应若干项，然后把执行1运算的结果压入操作数栈。接着以运算符栈新的项与2进行上述比较。3．重复步骤1，2，直到“$”和“$”配对为止。三、实验环境DOS或Windows操作系统TURBOC2.0或VisualC++四、实验参考（参考代码）#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_NUM20160892963690510#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#defineMAXLENGTH255#ifndef_SEMANTEM_H#define_SEMANTEM_H/*四元组的结构*/typedefstructQUAD{160892963690511charop[MAXLENGTH];/*操作符*/charargv1[MAXLENGTH];/*第一个操作数*/charargv2[MAXLENGTH];/*第二个操作数*/charresult[MAXLENGTH];/*运算结果*/}QUATERNION;voidlrparse(void);/*语法语义分析主函数*/#endifunionWORDCONTENT{charT1[MAXLENGTH];intT2;charT3;};typedefstructWORD{intsyn;unionWORDCONTENTvalue;}WORD;#ifndef_SCAN_H#define_SCAN_H#define_TAB_LEGNTH4#define_KEY_WORD_ENDwaitingforyouexpandingvoidScaner(void);#endif160892963690512QUATERNION*pQuad;intnSuffix,nNXQ,ntc,nfc;externWORDuWord;externintgnColumn,gnRow;FILE*fw;char*strFileName;char*strS