第四章_语法分析_自上而下_3.0.ppt

1、第四章语法分析自顶向下分析、本章内容语法分析的塔斯克和分类自顶向下分析面临的问题递归下降分析程序建构预测性分析程序计程仪程序LL(1)语法，一、语法分析的塔斯克和分类语法分析的任务：对任意给定的w VT*，w L(G )语法分析器：判断为一个程序， 根据p，识别w的办事儿，字句分析器，编译计程仪列的后续部分，符号表，图4.1语法分析器在编译计程仪列中的地位，二，自顶向下分析面临的问题，一，主旨：从语法开始符号，用于自顶向下的输入列的语法树，s，c，a，d，a，b， a，S cAd，ab，a，输入列w :语法G:IP，解析过程：1)w输入列； IP c S扩展，c a d，2)=c A d； 与

2、IP c匹配的3)IPa扩展，第一类ab，IPa和ab匹配的IP d，但是d和b不匹配，4 )报告失败，取消a的子树，返回a的指针返回IP a，对于a没有尝试备选方案，但是可能匹配的语法树的形成， 上述分析方法的实现：在每个非终止符对应递归子例程，仅生成两个字符串的语法中不需要递归，生成无数字符串的语法中免不得递归，递归子例程：如果找到与输入字符串匹配的候选项，则扩展语法树，并返回超过匹配子字符串的true 否则，返回false并保留原始语法树和指针。普计程仪程序实现：使用符号： input_symbol :当前符号内容input_pointer :输入字符指针使用过程： advance ()

3、 :将input_pointer移动到下一个输入符号位置，选择将input_symbol作为当前符号内容，s ()和的两个过程返回true或false，并确定是否在输入字符串中找到由相应的非结尾字符组成的字符串。 procedure S ()； begin if输入_ symbol=cthenbeginadvance ()； IFA () thenifinputsymbol=dthenbeginadvance ()； 返回真结束； 返回假； 结束； 程序a ()； 贝金I保存3360=输入指针； if输入_ symbol=athenbeginadvance ()； ifinputsymbol=

