LL1语法分析设计原理与实现技术实验报告

LL(1)语法分析设计原理与实现技术

实验报告

变更说明

日期

版本

变更位置

变更说明

作者

2014/4/30

1、0

初稿生成

房皓

、实验目的 :

本实验的目的在于在教师的引导下以问题回朔与思维启发的方式 , 使学生在不断的探究过程中掌握编译程序设计与构造的基本原理与实现技术 , 启迪学生的抽象思维、激发学生的学习兴趣、培养学生的探究精神与专业素养 , 从而提高学生发现问题、分析问题与解决问题的能力。

、实验内容

[ 实验项目 ]

实现LL(1)分析中控制程序(表驱动程序);完成以下描述算术表达式的LL(1)文法的LL(1)分析程序。

G[E]: E — TE

E'— ATE | &

T— F「

T'— MFT | &

F— (E)|i

A—+|-

M—*|/

[ 实验说明 ]

终结符号 i 为用户定义的简单变量 , 即标识符的定义。

[ 设计要求 ]

输入串应就是词法分析的输出二元式序列 ,即某算术表达式“实验项目一”的输出结果。输出为输入串就是否为该文法定义的算术表达式的判断结果

LL(1) 分析过程应能发现输入串出错 ;

设计两个测试用例 (尽可能完备,正确与出错), 并给出测试结果。

三、实验环境

操作系统 :Windows 7 软件: VC++6、 0

四、程序功能描述

提供了文件输入方式 , 且输入的内容为二元式序列 ; 能够对输入的字符串做出正确的 LL(1) 分析判断,并给出判断结果 ,判断结果输出到文件 , 并显示在屏幕 ;

能发现输入串中的错误 ,包含非法字符 , 输入不匹配等 ; 能够处理一些可预见性的错误 ,如文件不存在 , 输入非法等。

五、数据结构设计

全局：

MAX 50

ch^r dn^lvseSt^cl<[MAX]; 丿/勺?析丰戋

char toRen[HAJ<]|; "匾人車

typedef= struct CSS "严主式结构体

char loft;

char Klgtlt[5];

int rightlength;

}CSS; _

CSS E,G9G1,T9H,H1,F.F1PA,A1PM JI1 ;|

CSS anali)5elable[7][8];

局部(mai n()中):

int nain()

C1 h 3 厂 a "

int i=0,j = 0fni,u=6(u=n； "i指示栈顶位貳j扌繇剩余串扫描位置

Int num un,num ut;

bool Flag=true；

char tokenl[MAK];

char token2[HAX];

FILE *fpin,*fpout;

六、程序结构描述

设计方法：

本程序采用从文件读取的输入方式，输入的内容需为二元式序列，然后按照LL(1)分析的方法对输入的字符串进行分析判断，并输出判断结果，程序通

过对输入串的检查能够发现输入串中的错误。程序规定的单词符号及其种别

码见下表：

单词符号及其种别码表

单词符号

种别码

单词符号

种别码

(

)

分析表

(

)

E t TG

Et tg

Gt ATG

G t￡

Gt￡

T t FH

H t￡

Ht￡

Ht mfh

H t MFH

H t￡

Ft i

Ft (E)

A t +

A t -

M t *

M t /

主要函数说明：

-Globals

P check_VT(chHr ch)

0 create_analyseT3ble[)

.error[FILE *lp|

9 gctnurn_VN(char ch)

? getnuni_VT[char ch)

.jiisWyfctiar chu int i]

check_VT(char ch):

bool型函数,检查ch就是否为终结字符，就是则返回true;

create_a nalyseTable():

构建分析表函数，无返回值；

error(FILE *fp):

输出错误，表示不就是该文法的句子，参数fp用于退出前将打开的文件关闭；

get nu m_VN(char ch):

int型函数，查找ch在非终结字符中的位置并返回；

get nu m_VT(char ch):

int型函数，查找ch在终结字符中的位置并返回；

justify。：

bool型函数，判断文件读取内容就是否合法，包括检查非法字符与不匹配现象，出错返回false否则返回true;

mai n():

主函数。

函数调用关系说明：

main()调用 check_VT(char ch)、create_analyseTable() error(FILE *fp)、 getnum_VN(char ch)、getnum_VT(char ch)、justify();

执行框图:

牛‘0进栈.当前终结符送吕读下苻入号

牛‘0进栈.当前终结符送吕

读下苻

入

号

出

错

是

七、实验过程结果截图

| input.trt -记善本

丈他号爲(E)梧式(0)童看M 嵇助(H)

斤i)(気后亿15 (反巧亿i)爲/)⑺Q [&町

￡]?F：S诳二学朝偉谨屜爭刃竟宦甲每LL⑴语法分祈设汁腿

