编译原理自顶向下语法分析方法.pptxVIP

第四章

自顶向下语法分析方法

学习目标:掌握：LL(1)文法的判别，预测分析法，递归子程序的构造方法理解：LL（1）文法了解：不确定的自顶向下分析

语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子语法分析自顶向下分析自底向上分析确定的不确定的算法优先分析（第六章）LR分析（第五章）自顶向下基本思想: 从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子.分类:

从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。1定义:将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。2语法树的构造：选定产生式3自上而下分析的主要问题回顾——自上而下的分析方法

例文法G：S→cAd

A→ab

A→a

识别输入串w=cabd是否为该文法的句子ScAdab=cabdS=cAd回顾——自上而下的分析方法ScAda成功不成功=cadS=cAd

确定的自顶向下分析思想010102030405LL(1)文法的判别某些非LL(1)文法到LL(1)文法的等价变换不确定的自顶向下分析思想确定的自顶向下分析方章内容

确定分析的条件开始符号集FIRST(α)的定义后跟符号集FOLLOW(A)的定义选择集合SELECT(A→α)的定义LL(1)文法的定义4.1确定的自顶向下分析思想

1.确定分析的条件从文法的开始符出发，如能根据当前的输入符号（单词符号）唯一地确定选用哪个产生式进行推导，则分析是确定的。

例1设有文法G1[S]: S→pA|qB A→cAd|a B→dB|b 若输入串W=pccadd。自顶向下的推导过程为:SSApcAdcAda=pA=pcAd=pccAdd=pccaddG1[S]有如下特点：(1)每个产生式的右部由终结符开头;(2)同一非终结符的不同产生式的右部由不同的终结符开头。对于这种文法，在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导，即分析过程是确定的。

例2：设有文法G2[S]为:S→Ap|BqA→a|cAB→b|dBpAScAcAa=ccapS=cAp=ccAp=Ap该例说明，当(1)产生式右部以终结符或非终结符开头（无空产生式）；(2)同一非终结符的不同产生式的右部由不同的符号开头。若输入串W=ccap,自顶向下的推导过程为：对于这种文法，在推导过程选用哪个产生式不直观，关键是判断产生式右部推出的开始符号（集），分析过程可能是确定的

例3：设有文法G3[S]S→aA|dA→bAS|ε若输入串W=abd，自顶向下的推导过程为：AaSbSAεd=abdS=abAS=abS文法的特点——包含空产生式=aA对于空产生式左部的非终结符，关键是判断该非终结符的后跟符号（集），分析过程可能是确定的。

要进行确定的自顶向下的分析，文法要满足一定的限制——即文法是LL(1)文法先研究三个定义开始符号集FIRST后跟符号集FOLLOW选择集合SELECT

2.开始符号集FIRST(?)的定义A定义:设G=(VN,VT,P,S)是上下文无关文法，Bα→β(α∈VN,??(VN?VT)*)CFIRST(?)={a|a?VT且??*a......}D（若??*ε则规定ε∈FIRST(?)）E直观上说文法符号串?的开始符号集是由?推导出的所有的终结符开头和可能的ε组成。

例文法G2[S]:S→ApS→BqA→aA→cAB→bB→dBFIRST(Ap)={a,c}FIRST(Bq)={b,d}FIRST(a)={a}FIRST(cA)={c}FIRST(b)={b}FIRST(dB)={d}结论一针对无空产生式的文法G，同一非终结符的任两个产生式的右部串的First集无交集，即可进行确定的自顶向下分析。

3.后跟符号集FOLLOW(A)的定义定义 设G=(VT,VN,P,S)是上下文无关文法，B→xAy(A,B∈VNx,y∈(VN?VT)*) FOLLOW(A)={a|S=*…Aa…，a∈VT}， 若有S=*…A，则规定#∈FOLLOW(A) （注：#输入串#，‘#’做为输入串的结束符） 直观上说,非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括#）组成。

[例]文法G3[S]:S→aA|dA→bAS|εFOLLOW(A)FOLLOW(S)由S=aA=abAS=abbASS=abbASaA得a∈FOLLOW(S)…=abbASd