
编译原理与技术 自顶向下分析.ppt
90页编译原理与技术-- 自顶向下分析2024/8/311《编译原理与技术》讲义自顶向下分析¡分析树的建立l从根(开始符号)出发,从上而下,从左自右为输入串建立分析树l为输入串寻找一个最左推导e.g.1 文法G0如下S A B C A a B b C c输入串 abc$$-串结束符2024/8/312《编译原理与技术》讲义自顶向下分析e.g.1 文法G0:S A B CA a B b C ca b c $S $当前记号(指针)2024/8/313《编译原理与技术》讲义自顶向下分析e.g.1 文法G0:S A B CA a B b C ca b c $S $A B C$2024/8/314《编译原理与技术》讲义自顶向下分析e.g.1 文法G0:S A B CA a B b C ca b c $S $A B C$a2024/8/315《编译原理与技术》讲义自顶向下分析e.g.1 文法G0:S A B CA a B b C ca b c $S $A B C$a终结符叶子与当前符号匹配?2024/8/316《编译原理与技术》讲义自顶向下分析e.g.1 文法G0:S A B CA a B b C ca b c $S $A B C$ab指向下一记号2024/8/317《编译原理与技术》讲义自顶向下分析e.g.1 文法G0:S A B CA a B b C ca b c $S $A B C$ab2024/8/318《编译原理与技术》讲义自顶向下分析e.g.1 文法G0:S A B CA a B b C ca b c $S $A B C$abc2024/8/319《编译原理与技术》讲义自顶向下分析e.g.1 文法G0:S A B CA a B b C ca b c $S $A B C$abc2024/8/3110《编译原理与技术》讲义自顶向下分析e.g.1 文法G0:S A B CA a B b C ca b c $S $A B C$abcOK!输入串分析成功!2024/8/3111《编译原理与技术》讲义自顶向下分析e.g.1 文法G0:S A B CA a B b C c串abc$的最左推导过程:S$⇒ABC$⇒aBC$⇒abC$⇒abc$2024/8/3112《编译原理与技术》讲义自顶向下分析¡文法G0较简单-非终结符只有唯一的产生式¡试探分析法当待分析(展开)的非终结符对应多条产生式,可以选择其一进行尝试分析(最左推导);当此产生式无法与输入串“匹配”时则需要“回溯”-即放弃已建立的部分分析树,同时调整输入串指针恢复到此次分析前位置,再另选一产生式重新分析。
只有当所有的所有的尝试均不成功,分析失败!2024/8/3113《编译原理与技术》讲义自顶向下分析¡试探分析法e.g.2 文法G1如下S x A yA ab A a输入串 xay$ 的分析过程2024/8/3114《编译原理与技术》讲义自顶向下分析¡试探分析法e.g.2 文法G1:(1)S x A y(2)A ab (3)A a输入串 xay$的分析过程S$x A y $x a y $输入串终结符叶子x与输入符x匹配a b选用产生式(1)选用产生式(2)匹配失败!2024/8/3115《编译原理与技术》讲义自顶向下分析¡试探分析法e.g.2 文法G1:(1)S x A y(2)A ab (3)A a输入串 xay$的分析过程S$x A y $x a y $输入串a b选用产生式(1)选用产生式(2)匹配失败!回溯:重新分析A2024/8/3116《编译原理与技术》讲义自顶向下分析¡试探分析法e.g.2 文法G1:(1)S x A y(2)A ab (3)A a输入串 xay$的分析过程。
S$x A y $x a y $输入串选用产生式(1)a选用产生式(3)终结符叶子a与输入符a匹配分析成功!2024/8/3117《编译原理与技术》讲义¡试探分析法在文法有左递归特征时,可能导致无限循环而此时无法读入任何输入符(输入指针保持不变)如表达式文法G2:EE+T | T TT*F | FF(E) | id自顶向下分析a + b 输入串EE + TE + T… …2024/8/3118《编译原理与技术》讲义自顶向下分析¡预测分析法对于待分析的非终结符A,可以根据当前输入符当前输入符号(记号)号(记号)来准确唯一唯一地选择A的某一产生式若该产生式“匹配”成功,则意味着A分析成功;若匹配失败,则即使选择A的其它产生式也会导致A分析失败(因而不需要回溯不需要回溯)Case 1:文法G1 A a bA的两个产生式右部具有 A a相同的(非空)前缀a 那么A面临输入符a选择谁呢?2024/8/3119《编译原理与技术》讲义¡预测分析法提左因子的文法变换文法G1中, A a b A a A’ A a A’ b | 自顶向下分析A 1A 21和2不含相同前缀提左因子A A’A’ 1 | 2引入非终结符A’提左因子2024/8/3120《编译原理与技术》讲义¡预测分析法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。
可以与之“匹配”!2024/8/3121《编译原理与技术》讲义¡预测分析法提左因子变换的一般形式自顶向下分析A 1 | 2 |…| n A i不含相同前缀, 不含前缀提左因子变换后:A A’ | A’ 1 | 2 |…| n 2024/8/3122《编译原理与技术》讲义¡预测分析法Case 2: 文法G2 E E + TE的产生式的(直接)左递归妨碍了E T 输入符号的有效读入(实际上不读) 并导致死循环消除左递归(A ⇒+ A…)的文法变换 - 直接左递归的消除(A ⇒A…)自顶向下分析A AA 消除直接左递归A A’A’ A’ | 引入非终结符A’ ,形成右递归文法右递归文法2024/8/3123《编译原理与技术》讲义¡预测分析法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’2024/8/3124《编译原理与技术》讲义EETTFii+*FTiF文法G2:i+i*i的分析树ETE’FT’iT+E’FT’iFT’i*文法G2’:i+i*i的分析树2024/8/3125《编译原理与技术》讲义自顶向下分析¡预测分析法消除左递归(A ⇒+ A…)的文法变换-间接左递归的消除(A ⇒+ B… ⇒+A…) 对于含间接左递归的文法G,可以先设法变换为含有直接左递归直接左递归的文法G’(通常将较简单的产生式逐次代入较复杂的产生式),然后再行消除G’中的直接左递归即可。
2024/8/3126《编译原理与技术》讲义自顶向下分析¡预测分析法e.g.5消除文法G3中的(间接)左递归S Aa | a | bA Ac | c | Sd将S相应产生式分别代入A相关产生式,得到文法G3’:S Aa | a | bA Ac | c | Aad | ad | bd 消除G3’中(A的)直接左递归,则有2024/8/3127《编译原理与技术》讲义自顶向下分析¡预测分析法e.g.5消除文法G3中的(间接)左递归S Aa | a | bA c A’ | ad A’ | bd A’A’ c A’ | ad A’ | 上述文法不再含有左递归2024/8/3128《编译原理与技术》讲义自顶向下分析¡回顾一下什么是预测分析法?对于待分析的非终结符A,可以根据当前输入符当前输入符号(记号)号(记号)来准确唯一唯一地选择A的某一产生式若该产生式“匹配”成功,则意味着A分析成功;若匹配失败,则即使选择A的其它产生式也会导致A分析失败(因而不需要回溯不需要回溯)在对文法提左因子和消除左递归后,可以实施预测分析了!但是,待分析或展开的非终结符A如何利用当前输入符(记号)来选择产生式呢?2024/8/3129《编译原理与技术》讲义¡First集合(首符号集合) First() = { a | ⇒*a } { | ⇒* } , 其中 a∈VT, , ∈(VTVN) First(a) = { a | a∈VT } A∈V N,考查A的每个产生式:A X1X2…Xn,Xi ∈(VTVN), 计算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)2024/8/3130《编译原理与技术》讲义¡e.g.6文法G2‘的First集合 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idFirst( F ) = { (, id }2024/8/3131《编译原理与技术》讲义¡e.g.6文法G2‘的First集合 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idFirst( T’ ) = { *, }2024/8/3132《编译原理与技术》讲义¡e.g.6文法G2‘的First集合 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idFirst( T ) = First( F ) = { (, id }2024/8/3133《编译原理与技术》讲义¡e.g.6文法G2‘的First集合 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idFirst( E’) = { +, }2024/8/3134《编译原理与技术》讲义¡e.g.6文法G2‘的First集合 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idFirst( E ) = First( T ) = First( F ) = { (, id }2024/8/3135《编译原理与技术》讲义¡e.g.6文法G2‘的First集合 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idFirst( E ) = First( T )= First( F ) = { (, id }First( E’) = { +, }First( T ) = First( F ) = { (, id }First( T’ ) = { *, }First( F ) = { (, id }2024/8/3136《编译原理与技术》讲义¡Follow集合(后继符号集合) Follow(A)={ a | S ⇒* Aa },其中 a∈VT, A∈ VN ,, ∈(VTVN)* $ ∈Follow(S). 若 A B∈P,则把First()-{}加入Follow(B) 若 A B∈P 或 A B∈P 且 ⇒* (即 ∈First() ),则 把Follow(A)加入Follow(B) S ⇒* Aa S ⇒* Aa ⇒ Ba ⇒ Ba ⇒* B a ⇒ Ba 显然a ∈ Follow(A) Follow(B)2024/8/3137《编译原理与技术》讲义¡e.g.7文法G2‘的Follow集合 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idFollow( E ) = { $, ) }$ ∈Follow(E).2024/8/3138《编译原理与技术》讲义¡e.g.7文法G2‘的Follow集合 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idFollow( E’ ) = Follow(E)= { $, ) }2024/8/3139《编译原理与技术》讲义¡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)= { + } { $, ) }= { +, $, ) }2024/8/3140《编译原理与技术》讲义¡e.g.7文法G2‘的Follow集合 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idFollow( T’ ) = Follow(T)= {+, $, ) }2024/8/3141《编译原理与技术》讲义¡e.g.7文法G2‘的Follow集合 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F id Follow( F ) = (First(T’)-{}) Follow(T) Follow(T’)= { * } { + , $ , ) }= { * , + , $ , ) }2024/8/3142《编译原理与技术》讲义¡e.g.7文法G2‘的Follow集合 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idFollow( F ) = { * , + , $ , ) }Follow( T’ ) = {+, $ , ) }Follow( T ) = { + , $ , ) }Follow( E’ ) = { $ , ) }Follow( E ) = { $ , ) }2024/8/3143《编译原理与技术》讲义SA’a… …输入串b… …自顶向下分析A时,如果A只产生非空符号串,那么A期望“看到”的当前输入的符号最好是a∈First(A),这样的话,选用产生式A来分析,即能产生(推导)出以a开头的串并期待与相应输入串匹配。
2024/8/3144《编译原理与技术》讲义自顶向下分析A时,如果A只产生的是不包含任何有效符号的串- ,则它 “看到”的当前输入的符号只能是b∈Follow(A)这时选用产生式A 来“结束”对A的分析而开始的分析SA’输入串b… … …2024/8/3145《编译原理与技术》讲义SA’b… SA’a…b…自顶向下分析A时,如果A既产生非空串也可以产生 ,则它 可能“看到”的当前输入的符号来自a∈First(A),或者来自b∈Follow(A)但A最不期望的是 a=b,因为这样,A面临两难的选择- A 还是 A ?2024/8/3146《编译原理与技术》讲义LL(1)文法¡一般的,文法G是LL(1)文法,如果任何A∈VN,其产生式,A1|2|…|n,满足: First(i)First(j) = ∅,ij, i,j=1,2,…n ; 若∈First(k),则First(i)Follow(A) = ∅, i k.read from Left to rightLeftmost derivation1 lookhead2024/8/3147《编译原理与技术》讲义LL(1)文法¡产生式不含左递归¡具有相同左部的产生式不含左因子¡LL(1)文法G进行自顶向下分析时,非终结符A面临当前输入符号a时即可作出唯一的产生式的选择决定2024/8/3148《编译原理与技术》讲义自顶向下分析¡LL(1)文法的递归下降分析为LL(1)文法G(无左因子、左递归左因子、左递归)构造一个无回溯的预测分析器。
文法G的每一个非终结符A对应一个(递归)分析过程A()分析过程A()-1) 由当前输入符号(lookhead)决定产生式的选取;2) 产生式A X1X2…Xn的分析过程:从左往右逐个分析Xi∈VT,则调用匹配过程 match(Xi) Xi∈VN,则调用分析过程 Xi()3) 空产生式A , 直接返回2024/8/3149《编译原理与技术》讲义¡递归分析过程A()void A() { if ( lookhead ∈First(X1X2…Xn)){/*产生式AX1X2…Xn的分析过程*/} else if … … /*A的其它非空产生式的分析*/ else if ( ( lookhead ∈Follow(A))andA∈P) { return; /* 空产生式,直接返回 */ } else error() /* 语法错误*/ }2024/8/3150《编译原理与技术》讲义递归下降分析¡匹配过程 match( token t )void match( token t ){ if ( lookhead == t ) { //终结符叶子和输入符是否匹配(相同) lookhead = next_token(); //若匹配则获取下一记号,即向前移动输入指针 } else error() /* 否则语法错误-需要符号需要符号 t */ }2024/8/3151《编译原理与技术》讲义递归下降分析¡e.g.8 编写文法G2‘的递归分析过程。
E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idvoid E(){ if (lookhead==‘(‘ ) || (lookhead==‘id’)) { T(); E’(); } else error(); }2024/8/3152《编译原理与技术》讲义¡e.g.8 编写文法G2‘的递归分析过程 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idvoid E’ (){ if (lookhead==‘+‘) { match(‘+’); T(); E’ (); } else // {return; } //将看成与任一符号匹配// 从而将以下程序省略!!! if ( (lookhead==‘$’ ) || (lookhead==‘)’ ) { return; } else error(); }2024/8/3153《编译原理与技术》讲义¡e.g.8 编写文法G2‘的递归分析过程。
E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idvoid T(){ if (lookhead==‘(‘ ) || (lookhead==‘id’)) { F(); T’(); } else error(); }2024/8/3154《编译原理与技术》讲义¡e.g.8 编写文法G2‘的递归分析过程 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idvoid T’ (){ if (lookhead==‘*‘) { match(‘*’); F(); T’ (); } else // {return; } //将看成与任一符号匹配// 从而将以下程序省略!!! if ( (lookhead==‘+’ ) || (lookhead==‘$’ ) || (lookhead==‘)’ ) { return; } else error(); }2024/8/3155《编译原理与技术》讲义¡e.g.8 编写文法G2‘的递归分析过程。
E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idvoid F(){ if (lookhead==‘(‘ ) { match( ‘(‘ ); E(); match( ‘)’ ); } else if (lookhead==‘id’) { match( ‘id’ ); } else error(); }2024/8/3156《编译原理与技术》讲义自顶向下分析¡LL(1)文法的非递归的预测分析方法表驱动的预测分析-通过查表决定产生式的选取输入串控制程序(预测分析器)预测分析表X...$a1..ai..$分析栈输出TopBottom2024/8/3157《编译原理与技术》讲义非递归的预测分析方法¡分析栈(stack)栈的内容-VTVN {$},开始分析时,”$”位于栈底,S位于栈顶¡分析表 M : VN × (VT{$}) (P {error})对于A∈VN,a∈VT,有 A∈P M[ A, a ] = error() // 错误恢复例程¡控制程序2024/8/3158《编译原理与技术》讲义非递归的预测分析方法¡控制程序由当前栈顶符号X和当前输入符号a决定采取的分析动作。
• X∈VT① X=a=$ ,则分析成功,STOP!② X=a $ ,则 1) popup() // 从栈顶弹出X 2) 移动输入指针至下一符号③ X a,error() // 匹配失败! // 调用错误恢复程序2024/8/3159《编译原理与技术》讲义非递归的预测分析方法¡控制程序• X∈VN①M[ X, a ] = { X U V W },则 popup(); //弹出X push( W ); push( V ); push( U ); // 产生式右部符号以逆序入栈②M[ X, a ] = error(),则调用错误恢复程序 2024/8/3160《编译原理与技术》讲义e.g.9 表达式文法G2’的预测分析表 VT{$} VN id+*()$EETE’ETE’E’E’+TE’E’E’TTFT’TFT’T’T’T’*FT’T’T’FF idF (E)2024/8/3161《编译原理与技术》讲义e.g.10 表达式id+id*id的非递归预测分析过程分析栈输入串输出$ Eid + id * id $$ E’ Tid + id * id $E T E’$ E’ T’ Fid + id * id $T F T’$ E’ T’ idid + id * id $F id$ E’ T’ + id * id $id匹配成功$ E’ + id * id $T’$ E’ T ++ id * id $E’ + T E’2024/8/3162《编译原理与技术》讲义e.g.10 表达式id+id*id的非递归预测分析过程(续)分析栈输入串输出$ E’ T ++ id * id $E’ + T E’$ E’ Tid * id $+匹配成功$ E’ T’ Fid * id $T F T’$ E’ T’ idid * id $F id$ E’ T’* id $id匹配成功$ E’ T’ F ** id $T’ * F T’$ E’ T’ F id $*匹配成功2024/8/3163《编译原理与技术》讲义e.g.10 表达式id+id*id的非递归预测分析过程(续)分析栈输入串输出$ E’ T’ F id $*匹配成功$ E’ T’ id id $F id$ E’ T’ $id匹配成功$ E’ $T’$ $E’分析成功!2024/8/3164《编译原理与技术》讲义预测分析表的构造¡考查任意产生式A:M[ A, a ] = {A} ,如果 a ∈First()-{}M[A,b]={A} ,如果 ∈First()且b∈Follow(A)¡所有无定义的表项填上error()¡预测分析表如果不含多重定义表项则相应文预测分析表如果不含多重定义表项则相应文法是法是LL(1)的。
的2024/8/3165《编译原理与技术》讲义¡文法G4:(if … then … else)1) S i E t S S’ 2) S a3) S’ e S4) S’ 5) E be.g.11构造文法G4的预测分析表First(S) = { i, a }First(S’) = { e, }First(E) = { b }Follow(S) = { $, e }Follow(S’) = { $, e }Follow(E) = { t }2024/8/3166《编译原理与技术》讲义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 }2024/8/3167《编译原理与技术》讲义e.g.11构造文法G4的预测分析表 VT{$} VN a beit$SSaS iEtSS’S’S’ eSS’ S’ EE b有多重定义2024/8/3168《编译原理与技术》讲义¡二义性文法决不是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 a122024/8/3169《编译原理与技术》讲义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} ∅2024/8/3170《编译原理与技术》讲义Aa A aa A a文法G5关于串aaaa的最左推导与分析树 A1) a A a2) a a A a a3) a a a a4) a a a a显然,在只有在偶数长(≥2)的a串的前一半前一半a被产生(推导)出来后,产生式A方被选择来作分析(推导)。
而此前只用AaAa2024/8/3171《编译原理与技术》讲义Aa a a a $输入串自顶向下分析输入a串,即寻找一个产生a串的最左推导过程但遗憾是,输入串是从左往右一个一个符号地被读入,每当读入一个符号a时,由于不知道输入串中总共有多少符号a,也就无法判定此时是否已经“读完了”a串的前一半前一半a这就造成了A面临输入a时的存在矛盾(或多重)的产生式选择2024/8/3172《编译原理与技术》讲义错误恢复¡程序的错误类型编译时错误编译时错误(compile error)词法错误-如出现非法字符 语法错误-如括号不配对、语句结束无分号(静态)语义错误-如形/实参数类型不匹配运行时错误运行时错误(run-time error)动态(运行时)语义错误-无限递归(循环)、地址(指针)越界、栈上溢(overflow)和下溢(underflow)、异常(exception)2024/8/3173《编译原理与技术》讲义错误恢复¡错误恢复的目标错误(性质)报告准确,错误位置精准能快速地从当前错误中恢复,以期发现后面的错误;任何(编译)错误不能导致编译器崩溃对常见的错误应该有很好的恢复措施尽量减少“株连”错误的产生 2024/8/3174《编译原理与技术》讲义错误恢复¡错误恢复的策略紧急方式(panic mode)发现错误时,分析器将抛弃若干输入符号,直到遇上希望的输入-同步符号为止。
该方法较容易实现且不会陷入死循环,但对忽略的输入无法进行分析同步符号(集合)的选取-若待分析语法成份为A,则同步符号(集合)Synch(A)的可以考虑: 1)Follow(A)-考虑结束A的分析工作 2)First(A)- 重新开始A的分析2024/8/3175《编译原理与技术》讲义¡e.g. 13 紧急方式错误恢复 … a = Expr if … ; … ;寻找“;” 因为“;”∈Follow(Stat)被跳过的输入串Missing “;”2024/8/3176《编译原理与技术》讲义¡e.g. 13 紧急方式错误恢复 … a = Expr if … ; … 3)为避免忽略过多的输入符号,可以考虑将较高层次的语法单位的首符号(First)加入低层结构的同步符号集合中如语句Stat的首符号if加入Synch(Stat),这样,当某一语句分析出错时,可以抛弃该语句中的其它输入符号,而开始下一个新语句的分析新的分析起点2024/8/3177《编译原理与技术》讲义错误恢复¡错误恢复的其它策略短语级恢复(phrase level)- 对输入串作局部校正,插入或删除符号出错产生式(error production)- 将出错情况用产生式的形式来描述,(参见YACC)如 Stat error ‘;’ // 描述语句分析时出错时将跳过若干输入符号直至‘;’ 出现全局校正(global correction)2024/8/3178《编译原理与技术》讲义预测分析的错误恢复¡递归下降分析的错误恢复为每个分析过程增加一个参数-同步符号集合一个参数-同步符号集合一般地,当错误发生时,错误恢复例程error()将反复调用词法程序忽略若干输入符号,直至同步集合(可以考虑Follow集合)中的符号出现为止,然后分析过程结束返回。
2024/8/3179《编译原理与技术》讲义e.g. 14 文法G2‘带有错误恢复的分析过程 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idvoid E(SyncSet) // { $ }{ if (lookhead==‘(‘ ) || (lookhead==‘id’)) { T({ + } SyncSet); E’(SyncSet); } else errorE(SyncSet); }2024/8/3180《编译原理与技术》讲义e.g. 14 文法G2‘带有错误恢复的分析过程 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idvoid E’ (SyncSet) { if (lookhead==‘+‘) { match(‘+’); T({ + } SyncSet); E’ (SyncSet); } else if ( (lookhead==‘$’ ) || (lookhead==‘)’ ) { return; } else errorE‘(SyncSet); }2024/8/3181《编译原理与技术》讲义e.g. 14 文法G2‘带有错误恢复的分析过程 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idvoid T(SyncSet) { if (lookhead==‘(‘ ) || (lookhead==‘id’)) { F({ * } SyncSet); T’(SyncSet); } else errorT(SyncSet); }2024/8/3182《编译原理与技术》讲义e.g. 14 文法G2‘带有错误恢复的分析过程 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idvoid T’ (SyncSet) { if (lookhead==‘*‘) { match(‘*’); F({ * } SyncSet); T’ (SyncSet); } else if ( (lookhead==‘+’ ) ||(lookhead==‘$’ ) || (lookhead==‘)’ ){ return; } else errorT’(SyncSet); }2024/8/3183《编译原理与技术》讲义e.g. 14 文法G2‘带有错误恢复的分析过程 E T E’ E’ + T E’ | T F T’ T’ * F T’ | F ( E ) F idvoid F(SyncSet) { if (lookhead==‘(‘ ) { match( ‘(‘ ); E( { ) } SyncSet); match( ‘)’ ); } else if (lookhead==‘id’) { match( ‘id’ ); } else errorF(SyncSet); }2024/8/3184《编译原理与技术》讲义非递归预测分析的错误恢复¡ 出错情况: 1) 栈顶终结符 x 与当前输入符号a不匹配; 紧急方式的错误恢复- pop()() //弹出栈顶符号x,继续分析。
// 将当前输入符号a“看成”同步符号2)M[ A,a ] = error / 空白2024/8/3185《编译原理与技术》讲义非递归预测分析的错误恢复¡ 出错情况:2)M[ A,a ] = error / 空白 构造带错误恢复的预测分析表- ∙ 构造正常的预测分析表 ∙ 若M[ A,a ] = { } 且 a∈Follow(A)则填上synch 否则保持空白若A ∈ P则在错误2)发生时,可以选择该产生式来分析Why?2024/8/3186《编译原理与技术》讲义e.g. 15 有错误恢复的预测分析表 VT{$} VN id+*()$EETE’ETE’ synch synchE’E’+TE’E’E’TTFT’synchTFT’ synch synchT’T’T’*FT’T’T’FF idsynchsynchF (E) synch synch空白项:跳过当前输入符,栈顶不变,继续栈顶符的分析;synch:弹出栈顶符(结束它的分析),当前输入不变,开始下一符号(原次栈顶)的分析2024/8/3187《编译原理与技术》讲义e.g. 16 输入串+id*+$的分析过程分析栈输入串输出$ E+ id * + $跳过+$ Eid * + $$ E’ Tid * + $E T E’$ E’ T’ Fid * + $T F T’$ E’ T’ idid * + $F id$ E’ T’* + $id匹配成功$ E’ T’ F ** + $T’ * F T’2024/8/3188《编译原理与技术》讲义e.g. 16 输入串+id*+$的分析过程分析栈输入串输出$ E’ T’ F ** + $T’ * F T’$ E’ T’ F + $*匹配成功$ E’ T’ + $Synch弹出F$ E’ + $T’ $ E’ T + + $E’ + T E’$ E’ T $+匹配成功$ E’$Synch弹出T$$E’ 2024/8/3189《编译原理与技术》讲义预测分析错误恢复¡考查以下输入串的预测分析过程 ∙ ) a $ ∙ ( a $ ∙ a ) $¡能否改进e.g.15 中的错误恢复过程?2024/8/3190《编译原理与技术》讲义。












