编译原理课件Chapt4-2.ppt

1、第四章，自上而下的语法分析，编译原理，是本章的主要内容。本章主要介绍语法分析任务的自顶向下分析。4.3.2消除回溯和左提升因素。为了消除回溯，必须确保当需要任何非语法终止符来匹配输入字符串时，它能够根据它所面对的输入符号准确地分配它的候选项之一来执行任务，并且该候选项的工作结果应该是确定的。A 1 | 2 | | n，当同一个非终结符有多个候选表达式时，回溯的原因是示例=acb GS: SaAb Acd|c，(1)候选表达式的末端首字母是相同的，因此G是一个没有左递归的语法，其末端前缀集FIRST()定义为：对于G的所有非终结符的每个候选，特别是如果非终结符A的所有候选前缀集都是不相交的，即，

2、 当要求A匹配输入字符串时，A可以根据它所面对的第一个输入符号A准确地分配一个候选人来执行任务。 这个候选人的最后一个首字母是. 1。first集合，FIRST():所有的开始和结束符号，或者，可以从可能性中推导出，对于语法g的所有非结束符号的每个候选公式，其结束的FIRST符号集合被称为first集合，其定义如下：示例 SaAb Acd|c，示例 SAa Aa|,(1)如果=a和aVT，则为FIRST()。例如：FIRSt(I)=IFFIRSt(te)=et e te | tft t * ft | f(e)| I，构造第一个集合的算法，(2)如果=X，XVN，并且有一个生产公式Xb，将b添加

