循环语句的语法分析及语义分析程序设计

目 录

1 课程任务书····································（2）

1问题描述·······································（3）

2文法及属性文法的描述···························（3）

2.1 while-do循环语句的文法·····················（3）

2.2while-do循环语句的结构翻译·················（3）

3语法分析及中间代码形式的描述···················（4）

3.1 语法分析方法·······························（4）

3.2 中间代码形式描述···························（4）

4简要的分析与概要设计···························（5）

4.1词法分析··································（5）

4.2递归下降翻译器的设计·······················（5）

4.3语法制导翻译·······························（5）

5 详细的算法描述································（6）

5.1 文法·······································（6）

5.2 查错·······································（6）

6 测试方法和测试结果···························（9）

6.1测试方法··································（9）

6.2测试结果··································（10）

7 设计的特点、不足、收获与体会·················（10）

7.1 设计的特点································（10）

7.2 不足、收获与体会··························（11）

8 参考文献·····································（11）

课程设计任务书

题 目: 循环语句的语法分析及伍岁此语义分析程序设计（递归下降法）

1．目的

通过设计、编制、调试一个语法及语义分析程序，加深对语法及语义分析原理的理解。

2.设计内容及要求

WHILE〈布尔表达式〉DO〈赋值语句〉

其中

（1）学号29至32的同学按顺序分别选择递归下降法、LL（1）、算符优先分析法（或简单优先法）、LR法完成以上任务，中间代码选用四元式。

（2）如1题写出符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。

（3）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。

3.课程设计报告书的内容应包括：

1.设计题目、班级、学号、姓名、完成日期；

2.给出语法分析方法及中间代码形式腔迅的描述、文法和属性文法的设计；或者词法分析方法

3.及符号表和TOKEN代码的设计。

4.简要的分析与概要设计；

5.详细的算法描述；

6.源程序清单；

7.给出软件的测试方法和测试结果；

8.设计的评价、收获与体会。

4.时间安排：

第17周，周1-周4上午，周五全天

指导教师签名： 年月日

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

1问题描述

设计一个WHILE〈布尔表达式〉DO〈赋值语句〉雀岩循环语句的词法﹑语法及语义分析程序，语法分析选择递归下降法，采用用语法制导翻译输出中间代码四元式。

2文法及属性文法的描述。

2.1 while-do循环语句的文法

产生式为S->while E do A，为便于语法制导翻译将其改写如下：

文法G(s)如下：

S-->WEDG （意思是while E do G）

G-->c=R

R-->dTe|d

T-->+|-|*|/

E-->aFb

F-->>|==|<

2.2 whlie-do循环语句的结构翻译：

3.语法分析方法及中间代码形式的描述

3.1语法分析方法

递归下降法的实现思想是为文法的每个非终结符号设计一个相对应的递归子程序，识别程序由一组这样的子程序组成。

它的优点是简单直观，易于构造，很多编译系统所实现

缺点是对文法要求很高，由于递归调用多，影响分析器的效率

其文法可以表示为：

E→T│E+T

T→F│T*F

F→i│（E）

可以用语法图来表示语言的文法，如图：

E

T

F

3.2中间代码形式描述

中间代码采用四元式输出，一个四元式是一个带有四个域的记录结构，这四个域分别称为op﹑arg1﹑arg2及result。域op包含一个代表运算符的内部码。语句while a<b do a=a+b的四元式输出形式如下：

100 ( <, a , b , 102 )

101 ( j , _ , _ , 105 )

102 ( + , a , b , n )

103 ( = , n , _ , a )

104 ( j , _ , _ , 100)

105

4．简要的分析与概要设计

4.1词法分析

词法分析程序的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号的中间程序。词法分析检查的错误主要是挑出源程序中出现的非法符号。所谓非法符号是指不是程序设计语言中允许出现的符号，就像自然语句中的错字。

4.2递归下降翻译器的设计

1.：对每个非终结符A构造一个函数过程，对A的每个继承属性设置一个形式参数，函数的返回值为A的综合属性，A对应的函数过程中，为出现在A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。非终结符A对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。

2：每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号，非3：终结符和语义动作分别做以下工作。