4、bthenbeginadvance ()； 返回真实； 最终/*故障指数* /输入点：=I保存； ifinputsymbol=athenbeginadvance ()； 返回真实； 终止返回失败； 结束； 2、困难和问题，语法的左递归倒置取代符的顺序影响接受的语言。 例如，如果A ab|a变为A a|ab，将发现难以报告错误的正确位置，网罗未发现的发现方法，3，解决自顶向下分析的问题，解决语法的左递归倒退问题，区分1，3种左递归-直接左递归是形式： N-N -间接-潜在左递归是形式： N-N，2，直接左递归的消除，候补式： A-A|，A-A|，消除方法： a|，但是，以a开始的情况下将规则变更

5、为A A A A|，消除直接左递归后： tetete|tft*ft|f(e)|I，例4.2语法： et|t *。 对于(以p开始)，规则A A A A|，3，间接且潜在地左递归消除，并且代入法用n的备选方案替换一个产生式的右部分中的非终止符n。 n有n个候选公式的情况下，右侧重复有n次，而且每次重复有n个不同的候选公式来替代n。 例4.3n-a|bc|s-pnq中的代入结果是S-paq|pBcq|pq，间接和潜在的左递归通常可以通过代入直接变换为左递归，4、删除语法的所有左递归算法，将语法g的所有非终止符重新排序，将各非终止符Pi按上述顺序3366 j i-1； j )将pj代入Pi的生成式(

6、可代入的情况)消除关于Pi的直接左递归，简化上述得到的语法。5、消除后退、后退因子、后退原因，对当前符号=a、a展开，如果A -1|2|m，则知道哪个I是获得以a开头的列的唯一置换式。 即，选择哪个I，即通过看第一个(当前的)符号找到适当的置换式I。如何选择I？ 如果有多个以a开头的I，则以a开头是语法问题，例如，有语句-if条件then语句else语句| while条件do语句|begin语句表end，如果查找语句，则关牛鼻子字if，while，begin是哪个可能成功的置换式抽象地看问题：如果要求不能倒退，语法g (当然g不包含左递归)的必要条件是什么，也就是语法要求什么？ 从i a中选择

7、的话一定会中奖，但从j a中选择的话，会中百发百中。 解决方法是要求语法本身“不会发生这样的事情”，FIRST ()明确了这一点。FIRST () :定义FIRST ()=a|a、aVT若、first ()定理，如果AVN为1个，则FIRST(i )多，如果a的任意2个候补式I和j为FIRST(i ) FIRST(j )=，则按a的每个候补式导出的字符串的最初的VT不同于是，对于输入符号a，由于如果是aFIRST(i )的话则为a notFIRST(j )、(ji )，因此向a的展开没有错误，有可能以方程式I为候补而找到。 消除后退目的：非终止符a的所有候补式的前缀集的两个交叉方法：提取共同的

8、左因子，如果是A 1|2|n|1|2|m (其中，分别不是开头)，则将这些个的规则设为A A|1| 2|m A1|2|n，4， 在可以递归地降低分析计程仪柱结构的左递归和不包括每个非终止符的所有候选表达式的终止前缀定径套不相交的情况下，建构无回溯的自顶向下分析器。 此分析器由递归进程的定径套组成，每个进程都支持语法不终止符。 这种解析计程仪程序被称为递归下降解析器。 1例4.4语法g :程序e； 贝金特； e结束； 程序t； 贝金夫； 终点； 程序e； if sym=贝根进阶； t； e结束； 例如，te、te|、T FT、程序t； if sym=*贝根进阶； f； 终点； 程序f； if s

9、ym=ithenadvanceelseifsym=(深入进阶； e； if sym=) thenadvanceelseerrorendelseerror； 面对输入： i1 i2*i3的情况下的分析步骤为： T *FT| F (E)| i，i1 i2*i3分析过程：e，t，e，f，t，i1，PROCEDURE E； 贝金特； e结束； 程序t； 贝金夫； 终点； 程序f； if sym=ithenadvanceelseifsym=(深入进阶； e； if sym=) thenadvanceelseerrorendelseerror； 程序t； if sym=*贝根进阶； f； 终点； i1 i

10、2 * i3分析过程：e，t，e，f，t，e，t，f，t，i1，i3，PROCEDURE E； if sym=贝根进阶； t； e结束； 程序t； if sym=*贝根进阶； f； 终点； 2、注意：有、自动比对、不失败的成功/失败讯息不会传回错误的位置5、预测性分析程式计程仪、问题：在递归子程序中描绘递归下降分析器，要求在实现此编译系统的语言中行政许可递归。 改进：使用一张分析表和一个栈内存可以实现递归下降分析，用这种方法实现的句法分析计程仪称为预测性分析计程仪程序。 1、预测性分析计程仪柱的工作过程，预测性分析柱计程仪柱有4个部分，分析柱的工作，计程仪柱测量栈内存有x和当前的输入端a，用(

11、x，a )决定计程仪柱的工作，3种可能性：)x=a=#，停止分析，宣告分析成功X=a#、 如果x跳过栈内存且输入指针向下移动3)xvn，则检查分析表m的元素MX，a、其元素或x的生成公式、或错误元素。 如MX、a=XUVW，将栈内存掌门人的x替换为WVU(U为掌门人)后输出的MX，a=error时，调用error程序计程仪程序。条件(3)、XVN、显示查找表m的要素MX、a、显示查找表形式、eete|tft*ft|f(e)|i、例4.5是预测分析器，对输入id id*id进行如下动作1 # Eid * id #2# etid * id # ete3# et FID *。 标签：符号，符号，符号

12、，符号，符号，符号，符号，符号，符号，符号，符号成功地解析了id10 # etidiid # FID 11 # et * id # 12 # ETF * * id # t * ft13 # ETI idid # et # 16 # e # e中的3360 x=#。id、id、t、id、*.f、id、id、id、t、#、e、#、#、#、结论：输出的生成式是最左侧导出的生成式。 将右边放在栈内存上，等待匹配的表表示在(栈内存掌门人，a )的情况下，如何扩展树，错误很快被发现。 实质：栈内存：不完全规范句型表：表示VN如何被扩展，依赖于VT，在上述解析过程中生成的语法树：F (E )，F id，f，

13、t，t，t，T FT，t，t，e，e，e，e，e，e，e，e，e，f 、id*id# :e，t，f，t，id，2，分析表的结构，分析表的形式：思维方法：1)将生成式嵌入到哪里？2 )？ 生成公式分为以下两部分。 一个是建构关于a和g的两个集合。 FIRST ()和FOLLOW(A) 1定义： g、V*、s、AVN和2结构FIRST ()结构FIRST(X )和XV。 如果XVT是XVN，则FIRST(X )是XVN；如果X-a是a FIRST(X) X-，则FIRST(X )是XVN；如果X-Y和YVN是第一个，则FIRST(X )是x -。 如果是Y1Y2Yi-1，那么FIRST(X )就是

14、FIRST(X )；如果是Y1Y2Yi-1，那么FIRST(X1X2Xn )、FIRST(X1)的非关终止符字加上FIRST ()就是FIRST(X1) 再加上FIRST(X2 )，则FIRST(X3 )的所有非终止符都要加上FIRST ()，再加上FIRST(Xi )，再加上i=1.n，则加上FIRST ()，并且3 )结构FOLLOW(A )要经过FIRST(Xi )，直到应用以下规则，没有再加上FOLLOW为止。 属于FOLLOW(B )，但是A-B存在，或者如果是A-B且FIRST ()则属于FOLLOW(B) FOLLOW(A )的4 )例4.6已知语法第一个定径套的结构：第一个=第一个=第一个=*， 如果存在属于FOLLOW(S )的A-B，则除去FIRST() FOLLOW(B )，获得： FOLLOW(E)=#如果获得：