slide04自顶向下(Top-Down)语法分析

1、编译原理 自顶向下（自顶向下（Top-Down）语法分析）语法分析第四讲第四讲编译原理 基本思想基本思想 自顶向下预测分析自顶向下预测分析 LL(1) 分析分析自顶向下语法分自顶向下语法分析析 带回溯的自顶向下分析带回溯的自顶向下分析 文法变换：消除左递归、提取左公因子文法变换：消除左递归、提取左公因子 LL(1) 分析中的出错处理分析中的出错处理 LL(K) 文法的有关结论（选讲）文法的有关结论（选讲）编译原理基本思想基本思想- 核心问题核心问题：识别：识别（recognition）与与解析解析（parsing） 对任意对任意上下文无关文法上下文无关文法G = (V ，T ，P，S ) 和任

2、意和任意w T *，是否有，是否有w L(G)？ 若成立，若成立， 则给出分析树或（最左）推导步骤；否则，则给出分析树或（最左）推导步骤；否则， 进行报错处理。进行报错处理。- 两种实现途径两种实现途径 自顶向下（自顶向下（top-down）分析）分析 自底向上自底向上（bottom-up）分析分析 语法分析语法分析编译原理- 从文法从文法开始符号开始符号出发进行推导；每一步推导出发进行推导；每一步推导 都获得文法的一个都获得文法的一个句型句型；直到产生出一个；直到产生出一个句句 子子，恰好是所期望的终结符串，恰好是所期望的终结符串- 每一步推导是对当前句型中剩余的某个非终每一步推导是对当前句

3、型中剩余的某个非终 结符进行扩展，即用该非终结符的一个产生结符进行扩展，即用该非终结符的一个产生 式的右部替换该非终结符式的右部替换该非终结符- 如果不存在任何一个可以产生出所期望的终如果不存在任何一个可以产生出所期望的终 结符串的推导，则表明存在语法错误结符串的推导，则表明存在语法错误 自顶向下分析思想自顶向下分析思想基本思想基本思想编译原理 自顶向下分析举例自顶向下分析举例 S （ S AB） AB （A aA） aAB （ B b） aAb （A aA） aaAb （ A aA） aaaAb （ A ） aaab文法文法 G（S）: S AB A aA | B b | bB- 单词序列单

4、词序列 aaab 的一个自顶向下分析过程的一个自顶向下分析过程基本思想基本思想编译原理- 两类非确定性两类非确定性 在每一步推导中，选择对哪一个非终结符、在每一步推导中，选择对哪一个非终结符、 哪一个产生式都可能是非确定的哪一个产生式都可能是非确定的 分析成功的分析成功的结果结果：得到一个：得到一个推导推导 一般方法一般方法带回溯的自顶向下分析带回溯的自顶向下分析编译原理 举例举例 S （1） AB （2） aAB （5） aAbB （2） aaAbB （2） aaaAbB （3） aaabB （回溯回溯） 复杂度很高复杂度很高 失败条件较复杂失败条件较复杂文法文法 G（S）:（1）S AB（

5、2）A aA（3）A （4）B b（5）B bB- 单词序列单词序列 aaab 的一个自顶向下分析过程的一个自顶向下分析过程带回溯的自顶向下分析带回溯的自顶向下分析编译原理- 仅有产生式选择是非确定的仅有产生式选择是非确定的 在每一步推导中，总是对最左边的非终结符在每一步推导中，总是对最左边的非终结符 进行替换，但选择哪一个产生式是非确定的进行替换，但选择哪一个产生式是非确定的 分析成功的分析成功的结果结果：得到一个：得到一个最左推导最左推导 原理原理：每个合法的句子都存在至少一个起始：每个合法的句子都存在至少一个起始 于开始符号的最左推导；一个终结符串，只于开始符号的最左推导；一个终结符串，

6、只 要存在一个起始于开始符号的最左推导，它要存在一个起始于开始符号的最左推导，它 就是一个合法的句子就是一个合法的句子 从左向右扫描从左向右扫描输入单词，输入单词，失败条件较简单失败条件较简单 改进的方法改进的方法带回溯的自顶向下分析带回溯的自顶向下分析编译原理 改进的方法举例改进的方法举例 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- 单词序列单词序列

7、aaab 的一个自顶向下分析过程的一个自顶向下分析过程带回溯的自顶向下分析带回溯的自顶向下分析复杂度降低复杂度降低失败条件简化失败条件简化编译原理- 非终结符选择和产生式选择都是确定的非终结符选择和产生式选择都是确定的 在每一步推导中，总是对在每一步推导中，总是对最左最左边的边的非终结符非终结符 进行展开，且选择哪一个进行展开，且选择哪一个产生式产生式是是确定确定的，的， 因此是一种因此是一种无回溯无回溯的方法的方法 从左向右扫描，可能从左向右扫描，可能向前查看向前查看（lookahead） 确定数目的单词确定数目的单词 分析成功的分析成功的结果结果：得到：得到唯一的最左推导唯一的最左推导 分

