资源描述：
《编译原理 第五章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第5章自顶向下语法分析方法语法分析是编译程序的核心部分，其作用是识别由词法分析给出的单词符号序列是否为给定文法的正确句子，目前常用的语法分析方法有两大类：l自顶向下分析：也称面向目标的分析方法，也就是从文法的开始符出发，试图推导出与输入单词串相匹配的句子，分为确定的自顶向下分析和不确定的自顶向下分析两种，常用的有递归子程序法和LL分析法。l自底向上分析：也称移进—归约分析方法，从输入单词串开始，试图归约到文法的开始符。分为算符优先分析和LR分析。（第6、7章讲述）第5章自顶向下语法分析方法5.1确定的自顶
2、向下分析思想5.2LL（1）文法的判别5.3某些非LL（1）文法到LL（1）文法的等价变换5.4不确定的自顶向下分析思想5.5确定的自顶向下分析方法5.5.1递归子程序法5.5.2预测分析法5.1确定的自顶向下分析思想思想从文法的开始符出发，根据当前的输入符号，确定选用哪个产生式替换相应非终结符往下推导。若输入串是给定文法的句子，则必能推出，否则出错。例5.1G1[S]：S→pA
3、qBA→cAd
4、a分析输入串W=pccadd自顶向下推导过程：S＝〉pA＝〉pcAd＝〉pccAdd＝〉pccadd分析输入串
5、W=pccadd自顶向下推导过程：S＝〉pA＝〉pcAd＝〉pccAdd＝〉pccaddSpA=〉SpdAcA=〉AcSpdAcAda=〉AcSpdAcAd可以根据当前的输入符号决定选择哪个产生式往下推导，分析过程是唯一确定的。例5.2G2[S]：S→Ap
6、BqA→a
7、cAB→b
8、dB分析输入串W=ccap自顶向下推导过程：S＝〉Ap＝〉cAp＝〉ccAp＝〉ccapFIRST(Ap)={a,c},FIRST(Bq)={b,d}（下面定义）对同一非终结符（S）的不同的产生式右部，并且它们以非终结符开始，在
9、推导过程中选用哪个产生，要看它们的开始符号集合是什么。l对一个文法符号串的开始符号集合定义如下：定义5.1设G=（VN，VT，P，S）是上下文无关文法，FIRST（α）={a
10、α＝〉aβ,a∈VT，α,β∈V*}若α＝〉ε，则规定ε∈FIRST（α）**例5.3G[S]:S→aA
11、dA→bAS
12、εw=abd的分析过程。自顶向下推导过程：S＝〉aA＝〉abAS＝〉abS＝〉abd,FOLLOW(A)={#,a,d}（下面定义）当非终结符有不同的产生式右部，且有ε产生式时，选择产生式进行匹配要看该非终结符的后
13、跟符号集合。l定义一个文法符号的后跟符号集合如下：定义5.2设G=（VN，VT，P，S）是上下文无关文法，A∈VN，S是开始符FOLLOW(A)={a
14、S＝〉μAβ,a∈VT，a∈FIRST(β),μ∈V*,β∈V+}若S＝〉μAβ,且β＝〉ε，则#∈FOLLOW(A)****也可定义为FOLLOW(A)={a
15、S＝〉...Aa....，a∈VT}若有S＝〉...A，则规定#∈FOLLOW(A)用‘#’作为输入串的结束符，或称为句子括号，如：#输入串#*l定义一个产生式的选择集合如下：定义5.3选择集合S
16、ELECT给定上下文无关文法的产生式A→α,A∈VN，α∈V*，如果α＝〉ε,则SELECT（A→α）=FIRST（α），如果α＝〉ε,则SELECT（A→α）=FIRST（α）{ε}∪FOLLOW(A)**定义5.4一个上下文无关文法是LL（1）文法的充分必要条件是，*每个非终结符的两个不同产生式A→α，A→β，满足：SELECT（A→α）∩SELECT（A→β）=Φ，其中α、β不能同时＝〉ε或者：一个上下文无关文法是LL（1）文法，当且仅当同一非终结符的各个产生式的可选集互不相交。LL（1）文法的含
17、义：第一个L表明自顶向下分析是从左向右扫描输入串；第二个L表示分析过程中将用最左推导，1表示只需向右看一个符号便可决定选择哪个产生式进行推导。类似也可以有LL（k）文法，一般k=1，2例5.4设文法G[S]为：S→aAS
18、bA→bA
19、ε则SELECT（S→aAS）={a}SELECT（S→b）={b}SELECT（A→bA）={b}SELECT（A→ε）=FOLLOW（A）=FIRST（S）={a，b}因为：SELECT（S→aAS）∩SELECT（S→b）={a}∩{b}=ΦSELECT（A→bA）∩S
20、ELECT（A→ε）={b}∩{a，b}≠Φ所以，文法G[S]不是LL（1）文法。5.2LL（1）文法的判别例5.5G[S]:S→AB
21、bCA→b
22、εB→aD
23、εC→AD
24、bD→aS
25、c判别步骤：1．求出能推出ε的非终结符SABCD是是是否否假定所给文法是经过压缩的，即文法中不包含多余规则，说明判断LL（1）文法的步骤。2．计算FIRST集◆对每一文法符号X∈V，计算FIRST（X）（a）若X∈VT，则FIRST（X）={X}