3、到FIRSt()；示例：FIRST(FT)=(，I，将FIRST(X1)中的所有非终止符添加到FIRST()；如果是第一个(X1)，将第一个(X2)中的所有非终止符添加到第一个()；如果是第一个(X1)和第一个(X2)，将第一个(X3)中的所有非终止符添加到第一个()；以此类推，如果在所有1中，第一个(Xi)，第一个()将被添加。(3)如果=X1X2 Xn，其中XiVN，1in；ETE E TE| TFT T*FT| F(E)|i，示例：第一个(ft)=，第一个(f)=(，I，第一个(f)=(，I第一个(t)=*，第一个(f)=(，I第一个(e) I第一个(te)=第一个(t)=(，I第一个(

4、te)=第一个(ft)=第一个(f)=(，I第一个(ft)=*第一个(e)=(第一个(I)=I，示例4.9等，提取公共左侧假设关于A的规则是A 1 | 2 | n | 1 | 2 | m(其中每个规则不开始)，这些规则可以被重写为AA | 1 | 2 | | MA 1 | 2 | | n。在重复提取左因子之后，每个非终止符(包括新的引入符)的所有候选前缀集可以被改变为当一个语法不包含左递归，并且每个非终止符的所有候选前缀集都是不相交的，从上到下进行有效的分析是可能的吗？例如：I、i i、IP、E、E、G(E): E | TFT T * FT | F(E)| I、ii、IP、E、T、E、E、G(

5、E): E | TFT T * FT | F(E)| I、I、IP、E、T、E、E、T、E、F、T、G(E): E | TFT T * FT | F(E) G(E): ETE E TE | TFT T*FT | F(E) | i，I，I，IP，E，T，E，F，T，I，G(E): ETE E | TFT T * FT | F(E)| I，I，IP，E，T，E，F，T，I，G(E): ETE E | TFT T * FT | F(E)| I，I，I，IP，E，T，E，F，T，I，I ，T，E，F，T，I，G(E): et E TE | TFT T * FT | F(E)| I，I，I，IP，E，T

6、，E，F，T，I，T，E，F，T，I，G(E): et E | TFT T * FT | F(E)| I，I，I，IP，E，T，E，F，T，I，T，E，F，T，I，G(E)333333 ，注意：不能有，ETE E TE | t * ft | F(E)| I，# FOUND(E)，这可以从F(E)中得知，)FOUND(E)，通过ETE，应该将FOUND(E)添加到FOUND(E)由E TE和E，应该添加FOUND(E)。【示例4.10】 GE ETE E TE| TFT T*FT| F(E)|i，询问FOUND FOUND(E)=#)E是起始符号# FOUND(E)和F(E)FOUND(E)=#

7、)FOUND(E)FOUND(E)加入# E TE FIRST(E)-加上FOUND(T)和E，FOUND(E)加上FOUND(T)FOUND(T)=FOUND(T)，加上FOUND(T)FOUND(F)=*，)，# T FOUND FOUND(F) first (t)=(，if first (e)=，FIRSt(e)=(，I，没有构造也就是说，如果A 1| 2| n，那么FIRST(i)FIRST(j) (ij) 3。 对于语法中的每个非终结符，首先(I)跟随(A)=i=1，2，如果一个语法G满足上述条件，那么这个语法G就被调用。对于一个满足上述条件的语法，它可以有效地从上到下分析它的输入字

8、符串，而不需要回溯。假设非终止符A用于匹配，输入符号是A，并且A的所有表达式都是A 1 | 2 | | n 1。如果是第一个(I)，我将被分配执行匹配任务；2.如果一个不属于任何候选前缀集，那么：(1)如果一个属于一个第一(I)和一个跟随(A)，让一个自动匹配。(2)否则，A的出现就是一个语法错误。示例4.11ge:et e te | tft t * ft | f(e)| I确定语法是否为LL(1)语法。，FIRST(F)=(，i FIRST(T)=*，FIRST(T)=(，i FIRST(E)=，FIRST(E)=(，I，FOUND(E)=#)，FOUND(E)=#，FOUND(T)=，#

9、FOUND(T)=FOUND(T)=，# FOUND(F)=*，#，回顾：LL(1)分析方法，构造无回溯的自顶向下分析算法，消除语法的左递归，克服回溯， 4从一些非LL(1)文法到LL(1)文法的等价转换，以消除左递归【例4.12】GS : ASB | aabac | bbcbba | a，4.4递归下降分析程序的构造，无回溯的自顶向下分析程序的构造，消除左递归的语法，克服回溯，递归下降分析方法，为语法中的每个非终止符(语法成分)编写一个子程序，子程序的代码结构由相应的非终止符的右边部分决定：右边部分的终止符基本思想如下：(1)递归子程序法，分析程序由一组递归过程组成，每个语法中的非终结符对应

10、一个过程；因此，这种分析器被称为递归下降分析器。(因为语法的定义通常是递归的)几个全局过程和变量：高级，将输入字符串指示符指向下一个输入符号，即读入单个单词符号符号，当前由输入字符串指示的输入符号错误，错误处理子程序，示例：语法G(E): ETE E E TE |薄膜晶体管T*FT | F(E) | i每个非终结符都有相应的子程序定义。首先，在分析过程中，当需要从非终结符展开(推导)时，调用与该非终结符对应的子程序。例：语法G(E): ETE E TE | TFT T*FT | F(E) | i相应的递归下降子程序是：PROCESSE E；开始测试；E END，PROCESSE E；如果SYM

11、=那么开始前进；t。结束，程序测试；开始。测试结束，程序测试；如果SYM=*那么开始前进；f；T END示例：语法G(E): ETE E TE |薄膜晶体管T*FT | F(E) | i对应于：递归下降子程序，示例：语法G(E): ETE E TE |薄膜晶体管T*FT | F(E) | i对应于：递归下降子程序。如果SYM=我接着前进，否则如果SYM=(然后开始前进；e。如果SYM=)那么提前否则错误结束否则错误；主程序： PROGRAM PARSER开始前进；e。如果SYM #那么错误结束；在元符号“”和“|”的基础上，对几种元语言符号进行了扩展：1 .用花括号表示闭包运算*。2.0n可以

12、随意重复0到n次。3.使用方括号表示01，这意味着外观是可选的(相当于|)。用上述元符号引入的语法也被称为扩展的Bakos范式。另一种表示语法和转换图，例如，通常的“实数”可以定义为：十进制符号整数。digitexponent index sign integer integerdigitdigit sign |-扩展Bakos范式用于描述语法，直观易懂，便于表达左递归消去和因子提取。例4.5语法ET | E T TF | T*F Fi | (E)可以表示为et t TF * f fi | (e) (4.6)，而et t TF * f fi | (e) (4.6)可以用语法图来表达一种语言的语法。可以构造一套递归下降分析程序。开始测试；而SYM=开始前进；结束结束；PROGRAMME T；开始。而SYM=*开始前进；结束结束；(4.6)可以构造一组递归下降分析程序；如果SYM=我接着前进，否则如果SYM=(然后开始前进；e。如果SYM=)那么提前否则错误结束否则错误；构造方法非常简单，程序结构清晰，递归调用多，内存多，速度慢。如果采用的高级语言不允许递归，则不能使用此方法。递归减少了分析方法的优点和缺点。1.语法不包含左递归；2.语法中每个非