- 1、本文档共5页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
课外训练答案
1试构造与下列文法G[S]等价的无左递归文法。
G[S]: S→Sa|Nb|c
N →Sd|Ne|f
解:将非终结符按SN的循序排列
S→Sa|Nb|c 存在直接左递归,消除左递归为:
S-NbS’|cS’S’-aS’|ε
N →Sd|Ne|f中Sd中S的顺序在N之前需用S的右部代替S,则
N-〉(NbS’|cS’) d|Ne|f
整理为:N-〉NbS’d| Ne|cS’d|f
存在直接左递归,消除左递归为:
N- cS’dN’|fN’ N’-bS’dN’|eN’|ε
等价的无左递归文法为:S (NbS’ |cS’
S’ (aS’|(
N (cS’dN’ |fN’
N’ (eN’ |bS’dN’ | (
2:文法G的规则集为;
P →begin d : X end
X →d : X | sY
Y→: sY | (
做出该文法LL(1)分析表。
LL(1)分析表为:
begin d : end s e # P →begin d : X end X →d : X →sY Y →: sY →e
3 设有以下文法:
G[S]: S→eEfGh | g
E→FSG | h
F→SEc | cG | ε
G→Sh |ε
(1) 求出该文法每一个非终结符的FOLLOW集。
# h f c h e g
Follow(S) Follow(E) Follow(G) Follow(F) First(S)
First(G) First(E)
e g e g c
根据关系图:Follow(S)={#,h,e,g,c,f}
Follow(E)={f,c}
Follow(G)={f,c,h,e,g}
Follow(F)={e,g}
(2) 它是LL(1)文法吗?为什么?
不是F→SEc | cG | ε First(SEc)={e,g}
因为 F→ε,而Follow(F)={e,g}
First(SEc)∩ Follow(F)={e,g},不为空集,所以不是LL(1)文法
4:给出语言L={1na0n1ma0m|n0, m=0} 的LL(1)文法G[S]并说明其理由。
文法为:S-〉AB A-〉1A0|1a0 B-〉1B0|a
提取公共左因子为:
〉1A’ A’-A0|a0
改造后的文法为: S-〉AB
〉1A’
A’-A0|a0
〉1B0|a
判断文法是LL(1)文法的充要条件是:对每一个非终结符的任何两个不同产生式
〉α|β,则下述条件成立:
FIRST(α)∩FIRST(β)=Φ
*
若β=ε,则FIRST(α)∩FOLLOW(A)=Φ
由于文法不存在形如A-〉ε的产生式,所以无需求非终结符的FOLLOW集。
FIRST(A)=FIRST(S)={1} FIRST(A’)= FIRST(B)={1,a}
对非终结符A’和B有
FIRST(A0)∩FIRST(a0)=Φ
FIRST(1B0)∩FIRST(a)=Φ
文法是LL(1)文法。
该文法为LL(1)文法,因为左部相同,右部的符号串的First集为空集
5 设有文法:G[S]:
S→aBc | bAB
A→aAb | b
B→b | ε 这道题是B→ε不是B→e特此改正
构造其LL(1)分析表,并分析符号串baabbb是否是该文法的句子。
分析表为:
a b c # S →aBc →bAB A →aAb →b B →b →ε →ε 分析栈 余留符号串 产生式
#S baabbb# S- bAB
#BAb baabbb#
#BA aabbb# A →aAb
#BbAa aabbb#
#BbA abbb# A →aAb
#Bbb
文档评论(0)