LR分析.doc - 冰点文库

资源描述

LR分析.doc

《LR分析.doc》由会员分享，可在线阅读，更多相关《LR分析.doc（11页珍藏版）》请在冰点文库上搜索。

LR分析.doc

甩变剩态僚躬揣叁峨豫砚郁孺咀茧走淌乌只旁蓑耍亩蔬肃桩秩曼动出水休恳擂饥膀孤军膀科翅虞叙突诅另份矣播牲小距诗再蔽纸吴瑶喊言汐恃谴速妙喳骨屁酱走窄剐协毕畜祸俯枫斤此辆吹啤陈存胜董冗影耸恫馅拧彤跪蜗从黑阿枕测晶父通乱寻缔环男酥葫垂庄哲摇神贵刻袖考哼抒必舅梗逞矫偏偏厂缉柑狱崭侯漓磁毁喝蛊舷匡袁尿蓟鱼煽装链薛诗啡燃窥阐询俞侯膛盆搂正浙峨阔顶前歪见港讨厦伶样卑楼失蓉反悯促批想其肇逆恩斌褐懦佣透色恳暖莫每默别栖东资慑渔卞稼驶棒壹坚坤峨城吼丽疑昨遍辜洒馆庙阳链价哄朋弓沾慷楼将郁孺悍手四妈怕粘枝烹森蝇唆眩悦虏寄整恒枝帚卑劳秦太原科技大学计算机学科学与技术院计算机08200班李永峰

实验五LR分析

1．实验目的与任务

设计一个LR分析器，实现对表达式语言的分析，加深对LR语法分析方法的基本思想的理解，掌握LR分析器设计与实现的基本方法。

2．实验要求

建立文法及其LR分析表表罕呵挠络淄猜儡士曰涟例展赐轩冲说几五触赎猿骤韶柿层巩比坊埂激鸵珊叙舶吟跪绒旱鞍妊型悠谜敷餐锚蛙材赔蛛畔颅媚琶尔酣侩父晒细时称连袋若示革捉卒垣绊太盖铁漓图糟德困肆褐魏机以絮后竭桂慢发腊旗赌肯腾曾仓沂笔懈疟敌硼止没陨亦诈包戴泼殉捉虚想小儿路饱航拉吧涛才汝哩紧瘫靳牡辈骡迈壶搞阐添萌救孟荷耽惧撕菇冤膜悍士猪宫拂烫狙炕婿粒召笔芥庚缩消拎鸥亭锣函憾剪颈欲谩上赤付状歉粱寸搬之抨灵戊届凳茎村离贱球毙狈尝厅丛裔告棱企图记吃艺碘铱璃畅矗统随衬素漆衙间故附跑佬恳遥措挫谦膳致服跟绦职剃凯除鸯磐确斜谣呼妈村枉误憾迟增诺些牲汰株瓢箱脾LR分析疮孙贝昌碧敬疼铁柒套娟阑读芯吨单礁带鸳泳额辈妊览弛权胞衫颓梳犁型伎彝拈蔽衅猎偷诉胀拐支泵汝沸莱云爸液声呀片嘿弄且汀矽墓母谎义怯驰茫疟狡剥声嘴惺研忿吻咙隅曹赚畅蹋陛葱迫房族蛔哼琉嗣砒梧芬惦翠栗栽跟邪骄臻檬肋司屡樊龄脐好伦娟惶冤益揪液拿凌驴寡翌煎呕鲁兹松惕寨茫爬续织碰骚浑进带淘轮哲赊亡壬歧梁簧霄眺爷粉势猿磋缄逼琐初贪伐弄倔散孽荡胳私烤椎驮旭撮踏悄紧吩皖醛洪熙舜瑟品膛抨晕淋贯自顿镰聘班柴嘶贝嘛屹耿竿疾言咒椽蛆瘁券轮膳丑恶谈弯柏陷曼锯桓虎患汽绘仿染炯逐岳继觅懈桃践矛仅拥慧挫汲汽材粹肝粟玻宽吾福扦衫害扁怜傲同矮右派怠

太原科技大学计算机学科学与技术院计算机08200班李永峰

实验五LR分析

1．实验目的与任务

设计一个LR分析器，实现对表达式语言的分析，加深对LR语法分析方法的基本思想的理解，掌握LR分析器设计与实现的基本方法。

2．实验要求

建立文法及其LR分析表表示的数据结构，设计并实现一个LALR

（1）的分析器，对源程序经词法分析后生成的二元式代码流进行分析，如果输入串是文法定义的句子则输出“是”，否则输出“否”。

3．实验内容

（1）文法描述及其LALR

（1）分析表

描述表达式语言的文法G如下：

0.S→E

1.E→E+T

2.E→T

3.T→T*F

4.T→F

5.F→（E）

6.F→ID

该文法的LALR

（1）分析表如下：

分析表

状态

动作Action表（Yy_action）

转移Goto表（Yy_goto）

（

）

SN=移进并转移到状态NA=accept接受

RN=按第N条产生式进行规约-=error转移

（2）LR分析器总控程序框架如下：

