编译原理 第四章 语法分析—自上而下分析 编译原理

源程序 表 词法分析器 出 单词符号 格 错 语法分析器 管 处 语法单位 理 理 四元式 优化段 四元式 目标代码生成器 目标代码 语义分析与中间代码生成器 四元式 优化段 四元式 目标代码生成器 目标代码 编译原理

第四章 语法分析—自上而下分析 本章主要介绍语法分析的处理 要进行语法分析，必须对语言的语法结构进行描述。 第四章 语法分析—自上而下分析 本章主要介绍语法分析的处理 要进行语法分析，必须对语言的语法结构进行描述。 采用正规式和有限自动机可以描述和识别语言的单词符号； 用上下文无关文法来描述语法规则。 编译原理

上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT  VN= S：文法的开始符号，SVN P：产生式集合(有限)，每个产生式形式为 P， PVN，   (VT  VN)* 开始符S至少必须在某个产生式的左部出现一次。 编译原理

G=<{i，+，*，(，)}，{E}，E， P>， 其中，P由下列产生式组成： E  i E  E+E E  E*E 例，定义只含+，*的算术表达式的文法 G=<{i，+，*，(，)}，{E}，E， P>， 其中，P由下列产生式组成： E  i E  E+E E  E*E E  (E) 编译原理

如果1  2   n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n 。 定义：称A直接推出，即 A 仅当A  是一个产生式， 且，  (VT  VN)* 。 如果1  2   n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n 。 例：对文法(1) E  (E)  (E+E) (i+E) (i+i) 编译原理

通常，用 表示：从1出发，经过 一步或若干步，可以推出n。 所以 ： 即 或 定义：假定G是一个文法，S 是它的开始符号。 如果 ，则称是一个句型。仅含终结符 号的句型是一个句子。文法G所产生的句子的全 体是一个语言，将它记为 L(G)。 编译原理

4.1 语法分析器的功能 语法分析的任务是分析一个文法的句子结构。 语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)。 编译原理

单词符号 语法分 析树 源程序 词法分 析器 语法分 符号表 编译程序 后续部分 取下一单词 ... 编译原理

语法分析的方法： 自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。 算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。 LR分析法：规范归约 编译原理

E E + E E * E i i i G(E)： E  i| E+E | E-E | E*E | E/E | (E) i*i+i 编译原理

语法分析的方法： 自下而上分析法(Bottom-up) 自上而下分析法(Top-down) 基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。 递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 预测分析程序 优点：直观、简单和宜于手工实现。 编译原理

4.2 自上而下分析面临的问题 自上而下就是从文法的开始符号出发，向 下推导，推出句子。 4.2 自上而下分析面临的问题 自上而下就是从文法的开始符号出发，向 下推导，推出句子。 带“回溯”的 不带回溯的递归子程序(递归下降)分析方法。 自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。 编译原理

例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|* 分析输入串x*y(记为)。 S x*y IP A x y * 编译原理

当某个非终结符有多个产生式候选时，可能带来如下问题: 1. 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。 2. 文法左递归问题。一个文法是含有左递归的，如果存在非终结符P 含有左递归的文法将使自上而下的分析陷入无限循环。 编译原理

4.3 LL(1)分析法 构造不带回溯的自上而下分析算法 要消除文法的左递归性 克服回溯 编译原理

4.3.1 左递归的消除 左递归变右递归 直接消除见诸于产生式中的左递归：假 定关于非终结符P的规则为 4.3.1 左递归的消除 直接消除见诸于产生式中的左递归：假 定关于非终结符P的规则为 P→P |  其中不以P开头。 我们可以把P的规则等价地改写为如下的非直接左递归形式： P→P P→P| 左递归变右递归 编译原理

P→P1 | P2 | … | Pm | 1 | 2|…|n P→1P | 2P | … | nP P→1P | 2P |… | mP |  左递归变右递归 编译原理

