DOWHILE循环语句的翻译程序设计（简单优先法、输出四元式）.doc

武汉理工大学编译原理课程设计说明书学 号： 0120910340521课 程 设 计题 目DO-WHILE循环语句的翻译程序设计（简单优先法、输出四元式）学 院计算机科学与技术学院专 业计算机科学与技术专业班 级计算机0905姓 名冯 强指导教师杨克俭2012年01月04日课程设计任务书学生姓名： 冯 强 专业班级： 计算机0905班 指导教师： 杨克俭 工作单位：计算机科学与技术学院 题目: DO-WHILE循环语句的翻译程序设计（简单优先法、输出四元式）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码四元式的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名： 2011年 11月 23日系主任（或责任教师）签名： 2011年 11月 23日DO-WHILE语句的翻译程序设计(简单优先法,输出四元式)1问题描述输入一个DO-WHILE的语句,进行词法分析,词法分析器利用超前搜索,状态转换等方法,将源程序转化成为一个一个的单词符号二元式,如果词法分析无误,则进入语法分析部分,使用简单优先法进行文法分析,为每个终极符与非终极符之间定义优先关系,利用优先关系进行移进-规约,如果能规约到文法的开始符,则文法分析成功,输出四元式.2文法及属性文法的描述2.1文法描述G(s): S-do B while E,B-c:=a+1,E-ab2.2属性文法描述G(s): S-do B while E, S.begin:=newlabel; B.next:=S.begin; E.true:=newlabel; E.false:= S.next; S.code:=gen(S.begin:) B.code E.code gen(E.true:) gen(gotoS.begin) B-c:=a+1 B.code:= c:=a+1 E-ab E.code=gen(ifabgoto E.true) Gen(goto E.false) E-true E.code:=gen(goto E.true) E-false E.code:=gen(goto E.false) 3语法分析方法及中间代码形式的描述3.1语法分析方法描述3.1.1简单优先法的定义一个文法G，若它不含e产生式，也不含任何右部相同的不同产生式，并且它的任何符号对(X,Y)，或者没有关系，或者存在下述三种关系：=、之一，则称该文法是一个简单优先文法。 A)X=Y当且仅当G中含有形如PXY的产生式 B)XY当且仅当Y为G的终结符，G中含有形如PQR的产生式，其中Q，R为非终结符，且Q X，YFirst(R)D)对任何X，若文法开始符号SX，则#。3.1.2简单优先法的基本思想根据优先关系的定义，将简单优先文法中各文法符号之间的这种关系用一个矩阵表示，称作简单优先矩阵。PDA读入一个单词后，比较栈顶符号和该单词的优先级，若栈顶符号优先级低于该单词，继续读入；若栈顶符号优先级高于或等于读入符号，则找句柄进行归约，找不到句柄就继续读入。直到最后栈内只剩下开始符号，输入串读到“”为止。此时识别正确。可分点描述如下:1、对句型中相邻的文法符号规定优先关系，以寻找句型中的句柄; 2、规定句柄内各相邻符号之间具有相同的优先级; 3、规定句柄两端符号优先级要比位于句柄之外而又和句柄相邻的符号的优先级高，以先归约句柄; 4、对于文法中所有符号，只要它们可能在某个句型中相邻，就要为它们规定相应的优先关系，若某两个符号永远不可能相邻，则它们之间就无关系.3.1.3简单优先矩阵用于表示文法符号之间的简单优先关系的矩阵。3.1.4简单优先法的优缺点优点：技术简单缺点：适用范围小，分析表尺寸太大。3.2中间代码形式描述四元式是一种比较普遍采用的中间代码形式。四元式的四个组成成分是：算符op，第一和第二运算对象ARG1和ARG2及运算结果RESULT。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。例如:输入字符串 do c=a+1 while ab 则输出四元式 (1) (+,a,1,c) (2) (,a,b,t0) (3) (=,t0,true,1)(4) (-,-,-,-)4简要的分析与概要设计整个工程分为5个文件：Main.c - 程序的入口点，输入待分析的字符串后先进行词法分析，然后调用两个函数进行语法分析及产生中间代码。Global.h - 定义了一些全局变量及宏Parse.h - 语法分析器的主要算法Prece.h - 定义和实现了一些关于优先级的操作Stack.h - 定义和实现了一个栈及其操作5详细的算法描述5.1 Main的主要算法void InputString()/输入字符串 int len = 0; printf(表达式文法为: ); printf(GRAMMAR); printf(n Please input any string to parse:n); scanf(%s, Buff);/输入字符串 len = strlen(Buff);/取字符串长度 Bufflen = #;Bufflen+1 = 0; void main()/主程序 printf( DO-WHILE循环语句的翻译n ); printf(循环语句的格式为：DO WHILE n ); printf(翻译的语句:do c=a+1 while abn );cifa();/调用词法分析程序,对输入字符串进行词法分析InputString();/再次输入待分析字符串以便进行语法分析 Parse();/调用语法分析,对输入字符串进行语法分析 getch();void cifa()/词法分析 char str; printf( * 词法分析器 *n); if (fp=fopen(lj.txt,r)=NULL)/如果文件无法打开 printf(源程序无法打开！n); else str =fgetc(fp); while (str!=EOF) if (isalpha(str)!=0)/判断是否为字符 str=letterprocess(str);/调用字符处理 else if (isdigit(str)!=0)判断是否为数字 str=numberprocess(str);/调用数字处理 else/其它 str=otherprocess(str); /调用其它处理 ; printf(词法分析结束！n); 5.2 Global的主要算法typedef enum false=0, true bool;#define GRAMMAR G(s): S-do B while E,B-c:=a+1,E=ab/定义文法#define BUFFSIZE 100#define STACKSIZE 1005.3 Parse的主要算法void error()/规约不成功 printf(The input string doesnt match the grammar!);void succeed()/规约成功 printf(Succeed! The input match the grammar.);char Reduce(const char* c) /将终极符或非终极符规约为非终极符 if (*c = d) return S; else if (*c = c ) return B; else if (*c = a) return E; bool Parse()/简单优先语法分析 char c; /保存栈顶元素char t; /保存最有可能弹出的终极符int ip = 0; /指向输入缓冲区的指针 InitStack(); /初始化栈 while (true) TopValue(&c); if (c=S & Buffip=#)/如果栈顶为S或#,规约成功 succeed(); return true; else switch (GetPrecedence(&c, &Buffip) /如果优先符是小于或等于则压栈,否则进栈 case LT: case EQ: Push(&Buffip+);/压栈 PrintStack(); break; case GT: Pop(&c);/出栈 do t = c; Pop(&c); while (GetPrecedence(&c, &t) != LT); Push(&c); t = Reduce(&t); Push(&t); PrintStack(); break; default: error(); return false; 5.4 Prece的主要算法/定义优先关系Prece PreTable1818 = /* S d o B w h i l e E a = + 1 b c # */* S */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* d */ NO, NO, EQ, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* o */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, LT, GT ,/* B */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* w */ NO, NO, NO, NO, NO, EQ, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* h */ NO, NO, NO, NO, NO, NO, EQ, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* i */ NO, NO, NO, NO, NO, NO, NO, EQ, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* l */ NO, NO, NO, NO, NO, NO, NO, NO, EQ, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* e */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, LT, NO, NO, NO, NO, NO, NO, GT ,/* E */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* a */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, EQ, NO, NO, EQ, NO, GT ,/* = */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, EQ, NO, NO, NO, NO, NO, NO, GT ,/* + */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, EQ, NO, NO, NO, GT ,/* 1 */ NO, NO, NO, NO, NO, GT, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, EQ, NO, GT ,/* b */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* c */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, EQ, NO, NO, NO, NO, NO, GT ,/* # */ LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, EQ ,;int CharToIndex(const char* c)/定义矩阵switch (*c)case S: return 0;case d: return 1;case o: return 2;case B: return 3;case w: return 4;case h: return 5;case i: return 6;case l: return 7;case e: return 8;case E: return 9;case a: return 10;case =: return 11;case +: return 12; case 1: return 13; case : return 14;case b: return 15;case c: return 16;case #: return 17;default: return -1;Prece GetPrecedence(const char* c1, const char* c2) /取优先关系 int i, j;i = CharToIndex(c1);/栈顶元素j = CharToIndex(c2);/输入符号流第一个元素if (i!=-1 & j!=-1) return PreTableij; else return ND;/否则没有优先关系 5.5 Stack的主要算法void InitStack()/初始化符号栈 char c = #;StackTop = 0;Push(&c); bool Push(const char* c)/压栈 if (StackTop = 0) *c = TheStack-StackTop; return true; else return false; bool TopValue(char* c)/取栈顶元素值 if (StackTop 0)/* not null */ *c = TheStackStackTop-1;return true; else return false; void PrintStack()/打印栈的元素 int i;for (i=0; iStackTop; i+) printf(%c, TheStacki); printf(n);6软件的测试方法和测试结果6.1测试方法在visual c+ 6.0 下调试并通过.6.2测试结果7设计的特点,不足,收获与体会这次编译原理课程设计的题目是用简单优先分析法进行DO-WHILE循环语句的语法分析,并输出四元式.设计