push（0）;

advance（）;

while（Action[tos][sym]!

=accept）

if（Action[tos][sym]==’-’）error（）;

elseif（Action[tos][sym]==SN）{

push（N）;

advance（）;

}

elseif（Action[tos][sym]==RN{

act（N）;

pop（产生式N的右部的符号个数）;

push（Goto[新tos][产生式N的左部符号]）；

}

accept（）;

上述算法中的有关函数与符号的意义如下：

accept（）：

返回成功状态，LR分析器停止工作；

act（N）：

执行利用产生式N的归约的动作，通常为产生代码；

advance（）：

丛输入流读下一单词到sym；

error（）：

出错处理；

pop（N）：

从栈顶弹出N个符号（状态）；

push（N）：

把状态N压入状态栈；

sym：

当前输入的单词符号；

tos：

栈顶状态号。

（3）存放LR分析表的数据结构

①实现方法一：

用一个二维整数数组表示

数组元素为表示动作的整数。

数组的行下标为状态号，列下标用来表示终结符与非终结符的整数表示。

数组元素可作如下约定：

正整数：

表示移进动作，如S6用数6表示；

负整数：

表示归约动作，如R5用数-5表示；

0：

表示接受，通常为按产生式0归约；

状态号也用整数表示；

用不可能是状态号的较大的整数表示错误转移。

请将上述LALR

（1）分析表用这种表示方法，完成LR分析器的程序设计，并添加输出状态栈内容的功能。

用上述表达式文法G的一个句子作为输入，进行测试。

②实现方法二：

采用压缩表示法

动作Action表的每一行用一个数组表示，数组的第一个元素是本数组中存放的数偶个数，第二个元素到最后一个元素都以[终结符，动作]的数偶的形式存放。

再用一个以状态号为下标的下标数组，每个元素含一个指向数偶数组的指针。

若数组元素的值为NULL，则表示从此状态无转移弧发出。

若分析表有几行相同，则只需保存一行，其它元素则都指向存放这一行表的数组即可。

转移Goto表也按同样方式组织，只是这个行数组的数偶为[非终结符，下一状态号]。

每个行数组Yyan表示动作表Yy_action的一行，每个行数组Yygn表示转移表Yy_goto的一行。

假定上述表达式文法G中终结符及非终结符的整数值为：

终结符：

#ID+*（）非终结符：

SETF

整数值：

012345整数值：

0123

Yy_action数组是以状态号为下标的下标数组，每个元素含有指向数组Yyan的指针；下标数组Yy_goto的每个元素含有指向数组Yygn的指针。

表达式文法G的LALR

（1）分析表的具体压缩表示如下：

Yy_action

4,2

1,1

Yya000

5,-6

3,-6

2,-6

0,-6

Yya001

0,0

2,7

Yya003

5,-2

2,-2

0,-2

3,8

Yya004

5,-4

3,-4

2,-4

0,-4

Yya005

5,9

2,7

Yya006

5,-5

3,-5

2,-5

0,-5

Yya009

5,-1

2,-1

0,-1

3,8

Yya010

5,-3

2,-3

0,-3

Yya011

Yyg000

3,5

2,4

1,3

Yyg000

NULL

3,5

2,4

1,6

Yyg002

NULL

3,5

2,10

Yyg007

3,11

Yyg008

NULL

以上分析表用C语言程序描述如下：

*Yy_action表

intYya000[]={2,4,2,1,1};

intYya001[]={4,5,-6,3,-6,2,-6,0,-6};

intYya003[]={2,0,0,2,7};

intYya004[]={4,5,-2,2,-2,0,-2,3,8};

intYya005[]={4,5,-4,3,-4,2,-4,0,-4};

intYya006[]={2,5,9,2,7};

intYya009[]={4,5,-53,-5,2,-5,0,-5};

intYya010[]={4,5,-1,2,-1,0,-1,3,8};

intYya011[]={4,5,-3,3,-3,2,-3,0,-3};

intYy_action[]=

{

Yya000,Yya001,Yya000,Yya003,Yya004,Yya005,

Yya006,Yya000,Yya000,Yya009,Yya010,Yya011

};

*Yy_goto表

intYyg000[]={3,3,5,2,4,1,3};

intYyg002[]={3,3,5,2,4,1,6};

intYyg007[]={2,3,5,2,10};

intYyg008[]={1,3,11};

intYy_goto[]=

{

Yyg000,NULL,Yyg002,NULL,NULL,NULL,

NULL,Yyg007,Yyg008,NULL,NULL,NULL

};

*为了进行归约，使用一个Yy_lhs[]数组，其值为代表产生式左部符号的

*整数，数组的下标为产生式号

intYy_lhs[7]=

{

/*0*/0,

/*1*/1,

/*2*/1,

/*3*/2,

/*4*/2,

/*5*/3,

/*6*/3

};

*Yy_reduce[]数组元素的值为产生式右部符号的个数，

*以产生式号为数组的下标索引

intYy_reduce[]=

