MENU

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

June 2, 2020 • Read: 404 • 编程之路,编译原理

递归下降分析法

也称为预测分析,特点:

  • 分析高效(线性时间)
  • 容易实现(方便手工编码)
  • 错误定位和诊断信息准确
  • 被很多开源和商业的编译器所采用(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 | bC -> cD -> a | d 之类,必然在对A进行递归下降过程中需要进行回溯。

- - - 结束 - - -
  • 文章标题:【编译原理】递归下降分析法
  • 文章链接:https://blog.canye365.cn/archives/330.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: April 11, 2021