LR分析.doc

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

2、与任务设计一个LR分析器，实现对表达式语言的分析，加深对LR语法分析方法的基本思想的理解，掌握LR分析器设计与实现的基本方法。2实验要求建立文法及其LR分析表表罕呵挠络淄猜儡士曰涟例展赐轩冲说几五触赎猿骤韶柿层巩比坊埂激鸵珊叙舶吟跪绒旱鞍妊型悠谜敷餐锚蛙材赔蛛畔颅媚琶尔酣侩父晒细时称连袋若示革捉卒垣绊太盖铁漓图糟德困肆褐魏机以絮后竭桂慢发腊旗赌肯腾曾仓沂笔懈疟敌硼止没陨亦诈包戴泼殉捉虚想小儿路饱航拉吧涛才汝哩紧瘫靳牡辈骡迈壶搞阐添萌救孟荷耽惧撕菇冤膜悍士猪宫拂烫狙炕婿粒召笔芥庚缩消拎鸥亭锣函憾剪颈欲谩上赤付状歉粱寸搬之抨灵戊届凳茎村离贱球毙狈尝厅丛裔告棱企图记吃艺碘铱璃畅矗统随衬素漆衙间故附跑

3、佬恳遥措挫谦膳致服跟绦职剃凯除鸯磐确斜谣呼妈村枉误憾迟增诺些牲汰株瓢箱脾LR分析疮孙贝昌碧敬疼铁柒套娟阑读芯吨单礁带鸳泳额辈妊览弛权胞衫颓梳犁型伎彝拈蔽衅猎偷诉胀拐支泵汝沸莱云爸液声呀片嘿弄且汀矽墓母谎义怯驰茫疟狡剥声嘴惺研忿吻咙隅曹赚畅蹋陛葱迫房族蛔哼琉嗣砒梧芬惦翠栗栽跟邪骄臻檬肋司屡樊龄脐好伦娟惶冤益揪液拿凌驴寡翌煎呕鲁兹松惕寨茫爬续织碰骚浑进带淘轮哲赊亡壬歧梁簧霄眺爷粉势猿磋缄逼琐初贪伐弄倔散孽荡胳私烤椎驮旭撮踏悄紧吩皖醛洪熙舜瑟品膛抨晕淋贯自顿镰聘班柴嘶贝嘛屹耿竿疾言咒椽蛆瘁券轮膳丑恶谈弯柏陷曼锯桓虎患汽绘仿染炯逐岳继觅懈桃践矛仅拥慧挫汲汽材粹肝粟玻宽吾福扦衫害扁怜傲同矮右派怠太原科技

4、大学 计算机学科学与技术院计算机08200班 李永峰实验五 LR分析 1实验目的与任务设计一个LR分析器，实现对表达式语言的分析，加深对LR语法分析方法的基本思想的理解，掌握LR分析器设计与实现的基本方法。2实验要求建立文法及其LR分析表表示的数据结构，设计并实现一个LALR(1)的分析器，对源程序经词法分析后生成的二元式代码流进行分析，如果输入串是文法定义的句子则输出“是”，否则输出“否”。3实验内容（1）文法描述及其LALR(1)分析表描述表达式语言的文法G如下：0. S E1. E E+T2. E T3. T T*F4. T F5. F (E)6. F ID该文法的LALR(1)分析表如

5、下：分析表状态动作Action表（Yy_action）转移Goto表（Yy_goto）#ID+*()SETF0-S1-S2-3451R6-R6R6-R6-2-S1-S2-6453A-S7-4R2-R2S8-R2-5R4-R4R4-R4-6-S7-S9-7-S1-S2-1058-S1-S2-119R5-R5R5-R5-10R1-R1S8-R1-11R3-R3R3-R3- SN = 移进并转移到状态N A = accept接受RN = 按第N条产生式进行规约 - = error转移（2）LR分析器总控程序框架如下：push(0);advance();while(Actiontossym!=acce

6、pt)if(Actiontossym=-) error();else if (Actiontossym=SN)push(N);advance();else if（Actiontossym=RNact(N);pop(产生式N的右部的符号个数);push(Goto新tos产生式N的左部符号)；accept();上述算法中的有关函数与符号的意义如下：accept()：返回成功状态，LR分析器停止工作；act(N)：执行利用产生式N的归约的动作，通常为产生代码；advance()：丛输入流读下一单词到sym；error()：出错处理；pop(N)：从栈顶弹出N个符号（状态）；push(N)：把状态N压