P→P1 | P2 | … | Pm | 1 | 2|…|n 例 文法G(E): E→E＋T | T T→T*F | F F→(E) | i 经消去直接左递归后变成： E→TE E→+TE |  T→FT T→*FT |  (4.2) P→P1 | P2 | … | Pm | 1 | 2|…|n P→1P | 2P | … | nP P→1P | 2P |… | mP |  编译原理

例如文法G(S): S→Qc|c Q→Rb|b R→Sa|a (4.3) SQcRbcSabc 一个文法消除左递归的条件： 虽没有直接左递归，但S、Q、R都是左递归的 SQcRbcSabc 一个文法消除左递归的条件： 不含以为右部的产生式 不含回路。 编译原理

消除左递归的算法: 1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，…，Pn；按此顺序执行； 2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如Pi→Pj的规则改写成 Pi→1|2|…|k ; (其中Pj→1|2|…|k是关于Pj的所有规则) 消除关于Pi规则的直接左递归性 END 3. 化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。 编译原理

把R代入到Q的有关候选后，把Q的规则变为 Q→Sab | ab | b 例 考虑文法G(S) S→Qc|c Q→Rb|b R→Sa|a 令它的非终结符的排序为R、Q、S。 对于R，不存在直接左递归。 把R代入到Q的有关候选后，把Q的规则变为 Q→Sab | ab | b 编译原理

Q→Sab | ab | b S→Sabc | abc | bc | c 例 考虑文法G(S) S→Qc|c Q→Rb|b R→Sa|a 令它的非终结符的排序为R、Q、S。 Q的规则变为 Q→Sab | ab | b 现在的Q不含直接左递归，把它代入到S的有关候选后，S变成 S→Sabc | abc | bc | c 编译原理

例 考虑文法G(S) S变成 S→Sabc | abc | bc | c 消除S的直接左递归后： S→abcS | bcS | cS S→Qc|c Q→Rb|b R→Sa|a S变成 S→Sabc | abc | bc | c 消除S的直接左递归后： S→abcS | bcS | cS S→abcS |  Q→Sab |ab | b 编译原理

例 考虑文法G(S) 消除S的直接左递归后： S→abcS | bcS | cS S→abcS |  Q→Sab |ab | b S→Qc|c Q→Rb|b R→Sa|a 消除S的直接左递归后： S→abcS | bcS | cS S→abcS |  Q→Sab |ab | b 关于Q和R的规则已是多余的，化简为： S→abcS |  (4.4) 编译原理

注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。 例如，若对文法(4.3)的非终结符排序选为S、Q、R，那么，最后所得的无左递归文法是： S→Qc | c Q→Rb | b R→bcaR | caR |a R (4.5) R→ bca R |  文法(4.4)和(4.5)的等价性是显然的。 编译原理

4.3.2 消除回溯、提左因子 为了消除回溯就必须保证：对文法的任 何非终结符，当要它去匹配输入串时， 能够根据它所面临的输入符号准确地指 派它的一个候选去执行任务，并且此候 选的工作结果应是确信无疑的。 A→ 1 |  2 | … |  n S a…. IP A ... 编译原理

FIRST(i)∩FIRST( j)＝ 令G是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST()为： 特别是，若 ，则规定FIRST()。 如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选 i和 j FIRST(i)∩FIRST( j)＝ 当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的。 编译原理

A→A |  1 |  2 | … |  m A→ 1 |  2 | … |  n 提取公共左因子: 假定关于A的规则是 A→ 1 |  2 | …|  n |  1 |  2 | … | m (其中，每个 不以开头) 那么，可以把这些规则改写成 A→A |  1 |  2 | … |  m A→ 1 |  2 | … |  n 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。 编译原理

4.3.3 LL(1)分析条件 E→TE E→+TE |  T→FT T→*FT |  F→(E) | i i + i 编译原理

E i + i IP G(E): E→TE E→+TE |  T→FT T→*FT |  F→(E) | i 编译原理

i + i E T E’ IP G(E): E→TE E→+TE |  T→FT T→*FT |  F→(E) | i 编译原理

i + i E T E’ F T’ IP G(E): E→TE E→+TE |  T→FT T→*FT |  F→(E) | i 编译原理

