编译原理与技术 －－ 自顶向下分析 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 $ 2019/5/5 《编译原理与技术》讲义

自顶向下分析 e.g.1 文法G0： S A B C A a B b C c S $ $ A B C a 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 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 $ 2019/5/5 《编译原理与技术》讲义

自顶向下分析 e.g.1 文法G0： S A B C A a B b C c S $ A B C $ 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 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 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$ 2019/5/5 《编译原理与技术》讲义

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

自顶向下分析 试探分析法 e.g.2 文法G1如下 S  x A y A  ab A  a 输入串 xay$ 的分析过程。 2019/5/5 《编译原理与技术》讲义

自顶向下分析 试探分析法 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 《编译原理与技术》讲义

e.g.6文法G2‘的First集合 E T E’ E’ + T E’ |  T F T’ T’ * F T’ |  F ( E ) F id First( T’ ) = { *, } 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( T ) = First( F ) = { (, id } 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( E’) = { +,  } 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( 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 《编译原理与技术》讲义