1、编译原理实验教案编译原理实验教案授课教师：程细才适用专业：计算机科学与技术使用班级：04计算机科学与技术12班授课时间：2007年春季授课学时：54/44/10学时使用教材：编译原理华中科技大学出版社何炎祥 主编实验指导书：编译原理实验指导书，黄石理工学院计算机学院实验教学进度表周次日期实验课题学时实验报告次数105.8-5.12实验一C语言子集编译程序(1)20115.15-5.19实验一C语言子集编译程序(2)20125.22-5.26实验一C语言子集编译程序(3)21135.29-6.2实验二LEX词法分析程序生成器21146.5-6.9实验三YACC语法分析程序生成器21实验一 C语言
2、子集编译程序一、实验目的用C语言对一个C语言的子集编制一个一遍扫描的编译程序，以加深对编译原理的理解，掌握编译程序的实现方法和技术。1设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。2编制一个递归下降分析程序，并对C语言的简单子集进行分析。3通过上机实习，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法成分变换中间代码的语义翻译方法。二、实验要求、内容及学时词法分析部分：2学时（一）待分析的C语言子集的词法：1关键字 main if else int return void while所有关键字都是小写。2专用符号 = + - * / = = != ; : , ( )3.其
3、他标记ID和NUM通过以下正规式定义其他标记： IDletter(letter|digit)* NUMdigit(digit)* lettera|z|A|Z digit0|94.空格由空白、制表符和换行符组成空格一般用来分隔ID、NUM、专用符号和关键字，词法分析阶段空格通常被忽略。各种单词符号对应的类别码：（采用一符一类别码,见下表）单词符号类别码单词符号类别码单词符号类别码main1-23;34int2*2435char3/25=37else5)27=38for628=39while729!=40ID103001000NUM2031ERROR-1=21，32+22：33（二）词法分析程序的
4、功能：输入：所给文法的源程序字符串。输出：二元组（syn,token或sum）构成的序列。其中，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,
5、;) (31, )（三）词法分析程序主要算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。1主程序示意结构图（如下）：置初值调用扫描子程序输出单词二元组直至输入串结束注：关键字表初值 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表可处理为一个字符串数组（实际为指向字符数组的指针数组），其描述如下：char *KEY_WORDS8=“main”,”int”,”char”,”i
6、f”,”else”,”for”,”while”;为分析方便,这里把main作关键字处理。程序中需要用到的主要变量：syn,token和sum。2扫描子程序（scaner）的算法思想 首先设置三个变量：token用来存放构成单词符号的字符串；sum用来存放整型单词；syn用来存放单词的类别码。扫描子程序主要部分NS图如下：变量初始化忽略空格文件是否结束TF是否字母TF拼字符串是否数字是否关键字TFTF拼数是否运算符、界符等符号syn为对应关键字的类别码syn=10syn=20TF给出相应的syn值报错语法分析部分：2学时（一）待分析的C语言子集的语法用扩充的BNF表示如下：1main()2. 3
7、. ;4. |5. ID=6. if()7. while()8. 9. +|-10.*|/11.ID|NUM|()12.|=|=|!=（二）语法分析程序的主要算法思想1主程序结构示意图如下：置初值调用scaner读下一个单词符号调用lrparser结束2递归下降分析程序结构示意图如下：注：上接lrparser是否单词串main()TF调用scaner出错处理调用语句块分析函数源程序是否结束TF输出分析成功出错处理3语句块分析结构示意图。是否TF调用scaner出错处理调用语句串分析函数（过程）是否TF出错处理4语句串分析结构示意图如下：调用statement函数当为；时调用scaner调用st
8、atement函数出错处理5statement函数NS图如下：是否标识符TF调用scaner是否if是否=TFTF调用scaner是否while调用scaner出错处理调用conditionTF调用expression调用语句块调用scaner出错处理调用condition调用语句块6expression函数结构示意图如下：调用term是否+、-TF调用scaner出错处理调用term7term函数结构示意图如下：调用factor是否*、/TF调用scaner出错处理调用factor8.condition函数结构示意图如下：调用expression是否逻辑运算符TF调用scaner出错处理调用
9、expression9factor函数结构示意图如下：是否标识符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, , j7:j, j, 0, 98:j, , , 119:
10、=, 1, , k10:j, , , 7（二）算法思想1设置语义过程int gen(op,arg1,arg2,result)该函数是将四元式(op,arg1,arg2,result)送到四元式表中。char *newtemp()该函数回送一个新的临时变量名，临时变量名产生的顺序为：T1，T2，int merg(p1,p2)该函数将以p1和p2为头指针的两条链合并为一，合并后的链表首为返回值。int bp(p,t)该函数的功能是把p所链接的每个四元式的第四区段都填为t。2主程序示意图如下：置初值调用scaner调用lrparser打印四元式列表结束3函数lrparse在原来语法分析的基础上插入相
11、应的语义动作。 将输入串翻译成四元式序列。在实验中我们只对表达式、if语句和while语句进行翻译，其具体翻译程序见实例。算符优先分析法部分：（选作）算符优先分析法特别有利于表达式的处理，宜于手工实现。算符优先分析过程是自下而上的归约过程，但这种归约未必是严格的规范归约。因此，所谓算符优先分析法就是定义算符之间的某种优先关系，并借助这种关系寻找句型的最左素短语进行归约。算符优先分析法通常有两种：优先矩阵法和优先函数法。前者是提供一张算符优先关系表，后者提供两个优先函数（入栈优先函数f和比较优先函数g），优先函数法比优先矩阵法节约存储空间，所以较为普遍。下面介绍使用优先函数法的分析过程。分析过程
12、：先在算符栈置“$”，然后开始顺序扫描表达式。若读来的单词符号是操作数，则直接进操作数栈，然后继续下一个单词符号。分析过程从头开始，并重复进行；若读来的单词符号是运算符，则将当前处于运算符栈顶的运算符的入栈优先函数f与的比较优先函数g进行比较。1若，则进算符栈，并继续顺序往下扫描，分析过程重复进行。2若，则产生对操作数栈顶的若干项进行运算的中间代码，并从运算符栈顶移去，且从操作数栈顶移去相应若干项，然后把执行运算的结果压入操作数栈。接着以运算符栈新的项与进行上述比较。3重复步骤1，2，直到“$”和“$”配对为止。三、实验环境DOS或Windows操作系统TURBO C 2.0或Visual C
13、+四、实验参考（参考代码）#ifndef _GLOBALS_H#define _GLOBALS_H#include#include#include #define _SYN_MAIN 1#define _SYN_INT 2#define _SYN_CHAR 3#define _SYN_IF 4#define _SYN_ELSE 5#define _SYN_FOR 6#define _SYN_WHILE 7 #define _SYN_ID 10#define _SYN_NUM 20 #define _SYN_ASSIGN 21#define _SYN_PLUS 22#define _SYN_MI
14、NUS 23#define _SYN_TIMES 24#define _SYN_DIVIDE 25#define _SYN_LPAREN 26#define _SYN_RPAREN 27#define _SYN_LEFTBRACKET1 28#define _SYN_RIGHTBRACKET1 29#define _SYN_LEFTBRACKET2 30#define _SYN_RIGHTBRACKET2 31#define _SYN_COMMA 32#define _SYN_COLON 33#define _SYN_SEMICOLON 34#define _SYN_LG 35#define
15、_SYN_LT 36#define _SYN_ME 37#define _SYN_LE 38#define _SYN_EQ 39#define _SYN_NE 40#define _SYN_END 1000 #define _SYN_ERROR -1#define MAXLENGTH 255#ifndef _SEMANTEM_H#define _SEMANTEM_H/*四元组的结构*/typedef struct QUADchar opMAXLENGTH; /*操作符*/char argv1MAXLENGTH; /*第一个操作数*/ char argv2MAXLENGTH; /*第二个操作数*
16、/char resultMAXLENGTH; /*运算结果*/QUATERNION;void lrparse(void); /*语法语义分析主函数*/#endifunion WORDCONTENT char T1MAXLENGTH; int T2; char T3;typedef struct WORD int syn; union WORDCONTENT value;WORD;#ifndef _SCAN_H#define _SCAN_H#define _TAB_LEGNTH 4#define _KEY_WORD_END waiting for you expandingvoid Scaner
17、(void);#endifQUATERNION *pQuad;int nSuffix,nNXQ,ntc,nfc;extern WORD uWord;extern int gnColumn,gnRow;FILE *fw;char *strFileName;char *strSource;char *Expression(void);char *Term(void);char *Factor(void);void Statement_Block(int *nChain);/*FILE *Source;*/FILE *fw;char *strSource;void Do_Tag(char *strS
18、ource);void Do_Digit(char *strSource);void Do_EndOfTag(char *strSource);void Do_EndOfDigit(char *strSource);void Do_EndOfEqual(char *strSource);void Do_EndOfPlus(char *strSource);void Do_EndOfSubtraction(char *strSource);void Do_EndOfMultiply(char *strSource);void Do_EndOfDivide(char *strSource);voi
19、d Do_EndOfLParen(char *strSource);void Do_EndOfRParen(char *strSource);void Do_EndOfLeftBracket1(char *strSource);void Do_EndOfRightBracket1(char *strSource);void Do_EndOfLeftBracket2(char *strSource);void Do_EndOfRightBracket2(char *strSource);void Do_EndOfColon(char *strSource);void Do_EndOfComma(
20、char *strSource);void Do_EndOfSemicolon(char *strSource);void Do_EndOfMore(char *strSource);void Do_EndOfLess(char *strSource);void Do_EndOfEnd(char *strSource);void PrintWord(WORD uWord);void ApartWord(char *strSource);void PrintError(int nColumn,int nRow,char chInput);void Scaner(void);int gnColum
21、n,gnRow,gnLocate,gnLocateStart;WORD uWord;char *KEY_WORDS20=main,int,char,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 *strSo
22、urce)/开始识别一个单词 gnLocateStart=gnLocate; switch(strSourcegnLocate) 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_EndOfRPar
23、en(strSource); break; case : Do_EndOfLeftBracket1(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 ;:
24、 Do_EndOfSemicolon(strSource); break; case : Do_EndOfMore(strSource); break; case : Do_EndOfLess(strSource); break; case =: Do_EndOfEqual(strSource); break; case 0: Do_EndOfEnd(strSource); break; default: if(IsChar(strSourcegnLocate) Do_Tag(strSource); else if(IsDigit(strSourcegnLocate) uWord.value.
25、T2=strSourcegnLocate-0; Do_Digit(strSource); else if(strSourcegnLocate!= &strSourcegnLocate!=t &strSourcegnLocate!=n &strSourcegnLocate!=r) PrintError(gnColumn,gnRow,strSourcegnLocate); if(strSourcegnLocate=n |strSourcegnLocate=r) gnColumn+; gnRow=1; else if(strSourcegnLocate=t) gnColumn+=_TAB_LEGNT
26、H; else gnRow+; gnLocate+;Do_Start(strSource); break; return;void Do_Tag(char *strSource)/识别标识符的中间状态 gnLocate+; gnRow+; if(IsChar(strSourcegnLocate)|IsDigit(strSourcegnLocate) Do_Tag(strSource); else Do_EndOfTag(strSource); return;void Do_Digit(char *strSource)/识别整数的中间状态 gnLocate+; gnRow+; if(IsDigit(strSourcegnLocate) uWord.value.T2=uWord.value.T2*10+strSourcegnLocate-0; Do_Digit(strSource); else Do_EndOfDigit(strSource); return;void Do_EndOfTag(char *strSource)/识别标识符的最后状态 int nL
