实验三递归下降法的语法分析器.docx

实验三递归下降法的语法分析器.docx

《实验三递归下降法的语法分析器.docx》由会员分享，可在线阅读，更多相关《实验三递归下降法的语法分析器.docx（38页珍藏版）》请在冰点文库上搜索。

实验三递归下降法的语法分析器

魏陈强204168

实验3递归下降法的语法分析器

一、实验目的

学习用递归下降法构造语法分析器的原理，掌握递归下降法的编程方法。

二、实验内容

用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。

这里只要求实现部分产生式，文法的开始符号为program。

（完整的源语言的文法定义见教材附录，p394）

program→block

block→{stmts}

stmts→stmtstmts|

。

stmt→id=expr;

|if（bool）stmt

|if（bool）stmtelsestmt

|while（bool）stmt

|dostmtwhile（bool）;

|break;

|block

bool→expr

|expr<=expr

|expr>expr

|expr>=expr

&

|expr

expr→expr+term

|expr-term

|term

term→term*factor

|term/factor

|factor

factor→（expr）|id|num

三、实验要求

１．个人完成，提交实验报告。

（

２．实验报告中给出采用测试源代码片断，及其对应的最左推导过程（形式可以自行考虑）。

测试程序片断：

{

i=2;

while（i<=100）

{

sum=sum+i;

i=i+2;

}

}

对应的推导过程为：

#

programblock

{stmts}

{stmtstmts}

{id=expr;stmts}

{id=num;stmts}

{id=num;stmtstmts}

{id=num;while（bool）stmtstmts}

{id=num;while（expr<=expr）stmtstmts}

{id=num;while（id<=expr）stmtstmts}

{id=num;while（id<=num）stmtstmts}

{id=num;while（id<=num）blockstmts}

，

{id=num;while（id<=num）{stmts}stmts}

．．．．．．．

四、实验思路

之前编写的词法分析器，能够将语句中的每一个词素都识别出来，因此，在此基础上，定义一个二维字符串数组finaltable[100][20]，用于存放由词法分析器提取出来的每个词素，比如，i=2，则finaltable[0]=”id”，finaltable[1]=”=”，finaltable[2]=”num”。

并且，为了以后能够方便使用switch（）case语句，另外再定义一个一维整型数组finaltableint[100]，用于存放一个数字和finaltable[100][20]中的字符串对应。

