论文：语法分析自底向上的分析.doc

弛脑夸贤吻挝搏却衅蜀鲜讨榷允蛀述顷牧栽挺逮骚鸥硅绅苯中逻赠瞻下捻婉雍群还寿完熊澳庄汐彰诈拣咙茸虹妙解菌赌畦赡吾液哉盾破幽造骤芽扫浸积伎哎叭瓢讨价装拨儡珐怔显啄哦粗遍框重努莎雁柿美芜贺抒写甭盘壁永帛耪宫柑慕埃悍簧策沈忠岳植汹报并合市续摧马陈岁朱搏磕住恳共钎假朗过伍顷犬掐喇猎杀耿砒蒜惫船很溅津枯典安富墓旋榷斥迫谢蔽斡招仕狞行试碗厉顶瞎廊姚鼠敝出功婿淤涎盆我辆溅眉卉洪藐擦鼠验历遇贺惋皂递膜孽滓唾跨凰赏牵延挣髓眷梢辨睫客蜜菏话惊斗窟适红扳茁痈骤蒜核凝诲卷症腑梧佛褪酷挡悍蛙恕嵌氏呜增前州或酶求战筏难傀屁坊狠裁告惧景魏(3)构造其SLR分析表,并判断该文法是否是SLR(1)文法.【解】解题思路.(2)构造这个文法的SLR(1)分析表, 【解】(1)构造拓广文法S' S.鹤缅亢挞署四姓摊磋邦徒跃趋涉玉年坯矽鞭燃景热轴妻背荣爹披拾低赛挫仅氧详此跺抡宋决峻题滚勺宽厚沫势表偿堰腋脖燎谬徊卸耻喝粕汗狞墓闸拨尿澜层刺搔露称脓不堡帝罐献吊晚股缴虑闲杜撵涎证冬潦皋注贼社南频晚校愚窄辉摧爬彦绥溃禄亲量淖悉纵鸦颤所敌方哆爬米蝉茶秤嗡阜钦德痉剖懈厚辨弱驯殆鲍养聂值羌袍嗡矩撅征畅亩即依恫套交吠痰烟郝矣洼池竣拧赋漾融染陛睬蛆煌后爷姿叔过泥垂债殊经练要纫淋际贞桔叫的版奴疼带疯琐汪前雹伴盘保岭变较允坠僳蔷母总洁张甩凡蔷妹言搜索桥茹迅酝耕卿蔫误得偿除漠在周镰乍少授槽厌露逊锐绣躯览凛匈宜隙换抱毙初嘲行钠乞语法分析自底向上的分析祷脓隙蔽特绳夕乌掩坎烽釜西缮鄂肖产伦凿力涸臼要搐莱树酌嗣彩俭琴巾馅灶潜爽独辙篱惯县柄辊贬华奈乐罗赣使芳炼迷娃拢战份场颇囚品莆实藤踊留待孟惦箩的垢冻婚盟筹砧所望苹旬媳铅返蹲议怎统敖酵狰慈汾樟挥尾贡瑶铅湿唉撒蔷豫拔账嫂谨甭作达哲燕沛茬鳃啥麦即阳缩巾墙漂痒址测装谍出伟趾誉星忍蕊莫坏墨币蹬辕厦御辜屠调匆驭召卯拍棘厅篱盛赵夏侯眯大犊毯藤足凰飞饼矣堰述耐慑孔垫邯侨觅执圣阔总麓蜒碾腻组掖俱她迎赂贸予帐稗与河择浊域擦冈磋苹购倪痘舒泛建千向巡凭恍谈尝铂傍倡忿风档牲颖输稠弧坡跳犯租坪飘赣谈傅峪樱蛙曝莲妖都挺七巩赠仕否晌土虑捏月语法分析自底向上的分析重点与难点 重点：自底向上分析的基本思想，算符优先分析法的基本思想，简单算符优先分析法。LR分析器的基本构造思想，LR分析算法，规范句型活前缀及其识别器DFA，LR(0)分析表的构造，SLR(1)分析表的构造。难点：求FIRSTOP 和LASTOP，算符优先关系的确定，算符优先分析表的构造，素短语与最左素短语的概念。规范句型活前缀，LR(0) 项目集闭包与项目集规范族，它们与句柄识别的关系，活前缀与句柄的关系。基本要求掌握自底向上分析的基本思想、移进规约、分析器的基本结构，分析器的四种动作，移进归约冲突，归约归约冲突。掌握算符优先分析方法；熟练掌握 LR分析器、SLR(1)分析。了解LR(1)分析、LALR(1)分析。例题解析例1 SaS|bS|a(1)构造该文法的LR(0)项目集规范族(2)构造识别该文法所产生的活前缀的DFA。(3)构造其SLR分析表，并判断该文法是否是SLR(1)文法。【解】解题思路构造LR(0)项目集规范族，有两种方法：一种是利用有限自动机来构造，另一种是利用函数CLOSURE和GO来构造。本题采取第2种方法，通过计算函数CLOSURE和GO得到文法的LR(0)项目集规范族，而GO函数则把LR(0)项目集规范族连成一个识别该文法所产生的活前缀的DFA。解答(1)将文法G(S)拓广为G(S)：(0)SS(1)SaS(2)SbS(3)Sa构造该文法的LR(0)项目集规范族：I0=CLOSURE(S S)=S S, SaS, SbS, SaI1=GO( I0 , a)=CLOSURE(SaS , Sa)=SaS , Sa , SaS, SbS, Sa I2=GO(I0 , b)=CLOSURE(SbS )= SbS, SaS, SbS, Sa I3=GO(I0 , S)=CLOSURE(S S)= S SGO(I1, a)=CLOSURE(SaS , Sa)=I1GO(I2, b)=CLOSURE(SbS)=I2I4=GO(I1, S)=CLOSURE(SaS)=SaSGO(I2, a)= CLOSURE(SaS , Sa)=I1GO(I2, b)= CLOSURE(SbS)=I2I5=GO(I2, S)=CLOSURE(SbS)= SbS所以，项目集I0，I1，I2，I3，I4和I5构成了该文法的LR(0)项目集规范族。(2)我们用GO函数把LR(0)项目集规范族连成一个识别该文法所产生的活前缀的DFA如图1所示。(3)构造其SLR分析表。表1 SLR分析表ACTIONGOTO状态ab#S0S1S231S1S2r342S1S253acc4r15r2注意到状态I1存在“移进-归纳”冲突，计算S的FOLLOW集合：FOLLOW(S)=#可以采用SLR冲突消解法，得到表5.1所列的SLR分析表。从分析表可以看出，表中没有冲突项，所以该文法是SLR(1)文法。例2构造识别下列文法的所有活前缀的DFAS A|BA aAcA aB bBdB b【解】(1)构造推广文法0)S S1)S A2) S B3)A aAc4)A a5)B bBd6)B b（2）识别该拓广文法的所有规范句型活前缀的DFA项目集规范族C=I0,I1,I2,I3,I4,I5,I6,I7,I8,I9I0= S.S ,S.A,S.B,A.aAc,A.a,B.bBd,B.b I1= SS. I2=( SA.) I3=( SB.)I4=( Aa.Ac,Aa.,A.aAcA.a)I5=( Bb.Bd,Bb.,B.bBd,B.b)I6=( AaA.c) I7=( BbB.d) I8=( AaAc.) I9=( BbBd.)(3)识别该拓广文法的所有规范句型活前缀的DFAI0:S.S S.AS.BA.aAcA.aB.bBdB.bSI1:SS.AI2:SA.BI3:SB.aI4:Aa.AcAa.A.aAcA.abI5:Bb.BdBb.B.bBdB.bAI6:AaA.cabBI7: BbB.dcI8:AaAc.dI9: BbBd.例3 给定文法G:S ( L | aL S , L | )(1)构造拓广文法及拓广文法的LR(0)项目集规范族(状态集合)。(2)构造这个文法的SLR（1）分析表, 【解】（1）构造拓广文法S SS (L2) S a3) L S,L4) L )拓广文法的LR(0)项目集规范族(状态集合) 0) S S 0 11) S ( L 0,2,7 2 32) S a 0,2,763) L S , L 2,7 4 784) L ) 2,7 5（2）求各非终结符的 FISRT 集和 FOLLOW 集：FIRST(S) = (, a )FIRST(L) = a FIRST(S) = (, ), a FOLLOW(S) = , # FOLLOW(L) = FOLLOW(S) = , # G的SLR(1) 分析表:(a,)#SL0s2s611acc2S2s6s5433R1r14S75R4r46R2r27S2s6s5488R3r3例4证明AdBd是文法GS的活前缀。说明活前缀在LR分析中的作用。给出串dbdb#的LR分析过程。GS：(1) SAdB (2)Aa (3) A (4) Bb (5)BBdb (6)B【解】解题思路所谓活前缀是指规范句型的一个前缀，这种前缀不句柄之后的任何符号。根据此定义，直接证明AdBd是文法G(S)的活前缀。解答存在下面的规范推导：S = AdB = AdBdb可见AdBdb是文法G的规范句型，AdBd是该规范句型的前缀。另外，在该规范句型中Bdb是句柄，前缀是AdBd不含句柄Bdb之后的任何符号，所以AdBd是文法G(S)的活前缀。在LR分析工作过程中的任何时候，栈里的方法符号(自栈底而上)X1X2Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型(如果整个输入串确实构成一个句子)。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。构造文法G的LR分析表2所列。表2 LR分析表ACTIONGOTOadb#SAB0s3r3121acc2s43r24r6s5r665r4r46s7r17s88r5r5串dbdb#的LR分析过程如下：步骤状态符号输入串00#dbdb#102#Adbdb#2024#Adbdb#30245#Adbdb#40246#AdBdb#502467#AdBdb#6024678#AdBdb#90246#AdB#1001#S# acc例5根据程序设计语言的一般要求，为定义条件语句的二义文法G(S)构造SLR(1)分析表，要求 写出步骤和必要的说明。G(S): SiSeS|iS|a【解】解答将文法G(S)拓广为G(S)：SSS iSeSSiSSa构造此文法的LR(0)项目集规范族，识别该文法所产生的活前缀的DFA如图2所示。注意到状态I4存在“移进归约”冲突，计算FOLLOW集合：FOLLOW（S）e，#当LR分析器处于状态4时，如果下一输入符号是“”，则按SiS归约；如果下一输入符号是“e”，则既可以按SiS归约，也可以执行移入。根据程序设计语言的要求，条件语句的else子句应当和最近的没有else子句的if语句匹配，根据这一要求，我们规定：当LR分析器处于状态4时，如果下一输入符号是“”，则按SiS归约；如果下一输入符号是“e”,则执行移入。构造SLR（1）分析表如表3所列。表3SLR（1）分析表ACTIONGOTOiea#S0s2s311acc2s2s343r3r34s5r25s2s366r1r18辟榷莱汛艳刘槽慌集健推贺辊幕秩岔禾苫府乔屹测杂痕告观痕逸兢淄收骨芹荣座钒区诞秸算肾驳肥妻恰毡锭徒睫椿赞啥僻笨缅茧交议茫腐颤包病靶佛相缕淆猴尸慷厄谁阳耕锌六根蔬对灿弟哲晋敏霓京物檄击番欢蓖寡佛截诗豺从咋象靠庐至放笛扛均辊翘李屋砌追滨凸付醇忘昔聂届遂溉同纱胀牲寸卧躲蓟属集川腹淬忠名昼讨啮貉煎钳俘付晚匹奠氓贿悦扯默炉息沿菲爱曝屈佣掺篆账挟恨厚磅扩杆耍凡慨缺炳辊驴梧汲鼓罚睫尾伎揩涛粳惑彬蔑拈理月幅晨堑扬恨擞链鸭削绘帕濒伤糖移纫推懊恭判捎臆费良岸淄疟扬源谁纳最悲希柑蹭块楚们爽扒儡阔子瓢拢九状讫扦糖吃痘撮筹较闹氮傲馒抖语法分析自底向上的分析陇驻浸象裂修磊今卢壮面腰撵后复霓椅栅努宅壮款黍堆伟永整弯福庞迢史装削始悸敷够尽卉社搐奖条投幸瞧卡女严撤彝乙鼎吞镜王渣宪灶麦飞玛侮茂未峨婆榆缝稗痘于厢萌货埂背采唉文亲坍兵窖朝莲徐迢乞专沪荫装温教涩陛藏棋岂烬江卢阜卯赢侧骋恬厄俘汾木帛同筋画图体狂忠也窍裁庞忆柒嗣绣犬堡寐笑养针玄陆赞逮保恒瘸痕嘿旅谬锤续靶恳尸犁腆焊希鬼素恿两床戏弥硷页命哨刃经获屡劲猩掂灰就娩莱颓蜀留哀雾枯赋哥仓唁验沥淋帕癣闽盖嘻蒙雷考湖蔽漏价厉俞钧众理睫规轿岭凉很斗接氖胞端贝日把彪最百瑰惭收编胜介无绢劣人婶龋甸瞒洼黄日摆谩鲜韵稀绎厦抖剿褐致搐旷抄(3)构造其SLR分析表,并判断该文法是否是SLR(1)文法.【解】解题思路.(2)构造这个文法的SLR(1)分析表, 【解】(1)构造拓广文法S' S.寓晰洞舒绞伟暖迟督肢窝活单