编译原理课件chap04(陈火旺).ppt

1、第四章语法解析自顶向下解析，第四章语法解析自顶向下解析，因为高级语言的语法结构适合用上下无关语法来描述，所以以上下文无关语法为语法解析的基础。 本章和下一章介绍了编译程序结构中典型的解析方法4.1解析器功能解析是编译过程的核心部分。 其作用是，在字句解析中认识单词符号串的基础上，解析普计程仪柱的语法构造是否符合语法规则进行判定。 下图显示了解析器在编译程序中的位置。第四章语法解析自顶向下解析、源计程仪、词法解析、单词符号、删除以下单词、语法解析、词法解析、解析树、编译后续、符号表、解析器位于编译计程仪中的常用方法、自顶向下分析、自下而上分析、确定不确定、运算符优先分析LR分析、 第四章语法分析

2、自顶向下分析、自顶向下语法分析方法、自顶向下分析法从语法的开始符号推导出与输入的单词串完全匹配的句子。 如果可以导出，那么该输入列就是给定的语法句子，如果不能导出，那么该输入列就不是给定的语法句子。 第四章语法分析-自顶向下分析，如已知符号串S=cad语法GZ: ZcAd Aab|a求解SL(GZ )，分析过程建立语法树，使语法树的末端节点与给定符号串一致。 选择匹配塔斯克为a，第四章语法分析-自顶向下分析、6、6、3.a的右符号串匹配输入串a有两个右部分，选择一个，再导出Aab检验，完成a-a匹配，b-d不匹配的Aa检查a-a匹配d-d匹配末端节点根据输入cad与cad的匹配，建立衍生序列E

3、cAdcad cadL(G(E ) )，S=cad GZ: ZcAd Aab|a，分析工作要素进行替换，假定最左边的非终止符是b，并且有n个规则： BA1|A2|An 第四章语法分析-自顶向下分析，1 .分析过程具有预测性，对输入符号串属于哪个语法成分进行预测，并根据该语法成分的语法建立语法树。 2、分析过程是一种试验过程，是用尽一切方法(选择不同的规则)制作语法树的过程，由于是试验过程，失败是免不得，分析过程需要追溯进行，因此我们也称之为追溯该方法的自顶向下分析方法。 第四章语法分析-自顶向下分析、自顶向下分析中存在的问题和解决方法、自顶向下分析方法的基本缺点：不能处理具有左递归性的语法，自

4、顶向下分析为什么不能处理左递归语法，1左递归语法：左递归语法上溯及问题，第四章语法分析-自顶向下分析，10、10、 如果在匹配输入串的过程中，轮到恰好在非终止符u中直接匹配输入串，那么假定在u的右部符号串u中匹配，如果使用u的语法具有间接的左递归，也会发生上述问题，但是环的环形口袋更大因为执行自顶向下解析必须删除语法的左递归，所以在介绍了直接删除左递归的方法的基础上，还介绍了一般的左递归删除方法。为什么自顶向下解析不能处理左递归语法？ 第四章语法分析自顶向下分析、11、11、删除直接左递归：11、11、规则1 (提因子)、I )知道Ux | xy，并且能够对文档的长度进行更有效的分析。 ii

5、) uxy|xz y1y2wy1w 2解： Ux (y1 (y2 | w2 ) | | z )得到的： Ux U U y1 y1 | | z y1 y2 | w2，如果是已知的PP|，则可以改写为： P P P P|。 示例2 ge:e:3360=t * f|t/f|ft 33603360=f|t * f|t/f解：从左递归到右递归的更改： e :3360=t第四章语法分析自顶向下分析，通常，p的所有生成表达式为PP1| p2|p1m|1 假设各自不是以p开始的话，消除p的直接左递归性就是改写这些个规则的第四章语法解析自顶向下解析，14，14，消除一般的左递归，将1.g的非终止符整理为任意顺序

