123233

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

课程设计任务书

学生姓名：专业班级：

指导教师：工作单位：

题目:预测分析程序的设计

初始条件：

程序设计语言:主要使用C语言的开发工具，或者采用LEX、YACC等工具，也可利用其他

熟悉的开发工具。算法：可以根据《编译原理》课程所讲授的算法进行设计。

要求完成的主要任务:（包括课程设计工作量及其技术要求，说明书撰写等具体要求）

1.明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程设计指导书的要求，

学会设计的基本方法与步骤，学会如何运用前修知识与收集、归纳相关资料解决具体问题的

方法。严格要求自己，要独立思考，按时、独立完成课程设计任务。

2.课设任务：对教材P94中的上下文无关文法，实现它的预测分析程序，给出符号串i+i*i

的分析过程。（参考教材P93～96）

3.主要功能：对于这个给的LL（1）文法，假设所有非终结符号P的FIRST集合和FOLLOW

集合都是已知的，构造其预测分析表，程序显示输出预测分析表，同时用这个预测分析程序

对输入串进行分析，并给出了栈的变化过程。

4.进行总体设计，详细设计：包括算法的设计和数据结构设计。系统实施、调试，合理使用

出错处理程序。

5.设计报告：要求层次清楚、整洁规范、不得相互抄袭。正文字数不少于0.3万字。包含内

容：

①课程设计的题目。②目录。

③正文：包括引言、需求分析、总体设计及开发工具的选择，设计原则（给出语法分析方法

及中间代码形式的描述、文法和属性文法的设计），数据结构与模块说明（功能与流程图）、

详细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。

④结束语。⑤参考文献。⑥附录：软件清单（或者附盘）。

时间安排：

消化资料、系统调查、形式描述1天

系统分析、总体设计、实施计划3天

撰写课程设计报告书1天

指导教师签名：2010年6月11日

系主任（或责任教师）签名：2010年6月11日

目录

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

1引言.............................................3

2需求分析.........................................4

2.1问题的提出.....................................4

2.2问题的解决.....................................4

2.3解决步骤.......................................4

3总体设计.........................................5

3.1概要设计.......................................5

3.1.1设计原理.....................................5

3.1.2构造LL（1）分析表...........................6

3.2详细设计.......................................9

3.2.1程序流程图...................................9

3.2.2设计要求....................................10

3.2.3设计原理....................................11

3.2.3.1FIRST(X)(XVNVT)的构造...............11

3.2.3.2函数getFIRST()(=X1X2X3…Xn)的构造.11

3.2.3.3FOLLOW(A)(AVN)的构造................12

3.2.3.4分析表M【A,a】的构造..................12

3.2.3.5匹配过程的实现.........................12

3.3程序设计......................................13

3.3.1总体方案设计................................13

3.3.2各模块的实现................................13

4开发工具的选择...................................21

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

5程序测试........................................21

6有关技术的讨论...................................23

7收获与体会......................................24

8参考文献........................................24

1引言

一个编译程序在对某个源程序完成了词法分析工作之后，就进入了语法分析阶段，

分析检查源程序是否语法上正确的程序，并生成相应的内部中间表供下一阶段使用。

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

程序设计语言是一般形式语言的特例，程序语法正确性的检查时语法句子的识别，语

法分析问题也就是句型识别问题。按照识别句子语法树建立的方式，有自顶向下与自

底向上两大类分析技术。本课程讨论自顶向下的情况。

本次课程设计所做的工作是对已知FIRST集合和FOLLOW集合的LL(1)文法构造

其预测分析表，程序显示输出预测分析表，同时用这个预测分析程序对输入串进行分

析，并给出了栈的变化过程。

2需求分析

2.1问题的提出

语法分析是编译过程的核心部分。他的任务是在词法分析识别单词符号串的基础

上，分析并判断程序的的语法结构是否符合语法规则。语言的语法结构是用上下文无

关文法描述的。因此语法分析器的工作的本质上就是按文法的产生式，识别输入符号

串是否为一个句子。对于一个文法，当给你一串符号是，如何知道它是不是该文法的

一个句子，这是这个课程设计所要解决的一个问题。

2.2问题的解决

其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符

号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的分析法，一类

是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法，

