【编译原理】递归下降分析法

递归下降分析法

也称为预测分析，特点：

• 分析高效（线性时间）
• 容易实现（方便手工编码）
• 错误定位和诊断信息准确
• 被很多开源和商业的编译器所采用(GCC 4.0, LLVM...)

算法基本思想：

• 每个非终结符$ s$构造一个分析函数
• 用前看符号指导产生式规则的选择

公式：

• 遇到终结符号 a 时：if(当前输入 == a)，读入下一个，否则error。

• 遇到非终结符 A 时，调用 A() 。

  • A() 分析函数即把非终结符替换为对应的终结符，进行比较。

算法示例：

文法：

S -> N V N
N -> s
   | t
   | g
   | w
V -> e
   | d

算法：

parse_S()
  parse_N()
  parse_V()
  parse_N()
 
parse_N()
  token = tokens[i++]
  if (token==s||token==t||token==g||token==w)
    return;
  error(“…”);
 
parse_V()
  token = tokens[i++]
  if (token==e||token==d)
    return;
  error(“…”);

以句子 g d w为例，

• 调用parse_N()时，前看符号token = g，
• 调用parse_V()时，前看符号token = d，
• 再次调用parse_N()时，前看符号token = w,
• 执行结束，没有报错，说明语法无异常。

推导出一般的算法框架：

文法：

X -> β11 … β1i
   | β21 … β2j
   | β31 … β3k
   | …

算法：

parse_X()
  token = nextToken()
  switch(token)
  case …: // β11 … β1i
  case …: // β21 … β2j
  case …: // β31 … β3k
  …
  default: error (“…”);

算法缺点：

在A的分析过程中需要处理两个产生式都有a所带来的选择问题，即必须再看下一个token才能决定。如果文法再复杂一些，比如A -> aB | aaaC | aaD$，B -> a | b， C -> c， D -> a | d 之类，必然在对A进行递归下降过程中需要进行回溯。