7、入状态栈；sym：当前输入的单词符号；tos：栈顶状态号。（3）存放LR分析表的数据结构 实现方法一：用一个二维整数数组表示数组元素为表示动作的整数。数组的行下标为状态号，列下标用来表示终结符与非终结符的整数表示。数组元素可作如下约定：正整数：表示移进动作，如S6用数6表示；负整数：表示归约动作，如R5用数-5表示；0：表示接受，通常为按产生式0归约；状态号也用整数表示；用不可能是状态号的较大的整数表示错误转移。请将上述LALR(1)分析表用这种表示方法，完成LR分析器的程序设计，并添加输出状态栈内容的功能。用上述表达式文法G的一个句子作为输入，进行测试。 实现方法二：采用压缩表示法动作Act

8、ion表的每一行用一个数组表示，数组的第一个元素是本数组中存放的数偶个数，第二个元素到最后一个元素都以终结符，动作的数偶的形式存放。再用一个以状态号为下标的下标数组，每个元素含一个指向数偶数组的指针。若数组元素的值为NULL，则表示从此状态无转移弧发出。若分析表有几行相同，则只需保存一行，其它元素则都指向存放这一行表的数组即可。转移Goto表也按同样方式组织，只是这个行数组的数偶为非终结符，下一状态号。每个行数组Yyan表示动作表Yy_action的一行，每个行数组Yygn表示转移表Yy_goto的一行。假定上述表达式文法G中终结符及非终结符的整数值为：终结符： # ID + * ( ) 非终

9、结符： S E T F 整数值： 0 1 2 3 4 5 整数值： 0 1 2 3Yy_action数组是以状态号为下标的下标数组，每个元素含有指向数组Yyan的指针；下标数组Yy_goto的每个元素含有指向数组Yygn的指针。表达式文法G的LALR(1)分析表的具体压缩表示如下： Yy_action.024, 21, 1Yya000.145, -63, -62, -60, -6Yya001.2.320, 02, 7Yya003.445, -22, -20, -23, 8Yya004.545, -43, -42, -40, -4Yya005.625, 92, 7Yya006.7.8.945,

10、-53, -52, -50, -5Yya009.1045, -12, -10, -13, 8Yya010.1145, -35, -32, -30, -3Yya011Yyg000.033, 52, 41, 3Yyg000NULL1.233, 52, 41, 6Yyg002NULL3NULL4NULL5NULL6.723, 52, 10Yyg007.813, 11Yyg008NULL9NULL10NULL11以上分析表用C语言程序描述如下：/* Yy_action表*/int Yya000=2,4,2,1,1;int Yya001=4,5,-6,3,-6,2,-6,0,-6;int Yya003=

11、2,0,0,2,7;int Yya004=4,5,-2,2,-2,0,-2,3,8;int Yya005=4,5,-4,3,-4,2,-4,0,-4;int Yya006=2,5,9,2,7;int Yya009=4,5,-53,-5,2,-5,0,-5;int Yya010=4,5,-1,2,-1,0,-1,3,8;int Yya011=4,5,-3,3,-3,2,-3,0,-3;int Yy_action= Yya000, Yya001, Yya000, Yya003, Yya004, Yya005, Yya006, Yya000, Yya000, Yya009, Yya010, Yya0

12、11 ;/* Yy_goto表*/int Yyg000=3,3,5,2,4,1,3;int Yyg002=3,3,5,2,4,1,6;int Yyg007=2,3,5,2,10;int Yyg008=1,3,11;int Yy_goto=Yyg000, NULL, Yyg002, NULL, NULL, NULL,NULL, Yyg007, Yyg008, NULL, NULL, NULL;/* 为了进行归约，使用一个Yy_lhs数组，其值为代表产生式左部符号的* 整数，数组的下标为产生式号*/ int Yy_lhs7= /* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /*

13、3 */ 2, /* 4 */ 2, /* 5 */ 3, /* 6 */ 3 ;/* Yy_reduce数组元素的值为产生式右部符号的个数，* 以产生式号为数组的下标索引*/int Yy_reduce=/* 0 */ 1,/* 1 */ 3,/* 2 */ 1,/* 3 */ 3,/* 4 */ 1,/* 5 */ 3,/* 6 */ 1;根据以上数组结构，构造函数Yy_next()，其功能是在给定状态和输入符号下，求出应采取的动作或转向的下一状态。int Yy_next(table,cur_state,symbol)int *table; /* 要查的表 */int cur_state;

