编译原理实验报告二.doc

编译原理实验报告二

深 圳 大 学 实 验 报 告

课程名称： 编译原理

实验项目名称： 语法分析--递归下降法

学院： 计算机及软件

专业： 软件工程

指导教师： 张小建

报告人： 文成 学号： 2011150259 班级： 2

实验时间： 2013-12-25

实验报告提交时间： 2013-12-26

教务部制
一、实验目的：
掌握自顶向下的语法分析法——递归下降法。

二、实验内容：
用递归下降法对如下所定义的逻辑表达式进行语法分析。

1 L→ L || A

2 L→ A

3 A→ A && R

4 A→ R

5 R→ [ L ]

6 R→ ! L

7 R→ E >= E

8 R→ E > E

9 R→ E <= E

10 R→ E < E

11 R→ E == E

12 R→ E != E

13 R→ E

14 E→ E + T

15 E→ T

16 T→ T * F

17 T→ F

18 F→ ( E )

19 F→ n // 数

20 F→ i // 标识符

三、实验设计：
1、消除该文法的左递归（产生式1、3、14、16）；

产生式(1)L→ L || A
(2)L→ A

消除左递归得到： L→ AL'
L'→ || AL' | з
产生式(3)A→ A && R
(4)A→ R

消除左递归得到： A→ RA'
A'→ && RA' | з
产生式(14)E→ E + T

(15)E→ T

消除左递归得到： E→ TE'
E'→ + TE' | з
产生式(16)T→ T * F

(17)T→ F

消除左递归得到：T→ FT'
T'→ *FT' | з

2、 通过抽取公共左因子（产生式7 ~ 12），对该文法进行LL(1)改造；

产生式7~12
7 R→ E >= E

8 R→ E > E

9 R→ E <= E

10 R→ E < E

11 R→ E == E

12 R→ E != E

抽取公共左因子：
R→ ER'
R'→ >=E | >E | <=E | <E | ==E | !=E

3、 证明最终得到的文法为LL(1)文法。

对该文法进行LL(1)改造的结果为：
(01)L → AL'
(02)L'→ || AL' | з
(03)A → RA'
(04)A'→ && RA' | з
(05)R → [L] | !L | ER'
(06)R'→ >=E | >E | <=E | <E | ==E | !=E
(07)E → TE'

(08)E'→ + TE' | з
(09)T → FT'
(10)T'→ *FT' | з
(11)F → (E) | n | i

LL(1)文法的证明：
首先该文法无左递归存在,没有公共左因子。
‚该文法每个非终结符的FIRST无交集
产生式
FIRST
FOLLOW
L → AL'
{ [,!, (, n , i }
{],#}
L'→ || AL'
→ з
{ || }
{ з }
{],#}
A → RA'
{ [,!, (, n , i }
{||,],#}
A'→ && RA'
→ з
{&&}
{ з }
{||,],#}
R → [L]
→ !L
→ ER'
{[}
{!}
{(,n,i}
{&&,],#}
R'→ >=E | >E | <=E | <E | ==E | !=E
{>=,>,<=,<,==,!=}
{&&,],#}
E → TE'

{(, n , i}
{>=,>,<=,<,==,!=,+,)}
E'→ + TE'
→ з
{+}
{з}
{>=,>,<=,<,==,!=,+,)}
T → FT'
{(, n , i}
{*,+}
T'→ *FT'
→ з
{*}
{з}
{*,+}
F → (E)
→n
→i
{(}
{n}
{i}
{*}

ƒ则可以确定该文法是LL(1)文法

文法相应的LL(1)分析表如下：

(
)
n
i
+
*
[
]
>=...
&&
||
!
#
L
AL'

AL'
AL'

AL'

AL'

L'

з

||AL'

з
A
RA'

RA'
RA'

RA'

RA'

A'

з

&& RA'
з

з
R
ER'

ER'
ER'

[L]

!L

R'

>=E...

E
TE'

TE'
TE'

E'

з

+TE'/з

з

T
FT

FT
FT

T'

з
*FT'/з

F
(E)

n
i

四、源程序：
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <conio.h>
void error();
void terror();
void Scanner();
char sym = ' '; int i=0;char strToken[30]={" "};
FILE *in;
void L();
void L1();
void A();
void A1();
void R();
void R1();
void E();
void E1();
void T();
void T1();
void F();

void Retract(char str[30])
{
for(int j=0;j<30;j++)
{
str[j]=0;
}
}

void Scanner()
{
sym=fgetc(in);
if(isspace(sym))
{
while(1)
{
if(isspace(sym))
{
sym=fgetc(in);
}
else break;
}
}
if(isdigit(sym))
{
while(1)
{
if(isdigit(sym))
{
strToken[i]=sym;
i++;
sym=fgetc(in);
}
else
{
printf("%s",strToken);
i=0;
Retract(strToken);
fseek(in,-2,1);
sym=fgetc(in);
break;
}
}
}
else
{
if(sym=='+')
printf("+");
else if(sym=='-')
printf("-");
else if(sym=='*')
printf("*");
else if(sym=='/')
printf("/");
else if(sym=='^')
printf("^");
else if(sym=='(')
printf("(");
else if(sym==')')
printf(")");
}
}

void F()
{
if(isdigit(sym))
Scanner();
else if(sym=='(')
{
Scanner();
E();
if(sym==')')
Scanner();
else error();
}
else
terror();
}

void T1()
{
if(sym=='*')
{
Scanner();
F();
T();
}
}

void T()
{
F();
T1();
}

void E1()
{
if(sym=='+')
{
Scanner();
T();
E1();
}
}

void E()
{
T();
E1();
}

void L()
{
A();
L1();
}

L1()
{
if(sym=='+')
{
Scanner();
A();
L1();
}
}

A()
{
R();
A1();
}

A1()
{
if(sym=='&&')
{
Scanner();
R();
A1();
}
}

R()
{
E();
R1();
if(sym=='[')
{
Scanner();
L();
if(sym==']')
Scanner();
}
if(sym=='!')
{
Scanner();
L();
}
}

R1()
{
if(sym=='>=' || '>' || '<=' || '<' || '==' || '!=')
{
Scanner();
E();
}
}

void error()
{
printf(" This is the wrong phrase!\n");
exit(0);
}

void terror()
{
printf(" This is the wrong phrase2!\n");
exit(0);
}

void main()
{
if((in=fopen("input.txt", "r"))==NULL)
{
printf("THE 'T OPEN！");
exit(0);
}
Scanner();
L();
if(sym=='#')
printf("\nsuccess\n");
else
printf("fail");
fclose(in);
}
五、 运行结果：
程序输入/输出示例：
输入如下表达式（以分号为结束）和输出结果：
（a）3>5;
输出：正确

（b）23>>=454;
输出：正确

（c）2*3>=(2*3*4+3*3)&&[2>3];
输出：正确

六、心得体会：
这次试验不仅要用到试验一的词法扫描器，还要先对文法进行LL（1）改造和证明，还是挺困难的，做了很长时间。大部分时间主要花在设计上，上课讲的很多东西都忘了，需要重新复习下才能开始做。包括寻找FIRST和FOLLOW，以及构造分析表。
总之，这次试验让我收获很大。也重新复习了一遍学过的知识。我了解了语法分析器的内部工作原理，通过在本次实验中运用一定的编程技巧，掌握对表达式进行处理的一种方法,了解了也理解了递归下降分析法的基本原理。

指导教师批阅意见：

成绩评定：

指导教师签字：
年 月 日
备注：
注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。
2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。
20 / 20