第4章自上而下语法分析.ppt

第四章 自顶向下语法分析方法;4.1 语法分析概述; 语法分析在编译系统中所处的位置;语法分析器的输入 Token序列：词法分析的输出，是各个单词都正确的源程序的变换形式，是一个有限序列 语法分析器的输出 分析树：表示方法？ 见教材 P89 错误处理信息：定位、继续编译;语法分析器的功能 按照语言的语法构成规则, 识别输入的符号串能否构成一个句子。这些规则是用文法的产生式来定义的。 问题 对给定的一个输入串，如何判定它是不是一个句子？ 方法 根据文法的产生式规则，从开始符号出发，看能否推导出与这个输入串匹配的句子。这就需要建立与输入串匹配的语法分析树。;G = ({E}, {i, +, *, (, ) } , P , E) P： E ? E + E E ? E * E E ? ( E ) E ? i ;*;*;常用的语法分析方法：;4.2 自顶向下语法分析;句型的推导;自顶向下分析方法特点; 例1：设有文法 (1) S ? xAy (2) A ? |= 现有输入串：x=y 其分析过程如右：; 回溯问题;左递归：文法中存在某个A?Vn，有A A?。 直接左递归：有产生式A ? A? 间接左递归：; 结论;4.3 问题的解决方法;4.3.1 消除左递归;; 一般而言，若产生式形式为： A→Aα1|Aα2|…|Aαn|β1|β2|…|βm 将其替换为：;练 习;例：给定间接左递归文法，请消除左递归;方法是:反复 “提取公共左因子”，使得文法的每个非终结符号的各个候选式的首终结符集两两不相交，来避免回溯。;例3：有如下两个产生式： IF语句 ? if E then S1 else S2; IF语句 ? if E then S1; ;练习;问题: 如果希望没有回溯，对文法有什么要求？; 对不含左递归的文法G，对某非终结符的侯选式： First(α) = {a| α a…,a∈VT} 若α ε ，则ε∈ First(α);; S?ApS?BqA?aA?cAB?bB?dB ;(1) S ? xAy (2) A ? =|;因此，不产生回溯的条件就是： 对非终结符A的任意两个不同的侯选式ai 和aj ，都有： First(ai)∩ First(aj) = φ 当要求用A进行匹配时，就能根据所面临的输入字符，准确地选取一个A的侯选式。;*;求非终结符A的First集的算法 ; S?ApS?BqA?aA?cAB?bB?dB ;E ? TEE ? +TEE ?εT ? FTT ? *FTT ? εF ? (E)F ? i ;;确定的自上而下的分析 举例1：对于文法G1[S]：S→pA S→qB A→cAd A→a 对输入串pccadd，自上而下的推导过程是： S = pA = pcAd = pccAdd = pccadd 对应的分析树：;例2：对于文法G2[S]： ;4.4.2 后随符号集的定义;;求非终结符A的Follow集的算法 ;例:求下题的Follow集 ;练 习;例： 仍讨论文法G[S]: S→ AB | bC A→ b | ε B→ aD | ε C→AD | b D→ aS | c 所有非终结符求FOLLOW集过程如下： FOLLOW(S)={#}∪FOLLOW(D) FOLLOW(A)={a}∪{a,c}∪FOLLOW(S) FOLLOW(B)=FOLLOW(S) FOLLOW(C)=FOLLOW(S) FOLLOW(D)=FOLLOW(B)∪FOLLOW(C) 从FOLLOW(S)={#}开始，不断循环求解直到所有 FOLLOW集不再增大，最后可得： FOLLOW(S)= {#} FOLLOW(A)= {a, c,#$} FOLLOW(B)= {#} FOLLOW(C)= {#} FOLL