《编译原理 自上而下的语法分析课件.ppt》由会员分享，可在线阅读，更多相关《编译原理 自上而下的语法分析课件.ppt（62页珍藏版）》请在三一办公上搜索。
1、第四章 语法分析自上而下分析,内容,语法分析器的功能自上而下分析面临的问题LL（1）分析法递归下降分析程序构造预测分析程序LL（1）分析中的错误处理,4.1 语法分析器的功能,语法分析器的功能语法分析器的功能语法分析方法自上而下分析面临的问题LL（1）分析法递归下降分析程序构造预测分析程序LL（1）分析中的错误处理,4.1.1 语法分析器的功能,高级语言的语法结构适合用上下文无关文法描述语法分析器任务：分析与判定程序的语法结构是否符合语法规则工作本质：根据产生式识别输入串是否为一个句子在编译器中的地位：核心部分,4.1.2 语法分析方法,自上而下分析法从文法的开始符号出发，反复使用文法的产生式
2、，寻找与输入符号串匹配的推导将文法开始符号做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上分析法从输入符号串开始，逐步进行归约，直至归约到文法的开始符号从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树,例：文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子,自上而下分析,自下而上分析,4.2 自上而下分析面临的问题,语法分析器的功能自上而下分析面临的问题自上而下分析的主旨回溯举例自上而下的带回溯试探法自上而下分析面临的问题左递归与回溯LL（1）分析法递归下降分析程序构造预测分析程序LL（1）分析中的错误处理,4.2.1 自上而下分
3、析的主旨,自上而下从文法的开始符号出发，向下推导，推出句子存在问题：带“回溯”克服方法不带回溯的递归子程序（递归下降）分析方法自上而下分析的主旨为输入串寻找一个最左推导对任何输入串，试图用一切可能的办法，从文法开始符号（根结点）出发，自上而下地为输入串建立一棵语法树,4.2.2 回溯举例,例4.1 假定有文法(1)SxAy(2)A*|*分析输入串x*y(记为)。,证明是一个句子,实现途径让每个非终结符对应一个递归子程序如果发现某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值否则，保持原来的语法树和IP值不变，并返回“假”值,4.2.3 自上而下的带回溯试探法,自上而下分析面临的
4、五个问题消除左递归性克服回溯消除虚假匹配确定出错位置避免穷尽一切,4.2.4 自上而下分析面临的问题,文法的左递归问题一个文法是含有左递归的，若存在非终结符P将使自上而下分析陷入无限循环回溯问题分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。这时，不得不“回溯”,4.2.5 左递归与回溯,4.3 LL(1)分析法,语法分析器的功能自上而下分析面临的问题LL(1)分析法不带回溯的自上而下分析算法左递归的消除回溯的消除LL(1)分析条件递归下降分析程序构造预测分析程序LL(1)分析中的错误处理,4.3.1 不带回溯的自上而下分析算法,自上而下分析方法不允许文法含有任何左递归
5、构造不带回溯的自上而下分析算法消除文法的左递归性找出克服回溯的充分必要条件,4.3.2 左递归的消除（一）,直接消除产生式中的左递归假定关于非终结符P的规则为 PP|其中不以P开头那么，我们可以把P的规则等价地改写为如下的非直接左递归形式：PP PP|,4.3.2 左递归的消除（二）,一般而言，假定关于P的全部产生式是 PP1|P2|Pm|1|2|n 其中，每个都不等于，而每个都不以P开头 那么，消除P的直接左递归性就是改写这些规则：P1P|2P|nP P1P|2P|mP|,4.3.2 左递归的消除（三）,例4.2 文法EET|TTT*F|FF(E)|i经消去直接左递归后变成：ETE E+TE
6、|TFT T*FT|F(E)|i,注意：这个例子后面将再度用到,4.3.2 左递归的消除（四）,例如文法SQc|cQRb|bRSa|a虽没有直接左递归，但S、Q、R都是左递归的，如：SQcRbcSabc一个文法消除左递归的条件不含以为右部的产生式（空产生式）不含回路，形如,4.3.2 左递归的消除（五）,消除左递归的算法把文法G的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行；FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj 的规则改写成 Pi1|2|k;(其中Pj1|2|k是关于Pj 的所有规则)消除关于Pi 规则的直接左递归性
7、 END化简由第二步所得的文法即去除那些从开始符号出发永远无法到达的非终结符的产生规则,4.3.2 左递归的消除（六）,例4.3 考虑文法G(S)SQc|cQRb|bRSa|a令它的非终结符的排序为R、Q、S对于R，不存在直接左递归把R代入到Q的有关候选后，把Q的规则变为 QSab|ab|b 现在的Q不含直接左递归把Q代入到S的有关候选后，S变成 SSabc|abc|bc|c,4.3.2 左递归的消除（七）,SSabc|abc|bc|c存在直接左递归消除S的直接左递归后SabcS|bcS|cSSabcS|QSab|ab|bRSa|a关于Q和R的规则已是多余的，化简为 SabcS|bcS|cS
8、SabcS|由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但它们都是等价的,4.3.2 左递归的消除（八）,例4.3 考虑文法G(S)SQc|cQRb|bRSa|a非终结符排序选为S、Q、R，那么，R Qca|ca|a R Rbca|bca|ca|a最后所得的无左递归文法是：SQc|c QRb|b RbcaR|caR|a R R bca R|不同排序所得的文法的等价性是显然的,4.3.3 回溯的消除（一）,为了消除回溯就必须保证对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的A 1|2|n,
9、令G是一个不含左递归的文法对G的所有非终结符的每个候选定义它的终结首符集FIRST()为,特别是，若，则规定FIRST(),如果非终结符A的所有候选首符集两两不相交即A的任何两个不同候选 i 和 jFIRST(i)FIRST(j)当要求A匹配输入串时A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务这个候选就是那个终结首符集含a的,4.3.3 提公共左因子（二）,提取公共左因子假定关于A的规则是 A 1|2|n|1|2|m(其中，每个 不以开头)那么，可以把这些规则改写成 AA|1|2|m A 1|2|n经过反复提取左因子，就能够把每个非终结符（包括新引进者）的所有候选首符
10、集变成为两两不相交,4.3.3 消除回溯、提左因子（三）,例4.4：考察文法G：S iCtS|iCtSeS|a C b 解：由于S的前两个候选项中含有左因子iCtS，提取左因子之后，等价文法G如下：S iCtSS|a S eS|C b,4.3.4 LL(1)分析条件（一）,特别是，若，则规定 FOLLOW(A),假定S是文法G的开始符号，对于G的任何非终结符A，我们定义,4.3.4 LL(1)分析条件（二）,构造不带回溯的自上而下分析的文法条件文法不含左递归，对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交若A1|2|n，则FIRST(i)FIRST(j)(ij)对文法中的每个非终
11、结符A，若它存在某个候选首符集包含，则 FIRST(i)FOLLOW(A)=i=1,2,.,n若一个文法G满足以上条件，则称G为LL(1)文法,4.3.4 LL(1)分析条件（三）,LL(1)的含义第一个L从左至右扫描输入串第二个L最左推导1分析时每一步只需向前查看一个符号对于一个LL(1)文法可以对其输入串进行有效的无回溯的自上而下分析,4.3.4 LL(1)分析条件（四）,LL(1)分析过程假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为A 1|2|n若aFIRST(i)，则指派 i 执行匹配任务若a不属于任何一个候选首符集，则若属于某个FIRST(i)且aFOLLOW(A
12、)，则让A与自动匹配否则，a的出现是一种语法错误,4.4 递归下降分析程序构造,语法分析器的功能自上而下分析面临的问题LL(1)分析法递归下降分析程序构造递归下降分析器扩充的巴科斯范式语法图预测分析程序LL(1)分析中的错误处理,4.4.1 递归下降分析器,递归下降分析器当文法满足LL(1)条件时，构造不带回溯的自上而下分析程序该分析程序由一组递归过程组成，每个过程对应文法的一个非终结符,4.4.2 扩充的巴科斯范式,巴科斯范式元语言符号“”和“|”扩充的巴科斯范式（扩充几个元语言符号）用花括号表示闭包运算*用表示0n可任意重复0次至n次 用方括号表示01 的出现可有可无等价于|,4.4.3
13、扩充的巴科斯范式举例,例如，通常的“实数”可定义为：decimalsigninteger.digitexponent exponentEsigninteger integerdigitdigit sign+|-用扩充的巴科斯范式来描述语法直观易懂便于表示左递归消去和因子提取,4.4.4 语法图,例4.5 文法ET|E+TTF|T*FFi|(E)可表示成ET+TTF*FFi|(E),4.5 预测分析程序,语法分析器的功能自上而下分析面临的问题LL(1)分析法递归下降分析程序构造预测分析程序预测分析程序的工作过程预测分析表及其构造方法LL(1)分析中的错误处理,4.5.1 预测分析程序,实现LL(
14、1)分析的有效方法递归下降分析器要求编译器支持递归预测分析程序非递归的数学模型是下推自动机使用分析表和栈联合控制,4.5.1 预测分析程序工作过程,预测分析程序或LL(1)分析法工作原理：总控程序分析表 MA，a矩阵，A VN，a VT 是终结符或分析栈 STACK 用于存放文法符号,4.5.2 预测分析器模型,分析表：MA，a矩阵A VN，a VT，是输入串结束符，不是终结符分析栈：用于存放文法符号,4.5.3 预测分析表,例：对于文法G(E)ETEE+TE|TFT T*FT|F(E)|i对应的LL(1)分析表（预测分析表）如下,输入串为i*i+i，利用分析表进行预测分析,分析过程如下：,4
15、.5.4 总控程序,总控程序根据STACK栈顶符号X和当前输入符号a，执行下列三种动作之一若Xa，则宣布分析成功，停止分析若Xa，则把X从STACK栈顶逐出，让a指向下一个输入符号若X是一个非终结符，则查看分析表M 若MX，a中存放着关于X的一个产生式，把X逐出STACK栈顶，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为，则意味不推什么东西进栈)。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作（目前暂且不管）若MX，a中存放着“出错标志”，则调用出错诊察程序ERROR,4.5.5 预测分析算法,预测分析算法：BEGIN 首先把#入栈；然后把文法开始符号推入栈；把第
16、一个输入符号读进a；FLAG：=TRUE；WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在中；IF X Vt THEN IF X=a THEN 把下一个输入符号读进a ELSE ERROR ELSE IF X=#THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF X,a=X X1X2.XK THEN 把XK，XK-1,.,X1一一推进栈 ELSEERROR END OF WHILE;STOP/*分析成功，过程完毕*END,4.5.6 构造预测分析表,构造FIRST集计算单个文法符号的FIRST集计算一组文法符号串的FIRST集 构造F
17、OLLOW集构造预测分析表MA,a,4.5.6.1 单个文法符号的FIRST集,对于单个文法符合X，应用下列规则，直到没有终结符或可加到FIRST(X)集为止如果X是终结符，则FIRST(X)是 X如果X是非终结符，且X是一个产生式，则将加到FIRST(X)中如果X是非终结符，且XY1Y2Yk（k1）是一个产生式，则若FIRST(Yj)（j=1,2,k），则将加入FIRST(X)当某终结符aFIRST(Yi)(1ik)且 Y1Y2Yi-1 时，就把a 加入到FIRST(X)中去即：FIRST(Y1)，FIRST(Y2)，FIRST(Yi-1),4.5.6.2 文法符号串的FIRST集,假设一组
18、文法符号串由X1X2Xn构成将集合FIRST(X1)中的除的终结符号加入FIRST(X1X2Xn)如果FIRST(X1)，那么将集合FIRST(X2)中除的终结符号也加入FIRST(X1X2Xn)依次类推如果X1,X2,Xn中每一个文法符号的FIRST集中都有,那么把也加入到FIRST(X1X2Xn)中,4.5.6.3 构造FOLLOW集,计算文法中每个非终结符A的FOLLOW(A)，应用如下的三条规则，直到没有任何一个终结符能被添加到任何非终结符的FOLLOW集当中为止如果S是文法的开始符号，那么把#添加进FOLLOW(S)（#是输入串的结束符）如果有一个产生式A B，那么将集合FIRST(
19、)中除外的所有元素加入到FOLLOW(B)中如果有一个产生式 A B，或有一个产生式 A B且FIRST(),那么将集合FOLLOW(A)中的所有元素加入到集合FOLLOW(B)中,4.5.6.4 预测分析表构造算法,在对文法G的每个非终结符A及其任意候选都构造出FIRST()和FOLLOW(A)之后，用它们来构造G的分析表MA,a对文法G的每个产生式A执行第2步和第3步对每个终结符a FIRST()，把A加至MA,a中若FIRST()，则对任何bFOLLOW(A)把A加至MA,b中把所有无定义的MA,a标上“出错标志”,4.5.6.5 构造分析表举例,例:对于文法G(E)ETE E+TE|T
20、FT T*FT|F(E)|i构造每个非终结符的FIRST和FOLLOW集：FIRST(E)=(,i FOLLOW(E)=),#FIRST(E)=+,FOLLOW(E)=),#FIRST(T)=(,i FOLLOW(T)=+,),#FIRST(T)=*,FOLLOW(T)=+,),#FIRST(F)=(,i FOLLOW(F)=*,+,),#,ETEFIRST(E)=+,E FOLLOW(E)FOLLOW(T),TFT;T*FT|;FOLLOW(T)FOLLOW(F),例:对于文法G(E)ETE E+TE|TFT T*FT|F(E)|i 构造每个非终结符的FIRST和FOLLOW集合：FIRST
21、(E)=(,i FOLLOW(E)=),#FIRST(E)=+,FOLLOW(E)=),#FIRST(T)=(,i FOLLOW(T)=+,),#FIRST(T)=*,FOLLOW(T)=+,),#FIRST(F)=(,i FOLLOW(F)=*,+,),#,4.5.6.6 LL(1)文法,如果文法G是左递归或二义的，那么分析表M至少含有一个多重定义入口因此，消除左递归和提取左因子将有助于获得无多重定义的分析表M一个文法,若它的分析表M不含多重定义入口,则称它是一个LL(1)文法一个文法G的预测分析表M不含多重定义入口，当且仅当该文法为LL(1)的,4.5.6.7 LL(1)文法的条件,4.6
22、 LL(1)分析中的错误处理,发现错误栈顶的终结符与当前输入符不匹配非终结符A于栈顶，面临的输入符为a，但分析表M的MA,a为空“应急”恢复策略跳过输入串中的一些符号直至遇到“同步符号”为止同步符号的选择“synch”表示由相应非终结符的后继符号集得到的同步符号,4.6.1 加入同步符号的LL(1)分析表,把FOLLOW(A)中的所有符号作为A的同步符号,FIRST(E)=(,i FOLLOW(E)=),#FIRST(E)=+,FOLLOW(E)=),#FIRST(T)=(,i FOLLOW(T)=+,),#FIRST(T)=*,FOLLOW(T)=+,),#FIRST(F)=(,i FOLL
23、OW(F)=*,+,),#,4.6.2 同步符号的选择,把FOLLOW(A)中的所有符号作为A的同步符号跳过输入串中的一些符号直至遇到这些“同步符号”，把A从栈中弹出，可使分析继续把FIRST(A)中的符号加到A的同步符号集当FIRST(A)中的符号在输入中出现时，可根据A恢复语法分析若不能匹配栈顶的终结符号，一种简单的想法是弹出栈顶的这个终结符号，并发出一条信息，说明已经插入这个终结符，继续进行语法分析,练习一,文法GV：VN|NEEV|V+ENi 是否为LL(1)文法？若不是，如何改造成LL(1)文法？解：LL(1)文法的基本条件是不含左递归和回溯（公共左因子），而GV中含有回溯，所以先消
24、除回溯得到文法GV：GV：VNV V|EV EVE E|+EE Ni由LL(1)文法的充要条件可证GV是LL(1)文法,文法Gs:SBA ABS|d BaA|bS|c证明文法G是LL(1)文法构造LL(1)分析表写出句子adccd的分析过程解：一个LL(1)文法的充要条件是对每一个非终结符A的任何两个不同产生式A|，有下面的条件成立FIRST()FIRST()=若*,则有FIRST()FOLLOW(A)=,练习二（一）,练习二（二）,对于文法Gs:SBA ABS|d BaA|bS|cFIRST集FIRST(B)=a,b,c;FIRST(A)=a,b,c,d;FIRST(S)=a,b,c。FOL
25、LOW集 FOLLOW(S)=#对SBA有 FIRST(A)加入FOLLOW(B)，即FOLLOW(B)=a,b,c,d 对ABS有FIRST(S)加入FOLLOW(B)，即FOLLOW(B)=a,b,c,d 对BaA有FOLLOW(B)加入FOLLOW(A)，即FOLLOW(A)=a,b,c,d 对BbS有FOLLOW(B)加入FOLLOW(S)，即FOLLOW(S)=#,a,b,c,d,练习二（三）,由ABS|d得FIRST(BS)FIRST(d)=a,b,c d=由BaA|bS|c得FIRST(aA)FIRST(bS)FIRST(c)=abc=由于文法Gs不存在形如 的产生式，故无需求解形如FIRST()FOLLOW(A)的值也即，文法GS是一个LL(1)文法,练习二（四）,由Gs：SBA ABS|d BaA|bS|c的FIRST(B)=a,b,c;FOLLOW(B)=a,b,c,d;FIRST(A)=a,b,c,d;FOLLOW(A)=a,b,c,d;FIRST(S)=a,b,c。FOLLOW(S)=#,a,b,c,d 可构造LL(1)预测分析表如下：,(3)在分析表的控制下，句子adccd的分析过程如下：,
