实验二LL1分析法实验报告.docx

实验二LL1分析法实验报告.docx

《实验二LL1分析法实验报告.docx》由会员分享，可在线阅读，更多相关《实验二LL1分析法实验报告.docx（16页珍藏版）》请在冰点文库上搜索。

实验二LL1分析法实验报告

实验二LL

（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）,总控程序每次都执行下述

三种可能的动作之一：

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

（2）若X=a‘#'，则把＜从STACK栈顶弹出，让a指向下一个输入

符号。

（3）若X是一个非终结符，则查看预测分析表M。

若M[A,a]中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为£,则不推什么东西进STACK栈）。

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

三、程序结构描述

1、定义的变量

初始化预测分析表：

LLE[8]={"TG","TG","error","error","error","error","error","error"};

LLG[8]={"error","error","null","+TG","-TG","error","error","null"};

LLT[8]={"FS","FS","error","error","error","error","error","error"};

LLS[8]={"error","error","null","null","null","*FS","/FS","null"};

LLF[8]={"i","（i）","error","error","error","error","error","error"};

constintMaxLen=10;初始化栈的长度constintLength=10;初始化数组长度charVn[5]={'E','G','T','S','F'};非终结符数组charVt[8]={'i','（','）','+','-','*','/','#'};终结符数组charch,X;/全局变量，ch用于读当前字符，X用于获取栈顶元素charstrToken[Length];存储规约表达式

2、定义的函数

classstack栈的构造及初始化

intlength（char*c）输出字符数组的长度

voidprint（inti,char*c）剩余输入串的输出

voidrun（）分析程序

3、LL

（1）预测分析程序流程图

』和〈程序〉入

取一«入看号曲1,

r取弋入符^

•岀桂頂苻号能人*

ll（i）ss（分折趕序流程

四、程序源代码及运行结果

#include

usingnamespacestd;

constintMaxLen=10;//

初始化栈的长度

constintLength=10;//初始化数组长度

charVn[5]={'E','G','T','S','F'};//非终结符数组

charVt[8]={'i','（','）','+','-','*','/','#'};//终结符数组

charch,X;//全局变量，ch用于读当前字符，X用于获取栈顶元素

charstrToken[Length];//存储规约表达式

structLL//ll

（1）分析表的构造字初始化

{

char*c;

};

LLE[8]={"TG","TG","error","error","error","error","error","error"};

LLG[8]={"error","error","null","+TG","-TG","error","error","null"};

LLT[8]={"FS","FS","error","error","error","error","error","error"};

LLS[8]={"error","error","null","null","null","*FS","/FS","null"};

LLF[8]={"i","（i）","error","error","error","error","error","error"};

classstack//栈的构造及初始化

{

public:

stack（）;//初始化

boolempty（）const;//是否为空

boolfull（）const;//是否已满

boolget_top（char&c）const;//取栈顶元素

boolpush（constcharc）;//入栈

boolpop（）;//删除栈顶元素

voidout（）;//输出栈中元素

~stack（）{}//析构

private:

intcount;//栈长度

chardata[MaxLen];//栈中元素

};

stack:

:

stack（）

{

count=0;

}

boolstack:

:

empty（）const

{

if（count==0）

returntrue;

returnfalse;

}

boolstack:

:

full（）const

{

if（count==MaxLen）

returntrue;

returnfalse;

}

boolstack:

:

get_top（char&c）const

{

if（empty（））

returnfalse;

else

{

c=data[count-1];

returntrue;

}

}

boolstack:

:

push（constcharc）

{

if（full（））

returnfalse;

data[count++]=c;

returntrue;

}

boolstack:

:

pop（）

if（empty（））

returnfalse;

count--;

returntrue;

}

voidstack:

:

out（）

{

for（inti=0;i

cout<

cout<<"";

}

intlength（char*c）

{

intl=0;

for（inti=0;c[i]!

='\0';i++）

l++;

returnl;

}

voidprint（inti,char*c）//剩余输入串的输出

{

for（intj=i;j

cout<

cout<<"";

voidrun（）

{

boolflag=true;//循环条件

intstep=0,point=0;//步骤、指针

intlen;//长度

cout<<"请输入要规约的字符串：

"<

cin>>strToken;

ch=strToken[point++];//读取第一个字符

stacks;

s.push（'#'）;//栈中数据初始化

s.push（'E'）;

s.get_top（X）;//取栈顶元素

cout<<"步骤"<<"分析栈"<<"剩余输入串"<<"所用产生

式"<<"动作"<

cout<

s.out（）;

print（point-1,strToken）;

cout<<""<<"初始化"<

while（flag）if（（X==Vt[0]）||（X==Vt[1]）||（X==Vt[2]）||（X==Vt[3]）||（X==Vt[4]）||（X==Vt

[5]）||（X==Vt[6]））//判断是否为终结符（不包括#）

{

if（X==ch）//终结符,识别，进行下一字符规约

{

s.pop（）;

s.get_top（X）;

ch=strToken[point++];

cout<

s.out（）;

print（point-1,strToken）;

cout<<""<<"GETNEXT（I）"<

}

else

{

flag=false;

cout<<"error!

"<

}

}

elseif（X=='#'）//规约结束

if（X==ch）

cout<

s.out（）;

print（point-1,strToken）;

cout<<""<"<

s.pop（）;

flag=false;

}

else

{

flag=false;

cout<<"error!

"<

}

}

