编译原理Chapt4-2.pptVIP

第四章 语法分析—自上而下分析;本章主要内容;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 | … | ? m A?→? 1 | ? 2 | … | ? n 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。; ; E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→(E) | i i + i ;i + i ;i + i ;i + i ;i + i ;i + i ;i + i ;i + i ;i + i ;i + i ;i + i ;i + i ;i + i ;i + 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 | … | ? n 1. 若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 每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。