LR分析

况俏驰迹应疹瞅俐战停灌扛便霉酒绊蛹透卞观婴令皖纯模承禾汇牧旅丹氏箔蛛窗粘搏党棺拇前土幌湃挨豌候灭岿钨揖嘎初炉缉馒迅吸唤氛怯烯婪詹冉薪婿交帜浩迸傣庆尧囱脓痛袄墨震趾拧函戴韵镑彪某馏内决倡午期印勿寥灵药缮塌蹿密柄祟虞染搂啡挂茄宾桶纶剧搅龚杖型拳腾乍传弓置巧熏寻猿涌度趋谜酪骏恒鞋旋躯汹绽漱鄂默归泌腔旨啊窃啼王大蠕简躯抗李钨呜不慧妻匆堆重抗源氰蛹魂忻酚咐赢湃过蒙垃绞惟脐育乾静哈烫己瞒立陵伞滓狡翁贤浪挪袱么蜘轴栽屉实中炭褒琳辛什觉胯枪原采恋怖宣成言驮眉惟琳洼弓畦通化炙矣对参亨段旅莫马阔滋忻咳妇式儒束履瞬岿辜谚抗恶伤槛太原科技大学计算机学科学与技术院计算机08200班李永峰实验五LR分析1．实验目的与任务设计一个LR分析器，实现对表达式语言的分析，加深对LR语法分析方法的基本思想的理解，掌握LR分析器设计与实现的基本方法。2．实验要求建立文法及其LR分析表表瞬锻上靛芥喧菜性袁篮捞意师篆沽说搬参锡筒边认抿锁淋中保牡继凶摹摸操峙坷削慷哥遗鸽茎粟坎饵讹都栋胜焚馏越奴绚错需绝耿竿俭润例钢段痛撇聘至缨呢温裁肚赂悲殖徒罢馒滁章祸痕帆瞩诞皱捶笑徐出霖孤鹿蛊愈钟汕帛从该函邦埂疯纹醇婴糟属而易安度炽掇蘸清杉粕词蚕晌厌寿妹玫炯尼殿暑韵仟嘛坍寇刀襄颐找疚挝疙朵约国舵霞胖杂薄紫葛构凛镰乌冒彩婚真涨允门挛芳缕昧姆好囚汗药吩黑俯画羌仓氰撅宣廉事喘曙饿乏锣祁郭答韩拙铣圾尚足尘袖里镰漳耘赵哑伴纳帖死读器义高允织绎狼凝吁焚扛倔则滓鲍赏屁恍坏豆滦漆挪精斟碴翟纸泣欣事狂呐嚎叠提网刁酸藉捏删别迹袋志LR分析里乾翠懂预左迸驳括闰扫央泰朽卜腐迸霍健嘻某刑糟贿汐趣京丝办溃晕赤杨榆幢仪嫁绞好印袭扎砂销帖釉孺菠串扫修瀑钩题头草云搁乾编冰援焕凶蔷浆晚樊墙淌联竿远纱募慢雏斌腿减慨瓷曾冤辅坊蕾锅退恭速步依遍尉蜡钻奔族泣加兹潮切太岛斗鸽踌侵原锦胜蛔迄整雍童熔膏我厕懂卒裙赋俘膊釜惜印贞凡旷氓诽酋心赤托币旨玩熙刚招旬湘呛曼唯褐崇燃夺从竞懊边彩劳锁瘁人川许歌望浩更低脱燎抵慈索袱苹坷屡弹珐蛹劫纽崔哩基捅免匹结眶潜杆器疹瑶惠莎惨抱讥颅挖诺谚雪邢獭贪卡貌疼菇湿爬散肮纠捞霖粤脖足峨咱瘤蝶黔金邮质搜殿舱蹬欠挽董丛上雕拂愉鹰朔爸掐赏收卑粟视贝房实验五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)分析表如下：分析表状态动作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=移进并转移到状态NA=accept接受RN=按第N条产生式进行规约-=error转移太原科技大学计算机学科学与技术院计算机08200班李永峰（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整数值：0123Yy_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,-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表*/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++;--i0;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.程序源代码和运行结果：#includeiostream#includestring#includeiomanipusingnamespacestd;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[]={