请选择 进入手机版 | 继续访问电脑版

语法分析

[复制链接]
唐少琼 发表于 2021-1-3 12:15:45 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
语法分析相关知识聚集

一、自上而下的分析(LL(1)文法)

  1. 主要面对的的两个问题:        1.左递归        2.回溯
复制代码
问题办理:

1.左递归
  1. a.直接左递归        例子:P->Pa|b        (将左递归变为右递归)        改写后的文法:P->bP',P'->aP'|ε                小训练:给定文法G(E):        E->E+T|T        T->T*F|F        F->(E)|i        答案见最后        b.        间接左递归                例子:给定文法G(S):                S->Qc|c                Q->Rb|b                R->Sa|a                                消除左递归的条件:                ·不含以ε为右部的产生式                ·不含回路(P-+>P,P颠末若干步推导,回到自身)                                改写后的文法:                第一次:                S->Qc|c                Q->Sab|ab|b                R->Sa|b                                第二次:                S->Sabc|abc|bc|c                Q->Sab|ab|b                R->Sa|b                                第三次:                S->abcS'|bcS'|cS'                S'->abcS'|ε                Q->Sab|ab|b                R->Sa|b                                第四次(去掉多余的表达式):                S->abcS'|bcS'|cS'                S'->abcS'|ε               
复制代码
2.回溯(略)
  1. [/code] 3.First聚集和Follow聚集
  2. [code]例:对于文法G(E)E->TE'E'->+TE'|εT->FT'T'->*FT'|εF->(E)|i a.First聚集 第一次遍历:first(E)={}first(E')={+,ε}first(T)={}first(T')={*,ε}first(F)={(,i}第二次遍历:first(E)={}first(E')={+,ε}first(T)={(,i}first(T')={*,ε}first(F)={(,i}第三次遍历:first(E)={(,i}first(E')={+,ε}first(T)={(,i}first(T')={*,ε}first(F)={(,i}第四次遍历:稳定,竣事b.Follow聚集规则:①. 设S为文法中开始符号,把{#}参加FOLLOW(S)中(这里“#”  为句子括号)。②. 若A→αBβ是一个产生式,则把FIRST(β)的非空元素参加  FOLLOW(B)中。如果β可以或许推导出ε则把FOLLOW(A)也参加FOLLOW(B)中。文法G(E)  E->TE'E'->+TE'|εT->FT'T'->*FT'|εF->(E)|ifirst(E)={(,i}                                                  first(E')={+,ε}first(T)={(,i}first(T')={*,ε}first(F)={(,i} Follow(E)={#,)}Follow(E')={#,)}Follow(T)={+,#,)}Follow(T')={+,#,)}Follow(F)={*,+,#,)}网上答案详解:FOLLOW集的求解:因为E是文法的识别符所以把#参加FOLLOW(E),又由规则F  →  (E) | i 得E的后跟符号),所以,FOLLOW(E)={ #,) };FOLLOW(E’)={ #,) }    ∵E → TE’   ∴FOLLOW(E)参加 FOLLOW(E’)FOLLOW(T)={+,),#}      ∵E'→ +TE’  ∴FIRST(E’)-{ε}参加FOLLOW(T); 又E’→ε,     ∴ FOLLOW(E’)参加FOLLOW(T)FOLLOW(T’)= FOLLOW(T)= {+,),#}      ∵T → FT’   ∴ FOLLOW(T)参加FOLLOW(T’)FOLLOW(F)={*,+,),#}    ∵T → FT’   ∴ FOLLOW(F)=FIRST(T’)-{ε} ; 又T’→ε ∴ FOLLOW(T)参加FOLLOW(F)
复制代码
4.select聚集求解
  1. 对于文法G(E)E->TE'E'->+TE'|εT->FT'T'->*FT'|εF->(E)|iFirst聚集:                               Follow聚集:first(E)={(,i}                                                          Follow(E)={#,)}first(E')={+,ε}                                                                Follow(E')={#,)}first(T)={(,i}                                                                Follow(T)={+,#,)}first(T')={*,ε}                                                                Follow(T')={+,#,)}first(F)={(,i}                                                                 Follow(F)={*,+,#,)}select聚集:select(E->TE')=(first(TE')-{ε})U(Follow(E))={+,(,i,#,)}select(E'->+TE')=first(+TE')={+}select(E'->ε)=(first(ε)-{ε})U(follow(E'))={#,)}select(T->FT')=(first(FT')-{ε})U(follow(T))={(,i,*,+,#,)}select(T'->*FT')=first(*FT')={*}select(T'->ε)=follow(T')={+,#,)}select(F->(E))=first((E))={(}select(F->i)=first(i)={i}LL(1)文法判断: ∵select(E'->+TE')        ∩ select(E'->ε)=ф    select(T'->*FT')  ∩ select(T'->ε)=ф   select(F->(E)) ∩ select(F->i)=ф∴此文法为LL(1)文法
复制代码
5.LL(1)分析表的构造 (根据select集举行构造)
()+*i#E->TE’->TE’->TE’->TE’->TE’E’->ε->+TE’->εT->FT’->FT’->FT’->FT’->FT’->FT’T’->*FT’F->(E)i二、自下而上的分析(LR分析法,以LR(0)为例)

例:
S->A
A->Ab|bBa
B->aAc|a|aAb
写出增广文法:
S’->S
S->A
A->Ab|bBa
B->aAc|a|aAb
写LR(0)的项

S->AA->AbA->bBaB->aAcB->aB->aAbS->·AA->·AbA->·bBaB->·aAcB->·aB->·aAbS->A·A->A·bA->b·BaB->a·AcB->a·B->a·AbA->Ab·A->bB·aB->aA·cB->aA·bA->bBa·B->aAc·B->aAb·画出LR(0)项目集规范族

S’->S(r1)
S->A(r2)
A->Ab(r3)
A->bBa(r4)
B->aAc(r5)
B->a(r6)
B->aAb(r7)

构造LR(0)分析表



来源:https://blog.csdn.net/weixin_44863759/article/details/112055358
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )