递归下降分析法实现LL(1)文法的语法分析器_语法分析实验 - CSDN文库

语法分析器

5星 · 超过95%的资源需积分: 22 93 浏览量更新于2023-06-13 2 收藏 70KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

递归下降分析法实现 LL(1)文法的语法分析器

作者:余洪周nickhome@163.com 转贴请注明出自: nick19842000.cublog.cn



实验题目：编程识别由下列文法所定义的表达式的递归下降语法分析器。

 EàE+T | E-T | T

 TàT*F | T/F |F

  Fà(E) | i

 输入：每行含一个表达式的文本文件。

输出：分析成功或不成功信息。

 (题目来源：编译原理实验(三)--预测(LL(1))分析法的实现)

解答:



（1）分析

a) ∵E=>E+T=>E+T*F=>E+T*(E)即有 E=>E+T*(E)存在左递归。用直接

改写法消除左递归，得到如下：

E à TE’

E’ à +TE’ | −TE’|ε

T à FT’

T’ à *FT’ | /FT’|ε

F à (E) | i

b) 对于以上改进的方法。可得：

对于 E’: FIRST( E’ )=FIRST(+TE’)∪FIRST(-TE’)∪{ε}={+，−，ε}

对于 T’: FIRST( T’ )=FIRST(*FT’)∪FIRST(/FT’)∪{ε}={*，∕，ε}

而且： FIRST( E ) = FIRST( T ) =

FIRST( F )=FIRST((E))∪FIRST(i)={(，i }

由此我们容易得出各非终结符的 FOLLOW 集合如下：

FOLLOW( E )= { )，#}

FOLLOW(E’)= FOLLOW(E)={ )，#}

FOLLOW( T )= FIRST(E’)\ε∪FOLLOW(E’)={+，−，)，#}

FOLLOW( T’ ) = FOLLOW( T ) ={+，−，)，#}

FOLLOW( F )=FIRST(T’)\ε∪FOLLOW(T’)={*，∕，+，−，)，#}

由以上 FOLLOW 集可以我们可以得出 SELECT 集如下：

对 E SELECT（EàTE’）=FIRST(TE’)=FIRST(T)={ (，i }

对 E’ SELECT（E’ à+TE’）={ + }

 SELECT（E’ à −TE’）={ − }

 SELECT（E’ àε）={ε，)，#}

对 T SELECT（TàFT’）={(，i}

对 T’ SELECT（T’ à*FT’）={ * }

SELECT（T’ à ∕FT’）={ ∕ }

SELECT（T’ àε）={ε，+，−，)，#}

对 F SELECT（Fà(E) ）={ ( }

SELECT（Fài）={ i }

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余6页未读，立即下载

wang_alfred

粉丝: 0
资源: 4

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