（1）对于带有综合属性x的终结符X，把x的值存入为X，x设置的变量中。然后产生一个匹配X的调用，并继续读入一个输入符号。

（2）对于每个非终结符号B，产生一个右边带有函数调用的赋值语句c=B(b1,b2,…，bk)

（3）对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对应属性的每一次引用。

4.3语法制导翻译

在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译。属性文法的每个符号有属性，所以每个符号入栈时，必须连属性一起入栈，这样，栈符号就由文法符号及存放该符号属性的域所组成。由于属性类型不同，属性域存放的内容就要根据属性的类型来定。有的可能直接存放属性值，也有的存放的是指向属性值的指针。对于综合属性，其属性域不存放其属性值，而是存放一个指针，指向存贮该属性值的单元。对于继承属性，其属性域直接保存其属性值。继承属性的属性域刚入栈时为空，但是在该栈符号变成栈顶符号之前的某一时刻，它们必须接受相应的属性值，即在成为栈顶时，继承属性的属性域必须有值。

5详细的算法描述

5.1 文法

/*

文法G(s)

s-->WEDG

G-->c=R

R-->dTe|d

T ->+|-|*|/|%E-->aFb

F-->>|==|<

*/

5.2 查错

按照递归下降法求Wa<bDa=a+b，程序的执行顺序应该是S()W()EF()D()G()R()T()

S()

void S()

{

printf("%d\tS-->WEDG\n",total)total++

W()

E()

}

W()

void W()

{

if(ch!='W')

{

printf("有非法字符%c请按回车返回!!",ch)

getchar()

getchar()

exit(1)

}

}

E()

void E()

{

ch=a[++i1]

if(ch!='a')

{

printf("有非法字符%c %c请按回车返回!!",ch)

getchar()

getchar()

exit(1)

}

printf("%d\tE-->aFb\n",total)total++

F()

}

F()

void F()

{

int i

ch=a[++i1]

i=i1+1

if(a[i]!='b')

{

printf("有非法字符%c请按回车返回!!",a[i])

getchar()

getchar()

exit(1)

}

switch(ch)

{

case '>':

printf("%d\tF-->>\n",total)total++

break

case '==':

printf("%d\tF-->==\n",total)total++

break

default:

printf("%d\tF--><\n",total)total++

break

}

D()

G()

}

D()

void D()

{

++i1

ch=a[++i1]

if(ch!='D')

{

printf("有非法字符%c请按回车返回!!",ch)

getchar()

getchar()

exit(1)}

ch=a[++i1]

}

G()

void G()

{

int i=i1+1

if(ch!='c'&&a[i]!='=')

{

printf("有非法字符%c %c请按回车返回!!",ch,a[i])

getchar()

getchar()

exit(1)

}

printf("%d\tG-->c=R\n",total)total++

R()

}

R()

void R()

{

int i

i=i1+1

i1=i1+2

ch=a[i1]

if(a[i]!='='&&ch!='d')

{

printf("有非法字符%c %c请按回车返回!!",a[i],ch)

getchar()

getchar()

exit(1)

}

else

{

if((a[i1+1]=='+')||(a[i1+1]=='-')||(a[i1+1]=='*')||(a[i1+1]=='/'))

{

printf("%d\tR-->dTe\n",total)total++

T()

}

else

{

printf("%d\tR-->d\n",total)total++

W()

E()

}

}

}

T()

void T()

{

ch=a[++i1]

switch(ch)

{

case '+':

printf("%d\tT-->+\n",total)total++

break

case '-':

printf("%d\tT-->-\n",total)total++

break

case '*':

printf("%d\tT-->*\n",total)total++

break

default:

printf("%d\tT-->/\n",total)total++

break

}

ch='#'

}

6测试方法和测试结果

6.1测试方法

在C++环境下，设计几个有代表的用例，进行测试，例如：输入语句Wa<bDa=a+b#(其中d表示do ,w表示while)。若得出的不是预期的结果，那么程序就出现问题。如果有问题的话就进行单步调试找到程序中出现的逻辑问题。

6.2测试结果

测试结果如下：

7设计的特点、不足、收获与体会