8、析分析条件条件：对：对文法文法需要有一定的需要有一定的限制限制 确定的自顶向下分析确定的自顶向下分析自顶向下预测分析自顶向下预测分析编译原理 举例举例（向前查看（向前查看 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,0,m 0 0）的预测分析过程）的预测分析过程只要向前查看只要向前查看 2 个个单词，就可预测分单词，就可预测分析析L(G)中所有句子中所有句子

9、自顶向下预测分析自顶向下预测分析编译原理 左递归带来的问题左递归带来的问题文法文法 G（S）:（1）S Sa（2）S b- 考虑下列文法识别考虑下列文法识别 ban 的分析过程的分析过程 S （1） Sa （1） Saa （1） Saaa （1） San （2） ban但是：但是：无论向前查看的单词数确定为多少，无论向前查看的单词数确定为多少，都无法满足预测分析都无法满足预测分析L(G)中所有句子的需求中所有句子的需求需要向前查看需要向前查看n+2个单词，个单词，才能确定这样的推导序列才能确定这样的推导序列自顶向下预测分析自顶向下预测分析编译原理 要求要求文法不含左递归文法不含左递归- 例：例

10、：直接左递归直接左递归- 可以通过文法变换可以通过文法变换消除左递归消除左递归 专门讨论专门讨论- 例：例：间接左递归间接左递归P PaP bP AaA Pb自顶向下预测分析自顶向下预测分析编译原理 左公因子带来的问题左公因子带来的问题文法文法 G（S）: S abA abB A a B b- 如下文法需要向前查看如下文法需要向前查看3 3个单词来预测分析个单词来预测分析 L(G)中的句子中的句子文法文法 G（S）: S aAb aAc A a aA- 对于如下文法无法确定需要向前查看多少对于如下文法无法确定需要向前查看多少 个单词来预测分析个单词来预测分析 L(G) 中的句子中的句子自顶向下

11、预测分析自顶向下预测分析编译原理 通常要求通常要求文法不含左公因子文法不含左公因子- 可以通过文法变换可以通过文法变换消除左公因子消除左公因子 专门讨论专门讨论自顶向下预测分析自顶向下预测分析编译原理 应用较普遍的自顶向下预测分析是应用较普遍的自顶向下预测分析是 LL（1 1）分析）分析- 要求文法一定是要求文法一定是LL（1）文法文法 专门讨论专门讨论自顶向下预测分析自顶向下预测分析编译原理- 第一个第一个“L”, 代表从代表从左左（Left）向右扫描单词）向右扫描单词- 第二个第二个“L”, ,代表产生的是代表产生的是最左最左（Leftmost） 推导推导- “1”代表向前查看（代表向前查

12、看（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 = 或者或者

13、First（ ）= a lm* a , a VT, (VT VN)*, 或者或者 lm*时时 a = First 集合集合LL（1） 分析分析编译原理 计算计算 First 集合集合LL（1） 分析分析对所有对所有 x VN VT vAu P, 且且v是是u的后缀的后缀, 则则-对对 x V ，置，置 First(x)=x；对其它；对其它x，置，置 First(x)= -重复如下过程，直到所有重复如下过程，直到所有 First 集合没有变化为止：集合没有变化为止： (1) 对于对于 A P，置置 First(A) = First(A) . (2) 对于对于 Y1Y2YK vAu P, 且且v是