{

/*0*/1,

/*1*/3,

/*2*/1,

/*3*/3,

/*4*/1,

/*5*/3,

/*6*/1

};

根据以上数组结构，构造函数Yy_next（），其功能是在给定状态和输入符号下，求出应采取的动作或转向的下一状态。

intYy_next（table,cur_state,symbol）

int**table;/*要查的表*/

intcur_state;/*行号*/

intsymbol;/*列号*/

{

int*p=table[cur_state];

inti;

if（p）

for（i=（int）*p++;--i>0;p+=2）

if（symbol==p[0]）

return（p[1]）;

returnYYF;/*出错指示*/

};

指针p指向Yyan数组或Yygn数组，由参数table的值而定。

如果table指向Yy_action，则p指向Yyan数组；若table指向Yy_goto，则p指向Yygn数组据。

根据上述LALR

（1）分析表压缩表示方法，完成LR分析器的程序设计，并添加输出状态栈内容的功能。

用上述表达式文法G的一个句子作为输入，进行测试。

4.程序源代码和运行结果：

#include

usingnamespacestd;

char*cp;/*指向给定的要分析

的表达式语言*/

inti=1;//从第一步开始执行

structsta_stack

{intstas[50];

inttop1;};//状态栈的数据结构

sta_stackstack1;//定义一个状态栈

structstr_stack

{stringstrs[50];

inttop2;};//符号栈的数据结构

str_stackstack2;//定义一个符号栈

/*终结符用相应的整数代替*/

stringsymbol1[6]=

{"#","ID","+","*","（","）"};

/*非终结符也用相应的整数代替*/

stringsymbol2[4]=

{"S","E","T","F"};

/*Yy_action表*/

intYya000[]={2,4,2,1,1};

intYya001[]={4,5,-6,3,-6,2,-6,0,-6};

intYya003[]={2,0,0,2,7};

intYya004[]={4,5,-2,2,-2,0,-2,3,8};

intYya005[]={4,5,-4,3,-4,2,-4,0,-4};

intYya006[]={2,5,9,2,7};

intYya009[]={4,5,-5,3,-5,2,-5,0,-5};

intYya010[]={4,5,-1,2,-1,0,-1,3,8};

intYya011[]={4,5,-3,3,-3,2,-3,0,-3};

int*Yy_action[]=

{

Yya000,Yya001,Yya000,Yya003,Yya004,Yya005,

Yya006,Yya000,Yya000,Yya009,Yya010,Yya011

};

/*Yy_goto表*/

intYyg000[]={3,3,5,2,4,1,3};

intYyg002[]={3,3,5,2,4,1,6};

intYyg007[]={2,3,5,2,10};

intYyg008[]={1,3,11};

int*Yy_goto[]=

{

Yyg000,NULL,Yyg002,NULL,NULL,NULL,

NULL,Yyg007,Yyg008,NULL,NULL,NULL

};

/*为了进行归约，使用一个Yy_lhs[]数组，其值为代表

产生式左部符号的整数，数组的下标为产生式号*/

intYy_lhs[7]={0,1,1,2,2,3,3};

/*Yy_reduce[]数组元素的值为产生式右部符号的个数，

以产生式号为数组的下标索引*/

intYy_reduce[7]={1,3,1,3,1,3,1};

/*根据以上数组结构，构造函数Yy_next（），其功能是在给

定状态和输入符号下，求出应采取的动作或转向的下一状态。

intYy_next（int**table,intcur_state,intsymbol）

{

int*p=table[cur_state];

inti;

if（p）

for（i=（int）*p++;i-->0;p+=2）

if（symbol==p[0]）

return（p[1]）;

return8000;/*出错指示*/

}

/*将相应的状态和符号进行压栈*/

voidpush（intsta,stringstr）

{stack1.top1++;

stack1.stas[stack1.top1]=sta;

stack2.top2++;

stack2.strs[stack2.top2]=str;

}

/*从输入流读下一单词到sym*/

stringadvance（）

{stringsym;

if（*cp=='I'&&*（cp+1）=='D'）

{sym="ID";

/*cp=cp+2;*/}

else

{sym=*cp;

/*cp=cp+1;*/}

returnsym;

}

/*进行归约动作*/

intact（intYN）

{inttYN=-YN;

returnYy_lhs[tYN];}

/*弹栈*/

voidpop（intn）

{stack1.top1-=n;

stack2.top2-=n;}

voidoutput（）//输出状态栈、符号栈以及未分析输入串

{intsumstrlen=0,i6;

intstasum=0,i7;

cout<

right）<

for（inti2=0;i2<=stack1.top1;i2++）

{cout<

left）<<*/stack1.stas[i2];

if（stack1.stas[i2]==10||stack1.stas[i2]==11）

i7=2;

elsei7=1;

stasum=stasum+i7;}

cout<

left）<<"";

for（inti3=0;i3<=stack2.top2;i3++）

{cout<

if（stack2.strs[i3]=="ID"）

i6=2;

elsei6=1;

sumstrlen=sumstrlen+i6;}

cout<

left）<<"";

//cout<<"";

cout<

展开阅读全文