编译原理与技术－－自顶向下分析 2019/5/5 《编译原理与技术》讲义.

编译原理与技术－－自顶向下分析 2019/5/5 《编译原理与技术》讲义

自顶向下分析分析树的建立从根（开始符号）出发，从上而下，从左自右为输入串建立分析树为输入串寻找一个最左推导 e.g.1 文法G0如下
S A B C A a B b C c 输入串 abc$ $－串结束符 2019/5/5 《编译原理与技术》讲义

自顶向下分析 e.g.1 文法G0： S A B C A a B b C c S $ a b c $ 当前记号（指针）
2019/5/5 《编译原理与技术》讲义

自顶向下分析 e.g.1 文法G0： S A B C A a B b C c S $ $ A B C a b c $

自顶向下分析 e.g.1 文法G0： S A B C A a B b C c S $ $ A B C a a b c $

自顶向下分析 e.g.1 文法G0： S A B C A a B b C c S $ $ A B C a a b c $
终结符叶子与当前符号匹配？ a b c $ 2019/5/5 《编译原理与技术》讲义

自顶向下分析 e.g.1 文法G0： S A B C A a B b C c S $ $ A B C a b a b c $
指向下一记号 2019/5/5 《编译原理与技术》讲义

自顶向下分析 e.g.1 文法G0： S A B C A a B b C c S $ $ A B C a b a b c $

自顶向下分析 e.g.1 文法G0： S A B C A a B b C c S $ A B C $ a b c a b c $

自顶向下分析 e.g.1 文法G0： S A B C A a B b C c S $ A B C $ a b c a b c $
OK！输入串分析成功！ a b c a b c $ 2019/5/5 《编译原理与技术》讲义

自顶向下分析 e.g.1 文法G0： S A B C A a B b C c 串abc$的最左推导过程: S$ ⇒ABC$

自顶向下分析文法G0较简单－非终结符只有唯一的产生式试探分析法
当待分析（展开）的非终结符对应多条产生式，可以选择其一进行尝试分析（最左推导）；当此产生式无法与输入串“匹配”时则需要“回溯”－即放弃已建立的部分分析树，同时调整输入串指针恢复到此次分析前位置，再另选一产生式重新分析。只有当所有的所有的尝试均不成功，分析失败！ 2019/5/5 《编译原理与技术》讲义

自顶向下分析试探分析法 e.g.2 文法G1如下 S  x A y A  ab A  a 输入串 xay$ 的分析过程。

自顶向下分析试探分析法 e.g.2 文法G1：（1）S  x A y （2）A  ab （3）A  a 输入串 xay$的
分析过程。 S$ 选用产生式（1） x A y $ 选用产生式（2） a b 终结符叶子x与输入符x匹配匹配失败！ x a y $ 输入串 2019/5/5 《编译原理与技术》讲义

自顶向下分析试探分析法 e.g.2 文法G1：（1）S  x A y （2）A  ab （3）A  a 输入串 xay$的
分析过程。 S$ 选用产生式（1）回溯：重新分析A x A y $ 选用产生式（2） a b 匹配失败！ x a y $ 输入串 2019/5/5 《编译原理与技术》讲义

自顶向下分析试探分析法 e.g.2 文法G1：（1）S  x A y （2）A  ab （3）A  a 输入串 xay$
的分析过程。 S$ 选用产生式（1） x A y $ 选用产生式（3）分析成功！ a 终结符叶子a与输入符a匹配 x a y $ 输入串 2019/5/5 《编译原理与技术》讲义

自顶向下分析试探分析法在文法有左递归特征时，可能导致无限循环而此时无法读入任何输入符（输入指针保持不变）。如表达式文法G2：
EE+T | T TT*F | F F(E) | id E E T E T … … a b 输入串 2019/5/5 《编译原理与技术》讲义

