LR(1)实验报告(附代码)Word格式.doc
《LR(1)实验报告(附代码)Word格式.doc》由会员分享，可在线阅读，更多相关《LR(1)实验报告(附代码)Word格式.doc（14页珍藏版）》请在冰点文库上搜索。
r6:
F→i归约,GOTO（0,F）=3入栈
3
03
#F
r4:
T→F归约,GOTO（0,T）=3入栈
02
#T
r2:
E→T归约,GOTO（0,E）=1入栈
5
01
#E
ACTION[1,+]=S6,状态6入栈
6
016
#E+
i*i#
ACTION[6,i]=S5,状态5入栈
7
0165
#E+i
*i#
F→i归约,GOTO（6,F）=3入栈
8
0163
#E+F
T→F归约,GOTO（6,T）=9入栈
9
0169
#E+T
ACTION[9,*]=S7,状态7入栈
10
01697
#E+T*
i#
ACTION[7,i]=S5,状态5入栈
11
016975
#E+T*i
F→i归约,GOTO（7,F）=10入栈
12
0169710
#E+T*F
r3:
T→T*F归约,GOTO（6,T）=9入栈
13
r1:
E→E+T,GOTO（0,E）=1入栈
14
Acc：
分析成功
实验报告正文的内容：
u描述LR
（1）语法分析程序的设计思想:
u定义项目的一般形式是[A→a·
b,a1a2…ak]，这样的一个项目称为一个LR（k）项目。
项目中的a1a2…ak称为它的向前搜索符串（或展望串），令K=1,即为LR
（1）语法分析程序。
在此，重新定义CLOSURE（I）的算法：
项目集I的闭包CLOSURE（I）构造方法：
1.I的任何项目都属于CLOSURE（I）。
2.若项目[A→a·
Bb,a]属于CLOSURE（I），B→x是一个产生式，那么，对于FIRST（ba）中的每个终结符b，如果[B→·
x,b]原来不在CLOSURE（I）中，则把它加进去。
3.重复执行步骤2，直至CLOSURE（I）不再增大为止。
GO（）的算法保持与LR语法分析程序一样，通过以下方法构造文法分析表：
动作ACTION和状态转换GOTO构造如下：
1.若项目[A→a·
ab,b]属于Ik且GO（Ik,a）＝Ij，a为终结符，则置ACTION[k,a]为“sj”。
，a]属于Ik，则置ACTION[k,a]为“rj”；
其中假定A→a为文法G¢
的第j个产生式。
3.若项目[S¢
→S·
#]属于Ik，则置ACTION[k,#]为“acc”。
4.若GO（Ik，A）＝Ij，则置GOTO[k,A]=j。
5.分析表中凡不能用规则1至4填入信息的空白栏均填上“出错标志”。
当具体面对输入串时，通过查表进行分析该进行何种动作。
u程序结构描述：
函数调用格式、参数含义、返回值描述、函数功能均在程序源代码出注释出来，在此不再赘述，详细含义请参照源代码cpp文件。
u详细的算法描述（程序执行流程图）:
（1）总控程序，也可以称为驱动程序。
对所有的LR分析器总控程序都是相同的。
（2）分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。
（3）分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。
分析器的动作就是由栈顶状态和当前输入符号所决定。
uLR分析器由三个部分组成：
u其中:
SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。
状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。
uACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行。
动作有四种可能：
（1）移进：
action[i，a]=Sj：
状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。
（2）归约：
action[i，a]=rk：
当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A-B的产生式，若B的长度为R（即|B|=R），则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。
（3）接受acc:
当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'
#'
，则为分析成功。
（4）报错:
当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。
四、实验要求
本程序原本的设计思想与实验二相仿，但由于此种设计思想会导致程序灵活性大大降低，故对设计思想进行优化，在此，不在对原程序设计思想进行阐述，仅对改良后的程序设计思想进行阐述。
该文法的LR
（1）分析表：
算术表达式文法的LR分析表
状
态
ACTION
GOTO
i
+
*
（
）
E
T
F
S5
S4
S6
acc
r2
S7
r4
r6
S11
r1
r3
r5
本程序根据给出的LR
（1）文法分析表，构造string类的action[12][6]={"
S5"
"
0"
S4"
//ACTION表
"
S6"
acc"
r2"
S7"
r4"
r6"
S11"
r1"
r3"
r5"
};
int类的gotoarr[12][3]=
{1,2,3,//GOTO表
0,0,0,
8,2,3,
0,9,3,
0,0,10,
0,0,0}，用以记录LR
（1）分析表的内容。
定义终结符集vt[]，非终结符集vn[],产生式集合Production[],状态栈status,用int类的数组Status记录栈的内容，符号栈Stack，用string类的stacktd记录栈的内容，定义移进函数Shift（）,Goto函数Goto（）,归约函数Reduction（）,具体的分析函数Analyse（），对于给定的字符串，读取状态栈的栈顶元素及字符串当前的首字母，先通过函数Judge判断符号栈栈顶元素是否在文法终结符集中，若不在，则输出Error，结束程序，若在其中，则返回字符串首字母在终结符vt[]的下表，再通过查action表，执行相对应的操作，执行移进函数Shift（）或归约函数Reduction（），同时若执行归约操作，再通过查找Goto表判断应转到的状态，执行相应的Goto函数Goto（），重复进行以上步骤，直至分析执行至输出acc或Error，程序结束。
u给出软件的测试方法和测试结果：
根据程序的提示，输入一由该文法的终结符组成的字符串，程序即会进行分析，具体的测试实例如下：
正确的输入：
错误的输入：
u实验总结（设计的特点、不足、收获与体会）：
本程序摒弃了原设计思想，改使用构造action[]及Goto[]表来存储LR
（1）分析表的内容,对于不同的产生式，只需修改其对应的action表，Goto表，终结符及非终结符表即可，大大提高了程序分析的灵活性，但由于时间有限，测试实例不足，程序可能存在未知错误，在此需进一步改善，通过本次实验，进一步加深了对于LR
（1）分析法的理解与应用，同时关于本次实验，有几点深刻的体会：
程序的设计思想是程序的灵魂，在程序编写之前，一定要仔细阅读实验要求，正确理解实验要求，并综合考虑程序的算法优化，灵活性等诸多方面，作出正确的设计思想。
程序的实际编写工作是一门细致的工作，编写过程中一定要认真仔细，因为程序中的一个小错误可能会引起一连串的错误，同时编写时务必详细仔细，避免程序的逻辑错误，因为程序的逻辑错误调试是们十分复杂耗时的工作，对于程序编写中的一个小的逻辑错误，需要耗费大量时间调试，而本实验在编写完成后，即消耗接近两天的时间进行调试，所以程序的编写务求认真、仔细、准确。
PS:
实验源代码请参照cpp文件。
#include<
iostream>
stack>
string>
usingnamespacestd;
stringaction[12][6]={"
"
"
intgotoarr[12][3]={1,2,3,//GOTO表
0,0,0,
0,0,0,
8,2,3,
0,9,3,
0,0,10,
0,0,0};
charvt[6]={'
i'
'
+'
*'
（'
）'
//存放终结符
charvn[3]={'
E'
T'
F'
//存放非终结符
stringProduction[6]={"
E->
E+T"
T"
T->
T*F"
F"
F->
（E）"
i"
//产生式集合
intcount=0;
//记录当前进行处理的输入字符串字符位置
intline=1;
//记录处理的步骤数
boolflag=false;
intStatusNumber=1;
//栈中状态数
stringstacktd="
#"
;
//记录符号栈中内容
intStatus[50]={0};
//记录状态栈
stack<
char>
Stack;
//创建一个符号栈
int>
status;
//创建一个状态栈
voidJudge（int&
i,intj,chararr[],charch,strings）{//判断输入串是否由文法终结符组成
flag=false;
for（intl=0;
l<
j;
l++）{
if（ch==arr[l]）{
flag=true;
i=l;
break;
}
}
if（flag==false）{
cout<
<
\tError"
endl;
count=s.size（）;
}
voidOutputstatus（）{//输出状态集
for（inti=0;
i<
StatusNumber;
i++）
Status[i];
voidOutputstring（strings）{//输出未处理的字符串
for（inti=count;
s.size（）;
s.at（i）;
voidOutput（strings）{//输出步骤、状态集、符号集、输入串
cout<
line<
\t"
Outputstatus（）;
stacktd<
Outputstring（s）;
\t\t"
line++;
voidShift（inti,strings）{//移进函数S
Output（s）;
cout<
ACTION["
status.top（）<
s.at（count）<
]=S"
状态"
入栈"
status.push（i）;
//将状态i压进状态栈
Status[StatusNumber]=i;
//Status记录状态栈的内容
Stack.push（s.at（count））;
//将当前面临的输入串符号压进符号栈
stacktd=stacktd+s.at（count）;
//stacktd记录符号栈的内容
count++;
//当前面临的输入串字符往后移一位
StatusNumber++;
//状态数加一
voidGoto（stack<
st1,stack<
st2,strings）{//GoTo语句
intj=-1;
intch1=st1.top（）;
charch2=st2.top（）;
Judge（j,3,vn,ch2,s）;
//求得ch2在非终结符表中的位置
if（gotoarr[ch1][j]==0）{
count=s.size（）;
else{
status.push（gotoarr[ch1][j]）;
//新状态进栈
Status[StatusNumber]=gotoarr[ch1][j];
StatusNumber++;
}
voidReduction（inti,strings）{//归约函数R
Output（s）;
cout<
r"
:
Production[i-1]<
归约，GoTo（"
intN=Production[i-1].length（）-3;
for（intj=0;
j<
N;
j++）{//消除要归约的状态及符号
status.pop（）;
Stack.pop（）;
StatusNumber--;
stacktd.erase（stacktd.length（）-1）;
Production[i-1].at（0）<
）="
Stack.push（Production[i-1].at（0））;
//符号进栈
stacktd=stacktd+Stack.top（）;
Goto（status,Stack,s）;
Status[StatusNumber]=status.top（）;
voidAnalyse（strings）{//具体分析函数
Stack.push（'
）;
//初始化
status.push（0）;
s=s+"
intt=-1;
//记录ch在数组vt的位置
while（count<
s.size（））{
inti=status.top（）;
charch=s.at（count）;
Judge（t,6,vt,ch,s）;
if（flag==true）{
if（action[i][t]!
="
&
action[i][t]!
）{
if（action[i][t].at（0）=='
S'
action[i][t].erase（0,1）;
//删除action[i][t]的首字母S
Shift（atoi（action[i][t].c_str（））,s）;
//atoi（action[i][t].c_str（）），将action[i][t]转换为整型
action[i][t].insert（0,"
S"
//将S添加回action[i][t]
}
elseif（action[i][t].at（0）=='
r'
//删除action[i][t]的首字母r
Reduction（atoi（action[i][t].c_str（））,s）;
//atoi（action[i][t].c_str（）），将action[i][t]转换为整型
//将r添加回action[i][t]
}
elseif（action[i][t]=="
cout<
Output（s）;
cout<
\t分析成功"
break;
}
elseif（flag==false）
intmain（）{
strings;
************************LR
（1）分析*************************"
本分析文法产生式为"
6;
j++）
Production[j]<
charT;
do{
输入字符串"
cin>
>
s;
//输入要分析的字符串
************************现进行如下分析*************************"
步骤"
状态栈"
符号栈"
剩余输入串"
动作说明"
Analyse（s）;
count=0;
line=1;
stacktd="
StatusNumber=1;
while（!
Stack.empty（））{
Stack.pop（）;
while（!
status.empty（））{
status.pop（）;
是否继续分析,Y或y继续"
T;
}while（T=='
y'
||T=='
Y'
return0;
升级会员 