7.1设计的特点

本次设计是采用递归下降的方法对输入的while--do 循环语句进行语法，语义分析，并输出四元式。因此程序中充分体现了递归下降的思想。

7.2设计的不足，收获与体会

本次的设计的不足主要是我没将程序一般化，实现不了用户自动输入代码进行词法分析的四元式输出，此程序只能实现对Wa<bDa=a+b#的分析与四元式输出，由于我所设计的栈中只能一个字符一个字符的存放，因此只能用D W分别表示do while；而且我对语法制导翻译这一块很不熟悉，因此我始终不能用程序实现语法制导翻译输出四元式，于是根据自己的理解，直接把四元式写了出来。

本次课程设计巩固了我所学习的关于递归下降法这一方面的知识，并且使我对WHILE—DO循环语句也有了更深刻的理解,提高了我的动手能力。

8 课程设计参考资料

1张幸儿 《编译原理》（第二版）清华大学出版社

2何炎祥 《编译原理》华中理工大学出版社

3陈火旺 《程序设计语言编译原理》（第3版）国防工业出版社

本科生课程设计成绩评定表

班级：软件0701　姓名：周璐萍　学号：0120710680129

序号 评分项目 满分 实得分

1 学习态度认真、遵守纪律 10

2 设计分析合理性 10

3 设计方案正确性、可行性、创造性 20

4 设计结果正确性 40

5 设计报告的规范性 10

6 设计验收 10

总得分/等级

评语：

注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、

及格（60-69分）、60分以下为不及格

源程序

#include <stdio.h>

#include<dos.h>

#include<stdlib.h>

#include<string.h>

char a[50],g[50][50]

char ch

int n1,i1=0,i2=0

int total=0

void S()

void D()

void G()

void W()

void E()

void R()

void T()

void F()

void main()

{

int j=0

printf("文法G(s)为:\n")

printf("s-->DGWE\n")

printf("G-->c=R\n")

printf("R-->dTe|d\n")

printf("T-->+|-|*|/\n")

printf("E-->aFb\n")

printf("F-->>|==|<\n")

printf("请输入while-do语句(D代表do,W代表while),并以#结束:\n")

do{

scanf("%c",&ch)

a[j]=ch

j++

}while(ch!='#')

n1=j

ch=a[0]

S()

printf("\n")

if (ch=='#')

{ printf("输出四元式为：\n")

printf("100 (<,a,b,102)\n")

printf("101 (j,_,_,105)\n")

printf("102 (+,a,b,n)\n")

printf("103 (=,n,_,a)\n")

printf("104 (j,_,_,100)\n")

printf("105\n")

}

else {

printf("error\n")

printf("press any key to continue..\n")

getchar()getchar()

return

}

printf("\n")

printf("press any key to continue..\n")

getchar()

getchar()

}

/*出错情况分析*/

void S()

{

printf("%d\tS-->WEDG\n",total)total++

W()

E()

}

void W()

{

if(ch!='W')

{

printf("有非法字符%c请按回车返回!!",ch)

getchar()

getchar()

exit(1)

}

}

void E()

{

ch=a[++i1]

if(ch!='a')

{

printf("有非法字符%c %c请按回车返回!!",ch)

getchar()

getchar()

exit(1)

}

printf("%d\tE-->aFb\n",total)total++

F()

}

void F()

{

int i

ch=a[++i1]

i=i1+1

if(a[i]!='b')

{

printf("有非法字符%c请按回车返回!!",a[i])

getchar()

getchar()

exit(1)

}

switch(ch)

{

case '>':

printf("%d\tF-->>\n",total)total++

break

case '==':

printf("%d\tF-->==\n",total)total++

break

default:

printf("%d\tF--><\n",total)total++

break

}

D()

G()

}

void D()

{ ++i1

ch=a[++i1]

if(ch!='D')

{ printf("有非法字符%c请按回车返回!!",ch)

getchar()

getchar()

exit(1)}

ch=a[++i1]

}

void G()

{ int i=i1+1

if(ch!='c'&&a[i]!='=')

{ printf("有非法字符%c %c请按回车返回!!",ch,a[i])

getchar()

getchar()

exit(1)}

printf("%d\tG-->c=R\n",total)total++

R()

}

