编译原理与技术 自顶向下分析.ppt

2019/10/27,编译原理与技术讲义,1,编译原理与技术, 自顶向下分析,2019/10/27,编译原理与技术讲义,2,自顶向下分析,分析树的建立 从根（开始符号）出发，从上而下，从左自右为输入串建立分析树 为输入串寻找一个最左推导,e.g.1 文法G0如下 S A B C A a B b C c 输入串 abc$ $串结束符,2019/10/27,编译原理与技术讲义,3,自顶向下分析,e.g.1 文法G0： S A B C A a B b C c,a b c $,S $,当前记号（指针）,2019/10/27,编译原理与技术讲义,4,自顶向下分析,e.g.1 文法G0： S A B C A a B b C c,a b c $,S $,A B C,$,2019/10/27,编译原理与技术讲义,5,自顶向下分析,e.g.1 文法G0： S A B C A a B b C c,a b c $,S $,A B C,$,a,2019/10/27,编译原理与技术讲义,6,自顶向下分析,e.g.1 文法G0： S A B C A a B b C c,a b c $,S $,A B C,$,a,终结符叶子与当前符号匹配？,2019/10/27,编译原理与技术讲义,7,自顶向下分析,e.g.1 文法G0： S A B C A a B b C c,a b c $,S $,A B C,$,a,b,指向下一记号,2019/10/27,编译原理与技术讲义,8,自顶向下分析,e.g.1 文法G0： S A B C A a B b C c,a b c $,S $,A B C,$,a,b,2019/10/27,编译原理与技术讲义,9,自顶向下分析,e.g.1 文法G0： S A B C A a B b C c,a b c $,S $,A B C,$,a,b,c,2019/10/27,编译原理与技术讲义,10,自顶向下分析,e.g.1 文法G0： S A B C A a B b C c,a b c $,S $,A B C,$,a,b,c,2019/10/27,编译原理与技术讲义,11,自顶向下分析,e.g.1 文法G0： S A B C A a B b C c,a b c $,S $,A B C,$,a,b,c,OK！输入串分析成功！,2019/10/27,编译原理与技术讲义,12,自顶向下分析,e.g.1 文法G0： S A B C A a B b C c,串abc$的最左推导过程: S$ ABC$ aBC$ abC$ abc$,2019/10/27,编译原理与技术讲义,13,自顶向下分析,文法G0较简单非终结符只有唯一的产生式 试探分析法 当待分析（展开）的非终结符对应多条产生式，可以选择其一进行尝试分析（最左推导）； 当此产生式无法与输入串“匹配”时则需要“回溯”即放弃已建立的部分分析树，同时调整输入串指针恢复到此次分析前位置，再另选一产生式重新分析。 只有当所有的所有的尝试均不成功，分析失败！,2019/10/27,编译原理与技术讲义,14,自顶向下分析,试探分析法 e.g.2 文法G1如下 S x A y A ab A a 输入串 xay$ 的分析过程。,2019/10/27,编译原理与技术讲义,15,自顶向下分析,试探分析法 e.g.2 文法G1： （1）S x A y （2）A ab （3）A a 输入串 xay$的 分析过程。,S$,x A y $,终结符叶子x与输入符x匹配,a b,选用产生式（1）,选用产生式（2）,匹配失败！,2019/10/27,编译原理与技术讲义,16,自顶向下分析,试探分析法 e.g.2 文法G1： （1）S x A y （2）A ab （3）A a 输入串 xay$的 分析过程。,S$,x A y $,a b,选用产生式（1）,选用产生式（2）,匹配失败！,回溯：重新分析A,2019/10/27,编译原理与技术讲义,17,自顶向下分析,试探分析法 e.g.2 文法G1： （1）S x A y （2）A ab （3）A a 输入串 xay$ 的分析过程。,S$,x A y $,选用产生式（1）,a,选用产生式（3）,终结符叶子a与输入符a匹配,分析 成功！,2019/10/27,编译原理与技术讲义,18,试探分析法 在文法有左递归特征时，可能导致无限循环而此时无法读入任何输入符（输入指针保持不变）。 如表达式文法G2： EE+T | T TT*F | F F(E) | id,自顶向下分析,E,E + T,E + T, ,2019/10/27,编译原理与技术讲义,19,自顶向下分析,预测分析法 对于待分析的非终结符A，可以根据当前输入符号（记号）来准确唯一地选择A的某一产生式。若该产生式“匹配”成功，则意味着A分析成功；若匹配失败，则即使选择A的其它产生式也会导致A分析失败（因而不需要回溯）。 Case 1:文法G1 A a b A的两个产生式右部具有 A a 相同的（非空）前缀a 那么A面临输入符a选择谁呢？,2019/10/27,编译原理与技术讲义,20,预测分析法 提左因子的文法变换 文法G1中， A a b A a A A a A b | ,自顶向下分析,A 1 A 2 1和2不含相同前缀,提左因子,A A A 1 | 2 引入非终结符A,提左因子,2019/10/27,编译原理与技术讲义,21,预测分析法 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/10/27,编译原理与技术讲义,22,预测分析法 提左因子变换的一般形式,自顶向下分析,A 1 | 2 | n A ,i不含相同前缀, 不含前缀,提左因子变换后：,A A | A 1 | 2 | n,2019/10/27,编译原理与技术讲义,23,预测分析法 Case 2: 文法G2 E E + T E的产生式的（直接）左递归妨碍了 E T 输入符号的有效读入（实际上不读） 并导致死循环。 消除左递归（A A）的文法变换 直接左递归的消除（A A）,自顶向下分析,A A A ,消除直接左递归,A A A A | ,引入非终结符A ，形成右递归文法,2019/10/27,编译原理与技术讲义,24,预测分析法 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/10/27,编译原理与技术讲义,25,E,E,T,T,F,i,i,+,*,F,T,i,F,文法G2：i+i*i的分析树,E,T,E,F,T,i,T,+,E,F,T,i,F,T,i,*,文法G2：i+i*i的分析树,2019/10/27,编译原理与技术讲义,26,自顶向下分析,预测分析法 消除左递归（A A）的文法变换 间接左递归的消除（A B A） 对于含间接左递归的文法G，可以先设法变换为含有直接左递归的文法G（通常将较简单的产生式逐次代入较复杂的产生式），然后再行消除G中的直接左递归即可。,2019/10/27,编译原理与技术讲义,27,自顶向下分析,预测分析法 e.g.5消除文法G3中的（间接）左递归。 S Aa | a | b A Ac | c | Sd 将S相应产生式分别代入A相关产生式，得到文法G3： S Aa | a | b A Ac | c | Aad | ad | bd 消除G3中（A的）直接左递归，则有,2019/10/27,编译原理与技术讲义,28,自顶向下分析,预测分析法 e.g.5消除文法G3中的（间接）左递归。 S Aa | a | b A c A | ad A | bd A A c A | ad A | 上述文法不再含有左递归。,2019/10/27,编译原理与技术讲义,29,自顶向下分析,回顾一下什么是预测分析法？ 对于待分析的非终结符A，可以根据当前输入符号（记号）来准确唯一地选择A的某一产生式。若该产生式“匹配”成功，则意味着A分析成功；若匹配失败，则即使选择A的其它产生式也会导致A分析失败（因而不需要回溯）。 在对文法提左因子和消除左递归后，可以实施预测分析了！ 但是，待分析或展开的非终结符A如何利用当前输入符（记号）来选择产生式呢？,2019/10/27,编译原理与技术讲义,30,First集合（首符号集合） First() = a | *a | * , 其中 aVT, , (VTVN) First(a) = a | aVT AV N，考查A的每个产生式：A X1X2Xn， 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),2019/10/27,编译原理与技术讲义,31,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/10/27,编译原理与技术讲义,32,e.g.6文法G2的First集合,E T E E + T E | T F T T * F T | F ( E ) F id,First( T ) = *, ,2019/10/27,编译原理与技术讲义,33,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/10/27,编译原理与技术讲义,34,e.g.6文法G2的First集合,E T E E + T E | T F T T * F T | F ( E ) F id,First( E) = +, ,2019/10/27,编译原理与技术讲义,35,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/10/27,编译原理与技术讲义,36,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 ,First( E) = +, ,First( T ) = First( F ) = (, id ,First( T ) = *, ,First( F ) = (, id ,2019/10/27,编译原理与技术讲义,37,Follow集合（后继符号集合） Follow(A)= a | S * Aa ，其中 aVT, A VN , (VTVN)* $ Follow(S). 若 A BP，则把First()-加入Follow(B) 若 A BP 或 A BP 且 * (即 First() ），则 把Follow(A)加入Follow(B) S * Aa S * Aa Ba Ba * B a Ba 显然a Follow(A) Follow(B),2019/10/27,编译原理与技术讲义,38,e.g.7文法G2的Follow集合,E T E E + T E | T F T T * F T | F ( E ) F id,Follow( E ) = $, ) ,$ Follow(E).,2019/10/27,编译原理与技术讲义,39,e.g.7文法G2的Follow集合,E T E E + T E | T F T T * F T | F ( E ) F id,Follow( E ) = Follow(E) = $, ) ,2019/10/27,编译原理与技术讲义,40,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/10/27,编译原理与技术讲义,41,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/10/27,编译原理与技术讲义,42,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) = * + , $ , ) = * , + , $ , ) ,2019/10/27,编译原理与技术讲义,43,e.g.7文法G2的Follow集合,E T E E + T E | T F T T * F T | F ( E ) F id,Follow( F ) = * , + , $ , ) ,Follow( T ) = +, $ , ) ,Follow( T ) = + , $ , ) ,Follow( E ) = $ , ) ,Follow( E ) = $ , ) ,2019/10/27,编译原理与技术讲义,44,自顶向下分析A时，如果A只产生非空符号串，那么A期望“看到”的当前输入的符号最好是aFirst(A)，这样的话，选用产生式A来分析，即能产生（推导）出以a开头的串并期待与相应输入串匹配。,2019/10/27,编译原理与技术讲义,45,自顶向下分析A时，如果A只产生的是不包含任何有效符号的串 ，则它 “看到”的当前输入的符号只能是bFollow(A)。这时选用产生式A 来“结束”对A的分析而开始的分析。,2019/10/27,编译原理与技术讲义,46,自顶向下分析A时，如果A既产生非空串也可以产生 ，则它 可能“看到”的当前输入的符号来自aFirst(A)，或者来自bFollow(A)。 但A最不期望的是 ab，因为这样，A面临两难的选择 A 还是 A ?,2019/10/27,编译原理与技术讲义,47,LL（1）文法,一般的，文法G是LL(1)文法，如果任何AVN，其产生式，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 right,Leftmost derivation,1 lookhead,2019/10/27,编译原理与技术讲义,48,LL（1）文法,产生式不含左递归 具有相同左部的产生式不含左因子 LL(1)文法G进行自顶向下分析时，非终结符A面临当前输入符号a时即可作出唯一的产生式的选择决定,2019/10/27,编译原理与技术讲义,49,自顶向下分析,LL(1)文法的递归下降分析 为LL（1）文法G（无左因子、左递归）构造一个无回溯的预测分析器。 文法G的每一个非终结符A对应一个（递归）分析过程A()。 分析过程A() 1) 由当前输入符号(lookhead)决定产生式的选取； 2) 产生式A X1X2Xn的分析过程：从左往右逐个分析。 XiVT，则调用匹配过程 match(Xi) XiVN，则调用分析过程 Xi() 3) 空产生式A ， 直接返回,2019/10/27,编译原理与技术讲义,50,递归分析过程A() void A() if ( lookhead First(X1X2Xn) ) /* 产生式AX1X2Xn的分析过程 */ else if /*A的其它非空产生式的分析*/ else if ( ( lookhead Follow(A) ) and A P) return; /* 空产生式，直接返回 */ else error() /* 语法错误*/ ,2019/10/27,编译原理与技术讲义,51,递归下降分析,匹配过程 match( token t ) void match( token t ) if ( lookhead = t ) /终结符叶子和输入符是否匹配（相同） lookhead = next_token(); /若匹配则获取下一记号，即向前移动输入指针 else error() /* 否则语法错误需要符号 t */ ,2019/10/27,编译原理与技术讲义,52,递归下降分析,e.g.8 编写文法G2的递归分析过程。,E T E E + T E | T F T T * F T | F ( E ) F id,void E() if (lookhead=( ) | (lookhead=id) T(); E(); else error(); ,2019/10/27,编译原理与技术讲义,53,e.g.8 编写文法G2的递归分析过程。,E T E E + T E | T F T T * F T | F ( E ) F id,void E () if (lookhead=+) match(+); T(); E (); else / return; /将看成与任一符号匹配 / 从而将以下程序省略！ if ( (lookhead=$ ) | (lookhead=) ) return; else error(); ,2019/10/27,编译原理与技术讲义,54,e.g.8 编写文法G2的递归分析过程。,E T E E + T E | T F T T * F T | F ( E ) F id,void T() if (lookhead=( ) | (lookhead=id) F(); T(); else error(); ,2019/10/27,编译原理与技术讲义,55,e.g.8 编写文法G2的递归分析过程。,E T E E + T E | T F T T * F T | F ( E ) F id,void T () if (lookhead=*) match(*); F(); T (); else / return; /将看成与任一符号匹配 / 从而将以下程序省略！ if ( (lookhead=+ ) | (lookhead=$ ) | (lookhead=) ) return; else error(); ,2019/10/27,编译原理与技术讲义,56,e.g.8 编写文法G2的递归分析过程。,E T E E + T E | T F T T * F T | F ( E ) F id,void F() if (lookhead=( ) match( ( ); E(); match( ) ); else if (lookhead=id) match( id ); else error(); ,2019/10/27,编译原理与技术讲义,57,自顶向下分析,LL(1)文法的非递归的预测分析方法 表驱动的预测分析通过查表决定产生式的选取,输入串,控制程序 （预测分析器）,预测分析表,分析栈,输出,Top,Bottom,2019/10/27,编译原理与技术讲义,58,非递归的预测分析方法,分析栈(stack) 栈的内容VTVN $， 开始分析时，”$”位于栈底，S位于栈顶。 分析表 M : VN × (VT$) (P error) 对于AVN，aVT，有 AP M A, a = error() / 错误恢复例程 控制程序,2019/10/27,编译原理与技术讲义,59,非递归的预测分析方法,控制程序 由当前栈顶符号X和当前输入符号a决定采取的分析动作。,XVT, X=a=$ ，则分析成功，STOP!, X=a $ ，则 1) popup() / 从栈顶弹出X 2) 移动输入指针至下一符号, X a，error() / 匹配失败! / 调用错误恢复程序,2019/10/27,编译原理与技术讲义,60,非递归的预测分析方法,控制程序,XVN, M X, a = X U V W ，则 popup(); /弹出X push( W ); push( V ); push( U ); / 产生式右部符号以逆序入栈, M X, a = error()，则调用错误恢复程序,2019/10/27,编译原理与技术讲义,61,e.g.9 表达式文法G2的预测分析表,2019/10/27,编译原理与技术讲义,62,e.g.10 表达式id+id*id的非递归预测分析过程,2019/10/27,编译原理与技术讲义,63,e.g.10 表达式id+id*id的非递归预测分析过程（续）,2019/10/27,编译原理与技术讲义,64,e.g.10 表达式id+id*id的非递归预测分析过程（续）,分析成功！,2019/10/27,编译原理与技术讲义,65,预测分析表的构造,考查任意产生式A： M A, a = A ,如果 a First()- M A, b = A ,如果 First()且bFollow(A) 所有无定义的表项填上error() 预测分析表如果不含多重定义表项则相应文法是LL(1)的。,2019/10/27,编译原理与技术讲义,66,文法G4：(if then else) 1) S i E t S S 2) S a 3) S e S 4) S 5) E b,e.g.11构造文法G4的预测分析表,First(S) = i, a ,First(S) = e, ,First(E) = b ,Follow(S) = $, e ,Follow(S) = $, e ,Follow(E) = t ,2019/10/27,编译原理与技术讲义,67,e.g.11构造文法G4的预测分析表,1) S i E t S S , iFirst(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/10/27,编译原理与技术讲义,68,e.g.11构造文法G4的预测分析表,有多重定义,2019/10/27,编译原理与技术讲义,69,二义性文法决不是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/10/27,编译原理与技术讲义,70,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/10/27,编译原理与技术讲义,71,A,a A a,a A a,文法G5关于串aaaa的最左推导与分析树,A 1) a A a 2) a a A a a 3) a a a a 4) a a a a,显然，在只有在偶数长(2)的a串的前一半a被产生（推导）出来后，产生式A方被选择来作分析（推导）。而此前只用AaAa。,2019/10/27,编译原理与技术讲义,72,A,a a a a $,输入串,自顶向下分析输入a串，即寻找一个产生a串的最左推导过程。但遗憾是，输入串是从左往右一个一个符号地被读入，每当读入一个符号a时，由于不知道输入串中总共有多少符号a，也就无法判定此时是否已经“读完了”a串的前一半a。这就造成了A面临输入a时的存在矛盾（或多重）的产生式选择。,2019/10/27,编译原理与技术讲义,73,错误恢复,程序的错误类型 编译时错误(compile error) 词法错误如出现非法字符 语法错误如括号不配对、语句结束无分号 （静态）语义错误如形/实参数类型不匹配 运行时错误(run-time error) 动态（运行时）语义错误无限递归（循环）、地址（指针）越界、栈上溢（overflow）和下溢（underflow）、异常（exception）,2019/10/27,编译原理与技术讲义,74,错误恢复,错误恢复的目标 错误（性质）报告准确，错误位置精准 能快速地从当前错误中恢复，以期发现后面的错误；任何（编译）错误不能导致编译器崩溃 对常见的错误应该有很好的恢复措施 尽量减少“株连”错误的产生,2019/10/27,编译原理与技术讲义,75,错误恢复,错误恢复的策略 紧急方式（panic mode） 发现错误时，分析器将抛弃若干输入符号，直到遇上希望的输入同步符号为止。该方法较容易实现且不会陷入死循环，但对忽略的输入无法进行分析。 同步符号（集合）的选取若待分析语法成份为A，则同步符号（集合）Synch（A）的可以考虑： 1）Follow（A）考虑结束A的分析工作 2）First（A） 重新开始A的分析,2019/10/27,编译原理与技术讲义,76,e.g. 13 紧急方式错误恢复 a = Expr if ; ,;,寻找“;” 因为“;”Follow（Stat）,被跳过的输入串,Missing “;”,2019/10/27,编译原理与技术讲义,77,e.g. 13 紧急方式错误恢复 a = Expr if ; ,3）为避免忽略过多的输入符号，可以考虑将较高层次的语法单位的首符号（First）加入低层结构的同步符号集合中。如语句Stat的首符号if加入Synch（Stat），这样，当某一语句分析出错时，可以抛弃该语句中的其它输入符号，而开始下一个新语句的分析。,新的分析起点,2019/10/27,编译原理与技术讲义,78,错误恢复,错误恢复的其它策略 短语级恢复（phrase level） 对输入串作局部校正，插入或删除符号 出错产生式（error production） 将出错情况用产生式的形式来描述，（参见YACC）如 Stat error ; / 描述语句分析时出错时将跳过若干输入符号直至; 出现 全局校正（global correction）,2019/10/27,编译原理与技术讲义,79,预测分析的错误恢复,递归下降分析的错误恢复 为每个分析过程增加一个参数同步符号集合 一般地，当错误发生时，错误恢复例程error（）将反复调用词法程序忽略若干输入符号，直至同步集合（可以考虑Follow集合）中的符号出现为止，然后分析过程结束返回。,2019/10/27,编译原理与技术讲义,80,e.g. 14 文法G2带有错误恢复的分析过程,E T E E + T E | T F T T * F T | F ( E ) F id,void E(SyncSet) / $ if (lookhead=( ) | (lookhead=id) T( + SyncSet); E(SyncSet); else errorE(SyncSet); ,2019/10/27,编译原理与技术讲义,81,e.g. 14 文法G2带有错误恢复的分析过程,E T E E + T E | T F T T * F T | F ( E ) F id,void E (SyncSet) if (lookhead=+) match(+); T( + SyncSet); E (SyncSet); else if ( (lookhead=$ ) | (lookhead=) ) return; else errorE(SyncSet); ,2019/10/27,编译原理与技术讲义,82,e.g. 14 文法G2带有错误恢复的分析过程,E T E E + T E | T F T T * F T | F ( E ) F id,void T(SyncSet) if (lookhead=( ) | (lookhead=id) F( * SyncSet); T(SyncSet); else errorT(SyncSet); ,2019/10/27,编译原理与技术讲义,83,e.g. 14 文法G2带有错误恢复的分析过程,E T E E + T E | T F T T * F T | F ( E ) F id,void T (SyncSet) if (lookhead=*) match(*); F( * SyncSet); T (SyncSet); else if ( (lookhead=+ ) | (lookhead=$ ) | (lookhead=) ) return; else errorT(SyncSet); ,2019/10/27,编译原理与技术讲义,84,e.g. 14 文法G2带有错误恢复的分析过程,E T E E + T E | T F T T * F T | F ( E ) F id