自顶向下分析预测分析法对于待分析的非终结符A，可以根据当前输入符号（记号）来准确唯一地选择A的某一产生式。若该产生式“匹配”成功，则意味着A分析成功；若匹配失败，则即使选择A的其它产生式也会导致A分析失败（因而不需要回溯）。 Case 1:文法G1 A  a b A的两个产生式右部具有 A  a 相同的（非空）前缀a 那么A面临输入符a选择谁呢？ 2019/5/5 《编译原理与技术》讲义

自顶向下分析预测分析法提左因子的文法变换 A  A’ A  1 A’  1 | 2 文法G1中， A  2
A  a b A  a A’ A  a A’  b |  A  A’ A’  1 | 2 引入非终结符A’ A  1 A  2 1和2不含相同前缀提左因子提左因子 2019/5/5 《编译原理与技术》讲义

可以考虑（除b外的）任一符号c。可以与之“匹配”！
自顶向下分析预测分析法 e.g.3 文法G1中， A  a b A  a A’ A  a A’  b |  A 面临 a 时有唯一的产生式A  a A’； A’面临 b 时可以选A’  b；空产生式 A’   何时选用呢？提左因子可以考虑（除b外的）任一符号c。可以与之“匹配”！ 2019/5/5 《编译原理与技术》讲义

自顶向下分析预测分析法提左因子变换的一般形式 A  1 | 2 |…| n A   i不含相同前缀, 不含前缀
提左因子变换后： A  A’ |  A’  1 | 2 |…| n 2019/5/5 《编译原理与技术》讲义

自顶向下分析预测分析法 Case 2: 文法G2 E  E + T E的产生式的（直接）左递归妨碍了
消除左递归（A ⇒＋ A…）的文法变换－直接左递归的消除（A ⇒A…） A  A A   A  A’ A’   A’ |  消除直接左递归引入非终结符A’ ，形成右递归文法 2019/5/5 《编译原理与技术》讲义

自顶向下分析预测分析法 e.g.4 消除文法G2中的直接左递归。 E E + T E T E’ E T E’ + T E’ | 
T T * F T F T’ T F T’ * F T’ |  F ( E ) F ( E ) F id F id 含左递归的文法G2 不含左递归的文法G2’ 2019/5/5 《编译原理与技术》讲义

E E E’ E + T T F F T’ + T E’ T T * F T’ F F i i F T’ i i i * i
  F T’ i i i * i  文法G2：i+i*i的分析树文法G2’：i+i*i的分析树 2019/5/5 《编译原理与技术》讲义

自顶向下分析预测分析法消除左递归（A ⇒＋ A…）的文法变换－间接左递归的消除（A ⇒＋ B… ⇒＋A…）
对于含间接左递归的文法G，可以先设法变换为含有直接左递归的文法G’（通常将较简单的产生式逐次代入较复杂的产生式），然后再行消除G’中的直接左递归即可。 2019/5/5 《编译原理与技术》讲义

自顶向下分析预测分析法 e.g.5消除文法G3中的（间接）左递归。 S  Aa | a | b A  Ac | c | Sd
将S相应产生式分别代入A相关产生式，得到文法G3’： A  Ac | c | Aad | ad | bd 消除G3’中（A的）直接左递归，则有 2019/5/5 《编译原理与技术》讲义

自顶向下分析预测分析法 e.g.5消除文法G3中的（间接）左递归。 S  Aa | a | b
A  c A’ | ad A’ | bd A’ A’  c A’ | ad A’ |  上述文法不再含有左递归。 2019/5/5 《编译原理与技术》讲义

自顶向下分析回顾一下什么是预测分析法？对于待分析的非终结符A，可以根据当前输入符号（记号）来准确唯一地选择A的某一产生式。若该产生式“匹配”成功，则意味着A分析成功；若匹配失败，则即使选择A的其它产生式也会导致A分析失败（因而不需要回溯）。在对文法提左因子和消除左递归后，可以实施预测分析了！但是，待分析或展开的非终结符A如何利用当前输入符（记号）来选择产生式呢？ 2019/5/5 《编译原理与技术》讲义