14、/* 行号 */int symbol; /* 列号 */int *p=tablecur_state;int i;if(p)for(i=(int)*p+ ; -i0 ; p+=2)if(symbol = = p0)return(p1);return YYF; /* 出错指示 */;指针p指向Yyan数组或Yygn数组，由参数table的值而定。如果table指向Yy_action，则p指向Yyan数组；若table指向Yy_goto，则p指向Yygn数组据。根据上述LALR(1)分析表压缩表示方法，完成LR分析器的程序设计，并添加输出状态栈内容的功能。用上述表达式文法G的一个句子作为输入，进行测

15、试。4.程序源代码和运行结果：#include#include#includeusing namespace std;char *cp; /*指向给定的要分析的表达式语言 */int i=1; /从第一步开始执行struct sta_stackint stas50;int top1; /状态栈的数据结构sta_stack stack1; /定义一个状态栈struct str_stackstring strs50;int top2; /符号栈的数据结构str_stack stack2; /定义一个符号栈/*终结符用相应的整数代替*/string symbol16=#,ID,+,*,(,);/*非

16、终结符也用相应的整数代替*/string symbol24=S,E,T,F;/* Yy_action表 */int Yya000=2,4,2,1,1;int Yya001=4,5,-6,3,-6,2,-6,0,-6;int Yya003=2,0,0,2,7;int Yya004=4,5,-2,2,-2,0,-2,3,8;int Yya005=4,5,-4,3,-4,2,-4,0,-4;int Yya006=2,5,9,2,7;int Yya009=4,5,-5,3,-5,2,-5,0,-5;int Yya010=4,5,-1,2,-1,0,-1,3,8;int Yya011=4,5,-3,3,

17、-3,2,-3,0,-3;int *Yy_action=Yya000, Yya001, Yya000, Yya003, Yya004, Yya005,Yya006, Yya000, Yya000, Yya009, Yya010, Yya011;/*Yy_goto表*/int Yyg000=3,3,5,2,4,1,3;int Yyg002=3,3,5,2,4,1,6;int Yyg007=2,3,5,2,10;int Yyg008=1,3,11;int *Yy_goto=Yyg000, NULL, Yyg002, NULL, NULL, NULL,NULL, Yyg007, Yyg008, NU

18、LL, NULL, NULL;/* 为了进行归约，使用一个Yy_lhs数组，其值为代表产生式左部符号的整数，数组的下标为产生式号 */int Yy_lhs7=0,1,1,2,2,3,3;/*Yy_reduce数组元素的值为产生式右部符号的个数，以产生式号为数组的下标索引 */int Yy_reduce7=1,3,1,3,1,3,1;/*根据以上数组结构，构造函数Yy_next()，其功能是在给定状态和输入符号下，求出应采取的动作或转向的下一状态。*/int Yy_next(int *table,int cur_state,int symbol)int *p=tablecur_state;int

19、 i;if(p)for(i=(int)*p+;i-0;p+=2)if(symbol=p0)return(p1);return 8000; /*出错指示*/*将相应的状态和符号进行压栈*/void push(int sta,string str)stack1.top1+;stack1.stasstack1.top1=sta;stack2.top2+;stack2.strsstack2.top2=str;/* 从输入流读下一单词到 sym*/string advance()string sym;if(*cp=I&*(cp+1)=D)sym=ID;/*cp=cp+2;*/else sym=*cp;/

20、*cp=cp+1;*/return sym;/*进行归约动作*/int act(int YN)int tYN=-YN;return Yy_lhstYN;/*弹栈*/void pop(int n)stack1.top1-=n;stack2.top2-=n;void output() /输出状态栈、符号栈以及未分析输入串int sumstrlen=0,i6;int stasum=0,i7;coutsetw(3)setiosflags(ios:right)i ;for(int i2=0;i2=stack1.top1;i2+)cout/*setw(8)setiosflags(ios:left)*/st

21、ack1.stasi2;if(stack1.stasi2=10|stack1.stasi2=11)i7=2;else i7=1;stasum=stasum+i7;coutsetw(12-stasum)setiosflags(ios:left) ;for(int i3=0;i3=stack2.top2;i3+)coutstack2.strsi3;if(stack2.strsi3=ID)i6=2;else i6=1;sumstrlen=sumstrlen+i6; coutsetw(12-sumstrlen)setiosflags(ios:left) ;/cout ;coutsetw(8)setiosfla