编译原理报告(9)

编译原理报告(9)本文简介：课程实验报告课程名称：编译原理专业班级：信息安全1302班学号：姓名：指导老师：报告日期：2015年11月11日计算机科学与技术学院27目录实验一词法分析11.实验目的12.实验要求13.算法思想24.具体实现45.结果分析56.实验总结6实验二语法分析71.实验目的72.实验要求73.算法思想84

编译原理报告(9)本文内容：

课

程

实

验

报

告

课程名称：

编译原理

专业班级：

信息安全1302班

学

号：

姓

名：

指导老师：

报告日期：

2015年11月11日

计算机科学与技术学院

27

目录

实验一

词法分析1

1.

实验目的1

2.

实验要求1

3.

算法思想2

4.

具体实现4

5.

结果分析5

6.

实验总结6

实验二

语法分析7

1.

实验目的7

2.

实验要求7

3.

算法思想8

4.

具体实现10

5.

结果分析12

6.

实验总结12

附录·源程序13

词法分析13

语法分析18

实验一

词法分析

1.

实验目的

设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。

2.

实验要求

2.1

待分析的简单的词法

（1）关键字：

begin、if、then、while、do、end

所有的关键字都是小写。

（2）运算符和界符

：

=

+

-

/

>

>=

=

;

(

)

#

（3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义：

ID

=

letter

(letter

|

digit)*

NUM

=

digit

digit*

（4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。

2.2

各单词符号的种别码

各种单词符号所对应的种别码如表1所示。

2.3

词法分析程序的功能：

输入：所给文法的源程序字符串。

输出：二元组（syn，token或sum）构成的序列。

其中：syn为单词种别码；

token为存放的单词自身字符串；

sum为整型常数。

例如，对源程序

begin

x:=9:

if

x>9

then

x:=2*x+1/3;

end

#

的源文件，经过词法分析后输出如下序列：

(1,begin)

(10,x)

(18,:=)

(11,9)

(26,;)

(2,if)

……

表1

各种单词符号对应的种别码

单词符号

种别码

单词符号

种别码

begin

1

：

17

If

2

：=

18

Then

3

21

do

5

23

letter（letter

|

digit）*

10

>=

24

dight

dight*

11

=

25

+

13

；

26

—

14

(

27

15

)

28

/

16

#

0

3.

算法思想

算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。

3.1

主程序框图

主程序框图如图1-3-1所示。其中初始包括以下两个方面：

（1）关键字表的初值。

关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：

Charrwtab[6]

=

{“begin”,“if”,“then”,“while”,“do”,“end”,};

（2）程序中需要用到的主要变量为syn，token和sum。

3.2

扫描子程序的算法思想

首先设置3个变量：token用来存放构成单词符号的字符串；sum用来整型单词；syn用来存放单词符号的种别码。扫描子程序主要部分流程如图1-3-2所示。

置初值

调用扫描子程序

输出单词二元组

输入串结束

否

是

结束

图1-3-1

词法分析主程序框图

变量初始化

忽略空格

返回

是否文件结束？

是

否

字母拼字符串

数字其他符号

错误

是否关键字？

拼数

对不同符号给出相应的syn值

否

报错

syn=10

是

syn=11

syn为对应关键字的单词种别码

返回

图1-3-2

词法分析程序扫描子程序框图

4.

具体实现

charrwtab[6]

=

{“begin“,“if“,“then“,“while“,“do“,“end“};

//关键字表