void R()

{

int i

i=i1+1

i1=i1+2

ch=a[i1]

if(a[i]!='='&&ch!='d')

{

printf("有非法字符%c %c请按回车返回!!",a[i],ch)

getchar()

getchar()

exit(1)

}

else

{

if((a[i1+1]=='+')||(a[i1+1]=='-')||(a[i1+1]=='*')||(a[i1+1]=='/'))

{

printf("%d\tR-->dTe\n",total)total++

T()

}

else

{

printf("%d\tR-->d\n",total)total++

W()

E()

}

}

}

void T()

{

ch=a[++i1]

switch(ch)

{

case '+':

printf("%d\tT-->+\n",total)total++

break

case '-':

printf("%d\tT-->-\n",total)total++

break

case '*':

printf("%d\tT-->*\n",total)total++

break

default:

printf("%d\tT-->/\n",total)total++

break

}

ch='#'

}

指导教师签名：

2010 年　月　日

/颂毁竖//////////////////////////////////////////////////////////////////

////董超勋的for循环语句翻译 递归下降法 输出三地址码 /////////////

#define MAX 100

#include<iostream.h>

#include<stdio.h>

#include<string.h>

char str[MAX]

char ch

int turn

char strToken[MAX]

int kind

int n=0//存放strtoken[]元素的个数

struct Word//结构体 存放单词

{

int sort

char word[MAX]//存放strtoken[]的内容

}

//record[x]=new Word

Word *record[12]//放所有识别出来的单词，分别存放他们的编号以及字符串，x是其下标

////////////////////词法分析//////////////////野大/////

int buffer()//载入

{

int i=0

cout<<"输入程序，以“#”作为结束标志。"<<endl

for(int n=0n<=MAXn++)

{

for(i<=MAXi++)

{

scanf("%c",&str[i])

/////////////cin>>str[i]不可用，用C语言读入字符。

if(str[i]=='#')

break///////如果尾数为识别码#,则表示程序读完,跳出循环.

}

break

}

return(i)

}

bool IsLetter(char ch)///////////判断是否是字母

{

if(ch>=65&&ch<=90||ch>=97&&ch<=122)

return(true)

else

return(false)

}

bool IsDigit(char ch)//////////判断是否是数字

{

if(ch>=48&&ch<=57)

return(true)

else

return(false)

}

char GetChar(int i)///////读取字符

{

char ch

ch=str[i]

return(ch)

}

char GetBC(char ch)////判断是不是空格或者换行，如果是，直接读取下一个字符直道不再空白为止余尺

{

if(ch==32||ch==10)

{

turn++

ch=GetChar(turn)

ch=GetBC(ch)/////////递归实现

return(ch)

}

else

return(ch)

}

void Concat()/////////////连接，即为strtoken[]赋值

{

strToken[n]=ch

n++

}

int Reserve()/////以单词为单位查找保留字，是则返回编码，不是则返回0，用来区分标志符和保留字

{

if(strcmp(strToken," DIM\0")==0)///////调用strcmp函数实现,

return(1)

else if(strcmp(strToken,"for\0")==0)

return(2)

else if(strcmp(strToken,"step\0")==0)

return(3)

else if(strcmp(strToken,"until\0")==0)

return(4)

else if(strcmp(strToken,"do\0")==0)

return(5)

else

return(6)

}

void clear()

{

n=0

}

/////////////*语法递归分析*/////////////////

int A(int * c,int &q)

{

if(c[q++]==3)

{

if(c[q]==7)

{ q++

return 1

}

else {cout<<"step右部出错"<<endlreturn 0}

}else {cout<<"error 'step'"<<endlreturn 0}

}

int B(int * b,int &o)

{

if(b[o++]==4)

{

if(b[o]==7)

{ o++

return 1

}

else {cout<<"until右部出错"<<endlreturn 0}

}else {cout<<"error 'until'"<<endlreturn 0}

}

int S2(int * d,int &h)

