第四章语法分析—自上而下分析本章主要内容4.3.2消除回溯、提左因子同一非终结符有多个候选式时令G是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST()为：1.FIRST集（1）若α=aα′，且a∈VT，则a∈FIRST(α)；例：FIRST(i)={i}FIRST(+TE')={+}①将FIRST(X1)中的一切非ε的终结符加进FIRST(α)；②若ε∈FIRST(X1),则将FIRST(X2)中的一切非ε的终结符加进FIRST(α)；③若ε∈FIRST(X1)且ε∈FIRST(X2),则将FIRST(X3)中的一切非ε的终结符加进FIRST(α)；④依此类推，若对于一切1≤i≤n,ε∈FIRST(Xi)，则将ε加进FIRST(α)。FIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)=FIRST(F)={(,i}FIRST(E’)={+,ε}FIRST(E)=FIRST(T)={(,i}FIRST(TE’)=FIRST(T)={(,i}FIRST(+TE’)={+}FIRST(ε)={ε}FIRST(FT’)=FIRST(F)={(,i}FIRST(*FT’)={*}FIRST(（E）)={(}FIRST(i)={i}提取公共左因子:假定关于A的规则是A→1|2|…|n|1|2|…|m(其中，每个不以开头)那么，可以把这些规则改写成A→A|1|2|…|mA→1|2|…|n经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。E→TEE→+TE|T→FTT→*FT|F→(E)|ii+ii+ii+ii+ii+ii+ii+ii+ii+ii+ii+ii+ii+ii+i假定S是文法G的开始符号，对于G的任何非终结符A，我们定义构造集合FOLLOW的算法【例4.10】G[E]E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i构造不带回溯的自上而下分析的文法条件1.文法不含左递归，2.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A→1|2|…|n则FIRST(i)∩FIRST(j)＝(ij)3.对文法中的每个非终结符A，若它存在某个候选首符集包含，则FIRST(i)∩FOLLOW(A)=i=1,2,...,n如果一个文法G满足以上条件，则称该文法G为LL(1)文法。对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为A→1|2|…|n1.若aFIRST(i)，则指派i执行匹配任务；2.若a不属于任何一个候选首符集，则：(1)若属于某个FIRST(i)且aFOLLOW(A)，则让A与自动匹配。(2)否则，a的出现是一种语法错误。【例4.11】G[E]：E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i判别该文法是否为LL(1)文法。回顾：LL(1)分析法4．某些非LL(1)文法到LL(1)文法的等价转换4.4递归下降分析程序构造递归下降分析法分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。(因为文法的定义通常是递归的)几个全局过程和变量：ADVANCE，把输入串指示器IP指向下一个输入符号，即读入一个单字符号SYM，IP当前所指的输入符号ERROR，出错处理子程序例:文法G(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。例:文法G(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i对应的递归下降子程序为:PROCEDURET；BEGINF；TEND例:文法G(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i对应的递归下降子程序为:主程序:PROGRAMPARSER;BEGINADVANCE;E;IFSYM<>’#’THENERROREND;在元符号“→”和“|”的基础上，扩充几个元语言符号：1.用花括号{}表示闭包运算*。2.用表示{}0n可任意重复0次至n次，。3.用方括号[]表示{}01，即表示的出现可有可无(等价于|)。引入上述