First() = { a | ⇒*a }  {  | ⇒* } , 其中 a∈VT, , ∈(VTVN)
A∈V N，考查A的每个产生式：A  X1X2…Xn， Xi ∈(VTVN), 计算First(A), (初始为∅) 1) 把Firtst(X1)-{} 加入First(A), 如果First(X1)则结束计算First(A)，否则 2) 把Firtst(X2)-{} 加入First(A), 如果First(X2)则结束计算First(A)，否则 … … n) 把Firtst(Xn)-{} 加入First(A), 如果First(Xn)则结束计算First(A)，否则 n+1)  加入First(A) 2019/5/5 《编译原理与技术》讲义

e.g.6文法G2‘的First集合 E T E’ E’ + T E’ |  T F T’ T’ * F T’ | 
F ( E ) F id First( F ) = { (, id } 2019/5/5 《编译原理与技术》讲义

F ( E ) F id First( T’ ) = { *, } 2019/5/5 《编译原理与技术》讲义

F ( E ) F id First( T ) = First( F ) = { (, id } 2019/5/5 《编译原理与技术》讲义

F ( E ) F id First( E’) = { +,  } 2019/5/5 《编译原理与技术》讲义

F ( E ) F id First( E ) = First( T ) = First( F ) = { (, id } 2019/5/5 《编译原理与技术》讲义

e.g.6文法G2‘的First集合 First( E ) = First( T )= First( F ) E T E’
= { (, id } E T E’ E’ + T E’ |  T F T’ T’ * F T’ |  F ( E ) F id First( E’) = { +,  } First( T ) = First( F ) = { (, id } First( T’ ) = { *, } First( F ) = { (, id } 2019/5/5 《编译原理与技术》讲义

 Follow(A)={ a | S ⇒* Aa }，其中 a∈VT, A∈ VN ,, ∈(VTVN)*
 $ ∈Follow(S).  若 A  B∈P，则把First()-{}加入Follow(B)  若 A  B∈P 或 A  B∈P 且 ⇒*  (即 ∈First() ），则把Follow(A)加入Follow(B) S ⇒* Aa S ⇒* Aa ⇒ Ba ⇒  Ba ⇒* B  a ⇒ Ba 显然a ∈ Follow(A) Follow(B) 2019/5/5 《编译原理与技术》讲义

e.g.7文法G2‘的Follow集合 E T E’ E’ + T E’ |  T F T’
F ( E ) F id Follow( E ) = { $, ) } 2019/5/5 《编译原理与技术》讲义

e.g.7文法G2‘的Follow集合 E T E’ E’ + T E’ |  T F T’
F ( E ) F id Follow( E’ ) = Follow(E) = { $, ) } 2019/5/5 《编译原理与技术》讲义

e.g.7文法G2‘的Follow集合 E T E’ E’ + T E’ |  T F T’ T’ * F T’ | 
F ( E ) F id Follow( T ) = (First(E’)-{})  Follow(E) = { + }  { $, ) } = { +, $, ) } 2019/5/5 《编译原理与技术》讲义

e.g.7文法G2‘的Follow集合 E T E’ E’ + T E’ |  T F T’ T’ * F T’ | 
F ( E ) F id Follow( T’ ) = Follow(T) = {+, $, ) } 2019/5/5 《编译原理与技术》讲义

e.g.7文法G2‘的Follow集合 E T E’ E’ + T E’ |  T F T’ Follow( F )
F ( E ) F id Follow( F ) = (First(T’)-{})  Follow(T)  Follow(T’) = { * }  { + , $ , ) } = { * , + , $ , ) } 2019/5/5 《编译原理与技术》讲义

e.g.7文法G2‘的Follow集合 Follow( E ) = { $ , ) } E T E’ E’ + T E’ | 
T F T’ T’ * F T’ |  F ( E ) F id Follow( E’ ) = { $ , ) } Follow( T ) = { + , $ , ) } Follow( T’ ) = {+, $ , ) } Follow( F ) = { * , + , $ , ) } 2019/5/5 《编译原理与技术》讲义