读入字符串询；丨i it

SUCCISS?

Press any key to continue

result txt -记事:舉

文件(F)輛? 袒式Q〕査看曲牯丽j SUCCESS'

测试用例二：i+i*i/#

| input.txt -込事本

K D"怎炳冗 i?反 D 6 /)teTS

? ■ F；滾大嘩二学期繰爰原理、硏空性黑蠱丄L；H会圭亠丁■鹿

费入字符串対:l+i**iz4t

AIL!

ress any key to continue

result.txt -记華茶

文的 jftStE) ^rt(O) S^M 粥助(H)

FAIL：

八、实验总结：

实验心得：

通过本次实验我锻炼了自己的上机操作能力及编程能力，并对理论知识有了

进一步的了解。老师提供的LL(1)分析法的流程图给了我很大的帮助，使得本实验基本思路变得很清晰，用较为简单的算法就能实现，程序的难点就是产生式结构体的构造、分析表的构造、解决实验中遇到的问题也花费了一部分时间，我增长了处理关于文件错误的能力。

实验中遇到的问题及解决方法：

问题主要有

从文件输入二元式时，需要检查输入的内容就是否符合程序规定的字

符种别码，解决方法就是用了两个字符数组 token,token2分别记录种

别码与字符，并增加了一个函数justify()根据既定的种别码表判断;

当输入内容不匹配或输入内容非法时要退出程序，此时若不关闭已经

打开的文件可能导致文件内容受到破坏；解决方法就是给error()函数

设置一个文件指针变量参数FILE* fp,在退出程序之前通过fp关闭文件

程序的自我评价 :

此程序实现了要求中的所有功能 ,并增加了输入串错误检测的功能 ,但因编程能力及经验的有限 ,其中有的地方不免有些繁杂 ,还有一些潜藏的问题 ,需要进一步测试与修改来提高程序的健壮性。

九、程序清单 :

/**************************************************** 课题名称 :LL(1) 语法分析设计原理与实现技术作者 :房皓进修生最后修改时间 :2014、 4、30

***************************************************/

************************************************单词符号及其分类编码单词符号种别码1234567

************************************************

单词符号及其分类编码

单词符号种别码

