编译原理(第二版)第5章 自顶向下语法分析方法.ppt

《编译原理(第二版)第5章 自顶向下语法分析方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章自顶向下语法分析方法教学要求：本章介绍编译程序的第二个阶段语法分析的设计方法和实现原理，包括自上而下分析的无回朔的递归下降分析、LL(1)分析法。要求理解递归下降分析、LL(1)文法的基本概念；掌握LL(1)分析表的构造与分析方法。教学重点：预测分析表构造，LL(1)文法。5.1确定的自顶向下分析思想文法G1[S]:S→pAS→qBA→cAdA→aB→dBB→bW=pccadd自顶向下的推导过程：SpApcAdpccAddpccadd语法树：SpAcAdcAda确定的自顶向下分析1、基本思想：从识别符出发，不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的

2、符号串。2、遇到问题:（1）回溯（出现若干个左部相同的产生式）（2）无限循环（文法出现左递归）3、解决方法：（1）避免回溯（2）消除左递归为了避免回溯,先研究三个定义：符号串α的开始符号FIRST集非终结符A后跟符号FOLLOW集产生式的选择集合SELECT集定义：设G=(VT,VN,S,P)是上下文无关文法，FIRST(α)={a

3、αaβ,a∈VT,α,β∈V*}若αε，则规定ε∈FIRST(α)**1、符号串α的开始符号FIRST集的定义：FIRST(Ap)={a,c}FIRST(Bq)={b,d}文法G2[S]:S→ApS→BqA→aA→cAB→bB→dB2、非终结符A后跟符号FO

4、LLOW集的定义：定义：设G=(VT,VN,S,P)是上下文无关文法，A∈VN,S是开始符号。FOLLOW(A)={a

5、S…Aa…,a∈VT}若S…A，则规定#∈FOLLOW(A)**#作为输入串的结束符，或称为句子括号，如：#输入串#3、产生式A→α的选择集合SELECT的定义：（确定选择那个产生式来推导）定义：给定上下文无关文法的产生式A→α，A∈VN,α∈V*，若αε，则SELECT(A→α)=FIRST(α)如果αε，则SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)**例：S→aAS→dA→εA→bASSELECT(S→aA)=FIRST(aA)={

6、a}SELECT(S→d)=FIRST(d)={d}SELECT(A→ε)=FOLLOW(A)={a，d，#}SELECT(A→bAS)=FIRST(bAS)={b}定义：一个上下文无关文法是LL(1)文法的充要条件是：对每个非终结符A的任两个不同产生式A→α和A→β，满足SELECT(A→α)∩SELECT(A→β)=Φ其中α,β不能同时ε*LL(1)文法的含义：第一个L表示：自顶向下分析是从左向右扫描输入串。第二个L表示：分析过程中将用最左推导。1表示：只需向右看一个符号便可决定如何推导（即选择哪个产生式进行推导）。类似也可以有LL(K)文法：需向前查看K个符号才可确定选用哪个产生式。

7、文法G[S]是否是LL(1)文法:S→aAS→dA→bASA→εSELECT(S→aA)={a}SELECT(S→d)={d}SELECT(A→bAS)={b}SELECT(A→ε)={a,d,#}SELECT(S→aA)∩SELECT(S→d)={a}∩{d}=ΦSELECT(A→bAS)∩SELECT(A→ε)={b}∩{a,d,#}=Φ所以该文法是LL(1)文法。例：文法G[S]为:S→aASS→bA→bAA→ε则：SELECT(S→aAS)={a}SELECT(S→b)={b}SELECT(A→bA)={b}SELECT(A→ε)={a,b}SELECT(S→aAS)∩SELECT(

8、S→b)={a}∩{b}=ΦSELECT(A→bA)∩SELECT(A→ε)={b}∩{a,b}≠Φ所以该文法不是LL(1)文法。5.2LL(1)文法的判别求出能推出ε的非终结符计算FIRST集计算FOLLOW集计算SELECT集判别是否是LL(1)文法例：设文法G[S]为:S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c判断它是否是LL(1)文法。1.求出能推出的非终结符S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c能推出的非终结符为：A，B，SS→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→cFIRST(S)={a,b

9、,ε}FIRST(A)={b,ε}FIRST(B)={a,ε}FIRST(C)={a,b,c}FIRST(D)={a,c}FIRST(AB)={a,b,ε}FIRST(AD)={a,b,c}2.计算FIRST集3.计算FOLLOW集(1)对于文法的开始符号S,置#于FOLLOW(S)中;(2)若Ａ→αBβ是一个产生式,则把FIRST(β)-{}加至FOLLOW(B)中;*若β(即FIRST(β)），