S   A ’ a… … 输入串 b… … 自顶向下分析A时，如果A只产生非空符号串，那么A期望“看到”的当前输入的符号最好是a∈First(A)，这样的话，选用产生式A来分析，即能产生（推导）出以a开头的串并期待与相应输入串匹配。 2019/5/5 《编译原理与技术》讲义

S   A ’ 输入串 b… … …  自顶向下分析A时，如果A只产生的是不包含任何有效符号的串－  ，则它 “看到”的当前输入的符号只能是b∈Follow(A)。这时选用产生式A  来“结束”对A的分析而开始的分析。 2019/5/5 《编译原理与技术》讲义

但A最不期望的是 a＝b，因为这样，A面临两难的选择－ A 还是 A  ?
S   A ’ a… b… S   A ’ b…  自顶向下分析A时，如果A既产生非空串也可以产生  ，则它可能“看到”的当前输入的符号来自a∈First(A)，或者来自b∈Follow(A)。但A最不期望的是 a＝b，因为这样，A面临两难的选择－ A 还是 A  ? 2019/5/5 《编译原理与技术》讲义

LL（1）文法一般的，文法G是LL(1)文法，如果任何A∈VN，其产生式，A1|2|…|n，满足： 1 lookhead
read from Left to right Leftmost derivation 一般的，文法G是LL(1)文法，如果任何A∈VN，其产生式，A1|2|…|n，满足： First(i)First(j) = ∅，ij, i,j=1,2,…n ; 若∈First(k)，则First(i)Follow(A) = ∅, i  k. 2019/5/5 《编译原理与技术》讲义

LL（1）文法产生式不含左递归具有相同左部的产生式不含左因子
LL(1)文法G进行自顶向下分析时，非终结符A面临当前输入符号a时即可作出唯一的产生式的选择决定 2019/5/5 《编译原理与技术》讲义

自顶向下分析 LL(1)文法的递归下降分析为LL（1）文法G（无左因子、左递归）构造一个无回溯的预测分析器。
文法G的每一个非终结符A对应一个（递归）分析过程A()。分析过程A()－ 1) 由当前输入符号(lookhead)决定产生式的选取； 2) 产生式A X1X2…Xn的分析过程：从左往右逐个分析。 Xi∈VT，则调用匹配过程 match(Xi) Xi∈VN，则调用分析过程 Xi() 3) 空产生式A   ，直接返回 2019/5/5 《编译原理与技术》讲义

if ( lookhead ∈ First(X1X2…Xn) ) /* 产生式AX1X2…Xn的分析过程 */ }
void A() { if ( lookhead ∈ First(X1X2…Xn) ) /* 产生式AX1X2…Xn的分析过程 */ } else if … … /*A的其它非空产生式的分析*/ else if ( ( lookhead ∈ Follow(A) ) and A  ∈P) { return; /* 空产生式，直接返回 */ } else error() /* 语法错误*/ 2019/5/5 《编译原理与技术》讲义