i + i E T E’ F T’ i IP G(E): E→TE E→+TE |  T→FT T→*FT |  F→(E) | i 编译原理

i + i E T E’ F T’ i IP G(E): E→TE E→+TE |  T→FT T→*FT |  F→(E) | i 编译原理

i + i E T E’ F T’ i  IP G(E): E→TE E→+TE |  T→FT T→*FT |  F→(E) | i 编译原理

i + i E T E’ F T’ + T E’ i  IP G(E): E→TE E→+TE |  T→FT F→(E) | i 编译原理

i + i E T E’ F T’ + T E’ i  IP G(E): E→TE E→+TE |  T→FT F→(E) | i 编译原理

i + i E T E’ F T’ + T E’ F T’ i  IP G(E): E→TE E→+TE |  T→FT F→(E) | i 编译原理

i + i E T E’ F T’ + T E’ F T’ i  i IP G(E): E→TE E→+TE |  T→FT F→(E) | i i 编译原理

i + i E T E’ F T’ + T E’ F T’ i  i IP G(E): E→TE E→+TE |  T→FT F→(E) | i i 编译原理

i + i E T E’ F T’ + T E’ F T’ i  i  IP G(E): E→TE E→+TE |  T→FT F→(E) | i i  编译原理

i + i E S …T’+… T E’ F T’ + T E’ F T’ i   i  IP G(E): E→TE T→FT T→*FT |  F→(E) | i  i  编译原理

4.3.3 LL(1)分析条件 假定S是文法G的开始符号，对于G的任何非终结符A，我们定义 特别是，若 ，则规定 ＃FOLLOW(A) 特别是，若 ，则规定 ＃FOLLOW(A) 编译原理

FIRST( i)∩FOLLOW(A)= 构造不带回溯的自上而下分析的文法条件 1. 文法不含左递归， 2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若 A→ 1| 2|…| n 则 FIRST( i)∩FIRST( j)＝ (ij) 3. 对文法中的每个非终结符A，若它存在某个候选首符集包含，则 FIRST( i)∩FOLLOW(A)= i=1,2,...,n 如果一个文法G满足以上条件，则称该文法G为LL(1)文法。 编译原理

对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为 A→ 1 |  2 | … |  n 1. 若aFIRST( i)，则指派 i执行匹配任务； 2. 若a不属于任何一个候选首符集，则： (1) 若属于某个FIRST(i )且 aFOLLOW(A)， 则让A与自动匹配。 (2) 否则，a的出现是一种语法错误。 编译原理

回顾：LL(1)分析法 构造不带回溯的自上而下分析算法 要消除文法的左递归性 克服回溯 编译原理

P→P1 | P2 | … | Pm | 1 | 2|…|n P→1P | 2P | … | nP P→1P | 2P |… | mP |  编译原理

消除左递归的算法: 1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，…，Pn；按此顺序执行； 2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如Pi→Pj的规则改写成 Pi→1|2|…|k ; (其中Pj→1|2|…|k是关于Pj的所有规则) 消除关于Pi规则的直接左递归性 END 3. 化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。 编译原理

回顾：LL(1)分析法 构造不带回溯的自上而下分析算法 要消除文法的左递归性 克服回溯 编译原理

4.3.2 消除回溯、提左因子 为了消除回溯就必须保证：对文法的任 何非终结符，当要它去匹配输入串时， 能够根据它所面临的输入符号准确地指 派它的一个候选去执行任务，并且此候 选的工作结果应是确信无疑的。 A→ 1 |  2 | … |  n S a…. IP A ... 编译原理

FIRST(i)∩FIRST( j)＝ 令G是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST()为： 特别是，若 ，则规定FIRST()。 如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选 i和 j FIRST(i)∩FIRST( j)＝ 当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的。 编译原理

A→A |  1 |  2 | … |  m A→ 1 |  2 | … |  n 提取公共左因子: 假定关于A的规则是 A→ 1 |  2 | …|  n |  1 |  2 | … | m (其中，每个 不以开头) 那么，可以把这些规则改写成 A→A |  1 |  2 | … |  m A→ 1 |  2 | … |  n 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。 编译原理

