全部分类

搜索资料

首页

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

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

举报

开通vip

编译原理分知识点习题自下而上语法分析1．★已知文法G[S]：S→SaA|AA→AbB|BB→cSd|e请证实AacAbcBaAdbed是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。解：本题考查“句型”、“短语”、“句柄”、“素短语”等概念。符号栈S关系输入串最左素短语S1S2S3S4S5S6S7R1R2R3R4R5R6＃db)#d#)#b#)#VdV##(V)#V#接受因为存在从文法开始符号S到符号串AacAbcBaAdbed的推导过程（如图6.1中的语法树所示），所以符号串...

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

1．★已知文法G[S]：S→SaA|AA→AbB|BB→cSd|e请证实AacAbcBaAdbed是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。解：本题考查“句型”、“短语”、“句柄”、“素短语”等概念。符号栈S关系输入串最左素短语S1S2S3S4S5S6S7R1R2R3R4R5R6＃<(adb)##<(<adb)##<(db)#d#<(V<db)##<(V)#b#<(V)#VdV#<(V=)##<(=V)>#(V)#V#接受因为存在从文法开始符号S到符号串AacAbcBaAdbed的推导过程（如图6.1中的语法树所示），所以符号串AacAbcBaAdbed是文法的句型。从图6.1中句型A1a1c1A2b1c2Ba2A3d1b2ed2的语法树可知，该句型的短语有：A1、B、Ba2A3、c2Ba2A3d1、A2b1c2Ba2A3d1、e、A2b1c2Ba2A3d1b2e、c1A2b1c2Ba2A3d1b2ed2、A1a1c1A2b1c2Ba2A3d1b2ed2该句型的素短语有：Ba2A3、e该句型的句柄为：B2．★已知文法G[S]：S→*AA→0A1|*求文法G的各非终结符号的FIRSTVT集和LASTVT集;构造文法G的优先关系矩阵，并判断该文法是否是算符优先文法；分析句子*0*1，并写出分析过程。解：本题考查算符优先分析法中的有关知识：非终结符号的FIRSTVT集和LASTVT集的求法、算符优先关系的构造、算符优先文法的定义、算符优先分析过程等。求文法G的各非终结符号的FIRSTVT集和LASTVT集。根据非终结符号的FIRSTVT集定义得到FIRSTVT（S）＝｛*｝FIRSTVT（S）＝｛0，*｝根据非终结符号的LASTVT集定义得到LASTVT（S）＝｛*，1｝LASTVT（S）＝｛1，*｝SSa1AA1Bc1Sd2AAb2BA2b1Bec2Sd1Sa2A3AB图6.1句型AacAbcBaAdbed的语法树构造文法G的优先关系矩阵。根据（1）中的FIRSTVT集和LASTVT集及算符优先关系构造算法对S→*A，按算法第3种情形有：（*<0），（*<*）对A→0A1，按算法第1种情形有：（0|＝1）按算法第3种情形有：（0|<0）,(0|<*)按算法第4种情形有：（1|>1），(*|>1),根据上述算符优先关系得到算符优先关系矩阵如表 6.1所示。表中空白元素表示相应终结符号对之间没有算符优先关系，即它们不会在任何句型中相继出现。表6.1文法的算符优先关系矩阵01*0|<|=|<1|>*|<|>|<(3)对句子“*0*1#”分析过程如表6.2所示。表6.2分析输入符号串“*0*1#”的过程符号栈S关系输入串最左素短语S1S2S3S4S5S6S7R1R2R3R4R5#<*0*1##<*<0*1##<*<0<*1##<*<0<*>1#*#<*<0V=##<*<0V=1>#0V1#<*V>#*V#V#接受3．试为下列优先矩阵构造优先函数。（1）S1S2S3S4S1S2±±S3>>S4>>(2)S1S2S3S4S1>>S2>S3<±<S4±±解：本题考查优先函数的构造方法。采用迭代法求优先函数，过程如下。初始状态：S1S2S3S4f1111g1111第1次迭代：S1S2S3S4f1122g1111第2次迭代：S1S2S3S4f1122g1111第2次迭代没有变化，所以第2次迭代结果便是优先函数。采用Bell有向图法构造优先函数(省略)。因为fs1可以到达的结点：gs3，gs4，fs4，gs3，gs2fs2可以到达的结点：gs3，fs3，gs2，fs4，gs1fs3可以到达的结点：gs2，fs3fs4可以到达的结点：gs1，gs3，fs3，gs2，fs4gs1可以到达的结点：fs3，fs4，gs2，gs1，gs3gs2可以到达的结点：fs3，gs2gs3可以到达的结点：fs4，fs3，gs1，gs3，gs2gs4可以到达的结点：无于是得到优先函数如表6.3所示。S1S2S3S4f7625g52514.试为文法G[Z]：Z→A()A→(|Ai|B)B→i构造算符优先关系和优先函数。解：本题考查算符优先关系的构造方法和优先函数的构造方法。构造算符优先关系。首先构造FIRSTVT集和LASTVT集，根据定义有：FIRSTVT（Z）＝｛（，i，）｝FIRSTVT（A）＝｛（，i，）｝FIRSTVT（B）＝｛i｝和LASTVT（Z）＝｛｝｝LASTVT（A）＝｛（，），i｝LASTVT（B）＝｛i｝按照构造算符优先关系的算法得到如下算符优先关系：“＝”的构造∵有产生式Z→A（）∴按算法第1种情形有：（（＝））“<”的构造文法没有满足“<”的相邻符号“>”的构造∵有产生式Z→A（）∴按算法第4种情形有：（(>（），（）>（），（i>（）∵有产生式A→Ai∴按算法第4种情形有：（（>i）,()>i），（i>i）∵有产生式A→B)∴按算法第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：S→SaS|SbS|cSd|eS|f（1）请证实这是一个二义文法；（2）给出什么样的约束条件，可构造出无冲突的LR分析表？请证实你的论点。解：本题考查“二义文法”及二义文法的LR分析法。（1）该文法是二义文法，因为它存在句子：fafbf该句子有两棵不同的语法树，如图6.3中的（a），（b）所示。SSaSfSbSffSSbSfSaSff图6.3句子fafbf的两棵语法树（2）构造文法的无冲突的LR分析表。首先对文法进行拓广得到S’→S0S→SaS1S→SbS2S→cSd3S→eS4S→f5在此基础上构造文法的识别活前缀的有穷自动机(省略)。因为：FOLLOW(S)={#，a，b，d}构造文法的SLR(1)分析表如表6.6所示。表6.6文法的SLR(1)分析表状态ACTIONGOTOabcdef#S0S2S3S411S5S6acc2S2S3S493S2S3S4104r5r5r5r575S2S3S476S2S3S487r1/S5r1/S6r1r18r2/S5r2/S6r2r29S5S6S1110r4/S5r4/S6r4r411r3r3r3r36.已知文法：G[A]：A→AA|(A)|ε（1）该文法是LR(0)文法吗？为什么？（2）请构造该文法的以LR(0)项目集为状态的识别活前缀的DFA。（3）规定：出现“移进-归约”冲突时，移进优先；出现“归约-归约”冲突时，优先采用文法中出现在前的产生式进行归约。构造该文法的LR分析表。解：本题考查对二义性文法进行LR分析的方法。先构造出识别活前缀的有穷自动机，然后根据其中出现的冲突情况确定无二义规则的使用。首先构造拓广文法如下：A’→AA→AAA→(A)A→ε（1）该文法不是LR(0)文法。因为文法存在有相同左部的产生式A→AA和A→ε产生式A→ε在任何时候都只产生归约项目。当由项目A’→.A派生出新项目时，同时得到A→.(A)和A→.将出现“移进→归约”冲突。所以该文法不是LR(0)文法。（2）构造该文法的以LR(0)项目集为状态的识别活前缀的DFA如图6.4所示。（3）因为出现“移进－规约”冲突时，移进优先；出现“规约－规约”冲突时，优先采用文法中出现在前的产生式进行规约，所以得到该文法的LR分析表如表6.7所示。A(I0A’→．AA→．AAA→．(A)A→．I1A’→A．A→A．AA→．AAA→．（A）A→．I2A→(．A)A→．AAA→．（A）A→．I3A→AA．A→A．AA→．AAA→．（A）A→．I4I5A→(A)．(A(()A→(A．)A→A．AA→．AAA→．（A）A→．AA(A图6.4文法的以LR(0)项目集为状态的识别活前缀的DFA表6.7文法的LR分析表状态ACTIONGOTO()#A0S2r3r311S2r3acc22S2r3r333S2r1r144S2S5r355r2r2r27．★“算符优先分析采用“移进－归约”技术，其规约过程是规范的。”这种说法是否正确？解：本题考查算符优先分析法中句型的规约过程。在算符优先分析法中，每步自下而上分析、识别和归约的是当前句型的最左素短语，而不是严格地从左到右归约句柄。算符优先分析法只对算符优先文法进行，利用的是算符优先关系矩阵，该矩阵中只有终结符号间的优先关系，在归约过程中，利用算符优先关系矩阵无法找到句型中相应于产生式的句柄。因此，在算符优先分析法中，每次归约时，归约的是当前句型的最左素短语——所以产生式对归约没有起作用，因而算符优先分析不是规范规约。例如文法G[E]：E→E+T∣TT→T*F∣FF→P↑F∣PP→（E）∣i对句子i+i的归约过程如图6.5所示。从图6.5可见，算符优先分析中的归约不是规范规约。EEE+TP+PTFiiFii规范归约识别i+i的过程算符优先分析识别i+i的过程图6－5算符优先分析的归约8、★证明G[A]是LR(1)文法。G[A]:A→BA∣εB→Ab∣b解:本题考查“LR(1)文法”，涉及构造以LR（1）项目集为状态的识别活前缀的有穷自动机的方法。首先构造文法的托广文法，得到G[S]：S→A0A→BA1A→ε2B→aB3b→b4根据该托拓广文法构造以LR[1]项目集为状态的识别活动前缀的有穷自动机如图6.6所示。从图6.6中可知，所有的状态都不含有“移进－归约”、“归约－归约”冲突，因而该文法是LR(1)文法。BAabb[B→aB．，a/b/#]I2I1I5[A→BA．，#][A→B．A，#][A→．BA，#][A→．，#][B→．aB，a/b/#][B→．b，a/b/#]I4[B→b．，a/b/#]I3[B→a．B，a/b/#][B→．aB，a/b/#][B→．b，a/b/#]I6I0[S→．A，#][A→．BA，#][A→．，#][B→．aB，a/b/#][B→．b，a/b/#]ABabBa[S→A．，#]图6.6有穷自动机

                    本文档为【编译原理分知识点习题 自下而上语法分析】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