从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找

一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹

配输入串的过程我主要是自上而下的过程。

2.3解决步骤

在自上而下的分析法中，主要是研究LL(1)分析法。它的解决步骤是首先接收到用

户输入的一个文法，对文法进行检测和处理，消除左递归，得到LL(1)文法，这个文法

应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL

（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。当然本课设只

是针对FIRST和FOLLOW集合都以知的任意输入的LL（1）文法。LL（1）的语法

分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈。

3总体设计

3.1概要设计

3.1.1设计原理

所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，

且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现

LL（1）分析的程序又称为LL（1）分析程序或LL1（1）分析器。

我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无

左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和

FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分

析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，

总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法

进行语法分析，也是采用了C++语言来编写。

LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的

输入符号a做哪种过程的。对于任何（X，a），总控程序每次都执行下述三种可能的

动作之一：

（１）若X=a=‘#’，则宣布分析成功，停止分析过程。

（２）若X=a‘#’，则把X从STACK栈顶弹出，让a指向下一个输入符号。

（３）若X是一个非终结符，则查看预测分析表M。若M[A，a]中存放着关于X

的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

反序一一弹出STACK栈（若右部符号为ε，则不推什么东西进STACK栈）。若M[A，

a]中存放着“出错标志”，则调用出错诊断程序ERROR。

事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固

定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行

分析的。

3.1.2构造LL（1）分析表

在构造LL(1)预测分析表之前，首先要构造该文法的每个非终结符的FIRST和

FOLLOW集合，按照下面描述的算法来构造这两个集合。

①FIRST集合的构造算法：

（1）若X∈VT，则FIRST（X）={X}。

（2）若X∈VN，且有产生式X→a……，则把a加入到FIRST(X)中；若X→ε也是

一条产生式，则把ε也加到FIRST(X)中。

（3）若X→Y……是一个产生式且Y∈VN，则把FIRST(Y)中的所有非ε-元素都加

到FIRST(X)中；若X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，

对于任何j，1≤j≤i-1，FIRST(Yj)都含有ε（即Y1…Yi-1*ε），则把FIRST(Yj)中

的所有非ε-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有ε，j=1,2,…，

k，则把ε加到FIRST(X)中。

连续使用上面的规则，直至每个集合FIRST不再增大为止。

②FOLLOW集合的构造算法：

（1）对于文法的开始符号S，置#于FOLLOW(S)中；

（2）若A→αBβ是一个产生式，则把FIRST(β)|{ε}加至FOLLOW(B)中；

（3）若A→αB是一个产生式，或A→αBβ是一个产生式而βε（即ε∈FIRST(β)），

则把FOLLOW(A)加至FOLLOW(B)中。

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

连续使用上面的规则，直至每个集合FOLLOW不再增大为止。

根据以上描述的算法，可以构造文法G［A］的FIRST和FOLLOW集合如下：

非终结符AFIRST(A)FOLLOW(A)

