第4章自顶向下的语法分析语法分析的功能和位置4.1语法分析概述4.2自顶向下的语法分析面临的问题与文法的改造4.2.1自顶向下分析面临的问题4.2.1自顶向下分析面临的问题4.2.1自顶向下分析面临的问题4.2.1自顶向下分析面临的问题4.2.2对上下文无关文法的改造4.2.2对上下文无关文法的改造4.2.2对上下文无关文法的改造4.2.2对上下文无关文法的改造4.2.2对上下文无关文法的改造举例<stmt>→if<expr>then<stmt>|if<expr>then<stmt>else<stmt>提取左公共因子后<stmt>→if<expr>then<stmt><stmt_new><stmt_new>→ε|else<stmt>4.2.3LL(1)文法4.2.3LL(1)文法4.2.3LL(1)文法4.2.3LL(1)文法LL(1)文法的判定计算FIRST(X)的算法的另外一种描述输入：文法G=(V，T，P，S)，X(V∪T);输出：FIRST(X);若XT，则FIRST(X)＝{X}若XV，且有Xa…，aT，则aFIRST(X)若XV，X，则FIRST(X)若XV，y1，y2，…，yi都V∪T，若有产生式Xy1y2…yn，当y1，y2，…yi-1都时(1≤i≤n)，则FIRST(y1)－{}，FIRST(y2)－{}，…，FIRST(yi－1)－{}，FIRST(yi)都包含在FIRST(X)中。e)当上式中所有yi(1≤i≤n)，则FIRST(X)＝(FIRST(y1)-{})∪(FIRST(y2)-{})∪…∪(FIRST(yn)-{})∪{}LL(1)文法的判定一个文法符号串α的first集合另外一种求法例表达式文法的语法符号的FIRST集LL(1)文法的判定例表达式文法的语法变量的FOLLOW集表达式文法是LL(1)文法非LL(1)文法的不确定性不确定性的解决方法4.3预测分析法4.3.1预测分析器的构成系统的执行与特点预测分析程序的总控程序预测分析程序的总控程序FOLLOW(E')={),#}FOLLOW(T')={+,),#}FIRST(TE')={(,id}FIRST(+TE')={+}FIRST(FT')={(,id}FIRST(*FT')={*}FIRST((E))={(}FIRST(id)={id}简单算术表达式文法的预测分析表对输入串id+id*id进行分析的过程#E'T'Fid*id#T→FT'#E'T'idid*id#F→id#E'T'*id##E'T'F**id#T'→*FT'#E'T'Fid##E'T'idid#F→id#E'T'##E'#T'→ε##E'→ε4.3.2预测分析表的构造算法预测分析法的实现步骤4.4递归下降分析法—一个设想4.4.1递归下降分析法的基本思想4.4.1递归下降分析法的基本思想4.4.2语法图和递归子程序法4.4.2语法图和递归子程序法例4.15简单表达式文法的语法图4.4.3基于语法图的语法分析器工作方式4.4.3基于语法图的语法分析器工作方式4.4.4语法图的化简与实现例4.16简单算术表达式的语法分析器Ｔ的子程序(T→F(*F)*)Ｆ的子程序(F→(E)|id)主程序4.4.5递归子程序法的实现步骤递归子程序法的优缺点分析本章小结本章小结