编译原理第四章总结

编译原理（语法分析--自上而下分析）第四章总结
1.语法分析是编译过程的核心部分。
它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。
  实现这种自上而下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可对应一个布尔过程。
   自上而下分析法存在的困难和缺点：（1）存在左递归（2）回溯（3）当一个非终结符用某一候选匹配成功时，这种成功可能仅是暂时的
  （4）最终不成功时，很难知道输入窜中出错的正确位置。
2.LL（1）分析法
  消除左递归，克服回溯
  例如：P->Pa|b改成 P->bP'|e(e为空字)
  消除回溯，提左因子
  满足构造不带回溯的自上而下分析的文法条件
   （1）文法不含左递归
   （2）对于文法中每一个非终结符A的各个产生式的候选式的FIRST集两两不相交。
        即，若A→α1|α2|…|αn
  则 FIRST(αi)∩FIRST(αj)=Φ (i≠j)

    (3)对于文法中的每个非终结符A，若它的某个候选首符集包含ε,则

FIRST(A)∩FOLLOW(A)=Φ
3.递归下降分析程序构造
  当一个文法满足LL(1)条件时，我们就可以构造一个不带回溯的自上而下分析程序，


  这个分析程序由一组（可能的）递归程序组成，
每个过程对应文法的一个非终结符。


  这样一个分析程序称为递归下降分析器。
4.预测分析程序


  使用高级语言的递归过程描述递归下降分析器，只有当具有实现这种过程的编译系统时才有实际意义。


  实现LL(1)分析的另一种有效方式是使用一张分析表和一个栈进行联合控制。我们现在介绍的预测分析程序就是属于这种类型的LL(1)分析器。
  
  本节要掌握对给定文法构造出每个非终结符的FIRST和FOLLOW集合。


课后练习：
1.S->a|^|(T)
   T->T,S|S
 (1)消去G1的左递归。然后对于每个非终结符，写出不带回溯的递归子程序。
    G'(S)
    S->a|^|(T)
    S->ST'
    T'->,ST'|ξ