A{(，i}{),#}

B{+,ε}{),#}

C{(，i}{+,),#}

D{*,ε}{+,),#}

E{(，i}{*,+,),#}

构造预测分析表，设计预测分析表的存储结构（构造算法）。

i+*()

#AACBACB

BB+CBBεBε

CCEDCED

DDεD*EDDεDε

EEiE(A)

总体的框图：

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

句子分析过程的框图：

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

3.2详细设计

3.2.1程序流程图

在对程序各个模块分析之前。先给出整个程序的流程图。以便于在分析过程中更

好的对各个模块之间的联系进行了解。

程序的流程图如下：

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

3.2.2设计要求

1.实现FIRST(X)(X



VN



VT)；

开始

输入文法

相关信息

LL（1）文法

构造FIRST集

构造FOLLOW集

构造预测分析表

输入产生式

判断句型

Continue=“Y“

构造句子的预测分析过程

是

Y

结束

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

2.根据FIRST(X)(X



VN



VT)，实现getFIRST()(=X1X2X3…Xn)；

3.实现FOLLOW(A)(A



VN)；

4.根据getFIRST()以及FOLLOW(A)构造LL(1)分析表M【A,a】；

5.根据分析表M【A,a】，对任一输入字符串进行匹配，判断是否合法，并且显示

其匹配过程。

3.2.3设计原理

3.2.3.1FIRST(X)(X



VN



VT)的构造

连续使用下面的规则，直至每个集合FIRST不再增大为止：

(1).若X



VT，则FIRST(X)={X};

(2).若X



VN，且有产生式X—>a…，则把a加入到FIRST(X)中；若X—>$(表示空

字符串)也是一条产生式，则把$也加到FIRST(X)中。

(3)若X—>Y…是一个产生式且Y



VN，则把FIRST(Y)中的所有非$元素都加到

FIRST(X)中；若X—>Y1Y2…Yk是一个产生式，Y1,…,Yi-1都是非终结符，而且，对于

任何j,1<=j<=i-1，FIRST(Yj)都含有$(即Y1…Yi-1=>$)，则把FIRST(Yj)中的所有非$元

素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有$,j=1,2,…,k,则把$加到

FIRST(X)中。

如上可得到FIRST(X)(X



VN



VT)。

3.2.3.2函数getFIRST()(=X1X2X3…Xn)的构造

之前已经实现了FIRST(X)(X



VN



VT)，现在我们能够对文法G的任何符号串

=X1X2…Xn构造集合FIRST(a)。

首先，置FIRST()=FIRST(X1){$};若对任1<=j<=i-1,$



FIRST(Xj),则把

FIRST(Xi){$}加至FIRST()中；特别是，若所有FIRST(Xj)均含有$,1<=j<=n,则把$也

加至FIRST()中。显然，若=$,则FIRST()={$}。

如上可得到getFIRST()(=X1X2X3…Xn)。

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

3.2.3.3FOLLOW(A)(A



VN)的构造

对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直

至每个FOLLOW不再增大为止。

(1).对于文法的开始符号S，置#于FOLLOW(S)中；

(2).若A—>B是一个产生式，则把FIRST(){$}加至FOLLOW(B)中；

(3).若A—>B是一个产生式，或A—>B是一个产生式而=>$(即

$



FIRST()),则把FOLLOW(A)加至FOLLOW(B)。

如上可得到FOLLOW(A)(A



VN)的构造。

3.2.3.4分析表M【A,a】的构造

在对文法G的每个终结符A及其任意候选a都构造出FIRST(a)(2.2节的

getFIRST(a)),和FOLLOW(A)(2.3节的FOLLOW(A))之后,我们现在可以用它们来构造G

的分析表M【A,a】。

构造分析表M的算法是：

(1).对文法G的每个产生式A—>执行第2步和第3步；

(2).对每个终结符a



FIRST(),把A—>加至M【A,a】中；

(3).若$



FIRST(),则对任何a



FOLLOW(A)把A—>加至M【A,a】中；

(4).把所有无定义的M【A,a】标上“出错标志“。

如上可得到M【A,a】。

3.2.3.5匹配过程的实现

对于任何(A,a),总控程序每次都执行下述三种可能的动作之一：

(1).若X=a=’#’,则宣布分析成功，停止分析过程。

(2).若X=a!=’#’,则把X从stack栈顶逐出，让a指向下一个输入符号。

(3).若X是一个非终结符，则查看分析表M。若M【A,a】中存放着关于X的一个

产生式，那么把X逐出stack栈顶，然后，把产生式的右部符号串按反序一一推进stack

栈(若右部符号为$,则意味不推什么东西进栈)。若M【A,a】中存放着“出错标志“，

则中断匹配，显示出错信息。

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

3.3程序设计

3.3.1总体方案设计

(1).Main()调用input(),读入文法G的有关内容：G(VT,VN,S,&);

(2).Main()调用createFIRST(),实现FIRST(X),(X



VTVN);

(3).内部程序中通过调用getFIRST(string)得到字符串的FIRST终结符；

(4).Main()调用createFOLLOW(),实现FOLLOW(A),(A



VN);

(5).Main()调用createTABLE(),创建LL(1)分析表M【A,a】；

(6).Main()调用match(string)对任一输入的字符串进行匹配，判断其是否合法，并

且显示匹配过程；

3.3.2各模块的实现

(1).voidinput()

VT,VN都是以字符存储的，numVT表示VT的数目，numVN表示VN的数目。

VT标号0—numVT-1，VN标号numVT—numVT+numVN-1。函数findV(char)和V(int)

分别实现字符索引和索引字符间的转换($用nunVT+numVN索引)。

产生式&以字符串的方式读入，经过comsume()函数处理。产生式存在TT[i]的vector

数组中(numVT<=i

数组，存储V[i]的所有产生式。

input()函数代码如下：

voidinput()//存储文法G的有关内容

{

//memt:作用是在一段内存块中填充某个给定的值，它对较大的结构体或数组进行清零操作的一种最快方法

memt(FIRST,0,sizeof(FIRST));//把FIRST【】清零

memt(FOLLOW,0,sizeof(FOLLOW));//把FOLLOW【】清零

charcc;

stringss;

inttop=0;

cout<<"pleainputthetofVT(endby'0')"<

while(cin>>cc&&cc!='0')

V[top++]=cc;

numVT=top;

cout<<"pleainputthetofVN(endby'0')"<

while(cin>>cc&&cc!='0')

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

V[top++]=cc;

numVN=top-numVT;

V[top]='$';

cout<<"pleainputthestartVN"<

cin>>Start;

cout<<"pleainputthechanshengshi(endlineby'0')"<

while(cin>>ss&&ss[0]!='0')

consume(ss);

}

(2).voidcreateFIRST()

用布尔数组FIRST[i][j](0<=i,j<=numVT+numVN)来存储VTVN的开始终结字符

信息。FIRST[i][j]==1表示V[j]



FIRST[V[i]],否则表示V[j]FIRST[V[i]]。

先初始化FIRST[i][j](0<=i,j<=numVT+numVN)为fal，然后while循环按3.2.21

的构造规则进行构造，用len[i](0<=i

结符与非终结符X的开始终结字符数目(即FIRST(X))。每次循环结束检测len[i]并更新。

若检测到任一0<=i

出while循环，函数结束返回。

createFIRST()代码如下：

voidcreateFIRST()//存储VTVN的开始终结字符信息

{

intlen[maxV];

memt(len,-1,sizeof(len));

inti,j,t,no;

for(i=0;i

FIRST[i][i]=1;

boolsign=1;

while(sign)

{

for(i=numVT;i

{

for(j=0;j

{

intpp=findV(TT[i][j][0]);

if(pp

{

FIRST[i][pp]=1;

continue;

}

boolsign2;

for(t=0;t

{

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

sign2=0;

no=findV(TT[i][j][t]);

intiter;

for(iter=0;iter

if(FIRST[no][iter])FIRST[i][iter]=1;

if(FIRST[no][numVT+numVN])

{

sign2=1;

if(t==TT[i][j].size()-1)FIRST[i][numVT+numVN]=1;

}

if(sign2==0)break;

}

}

}

sign=0;

for(i=numVT;i

{

intplen=0;

for(j=0;j

if(FIRST[i][j])plen++;

if(FIRST[i][numVT+numVN])plen++;

if(len[i]!=plen)sign=1;

len[i]=plen;

}

}

}

(3).vectorgetFIRST(stringstr)

对于字符串str，该函数返回str的开始终结符数组。

可根据3.2.22的规则实现，对字符串的字符依次分析，将得到的开始

终结字符存储到临时vector数组tmp中，函数结束返回tmp数组。

vectorgetFIRST(stringstr)代码如下：

vectorgetFIRST(stringstr)//返回str的开始终结符数组

{

vectortmp;

if(()==0)returntmp;

if(str=="$")

{

_back('$');

returntmp;

}

inti,j,no;

boolsign;

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

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

{

sign=0;

no=findV(str[i]);

intiter;

for(iter=0;iter

if(FIRST[no][iter])_back(V[iter]);

if(FIRST[no][numVT+numVN])

{

sign=1;

if(i==()-1)_back('$');

}

if(!sign)break;

}

returntmp;

}

(4).voidcreateFOLLOW()

用布尔数组FOLLOW[i][j](numVT<=i

紧接终结字符信息。FOLLOW[i][j]==1表示V[j]



FOLLOW[V[i]],否则表示

V[j]FOLLOW[V[i]]。

先初始化FOLLOW[i][j](0<=i,j

则进行构造。接着while循环(3)规则用len[i](numVT<=i

循环处理后各个非终结符A的紧接终结字符数目(即FOLLOW(X))。每次循环结束检测

len[i]并更新。若检测到任一numVT<=i

说明已构造完毕，跳出while循环，函数结束返回。

voidcreateFOLLOW()代码如下：

voidcreateFOLLOW()//求得文法G中每个终结符的FOLLOW集

{

intlen[maxV];

memt(len,0,sizeof(len));

inti,j,t,no;

no=findV(Start);

FOLLOW[no][findV('#')]=1;

for(i=numVT;i

{

for(j=0;j

{

for(t=0;t

{

no=findV(TT[i][j][t]);

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

if(no>=numVT&&no!=numVT+numVN)

{

inttt;

if(t

{

vectortmp=getFIRST(TT[i][j].substr(t+1,TT[i][j].size()-t-1));

for(tt=0;tt<();tt++)

if(tmp[tt]!='$')FOLLOW[no][findV(tmp[tt])]=1;

}

}

}

}

}

boolsign=1;

while(sign)

{

for(i=numVT;i

{

for(j=0;j

{

for(t=0;t

{

no=findV(TT[i][j][t]);

if(no>=numVT&&TT[i][j][t]!='$')

{

inttt;

if(t

{

vectortmp=getFIRST(TT[i][j].substr(t+1,TT[i][j].size()-t-1));

for(tt=0;tt<();tt++)

{

if(tmp[tt]=='$')

{

intiter;

for(iter=0;iter

if(FOLLOW[i][iter])FOLLOW[no][iter]=1;

break;

}

}

}

el

{

intiter;

for(iter=0;iter

if(FOLLOW[i][iter])FOLLOW[no][iter]=1;

}

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

}

}

}

}

sign=0;

for(i=numVT;i

{

intplen=0;

for(j=0;j

if(FOLLOW[i][j])plen++;

if(len[i]!=plen)sign=1;

len[i]=plen;

}

}

}

(5).voidcreateTABLE()

用字符串数组M[i][j]来存储栈内符V[i]与输入字符V[j]的匹配

产生式，若不匹配，则为空。

按照3.2.24的规则进行栈顶字符和字符串的字符的依次匹配，匹配

处理结束后，函数结束返回。

voidcreateTABLE()代码如下：

voidcreateTABLE()//构建预测分析表

{

inti,j,t;

for(i=numVT;i

{

for(j=0;j

{

stringtmp=TT[i][j];

vectorfirst=getFIRST(tmp);

boolsign=0;

for(t=0;t<();t++)

{

if(first[t]=='$')sign=1;

el

{

stringstr(1,V[i]);

M[i][findV(first[t])]=str+"->"+TT[i][j];

}

}

if(sign)

{

intiter;

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

for(iter=0;iter

{

stringstr(1,V[i]);

if(FOLLOW[i][iter])M[i][iter]=str+"->"+TT[i][j];

}

}

}

}

}

(6).boolmatch(stringstr)

用栈来实现匹配算法：

栈stack用来存放文法符号。分析开始时，栈底先存放一个’#’,然后放入文法开始符

号。同时，假定输入串之后也总有一个’#’,标志输入串结束。

预测分析程序的总控程序在任何时候都是按stack栈顶符号X和当前的输入符号a

行事的。对具体情况根据规则3.2.25的3种处理方式之一进行处理。处理完后，函

数结束返回。

boolmatch(stringstr)代码如下：

boolmatch(stringstr)//用栈来实现匹配算法

{

str=str+"#";

cout<<"步骤t"<<"符号栈t"<<"输入串t"<<"产生式"<

intnum=0;

charstack[maxV];

inttop=0;

stack[top++]='#';

stack[top++]=Start;

cout<

inti=0,j;

while(i<())

{

charA=stack[top-1];

if(A!='#'&&findV(A)==-1)returnfal;

if(str[i]!='#'&&findV(str[i])==-1)returnfal;

stringtmp;

if(A=='#')

{

if(A==str[i])returntrue;

elreturnfal;

}

elif(findV(A)

{

if(A==str[i])

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

{

top--;

i++;

}

elreturnfal;

}

el

{

tmp=M[findV(A)][findV(str[i])];

if(tmp!="ERROR")

{

top--;

if(tmp[3]!='$')

{

for(j=()-1;j>=3;j--)

stack[top++]=tmp[j];

}

}

elreturnfal;

}

stack[top]='0';

cout<<++num<<"t"<

}

}

(7)intmain()函数

程序的主要功能均在main（）函数里面实现，首先是输入文法的相关信息，然后

是创建FIRST表和FOLLOW表（不输出），再输出预测分析表，最后提示输入句子，判断

是否是该文法的句型，程序实现了多次输入：

intmain()函数代码如下：

intmain()//主函数

{

cout<<"**************预测分析程序**************"<

input();

createFIRST();

createFOLLOW();

createTABLE();

inti,j;

cout<<"**************预测分析表**************"<

cout<<"t"<<"it"<<"+t"<<"*t"<<"(t"<<")t"<<"#t"<

for(i=numVT;i

{

cout<

for(j=0;j

{

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

if(M[i][j].size()>0)cout<

elcout<<"ERROR"<<"t";

}

cout<

}

stringstr;

chars;

boolbl;

do

{

cout<<"**************分析输入串**************"<

cout<<"pleainputthestring"<

cin>>str;

if(match(str))cout<<"YES"<

elcout<<"NO"<

cout<<"continue?(yorn)"<

cin>>s;

}while(s=='y');

if(s=='n')

system("pau");

return0;

}

4开发工具的选择

Visualstudio2008

5程序测试

程序的调试结果如下：

程序的运行结果如下：

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

6有关技术的讨论

本次课程设计主要实现了以下功能：实现对LL(1)文法预测分析表的构造，使得该

文法变的一目了然，从而为判断输入符号串是否是该文法的句型做铺垫。

总的来说本次课设基本上实现了相应的功能，但仍存在一定的问题，需要进一步

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

的思考，由于时间限制和本人能力这方面，做的不是很完美，没有实现程序自动的求

解FRIST集和FOLLOW集，在输出预测分析表的时候没有把对应的非终结符列输入进

去，那样的话预测分析表会更加的直观和美观，此部分功能还有待改进。如果以后能

把此次课设程序的输出用MFC界面做出来就更好了。

7收获与体会

通过这次实验，使我对LL(1)文法的预测分析程序更加了解了，对FIRST(X)与

FOLLOW(A)的构造和认识更加深刻了，也掌握了LL(1)预测分析表的建立的方法，学

会了总控程序的匹配过程，实现了对某一句子的分析，更让我再次复习了编译原理课

程学过的知识，尤其是自顶向下语法分析方法的许多知识。

通过本次课设，我明白了：1、学习一定要扎实，稳扎稳打，学好每一门功课，每

一章节的知识，如果不掌握基本的书本知识，做出来的程序肯定实现不了太多的功能；

2、要善于发现问题，解决问题，当遇到障碍的时候，要学会放松，更要多思考，也许

很快就会找到问题的突破口；3、要多与他人交流，学会团队协作的能力，三人行必有

我师，一个人思考问题，可能会考虑不周，但是人多力量大，集思广益，集体的智慧

是广大的；4、多动手编写程序，养成良好的编程风格，代码要缩进编排，变量的命名

规则要始终保持一致，最好多写注释。

最后感谢在此次课程设计里帮助我的所有同学，也感谢老师平日里的勤劳教学和

谆谆教导！！！

8参考文献

【1】《编译原理》（第二版）,主编：吕映芝、张素琴、蒋维杜,出版社：清华大学出

版社,出版时间：2004年11月

【2】《编译原理课程设计》,主编：王雷、刘志成、周晶,出版社：机械工业出版社,

出版时间：2005年3月

【3】《编译原理学习指导》,主编：胡元义、柯丽芳,出版社：西安电子科技大学出版

社,出版时间：2004年1月

【4】《编译原理实践教程》,主编：胡元义、邓亚玲、胡英,出版社：西安电子科技大

-----WORD格式--可编辑--专业资料-----

--完整版学习资料分享----

学出版社,出版时间：2002年1月

【5】《c++程序设计》,主编：谭浩强,出版社：清华大学出版社,出版时间：2006年1

月