版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第四章习题421 :考虑上下文无关文法:S->S S +|S S *|a以及串aa + a*(1)给出这个串的一个最左推导S -> S S *-> S S + S *-> a S + S *-> a a + S *-> aa + a*(3)给出这个串的一棵语法分析树习题431 :下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的符号|,以避免和文法中作为元符号使用的竖线相混淆:rexprrexpr + rterm | rtermrtermrterm rfactor | rfactorrfactorrfactor * | rprimaryr
2、primarya | b1)对这个文法提取公因子2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗?3)提取公因子之后,原文法中消除左递归4)得到的文法适用于自顶向下的语法分析吗? 解1)提取左公因子之后的文法变为rexpr rexpr + rterm | rtermrterm rterm rfactor | rfactorrfactor rfactor * | rprimary rprimary a | b2)不可以,文法中存在左递归,而自顶向下技术不适合左递归文法3)消除左递归后的文法rexpr - > rterm rexprrexpr -> + rterm rexp
3、r ; ' |rterm- > rfactor rterm 'rterm -> rfactor rterm ; ' |rfactor- > rprimay rfactor 'rfactor ->'*rfactor;'|rprimary-> a | b4) 该文法无左递归,适合于自顶向下的语法分析习题441 :为下面的每一个文法设计一个预测分析器,并给出预测分析表。可能要先对文 法进行提取左公因子或消除左递归(3)S->S(S)S|;(5)S->(L)|a L->L,S|S解 消除该文法的左递归后得到
4、文法S->S 'S ' ->(S)SS ' | ;用类Pascal语言构造的一个预测分析器:PROCEDURE SBEGINS;WHILE (lookahead='(')THEN BEGINmatch ('(');S;match (')');END;ELSE IF (lookahead='a')THEN match('a')ELSE errorEND; 计算FIRST和FOLLOW!合FIRST(S)=(, FOLLOW(S)=),$FIRST(S ' )=(,; FOL
5、LOW(S' )=),$ 构建预测分析表非终结符号输入符号()$SS->S'S->S'S->S'S'S' ->(S)SS 'S'-> 名S' -> £消除该文法的左递归得到文法S->(L)|aL->SL 'L ' ->,SL ' | ;用类Pascal语言的一个预测分析器:PROCEDURE SBEGINif (lookahead='(')THEN BEGINmatch ('(');L;match (
6、39;)');END;ELSE IF (lookahead='a')THEN match('a')ELSE errorEND;PROCEDURE L;BEGINS;WHILE (lookahead =',');BEGINmatch (',');S;END;END; 计算FIRST与FOLLOW!合FIRST(S)=(,a FOLLOW(S)= ), ,$FIRST(L)=(,a FOLLOW(L)= ) FIRST(L ' )= , , ; FOLLOW(L ' )= ) 构建预测分析表非终结符号输入符号(
7、)a$SS->(L)S->aLL->SL 'L->SL'L'L' -> &L' ->,SL '习题444 计算练习422的文法的FIRST和FOLLO嗓合3)S S(S)S| ;5) S(L)|a ,L L,S|S解:3)FIRST(S)= ; ,( FOLLOW(S)= (,),$ FIRST(S)= (,a FOLLOW(S)= ), ,$ FIRST(L)= (,a FOLLOW(L)=),习题462为练习421中的增广文法构造 SLR项集,计算这些项集的 GOTO!数,给出这 个文法的语法分析表
8、。这个文法是SLR文法吗?S SS+|SS*|a解: 构造该文法的增广文法如下S' ->SS->SS+S->SS*S->a构造该文法的LR(0)项集如下I0I1I2I3I4I5S' ->.SS' ->S.S->a.S->SS.+S->SS+.S->SS*.S->.SS+S->S.S+S->SS.*S->.SS*S->S.S*S->S.S+S->.aS->.SS+S->S.S*S->.SS*S->.SS+S->.aS->.SS*S-&g
9、t;.a GOTC函数如下GOTO(IO, S)=I1 GOTO(I0 ,a)=I2GOTO(I1,S)=I3 GOTO(I1 ,a)=I2 GOTO(l1,$)=accGOTO(I3, S)=I3 GOTO(I3 ,+)=I4 GOTO(I3 ,*)=I5 GOTO(I3 ,a)=I2 构造该文法的语法分析表状态ACTIONGOTO+*a$S0S211S2acc32R3R3R3R33S4S5S234R1R1R1R15R2R2R2R2注:FOLLOW(S )=FOLLOW(S)=+,*,a,$这个文法是SLR文法,因为语法分析表中没有重复的条目习题466说明下面文法S SA|AA a是SLR(
10、1的,而不是LL的。证明:1) 可以求得FIRST(SA)=FIRST(A)=a,故该文法不是 LL(1)文法构造该文法的增广文法的语法分析表如下 构造增广文法S ' ->SS->SAS->AA->a 构造LR(O)项集族I0I1I2I3I4S' ->.SS' ->S.S->A.A->a.S->SA.S->.SAS->S.AS->.AA->.aA->.a GOTO函数如下GOTO(IO, S)=I1 GOTO(I0 , A)=I2 GOTO(IO,a)=l3GOTO(I1, A)=I4
11、GOTO(I1 , a)=I3 GOTO(l1,$)=acc 构建语法分析表如下 (FOLLOW(A)=FOLLOW(S)=a,$)状态ACTIONGOTOa$SA0S3121S3acc42R2R23R3R34R1R1可以看到该语法分析表中没有重复的条目故该文法是SLR(1)文法习题4.7.4说明下面的文法S->Aa|bAc|dc|bdaA->d是LALR(1)的,但不是 SLR的证明:1、构造该文法的 SLR(1)语法分析表构造增广文法S ' ->SS->AaS->bAcS->dcS->bdaA->d构造LR(0)项集族I0S'
12、 ->.SS->.AaS->.bAcS->.dcS->.bdaA->.dI1S' ->S.I2S->A .aI5S->Aa.I8S->dc.I3S->b.AcS->b.daA->.dI4S->d.cA->d.I6S->bA.cI9S->bAc.I7S->bd.aA->d.I10 S->bda. GOTO函数GOTO(IO, S)=I1 GOTO(IO , A)=I2 GOTO(IO , b)=l3 GOTO(IO , d)=l4 GOTO(l1,$)=acc GOTO
13、(I2 , a)=I5 GOTO(I3 , A)=I6 GOTO(I3 , d)=I7GOTO(I4, c)=I8 GOTO(I6 , c)=I9 GOTO(I7 , a)=I10 构建SLR语法分析表如下(FOLLOW(A)=a,c)状态ACTIONGOTOabcd$SA0S3S4121acc2S53S764R5S8|R55R16S97S10|R5R58R39R210R4可以看到在图中存在二义性的条目,故该文法不是SLR(1)文法2、构造该文法的LALR(1)语法分析表构造该增广文法的 LR(1)项集族如下I0S' ->.S,$ S->. Aa,$ S->. bAc
14、,$ S-> dc,$ S->. bda,$ A->. d,aI1S' ->S.,$I3S->b Ac,$S->b da,$A->.d,cI5S->Aa .,$I7S->bd .a.,$A->d.,cI9S->bAc.,$I6S->bA C.,$I2S->A .a,$I8S->dc.,$I10S->bda .,$I4S->d. c,$A->d.,$ 项集合并:没有可以合并的项集 GOTO函数GOTO(IO, S)=I1 GOTO(I0 ,A)=I2 GOTO(I0 ,b)=I3 GOT
15、O(I0 ,d)=I4 GOTO(I1,$)=acc GOTO(I2 ,a)=I5 GOTO(I3 ,A)=I6 GOTO(I3 ,d)=I7GOTO(I4, c)=l8 GOTO(I6 , c)=l9 GOTO(I7 , a)=l10构造LALR(1)分析表如下状态ACTIONGOTOabcd$SA0S3S4121acc2S53S764R5S8R55R16S97S10R58R39R210R4可见该分析表中不存在二义性的条目,故该文法是LALR(1)文法习题4.7.5说明下面的文法S->Aa|bAc|Bc|bBaA->dB->d是LR(1)的,但不是 LALR(1)的证明:1
16、、构造该文法的LR(1)语法分析表 构造该文法的增广文法S' ->SS->AaS->bAcS->BcS->bBaA->dB->d 构造该增广文法的LR(1)项集族如下I0S' ->.S,$ S->. Aa,$S->. bAc,$S-> .Bc,$S-> bBa,$ A->. d,a B->.d,cI1S' ->S.,$I2S->A .a,$I6S->Aa .,$I10S->Bc.,$I12S->bBa .,$I3S->b .Ac,$ S->b.B
17、a,$ A->.d,c B->.d,aI4S->B .c,$I7S->bA C.,$I9A->d.,cB->d.,aI5A->d.,aB->d.,cI8S->bB .a.,$I11S->bAc.,$项集合并:没有可以合并的项集 GOTO函数GOTO(IO, S)=I1 GOTO(IO , A)=I2 GOTO(IO , b)=l3 GOTO(IO , B)=I4 GOTO(IO , d)=l5 GOTO(l1,$)=acc GOTO(I2 , a)=I6 GOTO(I3 , A)=I7 GOTO(I3 , B)=I8 GOTO(I3 , d)=I9 GOTO(I4, c)=I10 GOTO(I7 , c)=I11 GOTO(I8 , a)=I12构造LR(1)分析表如下状态ACTIONGOTOabcd$SAB0S3S51241ac
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 广东省珠海市凤凰中学2023-2024学年八年级上学期期中数学试题(解析版+原卷)
- 2023-2024学年山东省德州市武城县甲马营中学八年级(上)第一次月考数学试卷
- 苏教版八年级生物上册第7单元第十九章生态系统素养综合检测课件
- 七年级下语法练习
- 房地产 -五星级酒店样板房施工注意要点
- 山西省2020年中考化学真题(含答案)
- 化 学元素符号 元素周期表同步训练-2024-2025学年九年级化学人教版上册
- 化 学化学方程式(第1课时)-2024-2025学年九年级化学上册同步备课教学课件(人教版2024)
- 【四年级】上册道德与法治-4上3单元第9课《正确认识广告》
- 湘教版小学三年级上册音乐教案 全册
- 重庆大学版信息科技五年级上册全册教案教学设计
- 《广告法概述》课件
- 2024政务服务综合窗口人员能力与服务规范考试试题
- 舆情应对课件
- 渔业资源增殖放流苗种采购投标方案
- 提高住院患者静脉输液规范使用率实施方案
- 水电安装施工规范全套
- 大锁孙天宇小品《时间都去哪了》台词剧本完整版-一年一度喜剧大赛
- 4.2主动运输与胞吞、胞吐说课课件【知识精讲精研】高一上学期生物人教版必修1
- 心理减压及放松训练
- 宁夏特色美食文化介绍推介PPT图文课件
评论
0/150
提交评论