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

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 年　月　日

LL分析法和LR分析法。

1、自上而下语法分析方法（LL分析法）

给定文法G和源程序串r。从G的开始符号S出发，通过反复使用产生式对句型中的非终结符进行替换(推导)，逐步推导出r 。 是一种产生的方法，面向目标的方法。分析的主旨为选择产生式的合适的侯选式进行推导，逐步使推导结果与r匹配。

2、自下而上语法分析方法（LR分析法）

从给定的输入串r开始，不断寻找子串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替(归约)之，逐步归约到开始符号S。是一种辨认的方法，基于目标的方法。分析的主旨为寻找合适的子串与P的侯选式进行匹配，直到归约到G的S为止 。

扩展资料

LALR分析器可以对上下无关文法进行语法分析。LALR即“Look-AheadLR”。其中，Look-Ahead为“向前看”，L代表对输入进行从左到右的检查，R代表反向构造出最右推导序列。

LALR分析器可以根据一种程序设计语言的正式语法的产生式而对一段文本程序输入进行语法分析，从而在语法层面上判断输入程序是否合法。

实际应用中的LALR分析器并不是由人手工写成的，而是由类似于yacc和GNU Bison之类的LALR语法分析器生成工具构成。由机器自动生成的代码相比较于程序员手工的代码，拥有更好的运行效率而且减少了程序员的工作量。

参考资料来源：百度百科-语法分析器

参考资料来源：百度百科-语法分析