/**********************

G[E]:

E t TE '

E、ATE ' | ￡

T t FT'

T't MFT ' |￡

F t (E)|i

A t +|-

M t *|/

/********************

G[E]:

EtTG

Gt ATG| ￡

TtFH

HtMFH| ￡

文法

**********************

改为等价文法

**************

Ft(E)|i At+|- M t *|/

'*******************

'******************* ************************

'*******************

'******************* ************************

* / (

)

EtTG

GtATG G tATG

G t￡

TtFH

H t￡

H tMFH H tMFH

H t￡

Fti

Ft(E)

At+

At-

M M t * M t /

***********************************************

#include<iostream> #include<conio 、 h> #include<string 、 h> using namespace std; #define MAX 50 char analyseStack[MAX]; char token[MAX]; typedef struct CSS {

char left;

//分析栈

//输入串

//产生式结构体

int right_length;

}CSS;

CSS E,G,G1,T,H,H1,F,F1,A,A1,M,M1;

CSS analyseTable[7][8];

void error(FILE *fp)

{ fprintf(fp,"%s","FAIL!"); fclose(fp); cout<<"FAIL!"<<endl; exit(0);

}

bool justify(char ch,int i) //判断文件读取内容就是否合法 ,包括检查非法字符与不匹配现

象

{

switch(ch)

{

case '1':

if(token[i]!='(')

return false;

break;

case '2':

if(token[i]!=')')

return false; break;

case '3':

if(token[i]!='+') return false;

break;

case '4':

if(token[i]!='-') return false;

break;

case '5':

if(token[i]!='*') return false;

break;

case '6':

if(token[i]!='/') return false;

break;

case '7':

if(token[i]!='i') return false;

break;

case '8':

if(token[i]!='#') return false;

break;

default:

return false; break;

}

return true;

}

bool check_VT(char ch)

{ if(ch=='i' || ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='(' || ch==')') return true;

return false;

}

int getnum_VN(char ch)

{

char VN[7]={'E','G','T','H','F','A','M'};

int i; for(i=0;i<7;i++) if(ch==VN[i])

break;

return i;

}

int getnum_VT(char ch)

{

char VT[8]={'i','+','-','*','/','(',')','#'};

int i;

for(i=0;i<8;i++)

if(ch==VT[i]) break;

if(i==8)

{

cout<<"FAIL!"<<endl;

exit(0);

}

return i;

}

void create_analyseTable()

{

int i,j;

E、left='E';

strcpy(E、 right,"TG");

E、 right_length=2;

G、 left='G';

strcpy(G 、 right,"ATG");

G、 right_length=3;

G1、left='G'; strcpy(G1、right,"NULL");

G1、 right_length=0;

T、left='T';

strcpy(T、 right,"FH");

T、 right_length=2;

H 、 left='H';

strcpy(H 、right,"MFH");

H、 right_length=3;

H1、left='H'; strcpy(H1 、 right,"NULL");

H1、 right_length=0;

F、left='F';

strcpy(F、 right,"(E)");

F、 right_length=3;

F1、left='F';

strcpy(F1 、 right,"i");

F1、 right_length=1;

A 、 left='A';

strcpy(A 、 right,"+");

A 、 right_length=1;

A1、left='A';

strcpy(A1 、 right,"-");

A1 、 right_length=1;

M 、 left='M';

strcpy(M 、 right,"*");

M 、 right_length=1;

M1 、 left='M';

strcpy(M1 、 right,"/");

M1 、 right_length=1;

for(i=0;i<7;i++)

for(j=0;j<8;j++)

{

analyseTable[i][j] 、 left='N';

analyseTable[i][j] 、 right_length=0;

}

analyseTable[0][0]=E;

analyseTable[0][5]=E;

analyseTable[1][1]=G;

analyseTable[1][2]=G;

analyseTable[1][6]=G1;

analyseTable[1][7]=G1;

analyseTable[2][0]=T;

analyseTable[2][5]=T;

analyseTable[3][1]=H1;

analyseTable[3][2]=H1;

analyseTable[3][3]=H;

analyseTable[3][4]=H;

analyseTable[3][6]=H1;

analyseTable[3][7]=H1;

analyseTable[4][0]=F1;

analyseTable[4][5]=F;

analyseTable[5][1]=A;

analyseTable[5][2]=A1;

analyseTable[6][3]=M;

analyseTable[6][4]=M1;

}

int main()

{

char a,X;

int i=0,j=0,m,u=0,v=0; //i 指示栈顶位置 ,j 指示剩余串扫描位置 int num_vn,num_vt;

bool flag=true;

char token1[MAX];

char token2[MAX];

FILE *fpin,*fpout;

create_analyseTable(); //创建分析表

//读文件部分 if((fpin=fopen("input 、 txt","r"))==NULL)

{

cout<<" 文件打开失败！ "<<endl; exit(0);

} if((fpout=fopen("result 、 txt","w"))==NULL)

{ fclose(fpin); cout<<" 文件打开失败！ "<<endl; exit(0);

} token1[v++]=fgetc(fpin); while(!feof(fpin))

{ token1[v++]=fgetc(fpin); if((v%5)==0)

{ token2[u]=token1[v-4]; token[u]=token1[v-2]; if(justify(token2[u],u)) u++;

else

{

fclose(fpin); error(fpout);

}

fclose(fpin);

if((v-1)%5 != 0)

error(fpout);

}

cout<<" 读入字符串为 :"<<token<<endl;

//分析器部分 analyseStack[i++]='#';

analyseStack[i]='E';

a=token[j];

while(flag)

{

X=analyseStack[i]; if(check_VT(X))

if(X==a)

{

a=token[++j];

i--;

}

else

error(fpout);

else

if(X=='#')

if(X==a) flag=false;

else

{ fprintf(fpout,"%s","FAIL!"); cout<<"FAIL!"<<endl; fclose(fpout); exit(0);

}

else

{

num_vn=getnum_VN(X); num_vt=getnum_VT(a);

if(analyseTable[num_vn][num_vt] 、 left!='N')

{

if(analyseTable[num_vn][num_vt] 、 right_length!=0)

、right[m];{ m=analyseTable[num_vn][num_vt] 、 right_length-1; for(;m>=0;m--)

、right[m];

}

i--;

}

else error(fpout);

} fprintf(fpout,"%s","SUCCESS!"); fclose(fpout); cout<<"SUCCESS!"<<endl; return 1;

}

推荐访问:实验报告语法原理实验 LL1语法分析设计原理与实现技术实验报告