/*

自选函数/

char

m_getch(){

//从输入源读一个字符到CH中

ch

=

prog[p++];

return

ch;

}

void

getbc(){

//去掉空白字符

while

(ch

==

||

ch==

10){

ch

=

prog[p++];

}

}

void

concat(){

//拼接单词

token[m++]

=

ch;

token[m]

=

\0

;

}

int

letter(){

//判断是否是字母

if((ch>=

a

end

#

后经词法分析输出如下序列：

(1,begin)

(10,x)

(18,:=)

(11,9)

(26,;)

(2,if)

……

如图1-5-1所示：

图1-5-1

词法分析实验结果

6.

实验总结

词法分析的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。通过本试验的完成，更加加深了对词法分析原理的理解。

实验二

语法分析

1.

实验目的

编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。

2.

实验要求

利用C语言编制递归下降分析程序，并对简单语言进行语法分析。

2.1

待分析的简单语言的语法

用扩充的BNF表示如下：

（1）：：=beginend

（2）：：={；}

（3）：：=

（4）：：=ID：=

（5）：：={+

|

-}

（6）：：={*

|

/

（7）：：=ID

|

NUM

|

（）

2.2

实验要求说明

输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。

例如：

输入

begin

a:=9;

x:=2*3;

b:=a+x

end

#

输出

success！

输入

x:=a+b*c

end

#

输出

error

3.

算法思想

（1）主程序示意图如图2-3-1所示。

置初值

调用scaner读下一个单词符号

调用lrparser

结束

图2-3-1

语法分析主程序框图

（2）递归下降分析程序示意图如图2-3-2所示。

（3）语句串分析过程示意图如图2-3-3所示。

是否begin?

调用statement函数

否

是

调用scaner

是否

；?

否

调用语句串分析程序

是

是否end?

调用scaner

否

调用statement函数

是

调用scaner

syn=0

else

if(syn

==

27){

scaner();

//读下一个单词符号

expression();

//调用函数statement()

if(syn

==

28)

scaner();

//读下一个单词符号

else{

printf(“The

error

is

on

)

.\n“);

kk

=

1;

}

}

else{

printf(“The

expression

is

error!\n“);

kk

=

1;

}

return;

}

void

term(){

factor();

//调用函数factor()

while(syn==15

||

syn==16)

{

scaner();

//读下一个单词符号

factor();

//调用函数factor()

}

return;

}

void

expression(){

term();

//调用函数term()

while(syn==13

||

syn==14){

scaner();

//读下一个单词符号

term();

//调用函数term()

}

return;

}

void

statement(){

if(syn==10){

scaner();

//读下一个单词符号

if(syn==18){

scaner();

//读下一个单词符号

expression();

//调用函数statement()

}

else{

printf(“the

symbol

:=

is

error!\n“);

kk=1;

}

}

else{

printf(“The

sentence

is

error!\n“);

kk=1;

}

return;

}

void

yucu()

{

statement();

//调用函数statement()

while(syn

==

26){

scaner();

//读下一个单词符号

if(syn

!=

6)

statement();

//调用函数statement()

}

return;

}

void

lrparser(){

if(syn

==

1){

scaner();

//读下一个单词符号

yucu();

//调用yucu()函数

if(syn

==

6){

scaner();

if(syn==0

}

else{

if(kk

!=

1)

printf(“The

string

is

lack

of

a

end

!\n“);

kk

=

1;

}

}

else{

printf(“The

string

is

lack

of

a

begin

!\n“);

kk

=

1;

}

return;}

int

main(){

p

=

0;

printf(“Please

input

string

(end

of

#):

\n“);

do{

scanf(“%c“,prog[p++]

=

ch;

}while(ch

!=

#

);

p

=

kk

=

0;

scaner();

lrparser();

return

0;

}

5.

结果分析

（1）输入

begin

a:=9;

x:=2*3;

b:=a+x

end

#

后，输出success！

如图2-5-1所示：

图2-5-1

语法分析实验结果(一)

（2）输入

x:=a+b*c

end

#

后，输出The

string

is

lack

of

a

begin

!

如图2-5-2所示：

图2-5-2

语法分析实验结果(二)

6.

实验总结

通过本次试验，了解了语法分析的运行过程，主程序大致流程为：“置初值”à调用scaner函数读下一个单词符号à调用IrParseà结束。递归下降分析的大致流程为：“先判断是否为begin”à不是则“出错处理”，若是则“调用scaner函数”à调用语句串分析函数à“判断是否为end”à不是则“出错处理”，若是则“调用scaner函数”à“判断syn=0

char

ch;

int

syn,p,m,n;

charrwtab[6]

=

{“begin“,“if“,“then“,“while“,“do“,“end“};

char

m_getch()

//从输入源读一个字符到CH中

{

ch

=

prog[p++];

return

ch;

}

void

getbc()

//去掉空白字符

{

while

(ch

==

||

ch==

10)

{

ch

=

prog[p++];

}

}

void

concat()

//拼接单词

{

token[m++]

=

ch;

token[m]

=

\0

;

}

int

letter()

//判断是否是字母

{

if((ch>=

a

concat();

}

else

if(ch

==

=

)

{

syn

=

22;

concat();

}

else

{

syn

=

20;

retract();

}

break;

case

>

:

concat();

m_getch();

if(ch

==

=

)

{

syn

=

24;

concat();

}

else

{

syn

=

23;

retract();

}

break;

case

:

:

concat();

m_getch();

if(ch

==

=

)

{

syn

=

18;

concat();

}

else

{

syn

=

17;

retract();

}

break;

case

+

:

syn

=

13;

token[0]

=

ch;

break;

case

-

:

syn

=

14;

token[0]

=

ch;

break;

case

:

syn

=

15;

token[0]

=

ch;

break;

case

/

:

syn

=

16;

token[0]

=

ch;

break;

case

=

:

syn

=

25;

token[0]

=

ch;

break;

case

;

:

syn

=

26;

token[0]

=

ch;

break;

case

(

:

syn

=

27;

token[0]

=

ch;

break;

case

)

:

syn

=

28;

token[0]

=

ch;

break;

case

#

:

syn

=

0;

token[0]

=

ch;

break;

}

}

int

main()

{

p

=

0;

printf(“Please

input

string

(end

of

#):

\n“);

do

{

scanf(“%c“,prog[p++]

=

ch;

}while(ch

!=

#

);

p

=

0;

do

{

scaner();

switch(syn)

{

case

-1:

printf(“you

have

inputed

a

wrong

string!\n“);

getch();

exit(0);

default:

printf(“(%d,%s)\n“,syn,token);

break;

}

}while(syn

!=

0);

return

0;

}

语法分析

#include

#include

#include

#include

#include

void

expression();

char

prog[80],token[80];

char

ch;

int

syn,p,m,n,kk;

charrwtab[6]

=

{“begin“,“if“,“then“,“while“,“do“,“end“};

char

m_getch()

//从输入源读一个字符到CH中

{

ch

=

prog[p++];

return

ch;

}

void

getbc()

//去掉空白字符

{

while

(ch

==

||

ch==

10)

{

ch

=

prog[p++];

}

}

void

concat()

//拼接单词

{

token[m++]

=

ch;

token[m]

=

\0

;

}

int

letter()

//判断是否是字母

{

if((ch>=

a

concat();

}

else

if(ch

==

=

)

{

syn

=

22;

concat();

}

else

{

syn

=

20;

retract();

}

break;

case

>

:

concat();

m_getch();

if(ch

==

=

)

{

syn

=

24;

concat();

}

else

{

syn

=

23;

retract();

}

break;

case

:

:

concat();

m_getch();

if(ch

==

=

)

{

syn

=

18;

concat();

}

else

{

syn

=

17;

retract();

}

break;

case

+

:

syn

=

13;

token[0]

=

ch;

break;

case

-

:

syn

=

14;

token[0]

=

ch;

break;

case

:

syn

=

15;

token[0]

=

ch;

break;

case

/

:

syn

=

16;

token[0]

=

ch;

break;

case

=

:

syn

=

25;

token[0]

=

ch;

break;

case

;

:

syn

=

26;

token[0]

=

ch;

break;

case

(

:

syn

=

27;

token[0]

=

ch;

break;

case

)

:

syn

=

28;

token[0]

=

ch;

break;

case

#

:

syn

=

0;

token[0]

=

ch;

break;

}

}

void

factor()

{

if(syn==10

||

syn==11)

scaner();

else

if(syn

==

27)

{

scaner();

//读下一个单词符号

expression();

//调用函数statement()

if(syn

==

28)

scaner();

//读下一个单词符号

else

{

printf(“The

error

is

on

)

.\n“);

kk

=

1;

}

}

else

{

printf(“The

expression

is

error!\n“);

kk

=

1;

}

return;

}

void

term()

{

factor();

//调用函数factor()

while(syn==15

||

syn==16)

{

scaner();

//读下一个单词符号

factor();

//调用函数factor()

}

return;

}

void

expression()

{

term();

//调用函数term()

while(syn==13

||

syn==14)

{

scaner();

//读下一个单词符号

term();

//调用函数term()

}

return;

}

void

statement()

{

if(syn==10)

{

scaner();

//读下一个单词符号

if(syn==18)

{

scaner();

//读下一个单词符号

expression();

//调用函数statement()

}

else

{

printf(“the

symbol

:=

is

error!\n“);

kk=1;

}

}

else

{

printf(“The

sentence

is

error!\n“);

kk=1;

}

return;

}

void

yucu()

{

statement();

//调用函数statement()

while(syn

==

26)

{

scaner();

//读下一个单词符号

if(syn

!=

6)

statement();

//调用函数statement()

}

return;

}

void

lrparser()

{

if(syn

==

1)

{

scaner();

//读下一个单词符号

yucu();

//调用yucu()函数

if(syn

==

6)

{

scaner();

if(syn==0

}

else{

if(kk

!=

1)

printf(“The

string

is

lack

of

a

end

!\n“);

kk

=

1;

}

}

else

{

printf(“The

string

is

lack

of

a

begin

!\n“);

kk

=

1;

}

return;

}

int

main()

{

p

=

0;

printf(“Please

input

string

(end

of

#):

\n“);

do

{

scanf(“%c“,prog[p++]

=

ch;

}while(ch

!=

#

);

p

=

kk

=

0;

scaner();

lrparser();

return

0;

}