编译原理课程设计报告 LL(1)分析过程模拟

时间：2024.4.13

课程设计(论文)任务书

软件学院 　学　　院　　 软件工程 　专　　业　 07-1 　班　　　

一、课程设计(论文)题目　LL(1)分析过程模拟　　　

二、课程设计(论文)工作自 20## 年 6 月 22日起至 2010 年 6 月 28 日止。

三、课程设计(论文) 地点:

四、课程设计(论文)内容要求：

1．本课程设计的目的

（1）使学生掌握LL（1）模块的基本工作原理；

（2）培养学生基本掌握LL（1）分析的基本思路和方法；

（3）使学生掌握LL（1）的调试；

（4）培养学生分析、解决问题的能力；

（5）提高学生的科技论文写作能力。

2．课程设计的任务及要求

1）基本要求：

（1）分析LL（1）模块的工作原理；

（2）提出程序的设计方案；

（3）对所设计程序进行调试。

2）创新要求：

在基本要求达到后，可进行创新设计，如改算法效率。

3）课程设计论文编写要求

（1）要按照书稿的规格打印誊写课程设计论文

（2）论文包括目录、绪论、正文、小结、参考文献、附录等

（3）课程设计论文装订按学校的统一要求完成

4）答辩与评分标准：

（1）完成原理分析：20分；

（2）完成设计过程（含翻译）：40分；

（3）完成调试：20分；

（4）回答问题：20分。

5）参考文献：

（1）张素琴，吕映芝，蒋维杜，戴桂兰.编译原理（第2版）.清华大学出版社

（2）丁振凡 .《Java语言实用教程》北京邮电大学出版社

6）课程设计进度安排

内容 天数　　　　　　地点

构思及收集资料 2　　　　　　　图书馆

编程与调试 4　　　　　　实验室

撰写论文 1　　　　　　　图书馆、实验室

学生签名：

2009 年6 月22 日

课程设计(论文)评审意见

（1）完成原理分析（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）；

（2）设计分析　　（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）；

（3）完成调试　　（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）；

（4）翻译能力　　（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）；

（5）回答问题　　（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）；

（6）格式规范性及考勤是否降等级：是（　）、否（　）

评阅人：　　　职称：

年月日

目　录

一、课设题目__________________________________________________ 5

1.__________________________________________ 问题描述 5

2.__________________________________________ 基本要求 5

3.__________________________________________ 测试数据 5

二、需求分析__________________________________________________ 6

1.__________________________________________ 问题理解 6

2.__________________________________________ 问题分析 6

3._________________________________________ 问题的解决 6

4.__________________________________________ 解决步骤 6

三、概要设计__________________________________________________ 9

1、设计原理_____________________________________ 9

2、预测分析表具体构造____________________________ 11

3、主要算法思想_________________________________ 12

四、详细设计____________________________________________________ 12

1.________________________________ 总体思路分析及流程图 12

2、测试数据i*i+i 的语法树__________________________ 18

2.__________________________________________ 关键代码 18

3.__________________________________________ 函数说明 21

五．运行结果___________________________________ 23

1.__________________________________________ 出错处理 24

六、课程设计总结_______________________________________________ 26

七、参考文献____________________________________________________ 27

八、附录________________________________________________________ 27

一、课设题目

1. 问题描述

设计一个给定LL（1）分析表，输入一个句子，能由依据LL（1）分析表输出与句子对应的语法树。能对语法树生成过程进行模拟。

2. 基本要求

动态模拟算法的基本功能是：

（1）输入LL（1）分析表和一个句子；

（2）输出LL（1）总控程序；

（3）输出依据句子构成的对应语法树的过程；

3. 测试数据

输入句子：i*i+i

输入LL（1）分析表

二、需求分析

1. 问题理解

用数据库存储多行文法，用LIST控件显示算法，用GRID类依据算法进行作图。并实现算法与生成过程的关联。

2. 问题分析

求出First集和Follow集，是求出Select集的基础，因此本程序也做了些完善，功能扩展发面，在出First集和Follow集的基础上求Select集，判断是否为LL1文法，构造预测分析表。判断是在LL1分析文法中通过Select集判断是否是LL1文法，求出预测分析表之后，实现了字符串，依据LL1分析表单步输出字符串的分析过程。

