云题海 - 专业文章范例文档资料分享平台

当前位置:首页 > 编译原理复习题_给学生(2014)

编译原理复习题_给学生(2014)

  • 62 次阅读
  • 3 次下载
  • 2025/7/5 7:10:32

.. .. ..

(2) 写出文法G’(S)的预测分析表。 解:

(1)消除左递归,文法变为: S→aPS’| *aPS’ S’→ *aPS’ | ε

P→+aP| +a

提取公共左因子,文法变为G’(S): S→aPS’| *aPS’

S’→ *aPS’ |ε

P→+aP’ P’→P| ε

(2)计算每个非终结符的FIRST集和FOLLOW集: FIRST(S) = {a, *} FIRST(S’) = {*, ε} FIRST(P) = {+}

FOLLOW(S) = {#}

FOLLOW(S’) = {#} FOLLOW(P) = {*, #} FOLLOW(P’) = {*, #}

FIRST(P’) = {+, ε}

构造该文法的预测分析表如下:

S S’ P P’ * S→*aPS’ S’→ *aP P’→ε + P→+aP’ P’→P a S→aPS’ # S’→ ε P’→ε 参考材料

.. .. ..

19.已知文法G(S):

S→aS | bS | a

(1) 构造识别该文法所产生的活前缀的DFA;

(2) 判断该文法是LR(0)还是SLR(1),并构造所属文法的LR分析表。 解:

(1)将文法G(S)拓广为G’(S’):

(0) S’→S (1) S→aS (2) S→bS (3) S→a

识别该文法所产生的活前缀的DFA:

I4: S’→ aS? S I2: S→ a?S S→ ?aS S→ ?bS S→ ?a S→ a? a a I0: S’→ ?S S→ ?aS S→ ?bS S→ ?a b S I1: S’→ S? b a I5: S’→ bS? I3: S→ b?S S→ ?aS S→ ?bS S→ ?a S b (2)在状态I2存在“移近-归约”冲突,因此该文法不是LR(0)文法。

计算S的FOLLOW集合: FOLLOW(S)= {#}

参考材料

.. .. ..

I2中的冲突用FOLLOW集合可以解决,所以该文法是SLR(1)文法。 构造SLR(1)分析表如下:

ACTION 状态 a 0 1 2 3 4 5

20.构造文法S→AaAb|BbBa A→ε B→ε,的预测分析表。

答:first(S)={a,b},First(AaAb)={a},First(BbBa )={b} Follow(A)={a,b} Follow(B)={a,b}

S A B

21.设有如下文法:

参考材料

GOTO # acc r3 r1 r2 S 1 4 5 b s3 s3 s3 s2 s2 s2 a S→AaAb A→ε b S→BbBa A→ε $ B→ε B→ε .. .. ..

G[E]:E→EWT|T T→T/F|F F→(E)|a|b|c W→+|-

证明符号串a/(b-c)是句子。

解答:有推导E?T?T/F?F/F?a/F?a/(E)?a/(EWT)? a/(TWT)? a/(FWT)? a/(bWT)? a/(b-T)? a/(b-c),即从文法开始符号E能够推导出a/(b-c),所以a/(b-c)是文法G[E]的句子。 55.对于下列文法 G[S]: S→Sb|bA A→aA|a

(1)构造一个与G等价的LL(1)文法G′。 (2)对于文法G′,构造相应的LL(1)分析表。 解:

(1) G′:S→bAS′ S′→b S′|ε

A→aA′ A′→A|ε

(2)FIRST(S)={ b } FIRST(S′)={ b,ε} FIRST(A)={a} FIRST(A′)={a,ε} FOLLOW(S)={#}

参考材料

搜索更多关于: 编译原理复习题_给学生(2014) 的文档
  • 收藏
  • 违规举报
  • 版权认领
下载文档10.00 元 加入VIP免费下载
推荐下载
本文作者:...

共分享92篇相关文档

文档简介:

.. .. .. (2) 写出文法G’(S)的预测分析表。 解: (1)消除左递归,文法变为: S→aPS’| *aPS’ S’→ *aPS’ | ε P→+aP| +a 提取公共左因子,文法变为G’(S): S→aPS’| *aPS’ S’→ *aPS’ |ε P→+aP’ P’→P| ε (2)计算每个非终结符的FIRST集和FOLLOW集: FIRST(S) = {a, *} FIRST(S’) = {*, ε} FIRST(P) = {+}

× 游客快捷下载通道(下载后可以自由复制和排版)
单篇付费下载
限时特价:10 元/份 原价:20元
VIP包月下载
特价:29 元/月 原价:99元
低至 0.3 元/份 每月下载150
全站内容免费自由复制
VIP包月下载
特价:29 元/月 原价:99元
低至 0.3 元/份 每月下载150
全站内容免费自由复制
注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信:fanwen365 QQ:370150219
Copyright © 云题海 All Rights Reserved. 苏ICP备16052595号-3 网站地图 客服QQ:370150219 邮箱:370150219@qq.com