实验4 LRk分析器.docx
- 文档编号:2016583
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:12
- 大小:224.17KB
实验4 LRk分析器.docx
《实验4 LRk分析器.docx》由会员分享,可在线阅读,更多相关《实验4 LRk分析器.docx(12页珍藏版)》请在冰点文库上搜索。
实验4LRk分析器
实验四LR(k)分析器设计
一、实验目的
(1)掌握下推机这一数学模型的结构和理论,并深刻理解下推自动机在LR分析法中的应用(即LR分析器)。
(2)掌握LR分析法的思想,学会特定分析表的构造方法,利用给出的分析表进行LR分析。
二、实验内容
根据课堂讲授的形式化算法,编制程序实现对以下语法进行自底向上语法分析的LR分析器,设计分析表,对给出的输入语句进行语法分析,判断是否符合相应的文法要求。
Programblock
block{stmts}
stmtsstmtstmts|
stmtid=E;|while(bool)stmt|block
boolE<=E|E>=E
EE+T|T
Tid|num
输入语句:
三、实验要求
要求实现以下功能:
a)设计分析表和语句的输入;
b)要实现通用的LR分析思想的源代码;
c)输出对语句的语法分析判断结果,如果可能给出错误的信息提示。
四、实现方法
根据课本的LR分析器模型和LR分析算法,完成LR分析。
对要求中的错误信息提示,指的是对应分析表中的空白处,每一个空白的地方都应该有对应的错误情况,因而有相应的错误信息。
注意这里的语法分析,是在词法分析的基础上进行的。
五、识别活前缀的DFA
六、SLR
(1)分析表
1Program->block
2Block->{stmts}
3Stmts->stmtstmts
4Stmts->eps
5Stmt->id=E;
6Stmt->while(bool)stmt
7Stmt->block
8Bool->E<=E
9Bool->E>=E
10E->E+T
11E->T
12T->id
13T->num
FOLLOW(program)={‘#’}
FOLLOW(block)={‘#’,‘}’,‘id’,‘while’,‘{’}
FOLLOW(stmts)={‘}’}
FOLLOW(stmt)={‘}’,‘id’,‘while’,‘{’}
FOLLOW(bool)={‘)’}
FOLLOW(E)={‘<=’,‘>=’,‘+’,‘;’,‘)’}
FOLLOW(T)={‘<=’,‘>=’,‘+’,‘;’,‘)’}
七、主要代码
#ifndefLRANALYZER_H
#defineLRANALYZER_H
#include
#include
#include
#include
#include"Automation.h"
classLRAnalyzer:
publicQObject
{
Q_OBJECT
public:
explicitLRAnalyzer(QObject*parent=0);
boolbegin(QString,QTableWidget*);
boolloadTable(QString);
private:
Automation*lex;
QStringtable[30][30];
QMap
QMap
intderiveArg[30];
intderiveLeft[30];
};
#endif//LRANALYZER_H
#include"LRAnalyzer.h"
LRAnalyzer:
:
LRAnalyzer(QObject*parent):
QObject(parent)
{
lex=newAutomation;
lex->addKeyword("while");//2000
lex->addToken("+");//1000
lex->addToken("=");//1001
lex->addToken("<=");//1002
lex->addToken(">=");//1003
lex->addToken("{");//1004
lex->addToken("}");//1005
lex->addToken("(");//1006
lex->addToken(")");//1007
lex->addToken(";");//1008
lex->addToken("#");//1009
trans.insert(1004,0);trans2.insert(1004,"{");
trans.insert(1005,1);trans2.insert(1005,"}");
trans.insert(1006,2);trans2.insert(1006,"(");
trans.insert(1007,3);trans2.insert(1007,")");
trans.insert(1000,4);trans2.insert(1000,"+");
trans.insert(1001,5);trans2.insert(1001,"=");
trans.insert(1002,6);trans2.insert(1002,"<=");
trans.insert(1003,7);trans2.insert(1003,">=");
trans.insert(1008,8);trans2.insert(1008,";");
trans.insert(3000,9);trans2.insert(3000,"id");
trans.insert(3001,10);trans2.insert(3001,"num");
trans.insert(2000,11);trans2.insert(2000,"while");
trans.insert(1009,12);trans2.insert(1009,"#");
trans.insert(4001,13);trans2.insert(4001,"block");//block
trans.insert(4002,14);trans2.insert(4002,"stmts");//stmts
trans.insert(4003,15);trans2.insert(4003,"stmt");//stmt
trans.insert(4004,16);trans2.insert(4004,"bool");//bool
trans.insert(4005,17);trans2.insert(4005,"E");//E
trans.insert(4006,18);trans2.insert(4006,"T");//T
/*
1Program->block
2Block->{stmts}
3Stmts->stmtstmts
4Stmts->eps
5Stmt->id=E;
6Stmt->while(bool)stmt
7Stmt->block
8Bool->E<=E
9Bool->E>=E
10E->E+T
11E->T
12T->id
13T->num
*/
deriveArg[1]=1;deriveArg[2]=3;
deriveArg[3]=2;deriveArg[4]=0;
deriveArg[5]=4;deriveArg[6]=5;
deriveArg[7]=1;deriveArg[8]=3;
deriveArg[9]=3;deriveArg[10]=3;
deriveArg[11]=1;deriveArg[12]=1;
deriveArg[13]=1;
deriveLeft[2]=4001;deriveLeft[3]=4002;
deriveLeft[4]=4002;deriveLeft[5]=4003;
deriveLeft[6]=4003;deriveLeft[7]=4003;
deriveLeft[8]=4004;deriveLeft[9]=4004;
deriveLeft[10]=4005;deriveLeft[11]=4005;
deriveLeft[12]=4006;deriveLeft[13]=4006;
}
boolLRAnalyzer:
:
loadTable(QStringfilePath)
{
if(!
freopen(filePath.toLatin1(),"r",stdin))
returnfalse;
charbuf[256];
intline=0;
while(gets(buf))
{
intpos=0,cnt=0;
while(buf[pos])
{
if(buf[pos]=='\t')
cnt++,pos++;
else
{
while(buf[pos]!
='\t'&&buf[pos]!
='\0')
table[line][cnt].append(buf[pos++]);
}
}
line++;
}
returntrue;
}
boolLRAnalyzer:
:
begin(QStringsrc,QTableWidget*w)
{
src.append("#");
lex->begin(src);
MatchResultrlt;
QStack
QStack
state.push(0);
optr.push(1009);
while(rlt=lex->match(),rlt.type!
=0)
{
analyze:
QStrings=table[state.top()][trans[rlt.type]];
w->setRowCount(w->rowCount()+1);
w->setItem(w->rowCount()-1,0,newQTableWidgetItem(QString("%1").arg(w->rowCount())));
QStringtemp;
for(QStack
:
iteratorit=state.begin();it!
=state.end();it++)
temp.append(QString("%1").arg(*it));
w->setItem(w->rowCount()-1,1,newQTableWidgetItem(temp));
temp.clear();
for(QStack
:
iteratorit=optr.begin();it!
=optr.end();it++)
temp.append(QString("%1").arg(trans2[*it]));
w->setItem(w->rowCount()-1,2,newQTableWidgetItem(temp));
if(rlt.type!
=-1)
w->setItem(w->rowCount()-1,3,
newQTableWidgetItem(rlt.str+src.mid(rlt.line).replace(QRegExp("[\\n\\r\\s\\t]"),QString:
:
null)));
else
{
w->setItem(w->rowCount()-1,3,newQTableWidgetItem("LexicalAnalyzeError"));
returnfalse;
}
if(s.isEmpty())
{
//qDebug()<<"Error";
w->setItem(w->rowCount()-1,4,newQTableWidgetItem("Error"));
returnfalse;
}
elseif(s[0]=='S')
{
state.push(s.mid
(1).toInt());
optr.push(rlt.type);
w->setItem(w->rowCount()-1,4,newQTableWidgetItem(s));
//qDebug()<<"shift";
}
else
{
w->setItem(w->rowCount()-1,4,newQTableWidgetItem(s));
if(s=="acc")
break;
intr=s.mid
(1).toInt();
for(inti=0;i optr.pop(),state.pop(); optr.push(deriveLeft[r]); //qDebug()<<"Reduce"; state.push(table[state.top()][trans[optr.top()]].toInt()); //qDebug()<<"Goto"; gotoanalyze; } } returntrue; } 八、运行截图 九、实验总结与体会 在词法分析的基础上,实现了一个SLR (1)分析器,可以对给定的文法进行LR分析,并输出分析过程。 SLR (1)分析表通过文件加载。 分析过程中遇到错误可以及时终止分析过程,防止低效处理。 通过本实验,我熟悉了SLR (1)分析表的构造方法,深刻理解了LR分析的过程。 这个SLR (1)分析表比较复杂,构造的时候出现了很多错误,导致程序无法正确分析。 针对出错的地方,我对照程序的输出以及DFA,找到了分析表中填写错误的项目,反复调试修改,完成了这个分析器。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验4 LRk分析器 实验 LRk 分析器