3. 问题的解决

其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的分析法，一类是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。

4. 解决步骤

总体步骤

在自上而下的分析法中，主要是研究LL(1)分析法。它的解决步骤是首先接收到用户输入的一个文法，对文法进行检测和处理，消除左递归，得到LL(1)文法，这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈。

FIRST集的确定

FIRST集使用以下四个步骤判定：

(1)若X∈VT?,则FIRST(X)={X}

(2)若X∈VN,且有产生式X→a…，a∈VT 。

则把a加入到FIRST(X)中，即a∈FIRST(X)

(3)若X∈VN,且有产生式X→$，

则把$也加到FIRST(X)中，即$∈FIRST(X)

(4)若X∈VN, Y1，Y2，…，Yi 都∈VN，

且有产生式X→Y1Y2…Yn。当Y1，..Yi-1=>$ (1≤i≤n)，则FIRST(Y1)-{$}，…，FIRST(Yi-1)-{$}，FIRST(Yi)都包含在FIRST(X)中，即：

FIRST(Yi-1)-{$} ∈FIRST(X)

所有Y1,…Yn *=> $ ，则把$加到FIRST(X)中,即：

FIRST(Yi) ∈FIRST(X)

FOLLOW集的确定

FOLLOW集使用以下三个步骤判定：

(1)如果 X 是开始符那么把 # 加入到 FOLLOW(X)

(2)若Ａ=>αBβ是一个产生式,则把FIRST(β)－{$}加至FOLLOW(B)中

(3)若Ａ=>αB是一个产生式，或Ａ=>αBβ是一个产生式而β*=>$(即$∈FIRST(β)），则把 FOLLOW(A)加至FOLLOW(B)中

FOLLOW集的求法与FIRST集类似，但有不同的地方。FOLLOW集需要扫描每一个产生式。而FIRST集扫描的是产生式左部不同的产生式，然后扫描左部相同的产生式的每一个右部。FOLLOW集第一次扫描可以确定哪些FIRST集或FOLLOW集属于所求的FOLLOW集，由于FIRST集已经求出，所以第一次扫描就可以把相应的FIRST集加入到FOLLOW集中，设置FOLLOW集完成标记位，设置队列，把未完成的非终结符送入队列，依次取出队列元素，把求出FOLLOW集的非终结符的FOLLOW集加入到相应的FOLLOW集中，把未求出的送回队列。

碰到死循环使用FIRST集一样的方法处理就可以。

SELLECT集的确定

FIRST集＆FOLLOW集都已经求出来后SELLECT集就很好求了，扫描每一个产生式，使用以下三个步骤确定：

A→α A∈VN，α∈V*，

(1)若α是终结符，那么SELLECT(A→α)={α}

(2)若α是$，则SELECT(A→α)=FOLLOW(A)

(3)若α是非终结符那么

若α*=>$，则SELECT(A→α)=(FIRST(α)-$)∪FOLLOW(A)

若α┐*=>$ 则SELECT(A→α)=FIRST(α)

LL(1)文法的判定

当SELLECT集求出来后就可以判断是不是一个文法是不是LL(1)文法了，扫描产生式左部相同的SELLCET集是否含有相同元素，一旦发现相同元素立刻返回FALSE，扫描结束没有发现相同元素则返回TRUE。

句子的判定

当一个文法确定是LL(1)文法时就可以对输入的语句进行判定了。首先要安装SELLECT集生成LL(1)预测分析表，最简单的方法是使用哈希表来表示，把每一个产生式左部依次和这个产生式SELLECT集中的每一个终结符组成关键字，其值即为这个产生式，送入哈希表。这样在进行句子的分析时就可以很容易判断是否使用某一个产生式来进行规约。在实际分析时设置两个栈，把"#"压入分析栈和剩余栈，把开始符压入分析栈，把输入串从右向左送入剩余栈，然后只要两个栈元素个数同时大于1，那么依次从两个栈中取出两个元素进行比较，假如一样就匹配，假如可以规约就规约，否则就不是该文法的句子。

三、概要设计

1、设计原理

（1）、LL（1）文法的定义

LL(1)分析法属于确定的自顶向下分析方法。LL(1)的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。

LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。

需要预测分析器对所给句型进行识别。即在LL(1)分析法中，每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，判断其与剩余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。LL(1)分析方法要求文法满足如下条件：对于任一非终极符A的两个不同产生式Aàa,Aàb，都要满足下面条件：SELECT(Aàa)∩SELECT(Aàb)=Æ

（2）、预测分析表构造

LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字符串，一是null。若用M表示LL(1)分析表，则M可表示如下：

M: VN×VTàP∪{Error}

M(A, t) = Aàα，当tÎselect(Aàα) ，否则

M(A, t) = Error

其中P表示所有产生式的集合。

（3）、语法分析程序构造

LL(1)分析中X为符号栈栈顶元素，a为输入流当前字符，E为给定测试数据的开始符号，#为句子括号即输入串的括号。分析表用一个二位数组M表示，数组元素M[A，a]中的下标A表示非终结符，a为终结符或句子括号‘#’，二维数组中存放的是一条关于A 的产生式，表明当非终结符A向下推导时，面临输入符a时，所采用的候选产生式，当元素内容无产生式时，则表明用A 的左部向下推导时出现了不该出现的符号，因此元素内容转向出错处理的信息。

LL(1)分析过程主要包括以下四个动作：

替换：当XÎVN时选相应产生式的右部b去替换X。此时X出栈，b逆序入栈。

匹配：当XÎVT时它与a进行匹配，其结果可能成功，也可能失败，如果成功则符号栈中将X退栈并将输入流指针向前移动一位，否则报错。

接受：当格局为（#，空#）时报告分析成功。

报错：出错后，停止分析。并给出相应的错误提示信息。

驱动程序框图如：

2、预测分析表具体构造

此语法程序的实现采用手工操作输入构造LL(1)分析表。LL(1)分析表用一个二维矩阵表示，其中每个非终极符对应一行，每个终级符对应一列，一个非终极符和一个终极符可以确定矩阵中的一个元素，元素的值表示该非终极符和该终极符对应的产生式。每个矩阵元素都是一个字符串，所有元素初始化为null；构造LL(1)表时，根据给出的测试数据中相应的分析表LL(1)分析表的内容。其中输入产生式为空用&表示，产生式不存在则进行出错处理，在数组中出错用NULL或者null表示。在根据LL(1)分析表选择产生式进行推导时，若查到的产生式为NULL或者null表示无相应的产生式可选，不匹配错误；否则根据编号得到相应的产生式进行推导。

预测分析表的模型示意图

八边形: d 八边形: b

八边形: c

a. 控制程序是依据分析表和分析栈联合控制输入字符串的识别和分析，它在任何时候都是依据当前分析栈的栈顶符号和当前输入字符来执行控制功能。对不同文法，控制程序是相同的。

b. 输入缓冲器用来存放被分析的符号串，符号串后跟以标志符号#。

c. 栈中存放一系列文法符号，符号#存在于栈的底部，分析开始时，栈底先放好#，然后放进文法开始符号。

d. 分析表是一个二维数组M[A,a]，其中A是非终结符号，a是终结符号或是符号#，M[A,a]内容为一条关于A的产生式或出错标志，不同语言使用内容不同的分析表。

e. 输出流是在分析中不断产生的输出序列。

3、主要算法思想

（1）、分析开始时，首先将标志符号#和文法开始符号E依次压入符号栈；输入流指针指向分析串的第一个输入符号，即由符号栈和输入流构成的初始格局为：

(#E, a1a2...an#)

然后，反复执行第2步所列的工作。

（2）、设在分析的某一步，符号栈及剩余的输入流处于如下的格局：

(#A12...Am-1Am, aiai+1...an#)

其中，A1A2...Am-1Am为分析栈中的文法符号，此时，可视栈顶符号Xm的不同情况，分别作如下动作：

若AmÎVN，则以Am及ai组成的符号对(Am，ai)查分析表M。设M(Am，ai)为一产生式，假设是AmàUVW，此时将Am从分析栈中弹出，并将UVW逆序压入栈中，从而得到新的格局：

(#A1A2...Am-1WVU, aiai+1...an#)

但若T(Am，ai)=NULL或null，则调用出错处理程序进行处理；

若Am=ai¹#，则表明栈顶符号已经与当前扫描的输入符号得到匹配，此时应将Am（即ai）从栈中退出，并将输入流指针向前移动一个位置。

若Xm=ai=#，则表明输入串已经完全得到匹配，此时即可宣告分析成功而结束分析。

其它情形，转到错误处理程序。

四、详细设计

1. 总体思路分析及流程图

给定一个正规文法G，在LL(1)预测分析中，必须先求出First集和Follow集，然后求出Select集，通过Select集判断是否是LL1文法，如果是的话，构造预测分析表。求出预测分析表之后，再输入一个字符串，依据LL1分析表单步输出字符串的分析过程。

功能模块分解图

（1）主程序流程图

（2）核心算法流程图

1.计算非终结符的First集的算法及流程：

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不再增大为止。

2.计算非终结符的Follow集：

Follow集合的具体构造算法如下：

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

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

（3）若A→αB是一个产生式，或A→αBβ是一个产生式而β ε（即ε∈First(β)），则把Follow(A)加至Follow(B)中。

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

3.预测分析控制程序的算法流程

2、测试数据i*i+i 的语法树

2. 关键代码

（1）计算非终结符的First集：

void first(edge ni,edge *n,int x)//ni为一个产生式，n为整个文法

{ int i,j;

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

{ if(ni.getlf()==n[j].getlf())

{

if(NODE.find(n[j].getro())<NODE.length())//非终结符的情况

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

if(n[i].getlf()==n[j].getro())

first(n[i],n,x);

}

else n[x].newfirst(n[j].getro());//终结符的情况

}

（2）计算非终结符的Follow集：

void follow(edge ni,edge *n,int x) //计算follow

{ int i,j,k,s;

string str;

for(i=0;i<ni.getrlen();i++)

{ s=NODE.find(ni.getrg()[i]);

if(s<NODE.length()&&s>-1) //是非终结符

if(i<ni.getrlen()-1) //不在最右

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

if(n[j].getlf().find(ni.getrg()[i])==0)

{ if(NODE.find(ni.getrg()[i+1])<NODE.length())

{ for(k=0;k<SUM;k++) if(n[k].getlf().find(ni.getrg()[i+1])==0)

{

n[j].newfollow(n[k].getfirst()); if(n[k].getfirst().find("*")<n[k].getfirst().length())

n[j].newfollow(ni.getfollow());

}

else

{str.erase();

str+=ni.getrg()[i+1];

n[j].newfollow(str);

}

（3）输出预测分析表的主要代码：

void outgraph(edge *n,string (*yc)[50])

{ int i,j,k;

bool flag;

for(i=0;i<ENODE.length();i++)

{ if(ENODE[i]!='*')

{ outfu(10," ");

cout<<ENODE[i];

}

}outfu(10," ");

cout<<"#"<<endl;

int x;

for(i=0;i<NODE.length();i++)

{ outfu(4," ");

cout<<NODE[i];

outfu(5," ");

for(k=0;k<ENODE.length();k++)

{ flag=1;

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

{ if(NODE[i]==n[j].getlf()[0])

{ x=n[j].getselect().find(ENODE[k]);

if(x<n[j].getselect().length()&&x>-1)

{ cout<<"->"<<n[j].getrg();

yc[i][k]=n[j].getrg();

outfu(9-n[j].getrlen()," ");

flag=0;//

}

x=n[j].getselect().find('#'); if(k==ENODE.length()-1&&x<n[j].getselect().length()&&x>-1)

{ cout<<"->"<<n[j].getrg();

yc[i][j]=n[j].getrg();

}

if(flag&&ENODE[k]!='*')

outfu(11," ");

}

cout<<endl;

}

3. 函数说明

（1） void showStack(String st)显示分析栈中的内容，函数中定义了字符串数组来存放分析栈中的内容，栈中内容随着栈顶的弹出及栈顶替换、匹配发生改变变。

（2） boolean findString(String str,String array[]) 查找函数，用来判断输入的字符串是否有误，其中当前输入字符串为String 类型的str, String array[]中存放的是各个终结符，返回布尔值

（3） int location(String str,String array[]) 定位函数,指出字符串所在位置以便查找预测分析表，其中String str代表当前输入的字符，String array[]存放了出现在预测分析表中横向与纵向的字符即Vn或者Vt，当str等于array[i]时，返回i 值，否则报错。

（4） void error()出错处理函数，当输入的字符串不是该预测分析表所能得到的句子时，调用此函数显示输入串不可接受。

（5） void analyse(String Vn[],String Vt[],String M[][]) 分析函数，主要实现了符号串分析过程的显示，String Vn[]存放非终结符, String Vt[]存放终结符, String M[][]存放预测分析表中相应内容，

（6） showAnalyseTable(String Vn[],String Vt[],String M[][]) ，此方法通过循环将构造的预测分析表输出

（7） showMenu(String Vn[],String Vt[],String M[][]) ，此方法用来显示一些模拟菜单供用户使用。

（8） createAnalyseTable(String Vn[],String Vt[],String M[][]),此方法主要用来构造与测试分析表，其中还调用了showAnalyseTable(String Vn[],String Vt[],String M[][])等方法。

（9） main()主函数，主函数中通过调用其它函数如：void showMenu(String Vn[],String Vt[],String M[][])，实现程序的整体有机结合。

五．运行结果

1. 出错处理

在运行调试过程中碰到些问题，分析如下：

问题一：

就是将字符直接读入文法改成文本读入，

将字符界面输入文法的代码屏蔽删除

//cin>>left>>right;//非终结符产生式右部

cout<<"输入文件路径及文件名:";

修改如下：

cin>>filename;

ifstream file(filename,ios::in);

if(!file)

{ cerr<<"Open "<<filename<<" error!!"<<endl;

exit(1);

}

while(!file.eof())//逐行读入

{ for (int a=0;a<SUM;a++)

{ file.getline(temp0,sizeof(temp0));

int m=0;

int p=0;

for(int k=0;temp0[k]!='\0';k++)

{ c=temp0[k];

if(c==' '){continue;}

p++;

if((c>=97 && c<=122) || (c>=65&&c<=90) || (c>=48&&c<=57))

{temp[m]=c;

m++;}

else if(c=='*')

{ temp[m]=c;

m++;}

}

n[a].left=temp[0];n[a].left[1]='\0';

if(m>=2)

{ string tp="";

int q=0;

for(int z=1;temp0[z]!='\0';z++)

{ if(temp0[z]==' ')continue;

q++;

tp=tp+temp0[z];

}n[a].right=tp;

n[a].right[q]='\0';

}

if(m<2)

{ n[a].right=temp0[1];

n[a].right[1]='\0';

}

file.close();

问题二：

将命令行中提示的输入几个产生式数量去除，现实自动统计的产生式个数。具体实现就是单独使用几行代码就统计行数，实现代码如下

ifstream file1(filename,ios::in);

if(!file1)

{

cerr<<"Open "<<filename<<" error!!"<<endl;

exit(1);

}

while(!file1.eof())

{

file1.getline(temp0,sizeof(temp0));

SUM++; //逐行读取，统计SUM值，以便在后续程序的使用

}

问题三：

就是选题方面，我一直想自己选过一个自己比较感兴趣的题目，但一直没什么好的想法，后来想想，既然是做第一题First集和Follow集生成算法模拟，不如把LL（1）分析的全部完善下，改善老师提出的不足，这样对我来说也是一个很好的完善程序的机会，一直忙着考试，还没来得及改。

程序不足的方面：

是在实现文本输入时在字符提示下产生式可以输入任意的字符，比如数字1234，大于，小于号等等，是通过cin>>left>>right来实现，没什么限制，但在文本读入文法产生式时要对空格进行处理，这样的必须要进行过滤，就要对字符的输入进行限制，设置条件如下：

if((c>=97 && c<=122) || (c>=65&&c<=90) || (c>=48&&c<=57)){}

else if(c=='*'){}

可以看出删除了空格的同时也去除了其它符号，只能输入大小写字母，数字，及空代表符*，对其他如（、）、\、{、}等无法处理。

六、课程设计总结

通过这次学课设，我发现有很多东西，很多细节没注意，如经常漏；

大小写问题等很小的问题，真正自己动手做了才发现了自己的理论知识是如此的不扎实。有时候一个很小的问题卡一下就要处理很久，细节方面会带来很大的问题等等。我深刻体会到这给我带来的障碍。不过也因为通过这次的课程设计巩固了我的知识，查漏补缺，巩固我已有的知识，把那些遗忘掉的知识再重新学习一遍，使我学到很多，得到很多。

本课程设计的思路不难，但要不参考任何资料完全靠自己编确有不小的难度。在编程之前，我参考了他人的一个程序，在吸收其精华的基础上，自己做了些改进，最终将程序调出来了。

在这次课程设计当中，我感觉自己学到了很多东西，同时也发现了自己编程的不足之处。编程之前，我也参考了书中关于预测分析方法的描述研读了书中的例子。

通过这次课程设计，使我对LL（1）词法分析原理有了更透彻的了解，通过将理论付诸实践的过程中，不但对课本知识有了更深的理解，掌握，同时对编程能力也有很大的巩固，,希望为自己以后的学习打下基础，以便将来自己学得更好、做得更好。

七、参考文献

[1] 《MFC程序设计轻松入门》欧阳志宏董霖钟俊华人民邮电出版社

[2]《程序设计语言编译原理》陈火旺等. 国防工业出版社

[3] 《编译原理》吕映芝张素琴蒋维杜主编清华大学出版社

[4] 《编译原理及编译程序构造》高仲仪北京航天航空大学出版社

八、附录

核心算法（词法分析程序）的代码

publicstaticvoid analyse(String Vn[], String Vt[], String M[][]) // 句型分析函数

{

int i, m, p, q, len, t, step, j; // ,记录栈顶指针位置(s),记录产生式右部的长度(len),记录分析步骤数(step)

String a, A; // a用于记录剩余输入串的第一个元素,A记录分析栈的栈顶元素

String str = null; // 记录要分析的字符串

boolean flag1 = true, flag2 = true;

Scanner in = new Scanner(System.in);

OPT0: while (flag1) {

flag1 = false;

str = in.nextLine(); // 输入要分析的字符串，且以#结束

if (str == null || "".equals(str)) {

System.out.print("请输入要分析的字符串，且以#结束:");

flag1 = true;

continue OPT0;

}

for (i = 0; i < str.length(); i++) {

if (!findString(str.charAt(i) + "", Vt))

// 判断输入的字符串是否有误

{

System.out.println("输入字符串不是文法的句型!请重新输入!");

flag1 = true;

continue OPT0;

// 跳转向OPTO重新输入字符串

}

s = 0;

j = 0;

String st[] = new String[ConstantValue.MAXVN];

st[s] = "#";

st[++s] = Vn[0];

step = 1; // 步骤序号从1开始

a = str.charAt(0) + "";

System.out.println("步骤分析栈剩余输入串所用产生式或匹配");

// 显示符号串分析过程

OPT1: while (flag2) {

flag2 = false;

System.out.print(step + " ");

// 显示步骤

step++;

showStack(st); // 显示分析栈中内容

System.out.print(" ");

for (t = j; t < str.length(); t++) {

System.out.print(str.charAt(t));

// 显示剩余字符串

}

System.out.print(" ");

A = st[s--]; // 上托栈顶符号放入A

if (findString(A, Vt) && A.charAt(0) != '#')

// 假设A为终结符，但是不为#

{

if (A.charAt(0) == a.charAt(0))

// 分析栈的栈顶元素和剩余输入串的第一个元素相比较

{

System.out.println("'" + A + "' 匹配");

j++;

a = str.charAt(j) + "";

flag2 = true;

continue OPT1;

}

else

error();

}

elseif (findString(A, Vt) && A.charAt(0) == '#')

{

if (A.charAt(0) == a.charAt(0))

System.out.println("接受!");

else

error();

}

else // 当A 属于Vn，则以A及a组成的符号对(A，a)查分析表M。

{

p = location(A, Vn); // 调用前面的定位函数，指出字符所在位置

q = location(a, Vt);

String S1 = "NULL", S2 = "null";

if (M[p][q].equals(S1) || M[p][q].equals(S2)) // 查找二维数组中的产生式

error();

else {

String str1 = M[p][q];

System.out.println(A+ "->" + str1);// 显示对应的产生式

if (str1.equals("&"))

{

flag2 = true;

continue OPT1;

}

else

{

len = str1.length(); // 产生式逆序进栈

for (m = len - 1; m >= 0; m--) {

if("'".equals(str1.charAt(m)+""))

{

m--;

st[++s]=str1.charAt(m)+"'";

}

else

st[++s]=str1.charAt(m)+"";

}

flag2 = true;

continue OPT1;

}

} }

更多相关推荐：

编译原理课程设计报告: 南京航空航天大学编译原理课程设计题目一个PASCAL语言子集PL0编译器的设计与实现专业班号学号姓名指导老师答辩日期20xx年1月1设计的题目一个PASCAL语言子集PL0编译器的设计与实现2课程设计的要求PL...
编译原理课程设计报告编译器: 软件工程0801班和春辰U20xx18016编译技术课程设计编译技术课程设计实验报告实验名称编译器程序说明下载请好评姓名向难学号20xx12110106班级计算机系08本一班20xx年11月12日目录一二三四五...
编译原理课程设计报告: 编译原理课程设计报告实验1用Lex设计词法分析器1实验目的学会用lex设计一个词法分析器实验内容使用lex为下述文法语言写一个词法分析器实验要求输入为用该语言所写的源程序文件输出为记号序列每个记号显示为二元组记...
编译原理课设报告: 北华航天工业学院编译原理课程设计课程设计题目编译程序构造作者所在系部计算机科学与工程系作者所在专业计算机科学与技术作者所在班级作者学号作者姓名指导教师姓名完成时间20xx年6月18日课程设计任务书摘要编译原理是...
广工20xx编译原理课程设计报告: 课程设计课程名称编译原理题目名称PL0编译器的扩充学生学院计算机学院专业班级计算机科学与技术124学号31120xx901学生姓名柏石先指导教师李杨20xx年12月28日一实验目的与要求基本内容成绩范围中及格或...
编译原理课程设计报告: 20xx20xx学年第二学期编译原理课程设计报告学院班级学生姓名成绩指导教师学号时间20xx年5月目录一课程设计的目的1二课堂实验及课程设计的内容121课堂实验内容122课程设计内容1三visualstudio...
编译原理课程设计报告: 编译原理课程设计编译原理课程设计报告学院系班级电子信息与电气工程学院计算机系F0603034徐晓峰学号张冬茉5060309852学生姓名指导教师版本信息日期20xx1237版本10作者徐晓峰1编译原理课程设计一...

编译原理课程设计报告 (语法分析): 河海大学物联网工程学院常州课程设计报告题目编译原理课程设计授课班号专业学生姓名学号指导教师目录一课程设计概要1二语法分析设计思想1地位及作用1设计思路1分析方法1使用文法1First集合和Follow集合1构造...
编译原理课程设计报告-预测分析程序的设计: 课程设计任务书学生姓名专业班级指导教师工作单位题目预测分析程序的设计初始条件程序设计语言主要使用C语言的开发工具或者采用LEXYACC等工具也可利用其他熟悉的开发工具算法可以根据编译原理课程所讲授的算法进行设计...
编译原理课程设计报告: 编译原理课程设计报告课题名称C语言扫描器和分析器提交文档学生姓名提交文档学生学号同组成员名单指导教师姓名指导教师评阅成绩指导教师评阅意见提交报告时间20xx年6月15日1课程设计目标11实用性分析系统基本上实现...
编译原理课程设计报告: 编译原理课程设计报告姓姓名刘畅120xx60221姓名袁青伟120xx60222姓名张文120xx60223班级软件121班专业软件工程指导教师陈晓明时间20xx614项目名称算术表达式的语法及语义分析贵州大学...
编译原理课程设计报告: 编译原理课程设计报告姓名学号班级专业指导教师时间项目名称贵州大学计算机科学与信息学院1目录一课程设计目的2二课程设计题目描述和要求21选定的题目22课程设计要求描述23实现的功能描述24分析器的使用描述3三课程...

热门关注