递归下降分析匹配过程 match( token t ) void match( token t ) {
if ( lookhead == t ) { //终结符叶子和输入符是否匹配（相同） lookhead = next_token(); //若匹配则获取下一记号，即向前移动输入指针 } else error() /* 否则语法错误－需要符号 t */ } 2019/5/5 《编译原理与技术》讲义

递归下降分析 e.g.8 编写文法G2‘的递归分析过程。 void E() E T E’ { if (lookhead==‘(‘ ) ||
(lookhead==‘id’)) { T(); E’(); } else error(); } E T E’ E’ + T E’ |  T F T’ T’ * F T’ |  F ( E ) F id 2019/5/5 《编译原理与技术》讲义

e.g.8 编写文法G2‘的递归分析过程。 E T E’ E’ + T E’ |  T F T’ T’ * F T’ | 
void E’ () { if (lookhead==‘+‘) { match(‘+’); T(); E’ (); } else // {return; } //将看成与任一符号匹配 // 从而将以下程序省略！！！ if ( (lookhead==‘$’ ) || (lookhead==‘)’ ) { return; } else error(); } E T E’ E’ + T E’ |  T F T’ T’ * F T’ |  F ( E ) F id 2019/5/5 《编译原理与技术》讲义

e.g.8 编写文法G2‘的递归分析过程。 void T() E T E’ { if (lookhead==‘(‘ ) ||
(lookhead==‘id’)) { F(); T’(); } else error(); } E T E’ E’ + T E’ |  T F T’ T’ * F T’ |  F ( E ) F id 2019/5/5 《编译原理与技术》讲义

e.g.8 编写文法G2‘的递归分析过程。 E T E’ E’ + T E’ |  T F T’ T’ * F T’ | 
void T’ () { if (lookhead==‘*‘) { match(‘*’); F(); T’ (); } else // {return; } //将看成与任一符号匹配 // 从而将以下程序省略！！！ if ( (lookhead==‘+’ ) || (lookhead==‘$’ ) || (lookhead==‘)’ ) { return; } else error(); } E T E’ E’ + T E’ |  T F T’ T’ * F T’ |  F ( E ) F id 2019/5/5 《编译原理与技术》讲义

e.g.8 编写文法G2‘的递归分析过程。 void F() { if (lookhead==‘(‘ ) { E T E’
match( ‘(‘ ); E(); match( ‘)’ ); } else if (lookhead==‘id’) { match( ‘id’ ); } else error(); E T E’ E’ + T E’ |  T F T’ T’ * F T’ |  F ( E ) F id 2019/5/5 《编译原理与技术》讲义

自顶向下分析 LL(1)文法的非递归的预测分析方法表驱动的预测分析－通过查表决定产生式的选取输出输入串 Top 控制程序 X
a1 . ai $ Top 控制程序（预测分析器）输出 X . $ 分析栈预测分析表 Bottom 2019/5/5 《编译原理与技术》讲义

非递归的预测分析方法分析栈(stack) 栈的内容－VTVN {$}，开始分析时，”$”位于栈底，S位于栈顶。
分析表 M : VN × (VT{$}) (P {error}) 对于A∈VN，a∈VT，有 A∈P M[ A, a ] = error() // 错误恢复例程控制程序 2019/5/5 《编译原理与技术》讲义

非递归的预测分析方法控制程序由当前栈顶符号X和当前输入符号a决定采取的分析动作。 ① X=a=$ ，则分析成功，STOP!
② X=a  $ ，则 1) popup() // 从栈顶弹出X 2) 移动输入指针至下一符号 X∈VT ③ X  a，error() // 匹配失败! // 调用错误恢复程序 2019/5/5 《编译原理与技术》讲义

非递归的预测分析方法控制程序 ① M[ X, a ] = { X  U V W }，则 popup(); //弹出X
push( W ); push( V ); push( U ); // 产生式右部符号以逆序入栈 X∈VN ② M[ X, a ] = error()，则调用错误恢复程序 2019/5/5 《编译原理与技术》讲义

e.g.9 表达式文法G2’的预测分析表 id + * ( ) $ E ETE’ E’ E’+TE’ E’ T TFT’ T’
VT{$} VN id + * ( ) $ E ETE’ E’ E’+TE’ E’ T TFT’ T’ T’ T’*FT’ F F id F (E) 2019/5/5 《编译原理与技术》讲义

e.g.10 表达式id+id*id的非递归预测分析过程
分析栈输入串输出 $ E id + id * id $ $ E’ T id + id * id $ E T E’ $ E’ T’ F id + id * id $ T F T’ $ E’ T’ id id + id * id $ F id $ E’ T’ + id * id $ id匹配成功 $ E’ + id * id $ T’ $ E’ T + + id * id $ E’ + T E’ 2019/5/5 《编译原理与技术》讲义

e.g.10 表达式id+id*id的非递归预测分析过程（续）
分析栈输入串输出 $ E’ T + + id * id $ E’ + T E’ $ E’ T id * id $ +匹配成功 $ E’ T’ F id * id $ T F T’ $ E’ T’ id id * id $ F id $ E’ T’ * id $ id匹配成功 $ E’ T’ F * * id $ T’ * F T’ $ E’ T’ F id $ *匹配成功 2019/5/5 《编译原理与技术》讲义

e.g.10 表达式id+id*id的非递归预测分析过程（续）
分析栈输入串输出 $ E’ T’ F id $ *匹配成功 $ E’ T’ id id $ F id $ E’ T’ $ id匹配成功 $ E’ $ T’ $ E’ 分析成功！ 2019/5/5 《编译原理与技术》讲义

预测分析表的构造考查任意产生式A：所有无定义的表项填上error() 预测分析表如果不含多重定义表项则相应文法是LL(1)的。
M[ A, a ] = {A} ,如果 a ∈ First()-{} M[ A, b ] = {A} ,如果 ∈First()且b∈Follow(A) 所有无定义的表项填上error() 预测分析表如果不含多重定义表项则相应文法是LL(1)的。 2019/5/5 《编译原理与技术》讲义

e.g.11构造文法G4的预测分析表文法G4：(if … then … else) 1) S  i E t S S’ 2) S  a
5) E  b First(S) = { i, a } First(S’) = { e,  } First(E) = { b } Follow(S) = { $, e } Follow(S’) = { $, e } Follow(E) = { t } 2019/5/5 《编译原理与技术》讲义

e.g.11构造文法G4的预测分析表 1) S  i E t S S’ , i∈First(i E t S S’), 故而
M[ S, i ] = { S  i E t S S’ } 2) S  a ,显然，M[ S, a ] = { S  a } 3) S’  e S ,显然，M[ S’, e ] = { S’ e S} 4) S’   , 则对于Follow(S’)={$,e}中的每个符号,有：M[ S’, $ ]={ S’   } 和 M[ S’, e ] = { S’   } 5) E  b ,显然，M[ E, b ] = { E  b } 2019/5/5 《编译原理与技术》讲义