14、是u的后缀的后缀, 其中其中 k 1，Yj VN V （1 j k）, 若若 j:1 j i-1( First(Yj) First(Yi), 其中其中1 i k ，则令，则令 First(Y1Y2YK) = First(Yj) - - 否则，若否则，若 j:1 j k( First(Yj), 则令则令 First(Y1Y2YK) = First(Yj). (3) 若有若有 AY1Y2YK P，则置则置 First(A) = First(A) First(Y1Y2YK) .j=1ij=1k编译原理 例例：计算：计算 First 集合集合文法文法 G（S）:（1）S AB（2）A Da（3）B c

15、C（4）C aADC（5）D bFirst(a) = aFirst(b) = bFirst(c) = cFirst() = 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 bFirst(a) = aFirst(b) = bFirst(c) = cFirst()

16、= LL（1） 分析分析First(S) = First(A) = First(B) = First(C) = First(D) = , bFirst(AB) = First(Da) = First(cC) = First(aADC) = 编译原理 例例：计算：计算 First 集合集合( ( 续续) )文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC（5）D bFirst(a) = aFirst(b) = bFirst(c) = cFirst() = LL（1） 分析分析First(S) = First(A) = First(B) = First(C) = F

17、irst(D) = , bFirst(AB) = First(Da) = a, bFirst(cC) = c First(aADC) = a 编译原理 例例：计算：计算 First 集合集合( ( 续续) )文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC（5）D bFirst(a) = aFirst(b) = bFirst(c) = cFirst() = LL（1） 分析分析First(S) = First(A) = , a, bFirst(B) = cFirst(C) = a, First(D) = , bFirst(AB) = First(Da) = a,

18、 bFirst(cC) = c First(aADC) = a 编译原理 例例：计算：计算 First 集合集合( ( 续续) )文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC（5）D bFirst(a) = aFirst(b) = bFirst(c) = cFirst() = LL（1） 分析分析First(S) = First(A) = , a, bFirst(B) = cFirst(C) = a, First(D) = , bFirst(AB) = a, b, cFirst(Da) = a, bFirst(cC) = cFirst(aADC) = a编译

19、原理 例例：计算：计算 First 集合集合( ( 续续) )文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC（5）D bFirst(a) = aFirst(b) = bFirst(c) = cFirst() = LL（1） 分析分析First(S) = a, b, c First(A) = , a , bFirst(B) = cFirst(C) = a, First(D) = , bFirst(AB) = a, b, cFirst(Da) = a, bFirst(cC) = cFirst(aADC) = a编译原理- 定义定义 设设 G =（VT，VN，P，S

20、）是上下文无关文法，是上下文无关文法，对对 每个每个 A VN， Follow(A) = a S# * A # 且且 a First( #)， , (VT VN)* （# 代表输入单词序列右边的结束符）代表输入单词序列右边的结束符） Follow 集合集合LL（1） 分析分析编译原理 计算计算 Follow 集合集合-置置 Follow(S) = #，置所有其它的，置所有其它的 Follow 集合为集合为 ；-重复如下步骤，直至所有重复如下步骤，直至所有Follow集不再变化为止：集不再变化为止： 对于对于 AB P，把，把 First() - - 加至加至 Follow(B); 若有若有 F

21、irst()，则把，则把 Follow(A) 加至加至 Follow(B) 中中LL（1） 分析分析编译原理 例例：计算：计算 First 和和 Follow 集合集合文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC （5）D bFirst(B) = cFirst() = First(a) = aFirst(DC) = b, a, First(C) = a, Follow(S) = #LL（1） 分析分析Follow(A) = Follow(B) = Follow(C) = Follow(D) = 编译原理 例例：计算：计算 First 和和 Follow 集合

22、集合文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC （5）D bFirst(B) = cFirst() = First(a) = aFirst(DC) = b, a, First(C) = a, LL（1） 分析分析Follow(A) = cFollow(B) = # Follow(S) = #Follow(A) = Follow(B) = Follow(C) = Follow(D) = 编译原理 例例：计算：计算 First 和和 Follow 集合集合文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC （5）D bFirst(

23、B) = cFirst() = First(a) = aFirst(DC) = b, a, First(C) = a, LL（1） 分析分析Follow(D) = a Follow(S) = #Follow(A) = cFollow(B) = #Follow(C) = Follow(D) = 编译原理 例例：计算：计算 First 和和 Follow 集合集合文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC （5）D bFirst(B) = cFirst() = First(a) = aFirst(DC) = b, a, First(C) = a, LL（1）

24、分析分析Follow(C) = # Follow(S) = #Follow(A) = cFollow(B) = #Follow(C) = Follow(D) = a编译原理 例例：计算：计算 First 和和 Follow 集合集合文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC （5）D bFirst(B) = cFirst() = First(a) = aFirst(DC) = b, a, First(C) = a, LL（1） 分析分析Follow(A) = c,b,a, # Follow(S) = #Follow(A) = cFollow(B) = #F

25、ollow(C) = #Follow(D) = aFollow(D) = a, #编译原理 例例：计算：计算 First 和和 Follow 集合集合文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC （5）D bFirst(B) = cFirst() = First(a) = aFirst(DC) = b, a, First(C) = a, LL（1） 分析分析 Follow(S) = #Follow(A) = c,b,a, #Follow(B) = #Follow(C) = #Follow(D) = a, # 编译原理 定义：定义： 预测集合预测集合（Pred

26、ictive Set） 设设 G =（VT，VN，P，S）是上下文无关文法。是上下文无关文法。对任何产生式对任何产生式 A P，其预测集合，其预测集合 PS (A) 定义定义为：为：- 如果如果 first()，那么，那么 PS (A) = first ()；- 如果如果 first ()，那么，那么 PS (A) = ( first () ) follow(A) LL（1） 分析分析编译原理 定义：定义： LL（1）文法）文法文法文法 G 是是 LL（1）文法）文法，当且仅当对于，当且仅当对于 G 的每个非的每个非终结符终结符 A 的任何两个不同产生式的任何两个不同产生式 A，下面，下面的条

27、件成立：的条件成立： PS (A) PS (A) = LL（1） 分析分析编译原理 举例举例：验证如下文法验证如下文法 G（S）不是不是 LL（1）文法文法文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC （5）D bPS(ADa) = b,aPS(A) = c,b,a, #PS(CaADC) = aPS(C ) = #PS(Db) = bPS(D ) = a, #LL（1） 分析分析First(Da) = b, aFirst() = First(aADC) = aFirst(b) = bFollow(A) = c,b,a, #Follow(C) = #Foll

28、ow(D) = a, #PS(ADa) PS(A ) PS(C aADC ) PS(C ) = PS(Db) PS(D ) = 编译原理- 递归下降递归下降 LL（1）分析程序分析程序 每个非终结符对应一个分析子程序每个非终结符对应一个分析子程序 LL（1）分析的实现分析的实现- 表驱动表驱动 LL（1）分析程序分析程序 借助于借助于预测分析表预测分析表和一个和一个下推栈下推栈LL（1） 分析分析编译原理- 工作工作原理原理 每个非终结符都对应一个每个非终结符都对应一个子程序子程序。该子程序。该子程序 的行为根据语法描述来明确：根据下一个输的行为根据语法描述来明确：根据下一个输 入符号来确定按

29、照哪一个产生式进行处理，入符号来确定按照哪一个产生式进行处理， 再根据该产生式的右端，再根据该产生式的右端， 每遇到一个终结符，则判断当前读入的单词是否每遇到一个终结符，则判断当前读入的单词是否 与该终结符相匹配，若匹配，再读取下一个单词与该终结符相匹配，若匹配，再读取下一个单词 继续分析；不匹配，则进行出错处理继续分析；不匹配，则进行出错处理 每遇到一个非终结符，则调用相应的子程序每遇到一个非终结符，则调用相应的子程序 递归下降递归下降LL(1)分析程序分析程序递归下降递归下降 LL（1）分析程序分析程序编译原理- 例例 对于下列关于对于下列关于 function 的唯一产生式的唯一产生式

30、FUNC ID ( ) （，和和 是非终结符）是非终结符） 非终结符对应的递归下降非终结符对应的递归下降子子程序程序void ParseFunction() MatchToken(T_FUNC); /匹配匹配FUNC MatchToken(T_ID); /匹配匹配ID MatchToken(T_LPAREN); / 匹配匹配 （ ParseParameterList(); MatchToken(T_RPAREN); / 匹配匹配 ） ParseStatement();递归下降递归下降 LL（1）分析程序分析程序编译原理- 例例 续上页续上页 非终结符对应的递归下降非终结符对应的递归下降子子程序

31、程序void MatchToken(int expected) if (lookahead != expected) /判别当前单词是否与判别当前单词是否与 /期望的终结符匹配期望的终结符匹配 printf(syntax error n); exit(0); else / 若匹配若匹配,消费掉当前单词并读入下一个消费掉当前单词并读入下一个 lookahead = getToken(); /调用词法分析程序调用词法分析程序递归下降递归下降 LL（1）分析程序分析程序编译原理- 例例 对于下列文法对于下列文法 G(S): S AaS BbS d A a B c 递归下降递归下降LL(1)分析程序分

32、析程序举例举例PS(SAaS) = aPS(SBbS) = c,b PS(Sd) = dPS(Aa) = aPS(B) = bPS(Bc) = cFirst（AaS）= aFirst（BbS）= c,b First（d）= dFirst（a）= aFirst（ ）= First（c）= cFollow（S）= # Follow（A）= aFollow（B）= b递归下降递归下降 LL（1）分析程序分析程序PS(SAaS)，PS(SBbS) 以及以及 PS(Sd) 互不相交，互不相交， PS(B) 和和 PS(Sd)互不相交，互不相交，所以所以，G(S) 是是 LL(1) 文法文法编译原理- 一

33、般结构一般结构 设设 A 的产生式的产生式: A u1 u2 . un, 相对于非终结符相对于非终结符 A 的递归下降子程序的递归下降子程序 ParseA 的一般结的一般结 构如右图所示构如右图所示 非终结符对应的非终结符对应的 递归下降递归下降子子程序程序void ParseA() switch (lookahead) case PS(Au1): /* code to recognize u1 */ break; case PS(Au2): /* code to recognize u2 */ break; . case PS(Aun): /* code to recognize un */

34、 break; default: printf(syntax error n); exit(0); 递归下降递归下降 LL（1）分析程序分析程序编译原理- 接上接上例例 针对文法针对文法G(S)构造的递归下降分析程序构造的递归下降分析程序void ParseS( ) switch (lookahead) case a: ParseA( ); MatchToken(a); ParseS( ); break;G(S): S AaS BbS d A a B cPS(SAaS) = aPS(SBbS) = c,b PS(Sd) = d case b,c: ParseB( ); MatchToken(b

35、); ParseS( ); break; case d: MatchToken(d); break; default: printf(syntax error n) exit(0); 递归下降递归下降 LL（1）分析程序分析程序编译原理- 接上接上例例 针对文法针对文法G(S) 构造的递归下降分析程序构造的递归下降分析程序void ParseA( ) if (lookahead=a) MatchToken(a); else printf(syntax error n”); exit(0); PS(Aa) = aPS(B) = bPS(Bc) = cvoid ParseB( ) if (look

36、ahead=c) MatchToken(c); else if (lookahead=b) else printf(syntax error n”); exit(0); G(S): S AaS BbS d A a B c递归下降递归下降 LL（1）分析程序分析程序编译原理 实际应用中的推广实际应用中的推广 上面只讨论了根据普通文法构造递归下降分析程序。实上面只讨论了根据普通文法构造递归下降分析程序。实 际上，也可以将产生式右端扩展为更复杂的描述表达际上，也可以将产生式右端扩展为更复杂的描述表达 式，即除了文法符号之间的连接运算之外，还可以有选式，即除了文法符号之间的连接运算之外，还可以有选 择

37、、重复、任选以及优先括号等运算（如择、重复、任选以及优先括号等运算（如 EBNF 范式中范式中 的运算），以使语法描述更加简洁，分析程序更加高效的运算），以使语法描述更加简洁，分析程序更加高效 （比较：若将其展开为普通文法，则需要引入多个非终（比较：若将其展开为普通文法，则需要引入多个非终 结符，增加多个对应的子程序）。结符，增加多个对应的子程序）。- X1 | X1 | | Xm 多个成分之间的选择多个成分之间的选择- X 成分成分 X 的重复（的重复（0 到多次）到多次）- X 成分成分 X 的任选（的任选（0 或或 1 次）次）- ( X ) 成分成分 X 优先优先递归下降递归下降 LL

38、（1）分析程序分析程序编译原理 实际应用中的推广实际应用中的推广 将产生式右端扩展后，同样要求它的将产生式右端扩展后，同样要求它的 First 集合，以适集合，以适 应递归下降分析程序的构造方法。应递归下降分析程序的构造方法。- First（X1 | X2 | | Xm）= First（X1） First（Xm）- First（ X ）= First（X） - First（ X ）= First（X） - First（( X )）= First（X）递归下降递归下降 LL（1）分析程序分析程序编译原理 实际应用中的推广实际应用中的推广 将产生式右端扩展后，子程序的处理过程中需要针对不将产生式右

39、端扩展后，子程序的处理过程中需要针对不 同运算选择不同的语句形式（普通文法只有连接运算，同运算选择不同的语句形式（普通文法只有连接运算， 所以只对应顺序语句）。所以只对应顺序语句）。- X1 | X2 | | Xm 对应选择语句对应选择语句- X 对应循环语句对应循环语句- X 对应对应 If-Then 语句语句- ( X ) 对应复合语句对应复合语句- 可参考可参考 PL/0 编译器的语法分析程序编译器的语法分析程序递归下降递归下降 LL（1）分析程序分析程序编译原理- 工作工作原理原理 利用利用预测分析表预测分析表和一个和一个下推栈下推栈实现实现 初始时，下推栈只包含初始时，下推栈只包含#

40、；首先将文法开始符；首先将文法开始符 号入栈；之后依如下步骤：号入栈；之后依如下步骤：（1） 若栈顶为若栈顶为 终终 结符，则判断当前读入的单词是否与该终结符结符，则判断当前读入的单词是否与该终结符 相匹配，若匹配，再读取下一相匹配，若匹配，再读取下一 单词继续分析；单词继续分析； 不匹配，则进行出错处理；（不匹配，则进行出错处理；（2）若栈顶为非终）若栈顶为非终 结符，则根据该非终结符和当前输入单词查预测结符，则根据该非终结符和当前输入单词查预测 分析表，若相应表项中是产生式（唯一的），分析表，若相应表项中是产生式（唯一的）， 则将此非终结符出栈，并把产生式右部符号从则将此非终结符出栈，并把

41、产生式右部符号从 右至左入栈；若表项为空，则进行出错处理；右至左入栈；若表项为空，则进行出错处理； （3）重复（）重复（1）和（）和（2），直到栈顶为），直到栈顶为 # 同时输同时输 入也遇到结束符入也遇到结束符 # 时，分析结束时，分析结束 表驱动表驱动LL(1)分析程序分析程序表驱动表驱动 LL（1）分析程序分析程序编译原理- 表驱动分析程序需要的表驱动分析程序需要的二维表二维表M- 表的每一表的每一行行 A 对应一个对应一个非终结符非终结符- 表的每一表的每一列列 a 对应某个对应某个终结符终结符或输入结束符或输入结束符 # #- 表中的项表中的项 M(A,a) 表示栈顶为表示栈顶为A，

42、下一个输入符下一个输入符 号为号为a时，可选的时，可选的产生式集合产生式集合- 对于对于LL（1）文法，可以构造出一个）文法，可以构造出一个 M(A,a) 最最 多只包含一个产生式的预测分析表，可称之为多只包含一个产生式的预测分析表，可称之为 LL（1）分析表）分析表- M(A,a) 不含产生式时，对应一个出错位置不含产生式时，对应一个出错位置 预测分析表预测分析表表驱动表驱动 LL（1）分析程序分析程序编译原理 预测分析表的构造算法预测分析表的构造算法-对文法对文法 G 的每个产生式的每个产生式 A 执行如下步骤：执行如下步骤： 对每个对每个 a PS(A)，将，将 A 加入加入 MA,a-

43、把所有无定义的把所有无定义的 MA,a 标上标上“出错标志出错标志”可以证明可以证明: 一个文法一个文法 G 的预测分析表不含多重入的预测分析表不含多重入口，当且仅当该文法是口，当且仅当该文法是 LL(1) 的的表驱动表驱动 LL（1）分析程序分析程序编译原理 预测分析表的构造预测分析表的构造举例举例- 对于下列文法对于下列文法G(S)： S AaS BbS d A a B c可构造如下预测分析表：可构造如下预测分析表：SAaSSBbSSdAaBBcSBbS表驱动表驱动 LL（1）分析程序分析程序PS(SAaS) = aPS(SBbS) = c,b PS(Sd) = dPS(Aa) = aPS

44、(B) = bPS(Bc) = c编译原理 表驱动预测分析程序分析算法表驱动预测分析程序分析算法 初始时初始时#入栈，然后文法开始符号入栈；首个输入符号读进入栈，然后文法开始符号入栈；首个输入符号读进 a ； flag =TRUE； while (flag) do 栈顶符号栈顶符号出栈出栈并放在并放在X中；中； if (XVT) if (X=a) 把下一把下一个输入符号读进个输入符号读进a; else ERROR; else if (X=#） if (a=#) flag = FALSE; else ERROR; else if (MX,a = XX1X2Xk) Xk,XK-1,X1依次依次进栈

45、进栈; else ERROR; /*分析成功，过程完毕分析成功，过程完毕*表驱动表驱动 LL（1）分析程序分析程序编译原理 表驱动预测分析过程表驱动预测分析过程举例举例- 对于下列文法对于下列文法G(S)： S AaS BbS d A a B c 分析输入串分析输入串 aabd 的过程：的过程：#S剩余的输入串剩余的输入串 aabd#SAaSSBbSSdAaBBcSBbS表驱动表驱动 LL（1）分析程序分析程序编译原理 表驱动预测分析过程表驱动预测分析过程举例举例- 对于下列文法对于下列文法G(S)： S AaS BbS d A a B c 分析输入串分析输入串 aabd 的过程：的过程：#S

46、剩余的输入串剩余的输入串 aabd#aASAaSSBbSSdAaBBcSBbS表驱动表驱动 LL（1）分析程序分析程序编译原理 表驱动预测分析过程表驱动预测分析过程举例举例- 对于下列文法对于下列文法G(S)： S AaS BbS d A a B c 分析输入串分析输入串 aabd 的过程：的过程：#S剩余的输入串剩余的输入串 aabd#aaSAaSSBbSSdAaBBcSBbS表驱动表驱动 LL（1）分析程序分析程序编译原理 表驱动预测分析过程表驱动预测分析过程举例举例- 对于下列文法对于下列文法G(S)： S AaS BbS d A a B c 分析输入串分析输入串 aabd 的过程：的过

47、程：#S剩余的输入串剩余的输入串 abd#aSAaSSBbSSdAaBBcSBbS表驱动表驱动 LL（1）分析程序分析程序编译原理 表驱动预测分析过程表驱动预测分析过程举例举例- 对于下列文法对于下列文法G(S)： S AaS BbS d A a B c 分析输入串分析输入串 aabd 的过程：的过程：#S剩余的输入串剩余的输入串 bd#SAaSSBbSSdAaBBcSBbS表驱动表驱动 LL（1）分析程序分析程序编译原理 表驱动预测分析过程表驱动预测分析过程举例举例- 对于下列文法对于下列文法G(S)： S AaS BbS d A a B c 分析输入串分析输入串 aabd 的过程：的过程：

48、#剩余的输入串剩余的输入串 bd#SbBSAaSSBbSSdAaBBcSBbS表驱动表驱动 LL（1）分析程序分析程序编译原理 表驱动预测分析过程表驱动预测分析过程举例举例- 对于下列文法对于下列文法G(S)： S AaS BbS d A a B c 分析输入串分析输入串 aabd 的过程：的过程：#剩余的输入串剩余的输入串 bd#SbSAaSSBbSSdAaBBcSBbS表驱动表驱动 LL（1）分析程序分析程序编译原理 表驱动预测分析过程表驱动预测分析过程举例举例- 对于下列文法对于下列文法G(S)： S AaS BbS d A a B c 分析输入串分析输入串 aabd 的过程：的过程：#

49、剩余的输入串剩余的输入串 d#SSAaSSBbSSdAaBBcSBbS表驱动表驱动 LL（1）分析程序分析程序编译原理 表驱动预测分析过程表驱动预测分析过程举例举例- 对于下列文法对于下列文法G(S)： S AaS BbS d A a B c 分析输入串分析输入串 aabd 的过程：的过程：#剩余的输入串剩余的输入串 d#dSAaSSBbSSdAaBBcSBbS表驱动表驱动 LL（1）分析程序分析程序编译原理 表驱动预测分析过程表驱动预测分析过程举例举例- 对于下列文法对于下列文法G(S)： S AaS BbS d A a B c 分析输入串分析输入串 aabd 的过程：的过程：#剩余的输入串

50、剩余的输入串 #SAaSSBbSSdAaBBcSBbS表驱动表驱动 LL（1）分析程序分析程序编译原理- LL(1) 文法通常不含左递归和左公因子文法通常不含左递归和左公因子- 许多文法在消除左递归和提取左公因子后可许多文法在消除左递归和提取左公因子后可 以变换为以变换为LL(1)文法文法- 但不含左递归和左公因子的文法不一定都是但不含左递归和左公因子的文法不一定都是 LL(1)文法文法 文法变换：消除左递归、提取左公因子文法变换：消除左递归、提取左公因子文法变换文法变换编译原理文法变换：消除左递归文法变换：消除左递归 左递归消除规则左递归消除规则-消除直接左递归消除直接左递归 对形如对形如

51、P P 的产生式，其中的产生式，其中非非 ， 不以不以 P 打头，打头， 可改写为：可改写为： P Q Q Q 其中其中Q为新增加的非终结符为新增加的非终结符编译原理文法变换：消除左递归文法变换：消除左递归 左递归消除规则左递归消除规则-消除直接左递归消除直接左递归 对更一般的形如对更一般的形如 PP1 P2 Pm 1 2 n 的一组产生式，其中的一组产生式，其中i（1 i m）不为）不为 ，j（1 j n） 不以不以 P 打头，打头， 可改写为：可改写为： P1Q 2Q nQ Q 1Q 2Q mQ 其中其中Q为新增加的非终结符为新增加的非终结符编译原理文法变换：消除左递归文法变换：消除左递归

52、 左递归消除左递归消除举例举例原文法原文法 G E: E E T T T T F F F (E) a消除左递归后的文法消除左递归后的文法 G E: (1) E TE (2) E TE (3) E (4) T FT (5) T FT (6) T (7) F (E) (8) F a编译原理文法变换：消除左递归文法变换：消除左递归 左递归消除规则左递归消除规则-消除一般左递归消除一般左递归 对无回路对无回路(A A) 、无、无 -产生式的文法，通过下列步骤可消除产生式的文法，通过下列步骤可消除 一般左递归（包括直接和间接左递归）：一般左递归（包括直接和间接左递归）： （1）以某种顺序将文法非终结符排

53、列）以某种顺序将文法非终结符排列A1 ,A2 An （2）for i = 1 , n do for j=1,i-1 do 用用Ai 1 r 2r kr反复替代形如反复替代形如Ai Ajr的规则的规则, 其中其中Aj 1 2 k是关于是关于Aj的全部产生式的全部产生式; 消除消除Ai规则的直接左递归规则的直接左递归; （3）化简由（）化简由（2）得到的文法）得到的文法编译原理文法变换：消除左递归文法变换：消除左递归 左递归消除左递归消除举例举例原文法原文法 GS: S PQ a P QS b Q SP c非终结符排序为非终结符排序为 S、P、Q，按造消除一般左递归的方，按造消除一般左递归的方法，

54、进行如下变换法，进行如下变换:Q SP c结结果果：S PQ a P QS bQ bQPR aPR cRR SQPRQ PQP aP cQ QSQP bQP aP cQ bQPR aPR cRR SQPR编译原理文法变换：消除左递归文法变换：消除左递归 左递归消除左递归消除举例举例 原文法原文法 GS: S PQ a P QS b Q SP c 按造非终结符的另一种排序按造非终结符的另一种排序Q、P、S，依消除一般左，依消除一般左递归的方法，进行如下变换递归的方法，进行如下变换:P QS b结结果果 S cSQR bQR aR P SPS cS b Q SP c R PSQR P SPS cS

55、 bS PQ aS SPSQ cSQ bQ aS cSQR bQR aRR PSQR 编译原理文法变换：提取左公因子文法变换：提取左公因子 提取左公因子规则提取左公因子规则- 对形如对形如 P 的一对产生式，可用如下三个产生式替换：的一对产生式，可用如下三个产生式替换： P Q Q 其中其中Q为新增加的未出现过的非终结符为新增加的未出现过的非终结符编译原理文法变换：提取左公因子文法变换：提取左公因子 提取左公因子规则提取左公因子规则- 一般含有左公因子的产生式形如一般含有左公因子的产生式形如 P 1 2 m 1 2 n 其中，每个其中，每个不以不以开头开头. .提取左公共因子，提取左公共因子，

56、 产生式改写成：产生式改写成： P Q 1 2 n Q 1 2 m编译原理文法变换：提取左公因子文法变换：提取左公因子- 对文法对文法 G(S): S if C t S if C t S e S C b 提取左公因子后，可改写为文法提取左公因子后，可改写为文法G(S)： S if C t S A A e S C b 提取左公因子提取左公因子举例举例编译原理文法变换文法变换 举例：举例：许多文法在消除左递归和提取左公因许多文法在消除左递归和提取左公因 子后可以变换为子后可以变换为LL(1)文法文法可验证如下文法可验证如下文法 GE是是LL(1)文法文法: (1) E TE (2) E TE (3

57、) E (4) T FT (5) T FT (6) T (7) F (E) (8) F a编译原理文法变换文法变换 举例：举例：不含左递归和左公因子的文法不含左递归和左公因子的文法 不一定是不一定是LL(1)文法文法 First集集 Follow集集if C t S A : if S: #,eeS: e A: #,eb b C: t MA,e = Ae S，A S if C t S if C t S e S C b提取左公因子后：提取左公因子后： S if C t S A A e S C b编译原理文法变换文法变换 问题探讨问题探讨 某些非某些非LL(1)的文法也可采用的文法也可采用LL(1)

58、分析方法分析方法MA,e = A e S， A S if C t S if C t S e S C b提取左公因子后：提取左公因子后： S if C t S A A e S 优先使用优先使用编译原理预测分析中的出错处理预测分析中的出错处理 错误处理的原则错误处理的原则- 尽可能准确指出错误位置和错误属性尽可能准确指出错误位置和错误属性- 尽可能进行校正尽可能进行校正编译原理预测分析中的出错处理预测分析中的出错处理- 递归下降递归下降LL(1)分析中的出错处理分析中的出错处理介绍一种短语层错误恢复技术介绍一种短语层错误恢复技术- 表驱动表驱动LL(1)分析中的出错处理分析中的出错处理 介绍一种简

59、单的应急错误恢复技术介绍一种简单的应急错误恢复技术 预测分析中的出错处理预测分析中的出错处理编译原理- 出错报告出错报告（error reporting） 栈顶的终结符与当前输入符不匹配栈顶的终结符与当前输入符不匹配 非终结符非终结符A于栈顶，面临的输入符为于栈顶，面临的输入符为a， 但分析表但分析表M的的MA,a为空为空 表驱动表驱动LL(1)分析中的错误处理分析中的错误处理预测分析中的出错处理预测分析中的出错处理编译原理- 简单的简单的应急恢复应急恢复（panic-mode error recovery） 跳过输入串中的一些符号直至遇到跳过输入串中的一些符号直至遇到同步符号同步符号 （sy

60、nchronizing token）为止为止同步符号的选择：同步符号的选择： 把把 Follow(A) 中的所有符号作为中的所有符号作为A的同步符号的同步符号, 跳过跳过 输入串中的一些符号直至遇到这些输入串中的一些符号直至遇到这些“同步符号同步符号”， 把把A从栈中弹出，可使分析继续从栈中弹出，可使分析继续 把把First(A)中的符号加到中的符号加到A的同步符号集，当的同步符号集，当First(A) 中的符号在输入中出现时，可根据中的符号在输入中出现时，可根据A恢复分析恢复分析预测分析中的出错处理预测分析中的出错处理 表驱动表驱动LL(1)分析中的错误处理分析中的错误处理编译原理 在进入某