你可能还喜欢

最新资料

资料动态

专题动态

中小学教育资料大全

暂无简介~

格式：doc

大小：239KB

软件：Word

页数：10

分类：互联网

上传时间：2023-03-02

浏览量：0

热点搜索

七年级英语上册Unit9MyfavoritesubjectisscienceSectionB课件新版人教4 移动通信基站天线原理及基本知识讲座二甲医院信息化评审细则 UHT产品质量问题原因分析与解决办法 2021年学校五年发展规划方案实验室先进个人事迹材料建筑材料放射性检测委托单《上古卷轴5》各阵营有什么奖励？各阵营奖励介绍无机材料物理性能期末复习题分析理论题库小学四年级作文600字：我的玩具小熊山东财经大学燕山学院毕业论文格式二年级下册道德与法治我能行教案人保财险综合部工作计划七年级英语上册Unit9MyfavoritesubjectisscienceSectionB课件新版人教4 移动通信基站天线原理及基本知识讲座二甲医院信息化评审细则 UHT产品质量问题原因分析与解决办法 2021年学校五年发展规划方案实验室先进个人事迹材料建筑材料放射性检测委托单《上古卷轴5》各阵营有什么奖励？各阵营奖励介绍无机材料物理性能期末复习题分析理论题库小学四年级作文600字：我的玩具小熊山东财经大学燕山学院毕业论文格式二年级下册道德与法治我能行教案人保财险综合部工作计划