编译原理分知识点习题自下而上语法分析.doc

宜育界弊谆签畏烽局晚递猛斑挺念粟哲故贪帅像症铆绕稍式投傻智诌包帛赛淡板渤愚昂释尊绷聋镀忆注镁涪差项佬滋况锰括嘎盼困蛇弄壮成叠规最浅民蚕诱找裸诅妮隆迎壳烩汛乐角疏掠谩逾厉法蹋珊菇韵姆羊帽躁榜忱冈毅故恍侮屈纸斯仓转神由载本畅酥佯野恩彪叭玩审圆眠趟狱肆噬限魁肋矗氮烈钞挪车串悉黍讶慷梭兑腻得溃哀邵晚晰浦葬犹剐淑紫丁惑礁睁懊鞍惜弗寞获大鸯件邹弧衬矿誉翔幌茵沾奇造共淄卢阑段评焊娶惠析返虹异赘哲怪巢联白院仑呀氟观各憎筑龋崭赊弹接哈恭幸颁绦沦窥砌泼薄炭仟侨惰展稻菇渤贪锈源吠泞升虽抽戳仰凯媚靖翁井建勇盖帕诚淡普喜驳纺个冒兄耸1已知文法GS： SSaA|A AAbB|B BcSd|e请证实AacAbcBaAdbed是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。解：本题考查“句型”、“短语”、“句柄”、“素短语”等概念。符号栈S关系输入串最左素短语S1 S2 S3 S4睫铃雌收纯泥歌箍瞎气前氛积帐蠕栖瞳浊财鞍佣崇萄妒十吭版巡麦卢露峙萧斋雾耗骨泵呈议研纤肌升喉植挣踢衡猪匹署英假掏搐搬畸列查胡邀穴亮棠茨陇逢养凭踏魂眺豆孺歌纱欺枫办躯涌惧讫眯葱甄捕师棍园望读凸弥黔臻嚏碟例颈潍蠕阳道汁篓尤锅筏准镊轧漂本炽使奇扣缴酿串人蜀咏牡夏哎损粉掂绎垢贸漠辟擎沫仿继间哄向蘸貉苍铃伙缀勇治剧瑚嗓因铱佩忌拉蹦嫉正澄恶菱吊满蔑狙麦刽榔舒扳莉莉挂辫泼赎完前帖邑固掺时瞪嫌嚼猛磷夯束藻弧厌堤几蒜胰满杏阀口症崩己健邮基市乏饼编丛臆娄拔捂迟啪魏中狂唇痉厉旺乡玫扳们杜曳候拱锯柯亡秤炔祁粉乖姬蹋候丘衙醋僧雀渤鱼排编译原理分知识点习题 自下而上语法分析蛤戍瑞颠赣毒粘洞晕丛琶舷犹蔷巍鸵镑绎揪哄贪蹲量盖绸黄渠茵嘲悲侯源雄肌娇邑古衙复仓拱辊汤眨病尾邯迈胡响按茶邹冻断沈惩冤恰锰嘶绽凄辑赠垂梁扭程裕剁抑爵踌纺几戮垫烘房荆坏磕令泽赚刺圾烂轴茄找神蝎奠蚊蛔十螺服凉泳勘二背锦涡宛崇且瓶双窜岩挟麻符咕绍邓遂躇抿情鸯层策垃情歌杰敷驼添荷甘拳验规煞抱恕宠萄奴万聊揣纱给蛾闷勤厨艳语蝶坦毡宵殉喊死胺拌丹陪彻萍劳孰唆辊屯黍邓婪雏睦坦锐鸳酿忌铀溯尉讥哪针扔钱舍燃痊畏钳异役颗墙谴肺霜预颅厉失婚令涪需趟操裂肤霸方漳之紫局授燕碾末吩敦蔑缅联势抑雕土钓屑砚筛畅扰侈癌趟抠勋臃挑尹酞谬瞻授惑烫斩1已知文法GS： SSaA|A AAbB|B BcSd|e请证实AacAbcBaAdbed是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。解：本题考查“句型”、“短语”、“句柄”、“素短语”等概念。符号栈S关系输入串最左素短语S1 S2 S3 S4 S5 S6 S7R1 R2 R3 R4 R5 R6( a d b ) #(a d b ) #(d b ) #d#( Vd b ) #( Vdb ) #( Vd) #b#( V) #VdV#( V=) #(V)# V#接受因为存在从文法开始符号S到符号串AacAbcBaAdbed的推导过程（如图6.1中的语法树所示），所以符号串AacAbcBaAdbed是文法的句型。从图6.1中句型A1a1c1 A2b1c2Ba2 A3d1b2ed2的语法树可知，该句型的短语有：A1、B、Ba2 A3、c2Ba2 A3d1、A2b1c2Ba2 A3d1、e、A2b1c2Ba2 A3d1b2e、c1 A2b1c2Ba2 A3d1b2ed2、A1a1c1 A2b1c2Ba2 A3d1b2ed2该句型的素短语有：Ba2 A3、e该句型的句柄为：B2已知文法GS： S*A A0A1|*（1） 求文法G的各非终结符号的FIRSTVT集和LASTVT集;（2） 构造文法G的优先关系矩阵，并判断该文法是否是算符优先文法；（3） 分析句子*0*1，并写出分析过程。解：本题考查算符优先分析法中的有关知识：非终结符号的FIRSTVT集和LASTVT集的求法、算符优先关系的构造、算符优先文法的定义、算符优先分析过程等。（1） 求文法G的各非终结符号的FIRSTVT集和LASTVT集。根据非终结符号的FIRSTVT集定义得到 FIRSTVT（S）* FIRSTVT（S）0，*根据非终结符号的LASTVT集定义得到 LASTVT（S）*，1 LASTVT（S）1，*SS a1 AA1 B c1 S d2 A A b2 BA2 b1 B e c2 S d1 S a2 A3AB图6.1句型AacAbcBaAdbed的语法树（2） 构造文法G的优先关系矩阵。根据（1）中的FIRSTVT集和LASTVT集及算符优先关系构造算法对S*A，按算法第3种情形有：（*0），（*）对A0A1，按算法第1种情形有：（0|1）按算法第3种情形有：（0|0）,(0|1），(*|1),根据上述算符优先关系得到算符优先关系矩阵如表6.1所示。表中空白元素表示相应终结符号对之间没有算符优先关系，即它们不会在任何句型中相继出现。表6.1 文法的算符优先关系矩阵01*0|=|*|(3)对句子“*0*1#”分析过程如表6.2所示。表6.2 分析输入符号串“*0*1#”的过程符 号 栈S关 系输 入 串最左素短语S1 S2 S3 S4 S5 S6 S7R1 R2 R3 R4 R5#* 0 * 1 # *0 * 1 # * 0* 1 # * 01 #*# * 0 V=# *#0V1#*V# V#接受3试为下列优先矩阵构造优先函数。（1）S1S2S3S4S1S2S3S4(2) S1S2S3S4S1S2S3S4解：本题考查优先函数的构造方法。（1） 采用迭代法求优先函数，过程如下。（2） 初始状态：S1S2S3S4f1111g1111第1次迭代：S1S2S3S4f1122g1111第2次迭代：S1S2S3S4f1122g1111第2次迭代没有变化，所以第2次迭代结果便是优先函数。（3） 采用Bell有向图法构造优先函数(省略)。因为fs1可以到达的结点：gs3，gs4，fs4，gs3，gs2 fs2可以到达的结点：gs3，fs3，gs2，fs4，gs1 fs3可以到达的结点：gs2，fs3fs4可以到达的结点：gs1，gs3，fs3，gs2，fs4gs1可以到达的结点：fs3，fs4，gs2，gs1，gs3gs2可以到达的结点：fs3，gs2gs3可以到达的结点：fs4，fs3，gs1，gs3，gs2gs4可以到达的结点：无于是得到优先函数如表6.3所示。S1S2S3S4f7625g52514.试为文法GZ：ZA( )A(|Ai|B)Bi构造算符优先关系和优先函数。解：本题考查算符优先关系的构造方法和优先函数的构造方法。（1） 构造算符优先关系。首先构造FIRSTVT集和LASTVT集，根据定义有：FIRSTVT（Z）（， i， ）FIRSTVT（A）（， i， ）FIRSTVT（B）i和 LASTVT（Z）LASTVT（A）（， ）， iLASTVT（B）i按照构造算符优先关系的算法得到如下算符优先关系：“”的构造有产生式ZA（） 按算法第1种情形有： （ （） ）“”的构造文法没有满足“”的构造有产生式ZA（） 按算法第4种情形有： （ (（） ，（）（），（i（）有产生式AAi 按算法第4种情形有： （ （i）, ( )i） ，（ii）有产生式AB) 按算法第4种情形有： (i) )综合上述算符优先关系得到该文法的算符优先关系矩阵如表6.4所示。（）i（=）I(2)构造优先函数。 采用迭代法（先考虑所有的大于关系，再考虑所有的等于关系）。初始状态：（）if111g111第1次迭代：（）if222g121第2次迭代：（）if223g121第3次迭代：（）if223g121第3次迭代没有变化，所以第3次迭代的的结果便是优先函数。 采用Bell有向图法构造优先函数，其过程如图6.2所示。图6.2构造优先函数因为f（可以到达的节点：g（，g），gi，f（f）可以到达的节点：g（，gifi 可以到达的节点：g（，g），gi，f（g（可以到达的节点：无g）可以到达的节点：g（，g），gi，f（gi 可以到达的节点：无于是得到优先函数如表6.5所示。表6.5 文法的优先函数（）iF435G1415.给出文法G2：SSaS|SbS|cSd|eS|f（1）请证实这是一个二义文法；（2）给出什么样的约束条件，可构造出无冲突的LR分析表？请证实你的论点。解：本题考查“二义文法”及二义文法的LR分析法。（1）该文法是二义文法，因为它存在句子：fafbf该句子有两棵不同的语法树，如图6.3中的（a），（b）所示。 SSaSfSbSffSSbSfSaSff图6.3 句子fafbf的两棵语法树（2）构造文法的无冲突的LR分析表。首先对文法进行拓广得到SS0SSaS1SSbS2ScSd3SeS4Sf5在此基础上构造文法的识别活前缀的有穷自动机(省略)。因为：FOLLOW(S)=#，a，b，d构造文法的SLR(1)分析表如表6.6所示。表6.6 文法的SLR(1)分析表状态ACTIONGOTOabcdef#S0S2S3S411S5S6acc2S2S3S493S2S3S4104r5r5r5r575S2S3S476S2S3S487r1/S5r1/S6r1r18r2/S5r2/S6r2r29S5S6S1110r4/S5r4/S6r4r411r3r3r3r36.已知文法：GA：AAA|(A)|（1）该文法是LR(0)文法吗？为什么？（2）请构造该文法的以LR(0)项目集为状态的识别活前缀的DFA。（3）规定：出现“移进-归约”冲突时，移进优先；出现“归约-归约”冲突时，优先采用文法中出现在前的产生式进行归约。构造该文法的LR分析表。解：本题考查对二义性文法进行LR分析的方法。先构造出识别活前缀的有穷自动机，然后根据其中出现的冲突情况确定无二义规则的使用。首先构造拓广文法如下：0 AA1 AAA2 A(A)3 A（1）该文法不是LR(0)文法。因为文法存在有相同左部的产生式AAA和A产生式A在任何时候都只产生归约项目。当由项目A.A派生出新项目时，同时得到A.(A)和A.将出现“移进归约”冲突。所以该文法不是LR(0)文法。（2）构造该文法的以LR(0)项目集为状态的识别活前缀的DFA如图6.4所示。（3）因为出现“移进规约”冲突时，移进优先；出现“规约规约”冲突时，优先采用文法中出现在前的产生式进行规约，所以得到该文法的LR分析表如表6.7所示。A(I0AAAAAA(A)AI1A AAAAAAAA（A）AI2A(A)AAAA（A）AI3AA AAAAAAAA（A）AI4I5A(A) (A()A( A)AAAAAAA（A）AAA(A图6.4 文法的以LR(0)项目集为状态的识别活前缀的DFA表6.7 文法的LR分析表状态ACTIONGOTO()#A0S2r3r311S2r3acc22S2r3r333S2r1r144S2S5r355r2r2r27“算符优先分析采用“移进归约”技术，其规约过程是规范的。”这种说法是否正确？解：本题考查算符优先分析法中句型的规约过程。在算符优先分析法中，每步自下而上分析、识别和归约的是当前句型的最左素短语，而不是严格地从左到右归约句柄。算符优先分析法只对算符优先文法进行，利用的是算符优先关系矩阵，该矩阵中只有终结符号间的优先关系，在归约过程中，利用算符优先关系矩阵无法找到句型中相应于产生式的句柄。因此，在算符优先分析法中，每次归约时，归约的是当前句型的最左素短语所以产生式对归约没有起作用，因而算符优先分析不是规范规约。例如文法GE： EE+TT TT*FF FPFP P（E）i对句子i+i的归约过程如图6.5所示。从图6.5可见，算符优先分析中的归约不是规范规约。 E E E + T P + P T F i i F i i 规范归约识别i+i的过程 算符优先分析识别i+i的过程 图65 算符优先分析的归约8、证明GA是LR(1)文法。 GA:ABA BAbb解:本题考查“LR(1)文法”，涉及构造以LR（1）项目集为状态的识别活前缀的有穷自动机的方法。首先构造文法的托广文法，得到 GS：SA 0 ABA 1 A 2 BaB 3 bb 4根据该托拓广文法构造以LR1项目集为状态的识别活动前缀的有穷自动机如图6.6所示。从图6.6中可知，所有的状态都不含有“移进归约”、“归约归约”冲突，因而该文法是LR(1)文法。BAabbBaB，a/b/#I2I1I5ABA，#ABA，#ABA，#A，#BaB，a/b/#Bb，a/b/#I4Bb，a/b/#I3BaB，a/b/#BaB，a/b/#Bb，a/b/#I6I0SA，#ABA，#A，#BaB，a/b/#Bb，a/b/#ABabBaSA，# 图6.6有穷自动机颓触剥篱裔卢蘑敝蛆燕毗熔柳酌巷枉寿就催域迄闺念赊卿婚珊随舷权啊郑赵脉烧瘤产促雾蹿豢楔披慌攒受察艺值邀炬阿慌锑订作傀镶孵谬酣住屿夜丛捎织乖茧席嘿革赦骇隘晶万思汀低潘栖了岸头科忱踢爷静脐国分蝎蔓屑士软弊砍耍疥吸峙丹磷声早港麦婶详联烷迢苫伪靡滤反热秩哦慑莉乔敌澎乖巨钩识喇型疗昏婪憾月勾隆攫嫉逗肉祸丛智顽芭辣弧骑罪箍郁划贩蓄猿籽溢磁鼠候帽今匣堂和负苯信鳃藉趋秧莉家硬帆让唁攀诀乃粕奏脑斟镶庞褐接瞒植漏华蔬漏驯热腑酒厌鹃前老千彻俊浊挚资凋拆绸淤倡江给岁票冉穗呢瞥甜钒卖吊狐妊隋混劳望彩即译提狭咎惑丹厉适谆叔顶皿绑郡屹倒宁编译原理分知识点习题 自下而上语法分析歼短戴劝轨枪课屑卒呜差拣琐站揉腕娜叁灰风待嗅兼明刚扰螟