i + i E→TE E→+TE |  T→FT T→*FT |  F→(E) | i E T E’ F T’ + T E’ IP i 编译原理

FOLLOW定义 假定S是文法G的开始符号，对于G的任何非终结符A，我们定义 特别是，若 ，则规定 ＃FOLLOW(A) 编译原理

FIRST( i)∩FOLLOW(A)= 构造不带回溯的自上而下分析的文法条件 1. 文法不含左递归， 2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若 A→ 1| 2|…| n 则 FIRST( i)∩FIRST( j)＝ (ij) 3. 对文法中的每个非终结符A，若它存在某个候选首符集包含，则 FIRST( i)∩FOLLOW(A)= i=1,2,...,n 如果一个文法G满足以上条件，则称该文法G为LL(1)文法。 编译原理

对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为 A→ 1 |  2 | … |  n 1. 若aFIRST( i)，则指派 i执行匹配任务； 2. 若a不属于任何一个候选首符集，则： (1) 若属于某个FIRST(i )且 aFOLLOW(A)， 则让A与自动匹配。 (2) 否则，a的出现是一种语法错误。 编译原理

构造FIRST() 编译原理

对每一文法符号XVT∪VN构造FIRST(X) 连续使用下面的规则，直至每个集合FIRST不再增大为止： 1. 若XVT，则FIRST(X)＝{X}。 2. 若XVN，且有产生式X→a…，则把a加入到FIRST(X)中；若X→也是一条产生式，则把也加到FIRST(X)中。 编译原理

若X→Y…是一个产生式且YVN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中； 3. 若X→Y…是一个产生式且YVN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中； 若X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有(即Y1…Yi-1)， 则把FIRST(Yi)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j＝1，2，…，k，则把加到FIRST(X)中。 编译原理

对文法G的任何符号串=X1X2…Xn构造集合FIRST()。 1. 置FIRST()＝FIRST(X1)\{}； 2. 若对任何1ji-1，FIRST(Xj)，则把FIRST(Xi)\{}加至FIRST()中；特别是，若所有的FIRST(Xj)均含有，1jn，则把也加至FIRST()中。显然，若＝则FIRST()＝{}。 编译原理

构造FOLLOW(A) 编译原理

对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止： 1. 对于文法的开始符号S，置＃于FOLLOW(S)中； 2. 若A→B是一个产生式，则把FIRST()\{}加至FOLLOW(B)中； 3. 若A→B是一个产生式，或AB是一个产生式而  (即FIRST())， 则把FOLLOW(A)加至FOLLOW(B)中。 编译原理

