自上而下分析 4.4

复习

4.3 自上而下分析 4.3.2 LL(1)文法 对文法加什么样的限制可以保证没有回溯？ 先定义两个和文法有关的函数 FIRST( ) = {a |  * a…, a  VT} 特别是， * 时，规定  FIRST( ) FOLLOW(A) = {a | S * …Aa…，aVT} 如果A是某个句型的最右符号，那么$属于FOLLOW(A)

任何两个产生式A  |  都满足下列条件： 4.3 自上而下分析 LL(1)文法 任何两个产生式A  |  都满足下列条件： FIRST( )  FIRST( ) =  若 *  ，那么FIRST()  FOLLOW(A) =  例如, 对于下面文法，面临a…时，第2步推导不 知用哪个产生式 S  A B A  a b |  a  FIRST(ab)  FOLLOW(A) B  a C C  …

任何两个产生式A  |  都满足下列条件： 4.3 自上而下分析 LL(1)文法 任何两个产生式A  |  都满足下列条件： FIRST( )  FIRST( ) =  若 *  ，那么FIRST()  FOLLOW(A) =  LL(1)文法有一些明显的性质 没有公共左因子 不是二义的 不含左递归

计算X的FIRST(X)时，不断运用以下规则，直到没有新的终结符或ε可以被加入到FIRST(X) 4.3 自上而下分析 计算X的FIRST(X)时，不断运用以下规则，直到没有新的终结符或ε可以被加入到FIRST(X) 如果X是终结符，FIRST(X)= X

计算X的FIRST(X)时，不断运用以下规则，直到没有新的终结符或ε可以被加入到FIRST(X) 4.3 自上而下分析 计算X的FIRST(X)时，不断运用以下规则，直到没有新的终结符或ε可以被加入到FIRST(X) 如果X是终结符，FIRST(X)= X 如果XY1Y2…Yk, 且a在FIRST(Yi)集合中，并且Y1 * ε, Y2 * ε, …, Yi-1 * ε，则将a插入到FIRST(X)中。

计算X的FIRST(X)时，不断运用以下规则，直到没有新的终结符或ε可以被加入到FIRST(X) 4.3 自上而下分析 计算X的FIRST(X)时，不断运用以下规则，直到没有新的终结符或ε可以被加入到FIRST(X) 如果X是终结符，FIRST(X)= X 如果XY1Y2…Yk, 且a在FIRST(Yi)集合中，并且Y1 * ε, Y2 * ε, …, Yi-1 * ε，则将a插入到FIRST(X)中。 如果X ε是一个产生式，则将ε插入到FIRST(X)中。

计算非终结符A的FOLLOW(A)时，不断运用以下规则，直到没有新的终结符可以被加入到FOLLOW(A) 4.3 自上而下分析 计算非终结符A的FOLLOW(A)时，不断运用以下规则，直到没有新的终结符可以被加入到FOLLOW(A) 将$放到FOLLOW(S)中，S是开始符，$是输入右端的结束标记

计算非终结符A的FOLLOW(A)时，不断运用以下规则，直到没有新的终结符可以被加入到FOLLOW(A) 4.3 自上而下分析 计算非终结符A的FOLLOW(A)时，不断运用以下规则，直到没有新的终结符可以被加入到FOLLOW(A) 将$放到FOLLOW(S)中，S是开始符，$是输入右端的结束标记 如果存在AαBβ，那么FIRST(β)中非ε的所有符号都在FOLLOW(B)中

计算非终结符A的FOLLOW(A)时，不断运用以下规则，直到没有新的终结符可以被加入到FOLLOW(A) 4.3 自上而下分析 计算非终结符A的FOLLOW(A)时，不断运用以下规则，直到没有新的终结符可以被加入到FOLLOW(A) 将$放到FOLLOW(S)中，S是开始符，$是输入右端的结束标记 如果存在AαBβ，那么FIRST(β)中非ε的所有符号都在FOLLOW(B)中 如果存在AαB或AαBβ，且FIRST(β)包含ε，则FOLLOW(A)中的所有符号都在FOLLOW(B)中。