e.g.11构造文法G4的预测分析表有多重定义 a b e i t $ S Sa S iEtSS’ S’ S’  eS S’  
VT{$} VN a b e i t $ S Sa S iEtSS’ S’ S’  eS S’   E E  b 有多重定义 2019/5/5 《编译原理与技术》讲义

二义性文法决不是LL（1）文法。其预测分析表有多重定义表项。
文法G4不是LL(1)文法。文法G4具有二义性。对于串 i b t i b t a e a 有两个不同的最左推导： S  i E t S S’  i b t S S’  i b t i E t S S’ S’  i b t i b t S S’ S’  i b t i b t a S’ S’  i b t i b t a e S S’  i b t i b t a e a S’  i b t i b t a e a   i b t i b t a e a  i b t i b t a  S’  i b t i b t a S’  i b t i b t a e S  i b t i b t a e a 1 2 2019/5/5 《编译原理与技术》讲义

e.g.12文法G5不是LL（1）文法文法G5： 1) A  a A a 2) A  
文法G5产生串长为偶数的a串，它是非二义文法，但却不是LL(1)文法。因为： First( A ) = { a ,  } , Follow( A ) = { $, a } ① 分析表中M[ A, a ] = { A  a A a, A   }有多重定义；或者 ② 由于A  为空产生式，而 First( A  aAa )  Follow(A)  { a }  ∅ 2019/5/5 《编译原理与技术》讲义

文法G5关于串aaaa的最左推导与分析树 A A 1)  a A a 2)  a a A a a a A a
 显然，在只有在偶数长(≥2)的a串的前一半a被产生（推导）出来后，产生式A方被选择来作分析（推导）。而此前只用AaAa。 2019/5/5 《编译原理与技术》讲义

A 输入串 a a a a $ 自顶向下分析输入a串，即寻找一个产生a串的最左推导过程。但遗憾是，输入串是从左往右一个一个符号地被读入，每当读入一个符号a时，由于不知道输入串中总共有多少符号a，也就无法判定此时是否已经“读完了”a串的前一半a。这就造成了A面临输入a时的存在矛盾（或多重）的产生式选择。 2019/5/5 《编译原理与技术》讲义

