自上而下分析 4.4

上节课重点 上下文无关文法的定义，四元组的构成 推导，最左推导，最右推导 形式语言与文法 左递归 提取左公因子 消除二义性 自上而下分析 LL(1)文法 FIREST函数 FOLLOW函数

4.3 自上而下分析 4.3.1 自上而下分析的一般方法 例 文法 S  aCb C  cd | c 为输入串w = acb建立分析树 不能处理左递归

4.3 自上而下分析 不能处理左递归的例子 算术表达文法 E  E + T | T T  T  F | F F  ( E ) | id E E + T E + T E + T … … …

4.3 自上而下分析 4.3.1 自上而下分析的一般方法 例 文法 S  aCb C  cd | c 为输入串w = acb建立分析树 不能处理左递归、复杂的回溯技术

4.3 自上而下分析 4.3.1 自上而下分析的一般方法 例 文法 S  aCb C  cd | c 为输入串w = acb建立分析树 不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来

4.3 自上而下分析 4.3.1 自上而下分析的一般方法 例 文法 S  aCb C  cd | c 为输入串w = acb建立分析树 不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置

4.3 自上而下分析 4.3.1 自上而下分析的一般方法 例 文法 S  aCb C  cd | c 为输入串w = acb建立分析树 不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置、效率低

4.3 自上而下分析 4.3.2 LL(1)文法 对文法加什么样的限制可以保证没有回溯？ 先定义两个和文法有关的函数 FIRST( ) = {a |  * a…, a  VT} 特别是， * 时，规定  FIRST( ) 对A的任何两个不同选择i 和j，希望有 FIRST(i )  FIRST(j ) =  若FIRST(i ) 或 FIRST(j )含，还需增加条件

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 自上而下分析 非终 结符 输 入 符 号 id +  . . . E E  TE  E  E   +TE  T 分析表的一部分 非终 结符 输 入 符 号 id +  . . . E E  TE  E  E   +TE  T T  FT  T  T    T   FT  F F  id

4.3 自上而下分析 预测分析器接受输入id * id + id的前一部分动作 栈 输 入 输 出 $E id  id + id$

4.3 自上而下分析 栈 输 入 输 出 $E id  id + id$ $E T E  TE  输 入 输 出 $E id  id + id$ $E T E  TE 

4.3 自上而下分析 栈 输 入 输 出 $E id  id + id$ $E T E  TE  $E T F T  FT  输 入 输 出 $E id  id + id$ $E T E  TE  $E T F T  FT 

4.3 自上而下分析 栈 输 入 输 出 $E id  id + id$ $E T E  TE  $E T F T  FT  输 入 输 出 $E id  id + id$ $E T E  TE  $E T F T  FT  $E T  id F  id

4.3 自上而下分析 栈 输 入 输 出 $E id  id + id$ $E T E  TE  $E T F T  FT  输 入 输 出 $E id  id + id$ $E T E  TE  $E T F T  FT  $E T  id F  id $E T   id + id$

4.3 自上而下分析 栈 输 入 输 出 $E id  id + id$ $E T E  TE  $E T F T  FT  输 入 输 出 $E id  id + id$ $E T E  TE  $E T F T  FT  $E T  id F  id $E T   id + id$ $E T F  T   FT 

4.3 自上而下分析 栈 输 入 输 出 $E id  id + id$ $E T E  TE  $E T F T  FT  输 入 输 出 $E id  id + id$ $E T E  TE  $E T F T  FT  $E T  id F  id $E T   id + id$ $E T F  T   FT  id + id$

4.3 自上而下分析 栈 输 入 输 出 $E id  id + id$ $E T E  TE  $E T F T  FT  输 入 输 出 $E id  id + id$ $E T E  TE  $E T F T  FT  $E T  id F  id $E T   id + id$ $E T F  T   FT  id + id$

4.3 自上而下分析 自然语言例子 S  NP VP | IM VP NP  我 IM  请 VP  V Ｎ V  上 | 开 我　上　课

4.3 自上而下分析 自然语言例子 S  NP VP | IM VP NP  我 IM  请 VP  V Ｎ V  上 | 开 ＮＰ ＶＰ ＶＰ ＮＰ 我　上　课

4.3 自上而下分析 自然语言例子 S  NP VP | IM VP NP  我 IM  请 VP  V Ｎ V  上 | 开 ＮＰ ＶＰ 我 ＶＰ 我 我　上　课

4.3 自上而下分析 自然语言例子 S  NP VP | IM VP NP  我 IM  请 VP  V Ｎ V  上 | 开 ＮＰ ＶＰ 我 ＶＰ 上　课

4.3 自上而下分析 自然语言例子 S  NP VP | IM VP NP  我 IM  请 VP  V Ｎ V  上 | 开 ＮＰ ＶＰ Ｖ Ｎ 我 N Ｖ 上　课

4.3 自上而下分析 自然语言例子 S  NP VP | IM VP NP  我 IM  请 VP  V Ｎ V  上 | 开 ＮＰ ＶＰ Ｖ Ｎ 我 上 N 上 上　课

4.3 自上而下分析 自然语言例子 S  NP VP | IM VP NP  我 IM  请 VP  V Ｎ V  上 | 开 ＮＰ ＶＰ Ｖ Ｎ 我 上 N 课

4.3 自上而下分析 自然语言例子 S  NP VP | IM VP NP  我 IM  请 VP  V Ｎ V  上 | 开 ＮＰ ＶＰ Ｖ Ｎ 我 上 课 课 课

4.3 自上而下分析 自然语言例子 S  NP VP | IM VP NP  我 IM  请 VP  V Ｎ V  上 | 开 ＮＰ ＶＰ Ｖ Ｎ 我 上 课

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

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

4.3 自上而下分析

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

练习 下面的二义文法描述命题演算公式，为它写一个等价的非二义文法 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|ε