{

if(d[h++]==6)

{

if(d[h++]==8)

{

if((d[h]==6||d[h]==7)) {h++return 1}

else {cout<<"赋值语句右部出错 "<<endlreturn 0}

}else {cout<<"赋值语句缺少赋值运算符 "<<endlreturn 0}

}else {cout<<"赋值语句左部出错 "<<endlreturn 0}

}

int S1(int * m,int &n)

{

if(S2(m,n))

{

if(A(m,n))

{

if(B(m,n)) return 1

else return 0

}else return 0

}else return 0

}

int S(int *a,int &z)

{

if (a[z++]==2)

{

if (S1(a,z))

{

if(a[z++]==5)

{

if(S2(a,z))

{

cout<<"succeed!"<<endlreturn 1

}else return 0

}else {cout<<"error 'do'"<<endlreturn 0}

}else return 0

}else {cout<<"error 'for'"<<endlreturn 0}

}

void main()

{

cout<<"*************产生式***************"<<endl// for step until do i j =

cout<<" S ->for S1 do S2"<<endl // 编号 2 345 6 7 8

cout<<" S1 ->S2AB"<<endl

cout<<" S2 ->i=j"<<endl

cout<<" A ->stepj"<<endl

cout<<" B ->untilj"<<endl

int num

turn=0

num=buffer()-1

int x=0//计识别的单词的个数

for(turn<=numturn++)//总循环,ch存放刚读入的字符，strtoken[]存放已识别的标志付或保留字，turn是数组str[]的下标

{

ch=GetChar(turn)

ch=GetBC(ch)

if(IsLetter(ch))

{

while(IsLetter(ch)&&turn<=num||IsDigit(ch)&&turn<=num)

{

Concat()

ch=GetChar(++turn)

}

strToken[n]='\0'

ch=NULL//此ch不是标志符中的符号

turn=turn-1

kind=Reserve()

record[x]=new Wordrecord[x]->sort=kind//12345或6

//cout<<kind //测试

cout<<"("

for(int i=0i<ni++)

{

record[x]->word[i]=strToken[i]

cout<<record[x]->word[i]//输出识别的标志符或保留字

}

cout<<","<<kind<<")"<<endl

record[x]->word[i]='\0'

clear()

x++

}

else if(IsDigit(ch))

{

while(IsDigit(ch)&&turn<=num)

{

Concat()

ch=GetChar(++turn)

}

ch=NULL

turn=turn-1

kind=7

//////////////

record[x]=new Word

record[x]->sort=kind

////////////////

cout<<"("

for(int i=0i<ni++)

{

record[x]->word[i]=strToken[i]

cout<<record[x]->word[i]

}

cout<<","<<kind<<")"<<endl

record[x]->word[i]='\0'

clear()x++

}

else if(ch=='=')

{

kind=8

///////

record[x]=new Word

record[x]->word[0]='='

record[x++]->sort=kind

cout<<"(=,"<<kind<<")"<<endl

}

else

cout<<"error input!"<<endl

}

//////////////////////*语法分析*////////////////

//int y

/*for(y=0y<xy++)

{cout<<record[y]->sort<<" "//打印单词的编号 。

}cout<<endl*/

int ana[MAX]//存放词法分析得到的单词序列的编号的序列

int m

for(m=0m<xm++)

{

ana[m]=record[m]->sort//将sort作为数组保存起来

}

/////////语法分析///////

int j=0

///////////////////制导翻译//////////////////

if(!S(ana,j)) cout<<"语法出错!"<<endl

else

{ cout<<"三地址码如下："<<endl

cout<<"100 "

int i=0

while(record[1]->word[i]!='\0')

cout<<record[1]->word[i++]cout<<record[2]->word[0]

i=0

while(record[3]->word[i]!='\0')

cout<<record[3]->word[i++]cout<<endl

cout<<"101 goto 103"<<endl

cout<<"102 "

i=0

while(record[1]->word[i]!='\0')

cout<<record[1]->word[i++]cout<<":="

i=0

while(record[1]->word[i]!='\0')

cout<<record[1]->word[i++]cout<<"+"

i=0

while(record[5]->word[i]!='\0')

cout<<record[5]->word[i++]cout<<endl

cout<<"103 if "

i=0

while(record[1]->word[i]!='\0')

cout<<record[1]->word[i++]cout<<"<"

i=0

while(record[7]->word[i]!='\0')

cout<<record[7]->word[i++]

cout<<" goto 105"<<endl

cout<<"104 goto 107"<<endl

cout<<"105 "

i=0

while(record[9]->word[i]!='\0')

cout<<record[9]->word[i++]cout<<":="

i=0

while(record[11]->word[i]!='\0')

cout<<record[11]->word[i++]cout<<endl

cout<<"106 goto 102"<<endl

cout<<"107 end"<<endl

}

}