4.3 自上而下分析 例 E  TE  E   + TE  |  T  FT  T    FT  |  F  (E) | id FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E ) = {+, } FRIST(T ) = {, } FOLLOW(E) = FOLLOW(E ) = { ), $} FOLLOW(T) = FOLLOW (T ) = {+, ), $} FOLLOW(F) = {+, , ), $} * 在FRIST(T)中，+, )和$在FOLLOW (T) 中。

| array [simple] of type simple  integer | char | num dotdot num 4.3 自上而下分析 4.3.3 递归下降的预测分析 为每一个非终结符写一个分析过程 这些过程可能是递归的 例 type  simple |  id | array [simple] of type simple  integer | char | num dotdot num

4.3 自上而下分析 一个辅助过程 void match (terminal t) { if (lookahead == t) lookahead = nextToken( ); else error( ); }

4.3 自上而下分析 void type( ) { if ( (lookahead == integer) || (lookahead == char) || (lookahead == num) ) simple( ); else if ( lookahead ==  ) { match(); match(id);} else if (lookahead == array) { match(array); match( [ ); simple( ); match( ] ); match(of ); type( ); } else error( ); type  simple |  id | array [simple] of type

4.3 自上而下分析 void simple( ) { if ( lookahead == integer) match(integer); else if (lookahead == char) match(char); else if (lookahead == num) { match(num); match(dotdot); match(num); } else error( ); simple  integer | char | num dotdot num

4.3 自上而下分析 4.4.4 非递归的预测分析 a + b $ X Y Z 输入 预测分析程序 输出 栈 分析表M 以自然语言例子：我上课 请开门 做例子讲解非递归的自上而下分析

4.3 自上而下分析 4.4.4 非递归的预测分析 算法 初始时分析器的格局是： Ｓ$在栈里，其中Ｓ是开始符号并且在栈顶；ｗ$ 在输入缓冲区 主程序

4.3 自上而下分析 4.4.4 非递归的预测分析 预测分析程序根据当前的栈顶符号Ｘ和输入符号a决定分析器的动作，它有四种可能： 如果Ｘ是非终结符，程序访问分析表Ｍ

4.3 自上而下分析 4.4.5 构造预测分析表 （1）对文法的每个产生式A   ，执行(2)和(3) （2）对FIRST()的每个终结符a， 把A   加入M[A, a] （3）如果在FIRST()中，对FOLLOW(A)的每个终结符b（包括$）, 把A  加入M[A, b] （4）M中其它没有定义的条目都是error

4.3 自上而下分析 4.4.5 构造预测分析表 例： E  TE  E   + TE  |  T  FT  F  (E) | id FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E ) = {+, } FRIST(T ) = {, } FOLLOW(E) = FOLLOW(E ) = { ), $} FOLLOW(T) = FOLLOW (T ) = {+, ), $} FOLLOW(F) = {+, , ), $}

4.3 自上而下分析 4.4.5 构造预测分析表 非终 结符 输 入 符 号 id +  . . . E E  TE  E  输 入 符 号 id +  . . . E E  TE  E  E   +TE  T T  FT  T  T    T   FT  F F  id

4.3 自上而下分析 4.4.5 构造预测分析表 多重定义的条目 例： stmt  if expr then stmt e_part | other e_part  else stmt |  other  b FOLLOW(e_part) = (else, $) M[e_part, else]包括e_part  else stmt 和 e_part  

4.3 自上而下分析 非终 结符 输 入 符 号 other b else . . . stmt stmt  other e_part 多重定义的条目 非终 结符 输 入 符 号 other b else . . . stmt stmt  other e_part e_part else stmt e_part   expr expr  b

4.3 自上而下分析 非终 结符 输 入 符 号 other b else . . . stmt stmt  other e_part 多重定义的条目 非终 结符 输 入 符 号 other b else . . . stmt stmt  other e_part e_part else stmt expr expr  b

预测分析的错误恢复

4.3 自上而下分析 4.4.6 预测分析的错误恢复 1、先对编译器的错误处理做一个概述 词法错误，如标识符、关键字或算符的拼写错 语法错误，如算术表达式的括号不配对 语义错误，如算符作用于不相容的运算对象 逻辑错误，如无穷的递归调用

4.3 自上而下分析 2、分析器对错误处理的基本目标 清楚而准确地报告错误的出现，并尽量少出现伪错误 迅速地从每个错误中恢复过来，以便诊断后面的错误 它不应该使正确程序的处理速度降低太多

4.3 自上而下分析 3、非递归预测分析在什么场合下发现错误 栈顶的终结符和下一个输入符号不匹配 a + b $ X Y Z 输入 预测分析程序 分析表M 输出 X Y Z 栈

4.3 自上而下分析 3、非递归预测分析在什么场合下发现错误 栈顶是非终结符A，输入符号是a，而M[A , a]是空白 a + b $ X 预测分析程序 分析表M 输出 X Y Z 栈

4、非递归预测分析：采用紧急方式的错误恢复 4.3 自上而下分析 4、非递归预测分析：采用紧急方式的错误恢复 发现错误时，分析器每次抛弃一个输入记号，直到输入记号属于某个指定的同步记号集合为止 5、同步 词法分析器当前提供的记号流能够构成的语法构造，正是语法分析器所期望的 不同步的例子 语法分析器期望剩余的前缀构成过程调用语句，而实际剩余的前缀形成赋值语句

4.3 自上而下分析 6、同步记号集合的选择 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合

4.3 自上而下分析 6、同步记号集合的选择 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合 if expr then stmt （then和分号等记号是expr的同步记号）

4.3 自上而下分析 6、同步记号集合的选择 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中

4.3 自上而下分析 6、同步记号集合的选择 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中 a = expr; if … (语句的开始符号作为表达式的同步记号，以免表达式出错又遗漏分号时忽略if语句等一大段程序)

4.3 自上而下分析 6、同步记号集合的选择 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中 把FIRST(A)的终结符加入A的同步记号集合 a = expr; , if … （语句的开始符号作为语句的同步符号，以免多出一个逗号时会把if语句忽略了）

4.3 自上而下分析 6、同步记号集合的选择 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中 把FIRST(A)的终结符加入A的同步记号集合 如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用推出空串的产生式

4.3 自上而下分析 非终 结符 输 入 符 号 id +  . . . E ETE E E+TE T TFT  T  例 栈顶为T ，面临id时出错 非终 结符 输 入 符 号 id +  . . . E ETE E E+TE T TFT  T  出错 T   T FT 

4.3 自上而下分析 非终 结符 输 入 符 号 id +  . . . E ETE E E+TE T TFT  T  输 入 符 号 id +  . . . E ETE E E+TE T TFT  T  出错， 用T   T   T FT 

4.3 自上而下分析 6、同步记号集合的选择 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中 把FIRST(A)的终结符加入A的同步记号集合 如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用推出空串的产生式 如果终结符在栈顶而不能匹配，弹出此终结符

4.3 自上而下分析 错误恢复 例： E  TE  E   + TE  |  T  FT  T    FT  |  F  (E) | id FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E ) = {+, } FRIST(T ) = {, } FOLLOW(E) = FOLLOW(E ) = { ), $} FOLLOW(T) = FOLLOW (T ) = {+, ), $} FOLLOW(F) = {+, , ), $}

4.3 自上而下分析 错误恢复 例： E  TE  E   + TE  |  T  FT  T    FT  |  F  (E) | id FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E ) = {+, } FRIST(T ) = {, } FOLLOW(E) = FOLLOW(E ) = { ), $} FOLLOW(T) = FOLLOW (T ) = {+, ), $} FOLLOW(F) = {+, , ), $}