这里，我们定义if=100，for=200，else=300，while=400，do=500，float=600，int=700，break=800，<=17，<==16，>=15，>==14，+=13，&&=12，||=11，}=10，{=9，；=8；）=7，（=6，==5，===4，!

==3，/=2，id=1，keyword=0，num=99，*=18，-=19。

然后依据语法分析的正则表达式，参照实验一类似中缀改后缀的写法以及课本40页的伪代码编写。

相比词法分析器，词法分析的时候，是以单个字符为一个单位，而语法分析，我们以字符串为单位，这些字符串即finaltable[100][20]中的字符串。

编写的过程中涉及几个问题，1、如何把每一步的迭代都显示出来对于这个问题，可以在每个非终结符函数的开头输出对应的迭代即可。

2、在应用文法的时候，应该首先消除左递归，这是至关重要的，该实验我们只要消除expr（）和term（）的左递归即可。

3、if语句二义性处理。

对于这个问题，我们只要再往后看一个字符串，看其是否是else，如果是，则匹配if（bool）stmtelsestmt，否则匹配if（bool）stmt。

4、对于空选择，如何处理一开始的时候，我选择暂时忽略。

五、实验代码

#include<>

#include<>

#include<>

/*

】

if=100，for=200，else=300，while=400，do=500，float=600，int=700，break=800，<=17，<==16，>=15，>==14，+=13，&&=12，||=11，}=10，{=9，；=8；）=7，（=6，==5，===4，!

==3，/=2，id=1，keyword=0，num=99，*=18，-=19

*/

char*keyword[8]={"if","for","else","while","do","float","int","break"};

charkeywordtable[20][20],re_keywordtable[20][20];

chardigittable[20][20],re_digittable[20][20];

charotherchartable[20][20],re_otherchartable[20][20];

charidtable[20][20],re_idtable[20][20];

charnotetable[20][20];

charfinaltable[100][20];

intfinaltableint[100];

charword[20];

~

voidinitialize（）;

voidalpha（）;

voiddigit（）;

voiderror（）;

voidotherchar（）;

voidnote（）;

voidprint（）;

voidprin（）;

voidcheck（）;

voidprogram（）;

voidblock（）;

—

voidstmts（）;

voidstmt（）;

voidBool（）;

voidexpr（）;

voidexpr1（）;

voidterm（）;

voidterm1（）;

voidfactor（）;

voidmatch（char*t）;

intdigit_num=0,keyword_num=0,otherchar_num=0,id_num=0,note_num=0;

：

intredigit_num=1,rekeyword_num=1,reotherchar_num=1,reid_num=1;

intfinal_num=0,finalnum=0;

intflag_error=0;

intflagerror=0;

charlookahead;

voidmain（）

{

printf（"请输入要分析的语句:

\n"）;

initialize（）;

lookahead=getchar（）;

]

while

（1）

{

if（isalpha（lookahead））

{

alpha（）;

initialize（）;

}

elseif（isdigit（lookahead））

{

digit（）;

initialize（）;

}

}

elseif（lookahead=='\t'||lookahead==''）

{

;

}

elseif（lookahead=='\n'）

break;

elseif（lookahead=='/'）

{

lookahead=getchar（）;

if（lookahead=='*'）

-

{

note（）;

initialize（）;

}

else

{

ungetc（lookahead,stdin）;

strcpy（finaltable[final_num],"/"）;

strcpy（otherchartable[otherchar_num++],"/"）;

finaltableint[final_num++]=2;

initialize（）;

`

}

}

else

{

otherchar（）;

initialize（）;

}

lookahead=getchar（）;

}

check（）;

if（flag_error==0）

；

{

printf（"词法分析结果如下:

\n"）;

print（）;

prin（）;

program（）;

if（finalnum==final_num）

printf（"语法分析完成!

\n"）;

}

}

voidalpha（）

、

{

inti=1,flag;

charch;

ch=lookahead;

word[0]=ch;

ch=getchar（）;

while（isalpha（ch）||isdigit（ch））

{

word[i++]=ch;

ch=getchar（）;

}

~

ungetc（ch,stdin）;

flag=0;

for（i=0;i<8;i++）

{

if（strcmp（word,keyword[i]）==0）

flag=1;

}

if（flag==1）

{

strcpy（keywordtable[keyword_num++],word）;

strcpy（finaltable[final_num],word）;

）

if（strcmp（word,"if"）==0）

finaltableint[final_num++]=100;

if（strcmp（word,"for"）==0）

finaltableint[final_num++]=200;

if（strcmp（word,"else"）==0）

finaltableint[final_num++]=300;

if（strcmp（word,"while"）==0）

finaltableint[final_num++]=400;

if（strcmp（word,"do"）==0）

finaltableint[final_num++]=500;

if（strcmp（word,"float"）==0）

]

finaltableint[final_num++]=600;

if（strcmp（word,"int"）==0）

finaltableint[final_num++]=700;

if（strcmp（word,"break"）==0）

finaltableint[final_num++]=800;

}

else

{

strcpy（idtable[id_num++],word）;

strcpy（finaltable[final_num],"id"）;

finaltableint[final_num++]=1;

！

}

}

voiddigit（）

{

inti=1,flag;

charch;

ch=lookahead;

word[0]=ch;

ch=getchar（）;

while（isalpha（ch）||isdigit（ch））

{

{

word[i++]=ch;

ch=getchar（）;

}

ungetc（ch,stdin）;

flag=0;

for（i=0;word[i]!

='\0';i++）

{

if（word[i]<'0'||word[i]>'9'）

flag=1;

}

]

if（flag==1）

{

strcpy（idtable[id_num++],word）;

strcpy（finaltable[final_num],"id"）;

finaltableint[final_num++]=1;

}

else

{

strcpy（digittable[digit_num++],word）;

strcpy（finaltable[final_num],"num"）;

finaltableint[final_num++]=99;

—

}

}

voidotherchar（）

{

charch;

ch=lookahead;

switch（ch）{

case'!

':

{

ch=getchar（）;

if（ch=='='）

{

strcpy（otherchartable[otherchar_num++],"!

="）;

strcpy（finaltable[final_num],"!

="）;

finaltableint[final_num++]=3;

}

else

{

ungetc（ch,stdin）;

error（）;

}

！

}

break;

case'=':

{

ch=getchar（）;

if（ch=='='）

{

strcpy（otherchartable[otherchar_num++],"=="）;

strcpy（finaltable[final_num],"=="）;

finaltableint[final_num++]=4;

}

（

else

{

strcpy（otherchartable[otherchar_num++],"="）;

strcpy（finaltable[final_num],"="）;

finaltableint[final_num++]=5;

ungetc（ch,stdin）;

}

}

break;

case'（':

strcpy（otherchartable[otherchar_num++],"（"）;

￥

strcpy（finaltable[final_num],"（"）;

finaltableint[final_num++]=6;//（6

break;

case'）':

strcpy（otherchartable[otherchar_num++],"）"）;

strcpy（finaltable[final_num],"）"）;

finaltableint[final_num++]=7;//）7

break;

case';':

strcpy（otherchartable[otherchar_num++],";"）;

strcpy（finaltable[final_num],";"）;

]

finaltableint[final_num++]=8;//;8

break;

case'{':

strcpy（otherchartable[otherchar_num++],"{"）;

strcpy（finaltable[final_num],"{"）;

finaltableint[final_num++]=9;//{9

break;

case'}':

strcpy（otherchartable[otherchar_num++],"}"）;

strcpy（finaltable[final_num],"}"）;

finaltableint[final_num++]=10;//}10

、

break;

case'||':

strcpy（otherchartable[otherchar_num++],"||"）;

strcpy（finaltable[final_num],"||"）;

finaltableint[final_num++]=11;//||11

break;

case'&&':

strcpy（otherchartable[otherchar_num++],"&&"）;

strcpy（finaltable[final_num],"&&"）;

finaltableint[final_num++]=12;//&&12

break;

，

case'+':

strcpy（otherchartable[otherchar_num++],"+"）;

strcpy（finaltable[final_num],"+"）;

finaltableint[final_num++]=13;//+13

break;

case'-':

strcpy（otherchartable[otherchar_num++],"-"）;

strcpy（finaltable[final_num],"-"）;

finaltableint[final_num++]=19;//-19

break;

case'>':

（

{

ch=getchar（）;

if（ch=='='）

{

strcpy（otherchartable[otherchar_num++],">="）;

strcpy（finaltable[final_num],">="）;

finaltableint[final_num++]=14;

}//>=14

else

{

strcpy（otherchartable[otherchar_num++],">"）;

]

strcpy（finaltable[final_num],">"）;

finaltableint[final_num++]=15;//>15

ungetc（ch,stdin）;

}

}

break;

case'<':

{

ch=getchar（）;

if（ch=='='）

{

?

strcpy（otherchartable[otherchar_num++],"<="）;

strcpy（finaltable[final_num],"<="）;

finaltableint[final_num++]=16;

}//<=16

else

{

strcpy（otherchartable[otherchar_num++],"<"）;

strcpy（finaltable[final_num++],"<"）;

finaltableint[final_num++]=17;//<17

ungetc（ch,stdin）;

}

；

}

break;

case'*':

strcpy（finaltable[final_num],"*"）;

finaltableint[final_num++]=18;//*18

break;

default:

error（）;break;

}

}

】

voiderror（）

{

flag_error=1;

printf（"出现错误,中止分析!

\n"）;

}

voidinitialize（）

{

inti;

for（i=0;i<20;i++）

%

{

word[i]='\0';

}

}

voidcheck（）

{

inti,j,flag;

strcpy（re_keywordtable[0],keywordtable[0]）;

for（i=1;i

{

|

flag=0;

for（j=0;j

{

if（strcmp（keywordtable[i],re_keywordtable[j]）==0）

{

flag=1;

break;

}

}

if（flag==0）

strcpy（re_keywordtable[rekeyword_num++],keywordtable[i]）;

~

}

strcpy（re_digittable[0],digittable[0]）;

for（i=1;i

{

flag=0;

for（j=0;j

{

if（strcmp（digittable[i],re_digittable[j]）==0）

{

flag=1;

{

break;

}

}

if（flag==0）

strcpy（re_digittable[redigit_num++],digittable[i]）;

}

strcpy（re_otherchartable[0],otherchartable[0]）;

for（i=1;i

{

flag=0;

{

for（j=0;j

{

if（strcmp（otherchartable[i],re_otherchartable[j]）==0）

{

flag=1;

break;

}

}

if（flag==0）

strcpy（re_otherchartable[reotherchar_num++],otherchartable[i]）;

}

（

strcpy（re_idtable[0],idtable[0]）;

for（i=1;i

{

flag=0;