DO-WHILE语句的翻译程序设计（简单优先法，输出四元式）

武汉理工大学《编译原理》课程设计报告书

学 号：

课 程 设 计

题 目 学 院 专 业 班 级 姓 名 指导教师

年

月

日

1

武汉理工大学《编译原理》课程设计报告书

课程设计任务书

学生姓名： 蔡 亮 专业班级： 软件0505班 指导教师： 林 泓 工作单位：计算机科学与技术学院 初始条件：

理论：学完编译课程，掌握一种计算机高级语言的使用。 实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行

设计。

要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体

要求）

（1） 写出符合给定的语法分析方法的文法及属性文法。 （2） 完成题目要求的中间代码四元式的描述。

（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。 （4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。 （5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：

1 系统描述（问题域描述）； 2 文法及属性文法的描述；

3 语法分析方法描述及语法分析表设计；

4 给出中间代码形式的描述及中间代码序列的结构设计； 5 简要的分析与概要设计；

6 详细的算法描述（流程图或伪代码）； 7 给出软件的测试方法和测试结果；

8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）； 9 参考文献（按公开发表的规范书写）。

时间安排：

设计安排一周：周1、周2：完成系统分析及设计。

周3、周4：完成程序调试及测试。 周5：撰写课程设计报告。

设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。 设计报告书收取时间：设计周的次周星期一上午10点。

指导教师签名： 2008年 5月 23日 系主任（或责任教师）签名： 2008年 5月 23日

2

武汉理工大学《编译原理》课程设计报告书

DO-WHILE语句的翻译程序设计

(简单优先法,输出四元式)

1问题描述

输入一个DO-WHILE的语句,进行词法分析,词法分析器利用超前搜索,状态转换等方法,将源程序转化成为一个一个的单词符号二元式,如果词法分析无误,则进入语法分析部分,使用简单优先法进行文法分析,为每个终极符与非终极符之间定义优先关系,利用优先关系进行移进-规约,如果能规约到文法的开始符,则文法分析成功,输出四元式.

2文法及属性文法的描述

2.1文法描述

G(s): S->do B while E,

B->c:=a+1, E->a>b

2.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(‘goto’S.begin) ; }

B->c:=a+1 { B.code:= ’c:=a+1’ }

E->a>b { E.code=gen(‘if’’a>b’’goto’ 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简单优先法的定义

一个文法G，若它不含?产生式，也不含任何右部相同的不同产生式，并且它的任何符号对(X,Y)，或者没有关系，或者存在下述三种关系：=、<、>之一，则称该文法是一个简单

优先文法。

A)X=Y当且仅当G中含有形如P?…XY…的产生式

3

武汉理工大学《编译原理》课程设计报告书

B)X

C)X>Y当且仅当Y为G的终结符，G中含有形如P?…QR…的产生式，其中Q，R为非终结符，且Q ?…X，Y?First(R)

D)对任何X，若文法开始符号S?X…，则##。

3.2简单优先法的基本思想

根据优先关系的定义，将简单优先文法中各文法符号之间的这种关系用一个矩阵表示，称作简单优先矩阵。PDA读入一个单词后，比较栈顶符号和该单词的优先级，若栈顶符号优先级低于该单词，继续读入；若栈顶符号优先级高于或等于读入符号，则找句柄进行归约，找不到句柄就继续读入。直到最后栈内只剩下开始符号，输入串读到“＃”为止。此时识别正确。可分点描述如下:

1、对句型中相邻的文法符号规定优先关系，以寻找句型中的句柄; 2、规定句柄内各相邻符号之间具有相同的优先级; 3、规定句柄两端符号优先级要比位于句柄之外而又和句柄相邻的符号的优先级高，以先归约句柄;

4、对于文法中所有符号，只要它们可能在某个句型中相邻，就要为它们规定相应的优先关系，若某两个符号永远不可能相邻，则它们之间就无关系.

3.3简单优先矩阵

用于表示文法符号之间的简单优先关系的矩阵。

3.4简单优先法的优缺点

优点：技术简单,当做简单优先矩阵是要求较短。 缺点：适用范围小，分析表尺寸太大。

4 中间代码形式描述

四元式是一种比较普遍采用的中间代码形式。四元式的四个组成成分是：算符op，第一和第二运算对象ARG1和ARG2及运算结果RESULT。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。 例如:输入字符串 do c=a+1 while a>b 则输出四元式 (1) (+,a,1,c) (2) (>,a,b,t0) (3) (=,t0,true,1) (4) (-,-,-,-)

5简要的分析与概要设计

整个工程分为5个文件：

Main.c ---- 程序的入口点，输入待分析的字符串后先进行词法分析，然后调用两个函

数进行语法分析及产生中间代码。

Global.h ----定义了一些全局变量及宏 Parse.h ----- 语法分析器的主要算法

Prece.h ----- 定义和实现了一些关于优先级的操作

4

武汉理工大学《编译原理》课程设计报告书

Stack.h ----- 定义和实现了一个栈及其操作 而各模块的调度关系如下： Main.c Parse.h Global.h Stack.h

Prece.h 6详细的算法描述（各部分的主要算法）

6.1 Main的主要算法

void InputString()//输入字符串 {

