第四章 语法分析（自上而下）

主要内容：

  1：语法分析的过程（自上而下推导，自下而上规约）

  2：文法的改造

  3：递归下降分析器的设计（LL分析，自上而下的推导）

  4：语法分析器的自动生成（LR分析，自下而上的规约）

（一 ）定义： 语法分析是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。

（二） 工作：语法分析工作是判断一个输入串是否符合语法规则——————结果：构造一颗语法树

（三）基本思想：对任何一个输入串，试图用一切可能的办法，从文法的开始符号(根节点)出发，根据文法自上而下地为输入串建立一棵语法树，即为输入串寻找一个最左推导。

（四）本质：是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。

（五）面临问题：1. 文法的左递归问题
   2.回溯的不确定性，要求我们将已经完成工作推倒从来，
   3.虚假匹配的问题
   4.不能准确地确定输入串中出错的位置
   5.效率低

（六）改造文法：

  问题：
 对于许多程序设计语言的文法，都有产生式
  语句→if 条件 then 语句 else 语句
   | if 条件 then 语句

（七）消除文法左递归：（八）消除间接左递归考虑文法：  
 SQc|c
    QRb|b
    RSa|a
改造过程如下：
 S->Rbc|bc|c
 S Sabc|abc|ab|b
消除直接左递归：
 S->abcS’|abS’|bS’
 S->abcS’|ε
继续处理另外两个产生式
 Q->Sab|ab|b
 R->Sa|a

（九）消除回溯

1.消除回溯的要求

 对文法的任何非终结符，当要它去匹配输入串时，能够根据该非终结符所面临的输入符号准确地指派它的一个候选式去匹配，并且此候选式匹配后得到的工作结果应该是确信无疑的，即：
 (1)若该候选式匹配成功，那么该匹配不是虚假匹配

 (2)若该候选式无法完成最终的匹配任务，则其他任何候选式肯定也无法完成。

2.消除回溯的条件

 定义FIRST集
 令文法G是不含左递归的文法，对G的非终结符的候选α，定义它的开始符号（终结首符）集合：
特别地，如果α   ε，则ε∈FIRST(α)
如果非终结符A的任意两个候选式αi和αj的开始符号集满足FIRST(αi)∩FIRST(αj)=Φ，则A可以根据所面临的第一个输入符号，准确地指派一个候选式α去执行任务，α是那个FIRST集含a的候选式，即  a ∈FIRST(α)。