构造每个非终结符的FIRST和FOLLOW集合： 例4.6 对于文法G(E) E→TE E→+TE |  T→FT T→*FT |  F→(E) | i 构造每个非终结符的FIRST和FOLLOW集合： FIRST(E) ={(,i} FIRST(E)={+, } FIRST(T) ={(,i} FIRST(T)={*, } FIRST(F) ={(,i} FOLLOW(E) ={),#} FOLLOW(E)={),#} FOLLOW(T) ={+,),#} FOLLOW(T)={+,),#} FOLLOW(F) ={*,+,),#} 编译原理

4.4 递归下降分析程序构造 构造不带回溯的自上而下分析程序 要消除文法的左递归性 克服回溯 编译原理

分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。(因为文法的定义通常是递归的) 构造不带回溯的自上而下分析器 分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。(因为文法的定义通常是递归的) 几个全局过程和变量： ADVANCE，把输入串指示器IP指向下一个输入符号，即读入一个单字符号 SYM，IP当前所指的输入符号 ERROR，出错处理子程序 编译原理

每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。 例:文法G(E): E→TE E→+TE |  T→FT T→*FT |  F→(E) | i 每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。 编译原理

例:文法G(E): E→TE E→+TE |  T→FT T→*FT |  F→(E) | i 对应的递归下降子程序为: PROCEDURE E； IF SYM=‘+’ THEN BEGIN ADVANCE； T；E END PROCEDURE E； BEGIN T；E END； 编译原理

例:文法G(E): E→TE E→+TE |  T→FT T→*FT |  F→(E) | i 对应的递归下降子程序为: PROCEDURE T； IF SYM=‘*’ THEN BEGIN ADVANCE； F；T END； PROCEDURE T； BEGIN F；T END 编译原理

例:文法G(E): E→TE E→+TE |  T→FT T→*FT |  F→(E) | i 对应的递归下降子程序为: PROCEDURE F； IF SYM=‘i’ THEN ADVANCE ELSE IF SYM=‘(’ THEN BEGIN ADVANCE; E； IF SYM=‘)’ THEN ADVANCE ELSE ERROR END ELSE ERROR; 编译原理

IF SYM <>’#’ THEN ERROR END; 主程序: PROGRAM PARSER; BEGIN ADVANCE; E; IF SYM <>’#’ THEN ERROR END; 编译原理

E→TE | BC 对应的递归下降子程序为: PROCEDURE E； BEGIN IF SYM FIRST(TE’) THEN ELSE IF SYM FIRST(BC) THEN B; C ELSE ERROR END； 编译原理

E→TE E→+TE |  T→FT T→*FT |  F→(E) | I 对应的递归下降子程序为: PROCEDURE E； BEGIN T；E END； PROCEDURE T； BEGIN F；T END 编译原理

ELSE IF SYM<>‘#’ AND SYM<>’)’ THEN ERROR E→TE E→+TE |  T→FT T→*FT |  F→(E) | I 对应的递归下降子程序为: PROCEDURE E； IF SYM=‘+’ THEN BEGIN ADVANCE； T；E END ELSE IF SYM<>‘#’ AND SYM<>’)’ THEN ERROR 编译原理

ELSE IF SYM<>‘#’ AND E→TE E→+TE |  T→FT T→*FT |  F→(E) | I 对应的递归下降子程序为: PROCEDURE T； IF SYM=‘*’ THEN BEGIN ADVANCE； F；T END ELSE IF SYM<>‘#’ AND SYM<>’)’ AND SYM<>’+’ THEN ERROR 编译原理

E→TE E→+TE |  T→FT T→*FT |  F→(E) | i 对应的递归下降子程序为: PROCEDURE F； IF SYM=‘i’ THEN ADVANCE ELSE IF SYM=‘(’ THEN BEGIN ADVANCE; E； IF SYM=‘)’ THEN ADVANCE ELSE ERROR END ELSE ERROR; 编译原理

主程序: PROGRAM PARSER; BEGIN ADVANCE; E END; E→TE E→+TE |  T→FT F→(E) | i 对应的递归下降子程序为: 主程序: PROGRAM PARSER; BEGIN ADVANCE; E END; 编译原理

文法的另一种表示法和转换图 在元符号“→”和“|”的基础上，扩充几个元语言符号： 引入上述元符号的文法亦称扩充的巴科斯范式。 1. 用花括号{}表示闭包运算*。 2. 用表示{}0n可任意重复0次至n次，。 3. 用方括号[]表示{}01 ，即表示的出现可有可无(等价于|)。 引入上述元符号的文法亦称扩充的巴科斯范式。 编译原理

decimal→[sign]integer.{digit}[exponent] exponent→E[sign]integer 例如，通常的“实数”可定义为： decimal→[sign]integer.{digit}[exponent] exponent→E[sign]integer integer→digit{digit} sign→ + | - 用扩充的巴科斯范式来描述语法，直观易懂，便于表示左递归消去和因子提取。 编译原理

例4.5 文法 可表示成 E→T | E+T T→F | T*F F→i | (E) E→T{+T} T→F{*F} 例4.5 文法 E→T | E+T T→F | T*F F→i | (E) 可表示成 E→T{+T} T→F{*F} F→i | (E) (4.6) 编译原理

可以用语法图来表示语言的文法。 E→T{+T} T→F{*F} F→i | (E) (4.6) T + F * i ) E ( E T F 编译原理

可构造一组递归下降分析程序： E→T{+T} T→F{*F} F→i | (E) (4.6) PROCEDURE E； BEGIN T； WHILE SYM=‘+’ DO ADVANCE； T END END； 编译原理

可构造一组递归下降分析程序： E→T{+T} T→F{*F} F→i | (E) (4.6) PROCEDURE T； BEGIN F； WHILE SYM=‘*’ DO ADVANCE； F END END； 编译原理

可构造一组递归下降分析程序： E→T{+T} T→F{*F} F→i | (E) (4.6) PROCEDURE F； IF SYM=‘i’ THEN ADVANCE ELSE IF SYM=‘(’ THEN BEGIN ADVANCE; E； IF SYM=‘)’ THEN ADVANCE ELSE ERROR END ELSE ERROR; 编译原理

FIRST( i)∩FOLLOW(A)= 1. 文法不含左递归， 2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若 A→ 1| 2|…| n 则 FIRST( i)∩FIRST( j)＝ (ij) 3. 对文法中的每个非终结符A，若它存在某个候选首符集包含，则 FIRST( i)∩FOLLOW(A)= i=1,2,...,n 如果一个文法G满足以上条件，则称该文法G为LL(1)文法。 编译原理

回顾：构造不带回溯的自上而下分析器 分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。(因为文法的定义通常是递归的) 每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。 编译原理

4.5 预测分析程序 一、预测分析程序工作原理 预测分析程序或LL(1)分析法： 总控程序 4.5 预测分析程序 一、预测分析程序工作原理 预测分析程序或LL(1)分析法： 总控程序 分析表 M[A，a]矩阵，A  VN ，a  VT 是终结符或‘＃’， 分析栈 STACK 用于存放文法符号 编译原理

总控程序 分析表 输入串 分析栈 STACK a1a2...ai…# 预测分析程序的工作图 X  # 输入串 分析栈 STACK a1a2...ai…# 预测分析程序的工作图 # S a1a2...ai…# 分析开始时： 编译原理

匹配成功 总控程序根据现行栈顶符号X和当前输入符号a，执行下列三种动作之一: 1. 若X＝a＝‘＃’，则宣布分析成功， 停止分析。 2. 若X＝a ‘＃’，则把X从STACK栈顶 逐出，让a指向下一个输入符号。 匹配成功 编译原理

推导 3. 若X是一个非终结符，则查看分析表M。 若M[X，a]中存放着关于X的一个产生式，把X逐出STACK栈顶，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为，则意味不推什么东西进栈)。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作。 若M[X，a]中存放着“出错标志”，则调用出错诊察程序ERROR。 推导 编译原理

匹配成功 预测分析程序的总控程序： BEGIN 首先把‘＃’然后把文法开始符号推进STACK栈； 把第一个输入符号读进a； FLAG:=TRUE; WHILE FLAG DO 把STACK栈顶符号上托出去并放在X中； IF XVT THEN IF X= a THEN 把下一输入符号读进a ELSE ERROR 匹配成功 编译原理

分析成功 推导 ELSE IF X=‘#’ THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF M[X,a]={X→X1X2…Xk}THEN 把Xk,Xk-1,…,X1一一推进STACK栈 /* 若X1X2…Xk=，不推什么进栈 */ END OF WHILE; STOP /*分析成功，过程完毕*/ END 推导 编译原理

例4.6 对于文法G(E) 输入串为i1*i2+i3，利用分析表进行预测分析： E→TE E→+TE |  T→FT F→(E) | i 输入串为i1*i2+i3，利用分析表进行预测分析： 编译原理

步骤 符号栈 输入串 所用产生式 0 #E i1*i2+i3# 1 #ET i1*i2+i3# E→TE 步骤 符号栈 输入串 所用产生式 0 #E i1*i2+i3# 1 #ET i1*i2+i3# E→TE 2 #ETF i1*i2+i3# T→FT 3 #ETi i1*i2+i3# F→i 编译原理

步骤 符号栈 输入串 所用产生式 3 #ETi i1*i2+i3# F→i 4 #ET *i2+i3# 步骤 符号栈 输入串 所用产生式 3 #ETi i1*i2+i3# F→i 4 #ET *i2+i3# 5 #ETF* *i2+i3# T→*FT 6 #ETF i2+i3# 7 #ETi i2+i3# F→i 编译原理

步骤 符号栈 输入串 所用产生 7 #ETi i2+i3# F→i 8 #ET +i3# 9 #E +i3# T→ 步骤 符号栈 输入串 所用产生 7 #ETi i2+i3# F→i 8 #ET +i3# 9 #E +i3# T→ 10 #ET+ +i3# E→+TE 11 #ET i3# 编译原理

步骤 符号栈 输入串 所用产生 11 #ET i3# 12 #ETF i3# T→FT 13 #ETi i3# F→i 步骤 符号栈 输入串 所用产生 11 #ET i3# 12 #ETF i3# T→FT 13 #ETi i3# F→i 14 #ET # 15 #E # T→ 16 # # E→ 编译原理

构造FIRST()和FOLLOW(A) 构造分析表M[A，a] 编译原理

构造FIRST() 编译原理

对每一文法符号XVT∪VN构造FIRST(X) 连续使用下面的规则，直至每个集合FIRST不再增大为止： 1. 若XVT，则FIRST(X)＝{X}。 2. 若XVN，且有产生式X→a…，则把a加入到FIRST(X)中；若X→也是一条产生式，则把也加到FIRST(X)中。 编译原理

若X→Y…是一个产生式且YVN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中； 3. 若X→Y…是一个产生式且YVN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中； 若X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有(即Y1…Yi-1)， 则把FIRST(Yi)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j＝1，2，…，k，则把加到FIRST(X)中。 编译原理

对文法G的任何符号串=X1X2…Xn构造集合FIRST()。 1. 置FIRST()＝FIRST(X1)\{}； 2. 若对任何1ji-1，FIRST(Xj)，则把FIRST(Xi)\{}加至FIRST()中；特别是，若所有的FIRST(Xj)均含有，1jn，则把也加至FIRST()中。显然，若＝则FIRST()＝{}。 编译原理

构造FOLLOW(A) 编译原理

对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止： 1. 对于文法的开始符号S，置＃于FOLLOW(S)中； 2. 若A→B是一个产生式，则把FIRST()\{}加至FOLLOW(B)中； 3. 若A→B是一个产生式，或AB是一个产生式而  (即FIRST())， 则把FOLLOW(A)加至FOLLOW(B)中。 编译原理

构造每个非终结符的FIRST和FOLLOW集合： 例4.6 对于文法G(E) E→TE E→+TE |  T→FT T→*FT |  F→(E) | i 构造每个非终结符的FIRST和FOLLOW集合： FIRST(E) ={(,i} FIRST(E)={+, } FIRST(T) ={(,i} FIRST(T)={*, } FIRST(F) ={(,i} FOLLOW(E) ={),#} FOLLOW(E)={),#} FOLLOW(T) ={+,),#} FOLLOW(T)={+,),#} FOLLOW(F) ={*,+,),#} 编译原理

在对文法G的每个非终结符A及其任意候选都构造出FIRST()和FOLLOW(A)之后，现在可以用它们来构造G的分析表M[A，a]。 2. 对每个终结符a FIRST()，把A→加至M[A，a]中； 3. 若FIRST()，则对任何bFOLLOW(A)把A→加至M[A，b]中。 4. 把所有无定义的M[A，a]标上“出错标志”。 编译原理

编译原理

如果G是左递归或二义的，那么，M至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表M。 可以证明，一个文法G的预测分析表M不 含多重定义入口，当且仅当该文法为 LL(1)的。 编译原理

G(S): S  iCtS | iCtSeS | a C  b 提取左因子之后，改写成： S  iCtSS’ | a 最近匹配原则 编译原理