#include<stdio.h>

#include<string>

#include <ctype.h>

//#define ID 1

#define NUM 2

#define PLUS 3 // '+'

#define MINUS 4 // '-'

#define TIMERS 5 // '*'

#define OVER 6 // '/'

#define LPAREN 7 // '('

#define RPAREN 8 // ')'

#define ERROR 255

char token[10]

char *nextchar

//char g_strCalculate[]="122+2*(11-1)/(3-(2-0))"

char g_strCalculate[500]

/*int IsLetter(char ch)

{

if(ch >= 'A' &&ch <= 'Z')

return 1

if(ch >='a'激链 &&ch <='z')

return 1

return 0

}*/

int IsDigit(char ch)

{

if(ch >= '0' &&ch <='9')

return 1

return 0

}

int gettoken()

{

char *ptoken =token

while(*nextchar == ' ' || *nextchar=='\n' || *nextchar=='\t')

nextchar++

switch(*nextchar)

{

case '+': nextchar++return PLUS

case '-': nextchar++return MINUS

case '*': nextchar++return TIMERS

case '/': nextchar++return OVER

case '(': nextchar++return LPAREN

case ')': nextchar++return RPAREN

default: break

}

// ID的词法识别分析

/*if(IsLetter(*nextchar))

{

while(IsLetter(*nextchar) || IsDigit(*nextchar))

{

*ptoken = *nextchar

nextchar++

ptoken++

}

*ptoken ='\0'

printf("gettoken: token = %s\n",token)

return ID

} */

// NUM的词法判闷识别分析

if(IsDigit(*nextchar))

{

while(IsDigit(*nextchar))

{

*ptoken = *nextchar

nextchar++

ptoken++

}

*ptoken ='\0'

// printf("gettoken: token = %s\n",token)

return NUM

}

return ERROR

}

int expression()

int factor()

{

int number

switch(gettoken())

{

// case ID: break

case NUM:

number = atoi(token)

break

case LPAREN:

number = expression()

if(gettoken() != RPAREN)

printf("lost ')' in the expression \n"掘铅弯)

break

default:

break

}

return number

}

int term()

{

int temp

int tokentype

temp = factor()// 对应文法中的Factor

while(*nextchar == '*' || *nextchar == '\\') // 对应文法中的{Mulop Factor}

{

tokentype =gettoken()

switch(tokentype)

{

case TIMERS:

temp *= factor()

break

case OVER:

temp /= factor()

break

default:

break

}

}

return temp

}

int expression()

{

int temp = term()// 对应文法中的第一个Term

int tokentype

while(*nextchar == '+' || *nextchar == '-') // 对应文法中的{

//Addop Term }

{

tokentype = gettoken()

switch(tokentype)

{

case PLUS:

temp +=term()

break

case MINUS:

temp -=term()

break

default:

break

}

}

return temp

}

int main(int argc, char *argv[])

{

char chint i=0,j

FILE *in,*out

if((in=fopen("source.txt","rb"))==NULL)

{

printf("source.txt can't open or doesn't exist...\n")

}

if((out=fopen("output.txt","wb"))==NULL)

{

printf("output file can not open...\n")

}

while(!feof(in))

{

ch=fgetc(in)

g_strCalculate[i++]=ch

fputc(ch,out)

}

g_strCalculate[i]='\0'

nextchar = g_strCalculate

j=expression()

printf("result = %d\n",j)

fputc('=',out)

fprintf(out, "%d", j)

fclose(in)

fclose(out)

system("PAUSE")

return 0

}

---