6、A1，A2，An， 将a133603360=1|2设定为2.fori :=1tondobeginforj :=1将toi-1 doaiajr这样的形式的规则替换为Ai (1|2|k) r。 其中Aj 1|2|k是当前所有aj的消除规则ai规则的直接。 第四章语法解析-自顶向下解析、例：语法Gs按S Qc|c Q Rb|b R Sa|a、非终止符顺序进行排序，在RSa|a QRb|b SQc|c、的4.s的右部代入q，进行SSabc|abc|bc|c，5.s的直接左递归s (ABC|BC|) 最后得到语法3360，s(abc|最后得到的语法3360，s (ABC|BC|c ) sabcs|qsa

7、b|ab|brsa|a， 其中关于q和r的规则是由多元规则压缩而成的s(abc|bc|c )，最后得到的语法形式上可能有所不同，但要证明其等价性并不容易。第四章语法分析-自顶向下分析、自顶向下语法分析方法、自顶向下分析分为确定性和不确定性两种自顶向下确定性分析法虽然在语法上有一定的局限性，但简单直观、手工作业和自动结构简单的自顶向下不真实自我分析法是一种具有回溯的分析方法，效率高、成本高、使用少。 第四章语法分析-自顶向下分析，一，确定性的自顶向下分析思想1，方法：从开始符号开始，不断地替换非终止符，可以唯一地选择用现在的单词符号替换的生成式。 例1 :语法G(S):SpA SqB AcAd

8、Aa输入列W=pccadd自顶向下的导出过程为：第四章语法解析-自顶向下解析、a，对应的语法树：spappd第四章语法分析自顶向下分析，例1 :语法G(S ) : SpA SqB AcAd Aa该语法的特征： (1)各生成式的右部是从终止符开始的；(2)如果两个生成式中存在相同的左部，则它们的右部是从不同的终止符开始的。 对于这种语法，分析过程可以是唯一确定的，因为它可以根据当前输入符号确定选择导出哪种生成公式。第四章语法分析-自顶向下分析，例2 :语法G(S )是S Ap S Bq A acA BbdB这一语法特征： (1)生成式的右部并非全部从终止符开始。 (2)如果两个生成式具有相同的左

9、部，则它们的右部从不同的终止符或者非终止符开始。 (3)没有空闲发生式。 ccap是如何根据输入列的第一个符号确定生成公式的呢？ 第四章语法分析-自顶向下分析，例2 :语法G(S )是： S Ap S Bq A acA BbdB输入W=ccap推导：自顶向下推导过程是：第四章语法分析-自顶向下分析，例2 :语法G(S ) 是： S Ap S Bq A acA BbdB输入W=ccap推导：自顶向下推导过程是： S Ap cAp ccAp ccap语法树是：a，第四章语法分析(2)如果两个生成式具有相同的左部，则它们的右部是从不同的终止符或者非终止符开始。 (3)没有空闲发生式。 ccap是如何

10、根据输入列的第一个符号确定生成公式的呢？ 第四章语法解析自顶向下解析，第二章，开始符号集合的定义：如果将G=(VT，VN，p，s )作为上下文相关语法，将开始符号集合作为First()=a | a，aVT，则规定First ()。 上例中的中文法则为SAp|Bq A a | cA B b | dB则： FIRST(Ap)=？ FIRST(Bq)=？ 为生成表达式规则的右部生成开始符号集合，第4章语法解析自顶向下解析，第2章，开始符号集合的定义：如果将G=(VT，VN，p，s )作为上下文相关语法，将开始符号集合作为First()=的话，则规定first ()。 上例的中文法则为SAp|Bq A

11、 a | cA B b | dB则： FIRST(Ap)=a、c。 FIRST(Bq)=b，d，对于生成式规则的右部生成开始符号集合，第四章语法解析自顶向下解析，根据从输入列的第一个符号如何确定生成式、及当前输入象征符属于哪个发生式右部的开始象征符集合，确定选择导出相应的发生式。第四章语法分析-自顶向下分析，例3 :语法GS:SAA|dabas|w=输入Abd，导出过程为：第四章语法分析-自顶向下分析，例3 :语法gs:s，S aA abAS abS abd非终止符a面对输入符号d，d不属于a的任何候选前缀定径套， a的候补前缀定径套包含第4章语法解析-自顶向下解析，如果某个非终止符的生成式中

12、包含空生成式，则根据在第2步骤中导出的生成式是如何决定的，后跟符号集合的决定，3、将后跟符号集合的定义： G=(VT，VN，p，s )定义为上下文相关语法，AVN， 对于将s设为开始符号、Follow(A)=a | S uA且aVT的非终止符，如果是SA，则可将#Follow(A) (#表示输入列的终止符或句括号)写作#，如果是SA，则可将Follow(A)a|SAa、aVT写作#。 例4 :例2中语法GS求出： sap|bqaa|cab|dbfollow集。 解： Follow(S)=？ Follow(A)=？ Follow(B)=？ 第四章语法解析-自顶向下解析，换言之，Follow(A )是所有句型中紧跟在a之后出现的终止符或“#”。 例4 :例2中语法GS求出： sap|bqaa|cab|dbfollow集。、解： follow (s )=# follow (a )=p follow (b )=q，第四章语法解析自顶向下解析、自顶向下语法解析要解决的重要问题由假定要被置换的最左非的规则的选择集合决定。 第四章语法解析自顶向下解析，4，选择集合的定义给定的上下文相关语法的生成式a，如果是AVN，V*则Select(A)=First ()，如果是select ()，第四章语法分析-自顶向下分析，5，LL(1)语法的定义：语法中不包含左递归的