自底向上的分析 4.5

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde（读入ab） a b

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde（归约） a A

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde（再读入bc）

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde（归约） a b A c

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde（再读入d） a b A d c

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde aABe(再读入e) e a b A d c B

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde

S rm aABe rm aAde rm aAbcde rm abbcde 4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde aABe S S rm aABe rm aAde rm aAbcde rm abbcde S e a b A d c B

句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步 4.4 自下而上分析 4.4.2 句柄 句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步 S  aABe A  Abc | b B  d S rm aABe rm aAde rm aAbcde rm abbcde 句柄的右边仅含终结符 如果文法二义，那么句柄可能不唯一

4.4 自下而上分析 例 句柄不唯一 E  E + E | E  E | (E ) | id

4.4 自下而上分析 例 句柄不唯一 E  E + E | E  E | (E ) | id E rm E  E rm E  E + E rm E  E + id3 rm E  id2 + id3 rm id1  id2 + id3

4.4 自下而上分析 例 句柄不唯一 E  E + E | E  E | (E ) | id E rm E  E E rm E + E rm E  E + E rm E + id3 rm E  E + id3 rm E  E + id3 rm E  id2 + id3 rm E  id2 + id3 rm id1  id2 + id3 rm id1  id2 + id3 在句型E  E + id3中，句柄不唯一

4.4 自下而上分析 4.4.3 用栈实现移进归约分析 先通过 来了解移进归约分析的工作方式 移进归约分析器在分析输入串id1  id2 + id3时的动作序列 来了解移进归约分析的工作方式

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约 按E  EE归约

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约 按E  EE归约

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约 按E  EE归约 接受

要想很好地使用移进归约方式，尚需解决一些问题 4.4 自下而上分析 要想很好地使用移进归约方式，尚需解决一些问题 如何决策选择移进还是归约 进行归约时，确定右句型中将要归约的子串 进行归约时，如何确定选择哪一个产生式

4.4 自下而上分析 4.4.4 移进归约分析的冲突 1、移进归约冲突 例 stmt  if expr then stmt | if expr then stmt else stmt | other 如果移进归约分析器处于格局 栈 输入 … if expr then stmt else … $

4.4 自下而上分析 2、归约归约冲突 由A(I, J)开始的语句 栈 输入 … id ( id , id )… 归约成expr还 stmt  id (parameter_list) | expr = expr parameter_list  parameter_list, parameter | parameter parameter  id expr  id (expr_list) | id expr_list  expr_list, expr | expr 由A(I, J)开始的语句 栈 输入 … id ( id , id )… 归约成expr还 是parameter ?

4.4 自下而上分析 2、归约归约冲突 stmt  id (parameter_list) | expr = expr parameter_list  parameter_list, parameter | parameter parameter  id expr  id (expr_list) | id expr_list  expr_list, expr | expr 由A(I, J)开始的语句(词法分析查符号表,区分第一个id) 栈 输入 … procid ( id , id )… 需要修改上面的文法

4.4 自下而上分析 2、归约归约冲突 stmt  procid (parameter_list) | expr = expr parameter_list  parameter_list, parameter | parameter parameter  id expr  id (expr_list) | id expr_list  expr_list, expr | expr 由A(I, J)开始的语句(词法分析查符号表,区分第一个id) 栈 输入 … procid ( id , id )…

练习 下面的二义文法描述命题演算公式，为它写一个等价的非二义文法 S->S and S | S or S| not S |ture | false | (S)

为字母表{a,b}上的下列每个语言设计一个文法 练习 为字母表{a,b}上的下列每个语言设计一个文法 每个a后面至少有一个b的所有串 a和b的个数相等的所有串

练习 构造下面LL(1)文法的分析表 D->TL T->int|real L->id R R->, id R | ε

练习 构造下面文法的LL(1)分析表 S-aBS|bAS|ε A->bAA|a B->aBB|b

练习 下面文法是否是LL(1)文法？说明理由。 S->AB|PQx A->xy B->bc P->dP|ε Q->aQ|ε