清华编译原理课件

《编译原理》自顶向下（Top-Down）语法分析第四讲《编译原理》基本思想自顶向下预测分析LL(1)分析自顶向下语法分析带回溯的自顶向下分析文法变换：消除左递归、提取左公因子LL(1)分析中的出错处理《编译原理》基本思想−核心问题：句型分析对任意上下文无关文法G=(V，T，P，S)和任意w∈T*，是否有w∈L(G)？若成立，则给出分析树或（最左）推导步骤；否则，进行报错处理。−两种实现途径自顶向下（top-down）分析自底向上（bottom-up）分析语法分析《编译原理》−从文法开始符号出发进行推导；每一步推导都获得文法的一个句型；直到产生出一个句子，恰好是所期望的终结符串−每一步推导是对当前句型中剩余的某个非终结符进行扩展，即用该非终结符的一个产生式的右部替换该非终结符−如果不存在任何一个可以产生出所期望的终结符串的推导，则表明存在语法错误自顶向下分析思想基本思想《编译原理》自顶向下分析举例S（S→AB）⇒AB（A→aA）⇒aAB（B→b）⇒aAb（A→aA）⇒aaAb（A→aA）⇒aaaAb（A→ε）⇒aaab文法G（S）:S→ABA→aA|εB→b|bB−单词序列aaab的一个自顶向下分析过程基本思想《编译原理》−两类非确定性在每一步推导中，选择对哪一个非终结符、哪一个产生式都可能是非确定的分析成功的结果：得到一个推导一般方法带回溯的自顶向下分析《编译原理》举例S（1）⇒AB（2）⇒aAB（5）⇒aAbB（2）⇒aaAbB（2）⇒aaaAbB（3）⇒aaabB（回溯）……复杂度很高失败条件较复杂文法G（S）:（1）S→AB（2）A→aA（3）A→ε（4）B→b（5）B→bB−单词序列aaab的一个自顶向下分析过程带回溯的自顶向下分析《编译原理》−仅有产生式选择是非确定的在每一步推导中，总是对最左边的非终结符进行替换，但选择哪一个产生式是非确定的分析成功的结果：得到一个最左推导原理：每个合法的句子都存在至少一个起始于开始符号的最左推导；一个终结符串，只要存在一个起始于开始符号的最左推导，它就是一个合法的句子从左向右扫描输入单词，失败条件较简单改进的方法带回溯的自顶向下分析《编译原理》改进的方法举例S（1）⇒AB（2）⇒aAB（3）⇒aB（回溯）⇐aAB（2）⇒aaAB（2）⇒aaaAB（3）⇒aaaB（5）⇒aaabB（回溯）⇐aaaB（4）⇒aaab（成功）文法G（S）:（1）S→AB（2）A→aA（3）A→ε（4）B→b（5）B→bB−单词序列aaab的一个自顶向下分析过程带回溯的自顶向下分析复杂度降低失败条件简化《编译原理》−非终结符选择和产生式选择都是确定的在每一步推导中，总是对最左边的非终结符进行展开，且选择哪一个产生式是确定的，因此是一种无回溯的方法从左向右扫描，可能向前查看（lookahead）确定数目的单词分析成功的结果：得到唯一的最左推导分析条件：对文法需要有一定的限制确定的自顶向下分析自顶向下预测分析《编译原理》举例（向前查看2个单词）S（1）⇒AB（2）⇒aAB（2）……⇒anAB（3）⇒anB（5）⇒anbB（5）……⇒anbm-1B（4）⇒anbm（成功）文法G（S）:（1）S→AB（2）A→aA（3）A→ε（4）B→b（5）B→bB−单词序列anbm（n≥0,m0）的预测分析过程只要向前查看2个单词，就可预测分析L(G)中所有句子自顶向下预测分析《编译原理》左递归带来的问题文法G（S）:（1）S→Sa（2）S→b−考虑下列文法识别ban的分析过程S（1）⇒Sa（1）⇒Saa（1）⇒Saaa（1）……⇒San（2）⇒ban但是：无论向前查看的单词数确定为多少，都无法满足预测分析L(G)中所有句子的需求需要向前查看n+2个单词，才能确定这样的推导序列自顶向下预测分析《编译原理》要求文法不含左递归−例：直接左递归−可以通过文法变换消除左递归专门讨论−例：间接左递归P→PaP→b……P→AaA→Pb……自顶向下预测分析《编译原理》左公因子带来的问题文法G（S）:S→abA⏐abBA→aB→b−如下文法需要向前查看3个单词来预测分析L(G)中的句子文法G（S）:S→aAb⏐aAcA→a⏐aA−对于如下文法无法确定需要向前查看多少个单词来预测分析L(G)中的句子自顶向下预测分析《编译原理》通常要求文法不含左公因子−可以通过文法变换消除左公因子专门讨论自顶向下预测分析《编译原理》应用较普遍的自顶向下预测分析是LL（1）分析−要求文法一定是LL（1）文法专门讨论自顶向下预测分析《编译原理》−第一个“L”,代表从左（Left）向右扫描单词−第二个“L”,代表产生的是最左（Leftmost）推导−“1”代表向前查看（lookahead）一个单词LL（1）的含义LL（1）分析《编译原理》−要求文法是LL（1）的−什么是LL（1）文法？先引入两个重要概念对文法的限制LL（1）分析《编译原理》−First集合−Follow集合两个重要概念LL（1）分析《编译原理》−定义设G=（VT，VN，P，S）是上下文无关文法对α∈(VT∪VN)*，First（α）={a⏐α⇒*aβ,a∈VT,β∈(VT∪VN)*,或者α⇒*ε时a=ε}或者First（α）={a⏐αlm⇒*aβ,a∈VT,β∈(VT∪VN)*,或者αlm⇒*ε时a=ε}First集合LL（1）分析《编译原理》计算First集合LL（1）分析对所有x∈VN∪VT∪{ε}∪{v⏐A→u∈P,且v是u的后缀},则−对x∈VΤ∪{ε}，置First(x)={x}；对其它x，置First(x)=Φ−重复如下过程，直到所有First集合没有变化为止：(1)对于A→ε∈P，置First(A)=First(A)∪{ε}.(2)对于Y1Y2…YK∈{v⏐A→u∈P,且v是u的后缀},其中k≥1，Yj∈VN∪VΤ（1≤j≤k）,若∀j:1≤j≤i-1(ε∈First(Yj))∧ε∉First(Yi),其中1≤i≤k，则令First(Y1Y2…YK)=∪First(Yj)−{ε}否则，若∀j:1≤j≤k(ε∈First(Yj)),则令First(Y1Y2…YK)=∪First(Yj).(3)若有A→Y1Y2…YK∈P，则置First(A)=First(A)∪First(Y1Y2…YK).j=1ij=1k《编译原理》例：计算First集合文法G（S）:（1）S→AB（2）A→Da⏐ε（3）B→cC（4）C→aADC⏐ε（5）D→b⏐εFirst(a)={a}First(b)={b}First(c)={c}First(ε)={ε}LL（1）分析First(S)={}First(A)={}First(B)={}First(C)={}First(D)={}First(AB)={}First(Da)={}First(cC)={}First(aADC)={}《编译原理》例：计算First集合(续)文法G（S）:（1）S→AB（2）A→Da⏐ε（3）B→cC（4）C→aADC⏐ε（5）D→b⏐εFirst(a)={a}First(b)={b}First(c)={c}First(ε)={ε}LL（1）分析First(S)={}First(A)={ε}First(B)={}First(C)={ε}First(D)={ε}First(AB)={}First(Da)={}First(cC)={}First(aADC)={}《编译原理》例：计算First集合(续)文法G（S）:（1）S→AB（2）A→Da⏐ε（3）B→cC（4）C→aADC⏐ε（5）D→b⏐εFirst(a)={a}First(b)={b}First(c)={c}First(ε)={ε}LL（1）分析First(S)={}First(A)={ε}First(B)={}First(C)={ε}First(D)={ε}First(AB)={}First(Da)={a}First(cC)={c}First(aADC)={a}《编译原理》例：计算First集合(续)文法G（S）:（1）S→AB（2）A→Da⏐ε（3）B→cC（4）C→aADC⏐ε（5）D→b⏐εFirst(a)={a}First(b)={b}First(c)={c}First(ε)={ε}LL（1）分析First(S)={}First(A)={ε,a}First(B)={c}First(C)={ε,a}First(D)={ε,b}First(AB)={}First(Da)={a}First(cC)={c}First(aADC)={a}《编译原理》例：计算First集合(续)文法G（S）:（1）S→AB（2）A→Da⏐ε（3）B→cC（4）C→aADC⏐ε（5）D→b⏐εFirst(a)={a}First(b)={b}First(c)={c}First(ε)={ε}LL（1）分析First(S)={}First(A)={ε,a}First(B)={c}First(C)={ε,a}First(D)={ε,b}First(AB)={a,c}First(Da)={a,b}First(cC)={c}First(aADC)={a}《编译原理》例：计算First集合(续)文法G（S）:（1）S→AB（2）A→Da⏐ε（3）B→cC（4）C→aADC⏐ε（5）D→b⏐εFirst(a)={a}First(b)={b}First(c)={c}First(ε)={ε}LL（1）分析First(S)={a,c}First(A)={ε,a,b}First(B)={c}First(C)={ε,a}First(D)={ε,b}First(AB)={a,c}First(Da)={a,b}First(cC)={c}First(aADC)={a}《编译原理》例：计算First集合(续)文法G（S）:（1）S→AB（2）A→Da⏐ε（3）B→cC（4）C→aADC⏐ε（5）D→b⏐εFirst(a)={a}First(b)={b}First(c)={c}First(ε)={ε}LL（1）分析First(S)={a,c}First(A)={ε,a,b}First(B)={c}First(C)={ε,a}First(D)={ε,b}First(AB)={a,b,c}First(Da)={a,b}First(cC)={c}First(aADC)={a}《编译原理》例：计算First集合(续)文法G（S）:（1）S→AB（2）A→Da⏐ε（3）B→cC（4）C→aADC⏐ε（5）D→b⏐εFirst(a)={a}First(b)={b}First(c)={c}First(ε)={ε}LL（1）分析First(S)={a,b,c}First(A)={ε,a,b}First(B)={c}First(C)={ε,a}First(D)={ε,b}First(AB)={a,b,c}First(Da)={a,b}First(cC)={c}First(aADC)={a}《编译原理》−定义设G=（VT，VN，P，S）是上下文无关文法，对每个A∈VN，Follow(A)={a⏐S#⇒*αAβ#且a∈First(β#)，α,β∈(VT∪VN)*}（#代表输入单词序列右边的结束符）Follow集合LL（1）分析《编译原理》计算Follow集合−置Follow(S)={#}，置所有其它的Follow集合为∅；−重复如下步骤，直至所有Follow集不再变化为止：对于A→αBβ∈P，把First(β)−{ε}加至Follow(B);若有ε∈First(β)，则把Follow(A)加至Follow(B)中．LL（1）分析《编译原理》例：计算First和Follow集合文法G（S）:（1）S→AB（2）A→Da⏐ε（3）B→cC（4）C→aADC⏐ε（5）D→b⏐εFirst(B)={c}First(ε)={ε}First(a)={a}First(DC)={b,a,ε}First(C)={a,ε}Follow(S)={#}LL（1）分析F