chap4-1自顶向下语法分析课件.ppt

《chap4-1自顶向下语法分析课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、检查由扫描器输出的单词符号序列是否符合该语言的文法——句子扫描器分析器语义处理单词符号分析树源程序分析器的输入：Token序列分析器的输出分析树出错处理分析方法自顶向下（递归下降、预测分析)自底向上（算符优先、LR分析器）第四章语法分析10/2/202114.1自顶向下的分析方法基本思想寻找输入符号串最左推导试图根据当前输入单词判断使用哪个产生式基本过程从根开始，按与最左推导相对应的顺序，构造输入符号串(Token)的分析树10/2/202121、重要概念推导:αＡβαγβ(依据：Ａ→γ)最左(Left-most)推导——最左分析左句型最左推导对应最右归约最右(Righ

2、t-most)推导——最右分析规范推导、规范句型（右句型）最右推导对应最左归约（规范归约）自顶向下语法分析要解决的问题是?10/2/20213候选式的确定给定文法S→cAdA→ab

3、a?句子cad是该文法定义语言的句子SScAdcAdaba产生式(候选式)的选择：当要进行关于某个语法变量的推导时，希望能够根据当前符号确定候选式。10/2/20214带回溯的自顶向下分析思想给定文法G[S]和输入串W,从S出发自顶向下构造语法树:若存在某条推导路径,使得S=>*W,则W语法正确;若尝试所有推导路径,都无法得到S=>*W,则W语法错误.不确定的自顶向下分析需作回溯,效率很低.1

4、0/2/202152.确定的自顶向下分析思想基本思想：每一步根据当前输入符号可唯一确定某条规则用于推导.由根向下构造语法树.构造最左推导.推导出的终结符是否与当前输入符匹配10/2/20216确定的自顶向下分析思想例1:S–>pA[1]

5、qB[2]A–>cAd[3]

6、a[4]输入串：Ｗ＝pccadd分析结论：Ｗ语法正确且分析过程的每一步都唯一原因：本文法的非终结符（Ｓ，Ａ）的候选都以终结符开头，且两两不同．Ｓ：p≠qA:c≠a10/2/20217例2:S–>Ap[1]

7、Bq[2]A–>a[3]

8、cA[4]B–>b[5]

9、dB[6]输入串：Ｗ＝ccap分析结论:Ｗ语法正确且

10、分析过程的每一步都唯一原因：本文法的A和B的候选以终结符开头，且两两不同．A：a≠cB:b≠d;并且对于S:FIRST（Ａp）∩FIRST(Bq)={a,c}∩{b,d}=定义：FIRST（）={a

11、=>*a,a∈VT,,∈V*}若=>*ε则规定ε∈FRIST()10/2/20218例3:S–>aA[1]

12、d[2]A–>bAS[3]

13、[4]输入串：Ｗ＝abd分析结论：W语法正确且分析过程的每一步都唯一原因：S：a≠dA:{b}∩FOLLOW（A）={b}∩{a,d}=定义：FOLLOW（A）={aS=>*A且a∈FRIST（），∈V*，∈V

14、+}10/2/20219我们希望：从左到右扫描输入串——寻找它的一个最左推导对于G的每个非终结符A的任何两个不同的候选式A→α

15、β1)FIRST(α)∩FIRST(β)=φ2)如果β*ε，则FISRT(α)∩FOLLOW(A)=φ——文法Ｇ是LL(1)的充要条件第一个L:从左到右扫描输入串第二个L:生成的是最左推导1:向前看一个输入符号10/2/2021103.LL(1)文法的判别1.对于A∈Vn,计算First(A)2.对于A∈Vn,计算Follow(A)3.对于A–>

16、β,计算FIRST()∩FIRST(β)FIRST(β)∩follow(A)(若=>*成立

17、)10/2/2021111.若Ａ=>*，则∈First(A)2.若A–>B…,则FIRST(A)=FIRST(A)∪(FIRST(B)-{ε})若A–>a…,则FIRST(A)=FIRST(A)∪{a}3.若A–>B…及A–>a…,且=>*，则类似于步骤2处理求FIRST(A)的算法10/2/202112FIRST(F)={（,id}FIRST(T)=FIRST(F)={（,id}FIRST(E)=FIRST(T)={（,id}FIRST(E')={+，ε}FIRST(T')={*,ε}FIRST(+)={+},FIRST(*)={*}FIRST(（)={（}

18、FIRST(）)={）}FIRST(id)={id}E→TE'E'→+TE’

19、εT→FT'T'→*FT’

20、εF→(E)

21、id例10/2/202113例:S–>AＢ

22、bCA–>

23、bB–>

24、aDC–>AD

25、bD–>aS

26、cNFirst(N)Sa,b,Ab,Ba,Ca,b,cDa,c10/2/202114求FOLLOW(A)的算法对于所有非终结符,重复进行以下计算1)将#加入到FOLLOW(S)#为句子的结束符2)若A→αBβ，则FOLLOW(B)=FOLLOW(B)∪FIRST(β)–{ε}3)如果A→αB或A→αBβ，