错误恢复程序的错误类型编译时错误(compile error) 词法错误－如出现非法字符语法错误－如括号不配对、语句结束无分号
（静态）语义错误－如形/实参数类型不匹配运行时错误(run-time error) 动态（运行时）语义错误－无限递归（循环）、地址（指针）越界、栈上溢（overflow）和下溢（underflow）、异常（exception） 2019/5/5 《编译原理与技术》讲义

错误恢复错误恢复的目标错误（性质）报告准确，错误位置精准
能快速地从当前错误中恢复，以期发现后面的错误；任何（编译）错误不能导致编译器崩溃对常见的错误应该有很好的恢复措施尽量减少“株连”错误的产生 2019/5/5 《编译原理与技术》讲义

错误恢复错误恢复的策略紧急方式（panic mode）
发现错误时，分析器将抛弃若干输入符号，直到遇上希望的输入－同步符号为止。该方法较容易实现且不会陷入死循环，但对忽略的输入无法进行分析。同步符号（集合）的选取－若待分析语法成份为A，则同步符号（集合）Synch（A）的可以考虑： 1）Follow（A）－考虑结束A的分析工作 2）First（A）－重新开始A的分析 2019/5/5 《编译原理与技术》讲义

寻找“;” 因为“;”∈Follow（Stat）
e.g. 13 紧急方式错误恢复 … a = Expr if … ; Missing “;” ; 寻找“;” 因为“;”∈Follow（Stat）被跳过的输入串 2019/5/5 《编译原理与技术》讲义

e.g. 13 紧急方式错误恢复 … a = Expr if … ;
3）为避免忽略过多的输入符号，可以考虑将较高层次的语法单位的首符号（First）加入低层结构的同步符号集合中。如语句Stat的首符号if加入Synch（Stat），这样，当某一语句分析出错时，可以抛弃该语句中的其它输入符号，而开始下一个新语句的分析。新的分析起点 2019/5/5 《编译原理与技术》讲义

错误恢复错误恢复的其它策略短语级恢复（phrase level）－对输入串作局部校正，插入或删除符号
出错产生式（error production）－将出错情况用产生式的形式来描述，（参见YACC）如 Stat  error ‘;’ // 描述语句分析时出错时将跳过若干输入符号直至‘;’ 出现全局校正（global correction） 2019/5/5 《编译原理与技术》讲义

预测分析的错误恢复递归下降分析的错误恢复为每个分析过程增加一个参数－同步符号集合
一般地，当错误发生时，错误恢复例程error（）将反复调用词法程序忽略若干输入符号，直至同步集合（可以考虑Follow集合）中的符号出现为止，然后分析过程结束返回。 2019/5/5 《编译原理与技术》讲义

e.g. 14 文法G2‘带有错误恢复的分析过程 void E(SyncSet) // { $ } E T E’
{ if (lookhead==‘(‘ ) || (lookhead==‘id’)) { T({ + }  SyncSet); E’(SyncSet); } else errorE(SyncSet); } E T E’ E’ + T E’ |  T F T’ T’ * F T’ |  F ( E ) F id 2019/5/5 《编译原理与技术》讲义

e.g. 14 文法G2‘带有错误恢复的分析过程 E T E’ E’ + T E’ |  T F T’ T’ * F T’ | 
void E’ (SyncSet) { if (lookhead==‘+‘) { match(‘+’); T({ + }  SyncSet); E’ (SyncSet); } else if ( (lookhead==‘$’ ) || (lookhead==‘)’ ) { return; } else errorE‘(SyncSet); } E T E’ E’ + T E’ |  T F T’ T’ * F T’ |  F ( E ) F id 2019/5/5 《编译原理与技术》讲义

e.g. 14 文法G2‘带有错误恢复的分析过程 void T(SyncSet) E T E’
{ if (lookhead==‘(‘ ) || (lookhead==‘id’)) { F({ * }  SyncSet); T’(SyncSet); } else errorT(SyncSet); } E T E’ E’ + T E’ |  T F T’ T’ * F T’ |  F ( E ) F id 2019/5/5 《编译原理与技术》讲义

e.g. 14 文法G2‘带有错误恢复的分析过程 E T E’ E’ + T E’ |  T F T’ T’ * F T’ | 
void T’ (SyncSet) { if (lookhead==‘*‘) { match(‘*’); F({ * }  SyncSet); T’ (SyncSet); } else if ( (lookhead==‘+’ ) || (lookhead==‘$’ ) || (lookhead==‘)’ ) { return; } else errorT’(SyncSet); } E T E’ E’ + T E’ |  T F T’ T’ * F T’ |  F ( E ) F id 2019/5/5 《编译原理与技术》讲义

e.g. 14 文法G2‘带有错误恢复的分析过程 void F(SyncSet) { if (lookhead==‘(‘ ) {
match( ‘(‘ ); E( { ) }  SyncSet); match( ‘)’ ); } else if (lookhead==‘id’) { match( ‘id’ ); } else errorF(SyncSet); } E T E’ E’ + T E’ |  T F T’ T’ * F T’ |  F ( E ) F id 2019/5/5 《编译原理与技术》讲义

非递归预测分析的错误恢复出错情况： 1）栈顶终结符 x 与当前输入符号a不匹配；紧急方式的错误恢复－ pop（）
2）M[ A,a ] = error / 空白 2019/5/5 《编译原理与技术》讲义

非递归预测分析的错误恢复出错情况： 2）M[ A,a ] = error / 空白构造带错误恢复的预测分析表－ ∙ 构造正常的预测分析表
∙ 若M[ A,a ] = { } 且 a∈Follow（A）则填上synch 否则保持空白若A ∈ P则在错误2）发生时，可以选择该产生式来分析。Why？ 2019/5/5 《编译原理与技术》讲义

e.g. 15 有错误恢复的预测分析表 id + * ( ) $ E ETE’ synch E’ E’+TE’ E’ T TFT’
VT{$} VN id + * ( ) $ E ETE’ synch E’ E’+TE’ E’ T TFT’ T’ T’ T’*FT’ F F id F (E) 空白项：跳过当前输入符，栈顶不变，继续栈顶符的分析； synch：弹出栈顶符（结束它的分析），当前输入不变，开始下一符号（原次栈顶）的分析。 2019/5/5 《编译原理与技术》讲义

e.g. 16 输入串+id*+$的分析过程分析栈输入串输出 $ E + id * + $ 跳过+ $ E id * + $
$ E’ T id * + $ E T E’ $ E’ T’ F id * + $ T F T’ $ E’ T’ id id * + $ F id $ E’ T’ * + $ id匹配成功 $ E’ T’ F * * + $ T’ * F T’ 2019/5/5 《编译原理与技术》讲义

e.g. 16 输入串+id*+$的分析过程分析栈输入串输出 $ E’ T’ F * * + $ T’ * F T’
* + $ T’ * F T’ $ E’ T’ F + $ *匹配成功 $ E’ T’ + $ Synch弹出F $ E’ + $ T’  $ E’ T + + $ E’ + T E’ $ E’ T $ +匹配成功 $ E’ $ Synch弹出T $ E’  2019/5/5 《编译原理与技术》讲义

预测分析错误恢复考查以下输入串的预测分析过程 ∙ ) a $ ∙ ( a $ ∙ a ) $ 能否改进e.g.15 中的错误恢复过程？

编译原理与技术－－自顶向下分析 2019/5/5 《编译原理与技术》讲义.

Similar presentations

Presentation on theme: "编译原理与技术－－自顶向下分析 2019/5/5 《编译原理与技术》讲义."— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

编译原理与技术 －－ 自顶向下分析 2019/5/5 《编译原理与技术》讲义.

Similar presentations

Presentation on theme: "编译原理与技术 －－ 自顶向下分析 2019/5/5 《编译原理与技术》讲义."— Presentation transcript:

Similar presentations

About project

反馈

编译原理与技术－－自顶向下分析 2019/5/5 《编译原理与技术》讲义.

Presentation on theme: "编译原理与技术－－自顶向下分析 2019/5/5 《编译原理与技术》讲义."— Presentation transcript: