DO-WHILE循环语句的翻译程序设计(LL（1)法、输出三地址表示）

课程设计任务书

学生姓名： 专业班级： 指导教师： 工作单位：

题目: DO-WHILE循环语句的翻译程序设计（LL（1）法、输出三地址表示） 初始条件：

理论：学完编译课程，掌握一种计算机高级语言的使用。

实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设

计。

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

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

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

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

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

4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计； 5 编译系统的概要设计；

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

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

时间安排：

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

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

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

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

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

DO-WHILE循环语句的翻译程序设计 （LL（1）方法、输出三地址表示）

1. 系统描述

1.1目的

通过设计、编制、生成、调试一个do-while循环语句的语法及语义分析程序，以加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。

1.2 设计内容

对循环语句：do {赋值语句} while <表达式>

1) 设计符合自身语法分析方法要求的文法和属性文法（LL(1)语法）。 2) 设计LR分析法相关的语法分析表（LL(1)分析表）。 3) 设计中间代码格式（三地址中间代码）。

4) 对源文件进行词法和语法分析的同时进行语义处理（语法制导分析）。 5) 对源文件中的错误进行输出。

1.3 系统体系结构描述

本系统为子模块的体系结构风格，系统由两大模块组成：

1) 词法分析模块

2) 语法分析模块（调用语义分析模块）

1.3.1 系统结构图

源代码 词法分析 语法分析 语义分析 中间代码

说明：输入do-while语句后，词法分析模块对文件进行处理并输出单词序列到队列queue[i]，随后的语法分析模块将此队列内容作为输入，通过语法制导分析方法调用语

2

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

义分析模块最终生成中间代码。

1.3.2 词法分析模块

源文件 读取一个字符 判断字符类型 单词归类 （关键字、标识符…） 存入队列queue

说明：对输入的源文件进行处理，逐个读入字符，将字符流进行合并并进行判断归类，将单词和其类型输入队列并保存。

1.3.3 语法分析模块

队列queue 错误处理 （打印错误） 语法分析 （LL(1)分析法） 语义分析 （语法制导） 中间代码 （三地址码）

说明：接受由词法分析得到的队列queue，进行语法分析和语法制导翻译，最后得到三地址中间代码。

3

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

2. 文法及属性文法描述

2.1 文法：

文法是用于描述语言的语法结构的形式规则（即语法规则）。这些规则必须是准确的、易于理解的以及有相当强的描述能力。由这种规则所产生的程序语言应有利于句子分析和翻译，而且，最好能通过这些规则自动产生有效的语法分析程序。 DO-WHILE循环语句的文法如下所示： K->DLWS L->SP P->;SP P->ε D->do W->while

2.2 属性文法：

属性文法是在上下文无关文法的基础上，为每个文法符号（终结符或者非终结符）配

备若干相关的“值”（与文法符号相关的属性）。

在一个属性文法中，对应于每个产生式A→a都有一套与之相关联的语义规则，每规则的形式为：b:=f(c1,c2,?，ck)其中f是一个函数，而且或者①b是A的一个综合属性并且c1,c2,?，ck是产生式右边文法符号的属性或者②非终结符既可有综合属性也可有继属性，文法开始符号的所有继承属性作为属性计算前的初始值。 属性文法为：

1-{ if(S.value == true) emit(‘if(‘, S.value, ‘)goto’, codebegin) else emit(‘-‘, ‘-‘, ‘goto’, nextstate)} 2-{p = lookup(id.name); if(p != NULL) L.place = p; else error; E.place = L.place; emit(‘=‘, id, ‘-’,

L.place)}

3-{L.place = newtemp; emit(‘+’, F1.place, F2.place, F.place)}

4-{S.place = newtemp; S.value = (F1.value > F2.value); emit(‘>’, F1.place, F2.place, S.place)} 5-{F.place = newtemp; p = lookup(id.name); if(p != NULL) F.place = p; else error}

6-{F.place = newtemp; p = lookup(digit.name); if(p != NULL) F.value = digit.value; else error}

4

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

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

3.1语法分析

为实现LL(1)算法,可以使用栈结构，算法的基本思想是: 首先定义栈结构，栈中的元素是一个二维数组： void semantic() {

if(VT[opr]=='=') {

arr[d][0]=arr_i[opd]; arr[d][1]='='; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' '; id++; }

else if(opr==-2) {

arr[d][0]=id-1; arr[d][1]='=';

arr[d][2]=arr_i[opd]; arr[d][3]=' '; arr[d][4]=' '; }

else {

if(VT[opr]!='<'&&VT[opr]!='>') arr[d][0]=id-1; else

arr[d][0]=id+1; arr[d][1]='=';

arr[d][2]=arr_i[opd]; arr[d][3]='+';

arr[d][4]=id; id++; }

d++; }

3.2 预测分析部分：

int M[10][14]={ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0,-1,-1,-1}, {1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 3, 2,-1}, {4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}, {5,-1,-1,-1,-1,-1,-1,-1,5,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,6,7,-1,-1,-1,-1,-1, 8, 8, 8}, {9,-1,-1,-1,-1,-1,-1,-1,9,-1,-1,-1,-1,-1},

5

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

}; {-1,-1,-1,-1,12,12,10,11,-1,-1,-1,12,12,12}, {14,-1,-1,-1,-1,-1,-1,-1,13,-1,-1,-1,-1,-1}, {-1,15,16,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},

3.3 语法分析过程：

void syntax() {

int n;

count++; print();

X=stack[sp]; //将sp压入栈STACK中

a=queue[front]; //从queue队列中读取词法分析后的字符 if(X=='#'&&a=='#')f=4; if(X<'A'||X>'Z') {

if(X==a) {

sp--; front++; if(a!='i') {

if(a!='d'&&a!='w'&&a!=';'&&a!='#') {

opr=index(a,VT);

semantic(); //语法分析调用 }

else if(a==';'||a=='w'||a=='#') {

opr=-2;

semantic(); //语法分析调用 }

cout<<'\\t'<<'\\''<

opd=c;

//cout<

cout<<'\\t'<<'\\''<

else f=1; //转入出错处理 }

else {

int tx=index(X,VN); int ta=index(a,VT); n=M[tx][ta];

td[t++]=M[tx][ta];

6

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

if(ta==-1)

{

f=2; // } cout<

else if(n==-1)f=3;

else //转入出错处理 {

sp--;

cout<<'\\t'<

for(int i=len(p[n])-1;i>=0;i--) {

stack[++sp]=p[n][i];

cout<

}

cout<

else cout<<\空串\ }

if(f==0)syntax(); else {

td[t]='-1'; }

}

err(f); 4. 中间代码形式及其序列的结构设计

中间代码是3地址码形式来表示，即4元式的变形。

三地址码由5个域构成：中间代码地址标号，操作符，左操作数，右操作数，目的操作数

操作符：=，+，> ，< （文法仅定义这些操作）； 左操作数，右操作数：opt，opr； 目的操作数：用来存放操作值的变量。 例如：i=（0） （0）=i+1 （1）=i 表示 i=i+1 。

7

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

5. 简要分析与概要设计

5.1 系统分析

5.1.1 词法分析

输入源程序文本，对输入串进行预处理，然后从左至右逐个字符地对源程序进行扫（超前搜索法），产生一个一个的单词符号，在状态转换图的基础上，把作为字符串源程序改造成为单词符号串。 概要流程图见图1.3.2。

5.1.2 语法分析

在完成词法分析的基础上对DO-WHILE循环语句进行语法分析，对状态栈、符号栈分别进行移进、规约（采用LL(1)分析方法）、接受和出错处理四步操作，从而分析判定程序的语法结构是否符合语法规则。 概要流程图见1.3.3节。

5.1.3 语义分析以及三地址码表示

当在栈中找到可归前缀后，进行规约时，根据相应产生式对应的语义子程序进行语法制导翻译（在语法的分析过程中，随着分析的步步进展，根据每一个产生式所对应的语义子程序进行翻译的方法）.三地址指令很类似于四元式,这种中间表示通常称为三地址代码,三个地址即是两个为操作数,一个是操作符。

5.1.4 LL（1）语法分析中的出错处理

1) 字符不匹配,转去出错处理。

2) 字符没有出现在产生式终结符集VT[]中,转去出错处理 3) 没有找到合适的候选产生式来做进一步推导,转去出错处理

5.2 概要设计（系统总体描述）

词法分析 语法分析 语义分析 源代码 中间代码

8

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

6. 详细的算法描述

详细的伪代码（源程序）

#include #define MAX 35

char X,a;

char VN[11]={'K','L','P','S','E','G','T','R','F','Q','\\0'};

char VT[15]={'i','=','<','>','+','-','*','/','(',')','d','w',';','#','\\0'}; char

p[18][6]={\\char stack[MAX]; char queue[MAX]; int sp,front;

int M[10][14]={ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0,-1,-1,-1}, {1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 3, 2,-1}, {4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}, {5,-1,-1,-1,-1,-1,-1,-1,5,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,6,7,-1,-1,-1,-1,-1, 8, 8, 8}, {9,-1,-1,-1,-1,-1,-1,-1,9,-1,-1,-1,-1,-1},

{-1,-1,-1,-1,12,12,10,11,-1,-1,-1,12,12,12}, {14,-1,-1,-1,-1,-1,-1,-1,13,-1,-1,-1,-1,-1}, {-1,15,16,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}, }; int f=0;

int count=0; int c=0;

char arr_i[MAX];

char var[MAX]; //表格管理

int td[MAX]; //输出产生式序列 int t=0;

int opd=-1; int opr=-1; int id=0;

//int ptr[MAX]; int d=0;

char arr[MAX][5]; //存放待输出的三地址 //char keyword[2][7]={\

int len(char str[]) {

int i=0;

while(str[i]!='\\0')i++; return i; }

9

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

int index(char ch,char str[]) {

int i=0;

while(str[i]!='\\0') {

if(ch!=str[i])i++; else break; }

if(str[i]=='\\0')return -1; return i; }

void err(int n) {

if(n==1)

cout<<\字符不匹配\ else if(n==2)

cout<<\字符没有出现在产生式终结符集VT中\ else if(n==3)

cout<<\没有找到合适的候选产生式来做进一步推导\ else

cout<<\该句子是文法语言的句子！\}

void print() {

cout<<\

if(count<10)cout<<'0'; cout<

for(i=0;i<=sp;i++)cout<

for(i=0;i

for(;queue[i]!='#';i++)cout<

for(;i<=20;i++)cout<<\}

void semantic() {

if(VT[opr]=='=') {

arr[d][0]=arr_i[opd]; arr[d][1]='='; arr[d][2]=id; arr[d][3]=' '; arr[d][4]=' ';

10

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

id++; }

else if(opr==-2) {

arr[d][0]=id-1; arr[d][1]='=';

arr[d][2]=arr_i[opd]; arr[d][3]=' '; arr[d][4]=' '; }

else {

if(VT[opr]!='<'&&VT[opr]!='>') arr[d][0]=id-1; else

arr[d][0]=id+1; arr[d][1]='=';

arr[d][2]=arr_i[opd]; arr[d][3]='+';

arr[d][4]=id; id++; }

d++; }

void syntax() {

int n;

count++; print();

X=stack[sp]; a=queue[front];

if(X=='#'&&a=='#')f=4; if(X<'A'||X>'Z') {

if(X==a) {

sp--;

front++; if(a!='i') {

if(a!='d'&&a!='w'&&a!=';'&&a!='#') {

opr=index(a,VT); semantic(); }

else if(a==';'||a=='w'||a=='#') {

11

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

opr=-2; semantic(); }

cout<<'\\t'<<'\\''<

opd=c;

//cout<

cout<<'\\t'<<'\\''<

else f=1; //字符不匹配,转去出错处理 }

else {

int tx=index(X,VN); int ta=index(a,VT); n=M[tx][ta];

td[t++]=M[tx][ta]; if(ta==-1) {

f=2;cout<

} //字符没有出现在产生式终结符集VT中,转去出错处理 else if(n==-1)f=3; //没有找到合适的候选产生式来做进一步推导,转去出错处理

else

{ //用产生式M[tx][ta]来做进一步推导 sp--;

cout<<'\\t'<

for(int i=len(p[n])-1;i>=0;i--) {

stack[++sp]=p[n][i];

cout<

cout<

else cout<<\空串\ } }

if(f==0)syntax(); else {

td[t]='-1'; err(f); } }

12

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

void lexical()

{ //do{m=m+i;i=i+1;}while(i<4);# int i,j,d; char ch; j=d=0;

for(i=0;var[i]!='#';i++) {

ch=var[i];

if(ch=='d'&&var[i+1]=='o') {

cout<<\ queue[j++]='d';i+=1; }

else if(ch=='w') {

ch=var[i+1]; if(ch=='h') {

ch=var[i+2]; if(ch=='i') {

ch=var[i+3]; if(ch=='l') {

ch=var[i+4]; if(ch=='e') {

ch=var[i+5]; } } } }

cout<<\ queue[j++]='w';i+=4; }

else if(index(ch,VT)<=0) {

if(ch!='{'&&ch!='}'&&ch!='('&&ch!=')') {

cout<

else cout<

else if(index(ch,VT)>0) {

cout<

13

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

} }

queue[j]='#';

for(i=0;queue[i]!='#';i++)cout<

int main() //主程序 {

int i=0; char S='K'; sp=front=0; stack[0]='#'; sp++;

stack[1]='K';

cout<<\文法如下:\

cout<<\ε\\n(4)S->iQE\\n(5)E->TG\\n(6)G->+TG\\n\

<<\ε\\n(9)T->FR\\n(10)R->*FR\\n(11)R->/FR\\n(12)R->ε\\n(13)F->(E)\\n\

<<\ cout<<\请输入do-while语句:\ do {

cin>>var[i]; i++;

if(var[i]==' ')i--; }while(var[i-1]!='#'); var[i]='\\0';

cout<<\词法分析:\ lexical();

cout<<\语法分析:\ syntax();

cout<<\所用产生式序列:\

for(i=0;td[i]!='-1';i++)cout<

cout<<\输出三地址:\ for(i=0;i

for(int j=0;j<5;j++) {

if(arr[i][j]>=0&&arr[i][j]<=9)

cout<<\ else

cout<

cout<

return 0; }

14

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

7. 测试用例及测试结果描述

7.1

测试用例

(1)正确的语法 输入do{i=i+1}while{i<4}# (2)错误的语法 输入do{i=i+1}while#

7.2 测试结果（如下图）

（1）正确的语法 1.输入语句 #结束

2.词法分析

15

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

3.语法分析及所用产生式序列

4.输出三地址

（2）错误的语法

1.输入语句 #结束

16

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

2.词法分析

3.语法分析及所用产生式序列

17

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

4.输出三地址

8. 研制报告

8.1 研制过程

从周日拿到题目对题目进行分析，再到周一至周三的编写，到周四的调试，我觉得我的程序编写能力又有了一定的提升。回顾起这次DO-WHILE循环语句的课程设计，我感慨颇多，的确，从分析到编写，从理论到实践，在这一个星期的日子里，可以说是花了很多功夫的，但是我学到了很多很多的的东西，不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。在本次课程设计中，我先是重温了课本上对于相关知识的讲解，然后根据自己的题目进行了文法的设计，将二者结合起来，作出一个自己的文法，然后我开始设计一些基本的构件并描述出它们的具体接口功能，接口设计好之后，下一步便是进行接口的

18

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

实现了，最关键的一步是总控程序的设计，对其他构件类的调用。在以上功能完成之后，我就开始遍程了。最后，进行调试。

8.2 设计评价

我对这次课程设计的评价就是收获颇多，可以说我这个程序还没有达到预想的结果，但是对于我这样一个编程很一般的学生来说，我觉得是一个成功。

首先我的程序实现了大部分的功能，包括语法分析和三地址输出，但是在词法分析这个问题上还有很大的问题。在设计的时候，我也找同学帮忙指正，但是仍然存在着一些细小的问题，不过我的设计在总体上还是不错的。

8.3 体会和收获

在整个设计过程中,最大的收获就是切身体会了编程语言在具体分析方法下进行翻译的实现机制和步骤.其次才是对LL（1）算法的理解和运用以及对堆栈的操作原理的掌握. 因为之前学理论的时候,感觉和实际的编程语言联系不是很大,也不知道所学理论如何在语句的翻译过程中发挥作用.而在具体DO----WHILE循环语句翻译的设计实践过程中,才真正体会了该步骤是如何一步步实现的,这些都是以往单纯理论知识学习所感触不到的.

在词法分析和语法分析的程序过程中,遇到了一些编程方面的困难,有些语句功能实现不了,而且在调试的时候也出现了问题,例如词法分析的错误调试的还不够好,但总体来说不是很严重.在请教同学检查修改之后,都得到了解决.所以自身感觉在编程设计和具体实践过程中还需要进一步的学习,尤其是要提高把理论运用到实践当中的编程能力.

9. 参考文献

教材：

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

2月

参考书：

［1］何炎祥．编译原理（第二版）．武汉：华中科技大学出版社．2005年8月 ［2］陈火旺等．程序设计语言编译原理（第3版）．国防工业出版社．2003年2月

［3］Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman．Compilers:Principles,Techniques,and Tools．人民邮电出版

社．2002年2月

［4］胡伦骏．编译原理（第2版）．电子工业出版社．2005年2月 ［5］陈意云．编译原理与技术（第二版）．中国科学技术大学出版社．2002年1月

19

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