elseif（X==Vn[0]）//非终结符E

{

for（inti=0;i<8;i++）//查分析表

if（ch==Vt[i]）

{

if（strcmp（E[i].c,"error"）==0）//出错

{

flag=false;

}

else{//对形如X->X1X2的产生式进行入栈操

作

s.pop（）;

len=length（E[i].c）-1;

for（intj=len;j>=0;j--）

s.push（E[i].c[j]）;

cout<

s.out（）;

print（point-1,strToken）;

cout<"<

for（intz=len;z>=0;z--）

cout<

cout<<"）"<

s.get_top（X）;

}

}

}

elseif（X==Vn[1]）//同上，处理G

for（inti=0;i<8;i++）if（ch==Vt[i]）

{

if（strcmp（G[i].c,"null"）==0）

{

s.pop（）;

cout<

s.out（）;

print（point-1,strToken）;

"<<"POP"<

coutvv""<"<<"£"<<"

s.get_top（X）;

}

elseif（strcmp（G[i].c,"error"）==0）

{

flag=false;

cout<<"error"<

}

else{

s.pop（）;

len=length（G[i].c）-1;

for（intj=len;j>=0;j--）

s.push（G[i].c[j]）;

s.out（）;print（point-1,strToken）;

"<<"POP,PUSH（";

cout<"<=0;z--）cout<

}

}

}

elseif（X==Vn[2]）//同上处理T

{

for（inti=0;i<8;i++）

if（ch==Vt[i]）

{

if（strcmp（T[i].c,"error"）==0）

{

flag=false;

cout<<"error"<

}

else{

s.pop（）;

for（intj=len;j>=0;j--）

s.push（T[i].c[j]）;cout<

"<<"POP,PUSH（";

print（point-1,strToken）;cout<"<=0;z--）cout<

}

}

}

elseif（X==Vn[3]）//同上处理S

{

for（inti=0;i<8;i++）

if（ch==Vt[i]）

{if（strcmp（S[i].c,"null"）==0）

{

s.pop（）;

s.out（）;

print（point-1,strToken）;

coutvv""<"<<"£"<<"

s.get_top（X）;

}

elseif（strcmp（S[i].c,"error"）==0）

{

flag=false;

cout<<"error"<

}

else{

s.pop（）;

len=length（S[i].c）-1;

for（intj=len;j>=0;j--）

s.push（S[i].c[j]）;

cout<

s.out（）;print（point-1,strToken）;

cout<"<

"<<"POP"<

"<<"POP,PUSH（";

for（intz=len;z>=0;z--）cout<

s.get_top（X）;

}

}

}

elseif（X==Vn[4]）//同上处理F

{

for（inti=0;i<7;i++）

if（ch==Vt[i]）

{

if（strcmp（F[i].c,"error"）==0）

{

flag=false;cout<<"error"<

}

else{

s.pop（）;

len=length（F[i].c）-1;

for（intj=len;j>=0;j--）

s.push（F[i].c[j]）;

cout<

s.out（）;

print（point-1,strToken）;

"<<"POP,PUSH（";

cout<"<

for（intz=len;z>=0;z--）cout<

}

}

}

else//出错处理

{

flag=false;

cout<<"error"<

}

}

}

intmain（）

{

run（）;

system（"pause"）;

return0;

}

测试：

输入i*i+i#

结果:

请输入要规约的字符串:

分析栈

剌余输人串

所用产生式

刑

ttE

初始化i

ttGT

E->TG

POP,PUSH

ItGSF

i*i+ifl

I->FS

POP,FUSH

UGSL

F->i

POP,PUSH（1>

ttCS

GETNEXTCn

ItGSP*

S->*FS

POP,PUSH<£F*>

ttGEP

i+itt

QETNEMKn

ttGSl

i+iit

F->i

POPrPUSHCi>

«GS

+i#

GETNEXT<1>

ItG

+ilt

S->£

POP

10

#GT+

+i#

C->+TG

POP,PUGH

11

#GT

itt

GETNEXT

丄2

lit

T->FS

POP,PUSH（SF>

13

#G£i

itt

F->i

POP,PUSH

14

GETMEXT<1>

15

»G

S->£

POP

16

tt

tt

G->2

POP

17

tt

tt

#->tt

结束

按任意键维纹-

五、实验总结

1.本实例能利用正确的LL1文法分析表判断任意符号串是否属于该文法的句子；显示了具体分析过程；支持打开、新建、保存分析表；保存分析结果。

2.吸取了上次程序设计的经验教训，优化了代码整洁性，提高了程序设计效率，尽可能细化函数功能，便于移植、错误查找和修改