int len = 0; printf(\表达式文法为: \ printf(GRAMMAR);

printf(\ scanf(\输入字符串 len = strlen(Buff);//取字符串长度 Buff[len] = '#';

Buff[len+1] = 0; }

void main()//主程序 {

printf(\循环语句的翻译\\n \

printf(\循环语句的格式为：DO <赋值语句> WHILE <表达式>\\n \ printf(\翻译的语句:do c=a+1 while a>b\\n \ cifa();//调用词法分析程序,对输入字符串进行词法分析 InputString();//再次输入待分析字符串以便进行语法分析 Parse();//调用语法分析,对输入字符串进行语法分析 getch(); }

void cifa()//词法分析 {

char str;

printf(\词法分析器 **********\\n\

if ((fp=fopen(\如果文件无法打开 printf(\源程序无法打开！\\n\

5

武汉理工大学《编译原理》课程设计报告书

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\

} }

6.2 Global的主要算法

—— ——关于一些全局变量及宏的定义

typedef enum{ false=0, true } bool;

#define GRAMMAR \定义文法 #define BUFFSIZE 100 #define STACKSIZE 100

6.3 Parse的主要算法

void error()//规约不成功

{ printf(\ void succeed()//规约成功

{ printf(\

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)

6

武汉理工大学《编译原理》课程设计报告书

{ TopValue(&c);

if (c=='S' && Buff[ip]=='#')//如果栈顶为S或#,规约成功 { succeed(); return true; } else

{ switch (GetPrecedence(&c, &Buff[ip]))

{//如果优先符是小于或等于则压栈,否则进栈 case LT: case EQ:

{ Push(&Buff[ip++]);//压栈 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; } } } } }

6.3 Prece的主要算法

//定义优先关系

Prece PreTable[18][18] =

{ /** 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 },

7

武汉理工大学《编译原理》课程设计报告书

/* 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;

8

武汉理工大学《编译原理》课程设计报告书

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 PreTable[i][j]; } else { return ND; //否则没有优先关系 } }

6.3 Stack的主要算法

void InitStack()//初始化符号栈 { char c = '#'; StackTop = 0; Push(&c); }

bool Push(const char* c)//压栈 {

if (StackTop < STACKSIZE) { TheStack[StackTop++] = *c; return true; } else

{ return false; } }

bool Pop(char* c)//出栈 {

if (StackTop >= 0)

{ *c = TheStack[--StackTop]; return true; } else

{ return false; } }

bool TopValue(char* c)//取栈顶元素值 {

if (StackTop > 0) /* not null */

9

武汉理工大学《编译原理》课程设计报告书

{ *c = TheStack[StackTop-1]; return true; } else { return false; } }

void PrintStack()//打印栈的元素 { int i; for (i=0; i

7软件的测试

7.1调试

在visual c++ 6.0 下调试出现一下问题： 编译原理\\ljsimple\\prece.h(49) : warning C4013: 'CharToIndex' undefined; assuming extern returning int

编译原理\\ljsimple\\main.c(11) : warning C4005: 'NULL' : macro redefinition 编译原理\\ljsimple\\parse.h(37) : warning C4715: 'Reduce' : not all control paths return a value

具体的这些问题全都出现在文件调用过程中，修改个别输出方面的问题后成功得以解决。

7.2测试结果

调试成功后运行如下：

10

武汉理工大学《编译原理》课程设计报告书

8 研制报告

这次编译原理课程设计的题目是用简单优先分析法进行DO-WHILE循环语句的语法分析,并输出四元式.设计的特点是利用定义每个终极符和非终极符之间优先关系,来进行符号的移进与规约,如果栈顶符号优先级低于该单词，继续读入；若栈顶符号优先级高于或等于读入符号，则找句柄进行归约，找不到句柄就继续读入。这样使得程序简化,只需定义一个栈用来存放移进的字符,然后用栈顶指针指向它后与待移进字符比较优先级即可,设计简单.此设计的严重不足是只能进行一个固定句子的词法与语法分析,因为在定义优先关系时已固定了DO,和WHILE的每个字符之间的优先关系,且赋值表达式和条件式也已固定,所以只能进行本程序已约定好的语句.最大的收获是在提出一个难题以后，如果能比较顺手的解决的话，那是一件比较开心的事。只是有些时候越想问题就会越多，也越难解决，那就得慢慢调试，慢慢推导了。相信只要想得出，就能调得出，当然耐心是很重要的，花在上面的时间也是要多一点的。

完成此次课程设计以后,觉得自己在编译原理的学习中存在很多的不足和需要提高的地方.通过对简单优先法翻译程序的编程也使自己在编写编译程序上有了感官的认识,且能力也得到了一定的提高!虽然此程序还存在很多的缺点与不足,但在将来的学习中我会不断的完善此部分知识.独立的完成程序以后也有不少收获,为自己在以后的学习中做了很好的铺垫!

9 参考文献

［1］张素琴、吕映芝、蒋维杜、戴桂兰等．编译原理（第二版）．清华大学出版社．2005

11

武汉理工大学《编译原理》课程设计报告书

年2月 参考书：

［1］何炎祥．编译原理（第二版）．武汉：华中科技大学出版社．2005年8月 ［2］陈火旺等．程序设计语言编译原理（第3版）．国防工业出版社．2003年2月 ［3］胡伦骏．编译原理（第2版）．电子工业出版社．2005年2月 ［4］陈意云．编译原理与技术（第二版）．中国科学技术大学出版社．2002年1月 ［5］胡元义等．编译原理实践教程．西安电子科技大学出版社．2002年1月 ［6］王雷等．编译原理课程设计．机械工业出版社．2005年3月

12

本文来源：https://www.bwwdw.com/article/zexv.html