递归下降分析法的基本思想。_语法分析 | 递归下降分析算法

95 阅读 0 评论 63 点赞

我是靠谱客的博主安静唇膏，这篇文章主要介绍递归下降分析法的基本思想。_语法分析 | 递归下降分析算法，现在分享给大家，希望可以做个参考。

递归下降分析算法是自顶向下分析算法的一部分。

递归下降分析算法

也称为预测分析
- 分析高效（线性时间）
- 容易实现（方便手工编码）
- 错误定位和诊断信息准确
- 被很多开源和商业的编译器所采用
  - GCC 4.0， LLVM， ...
算法基本思想
- 每个非终结符构造一个分析函数
- 用前看符号指导产生式规则的规则

对于给定的文法G如下：

复制代码

1
2
3
4
5
6
7
S -> N V N
N -> s
   | t
   | g
   | w
V -> e
   | d

我们写出它的递归下降算法如下：

复制代码

1
parse_S

一般算法框架

复制代码

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

对应的代码实现如下：

复制代码

1
parse_X

举个例子，当 β11 ... β1i 为 a B c D 时，也就是 i 为 4。（其中大写表示非终结符，小写为终结符），则其分析过程如下：

复制代码

1
parse_X

当然，使用递归下降算法也存在一定的问题，当对于上面给出的算法框架的第三行我们也是 a 开头的一些类符号的时候，当读入前看字符为 a 的时候，不仅仅可以对第一行的 a B c D 的判断执行操作，对于第三行也可以。

对算数表达式的递归下降分析

复制代码

1
2
3
4
5
E -> E + T
   | T
T -> T * F
   | F
F -> num

对于给定的上述文法，我们应用其对句子 3+4*5 做语法分析

复制代码

1
2
3
4
5
6
7
// a first try 
parse_E()
    token = tokens[i++]
    if(token == num)
        ? //  E+T or T
    else 
        error("...")

然而该算法存在一定的问题，对于 token == num的情况下，我们不知道如何做出判断，因为就 E 可以推导出的结果来说 T 可以通过 F 推出 num，而 E + T由于是 T 的递归，所以 T 能推出的 num ， E +T 也可以推出。存在选择问题。

那么我们需要对算法进行改进。

对于 E 可以推出的 T 的结果可以衍生为 T+T+...+T，

而对于 T 可以推出的 F 的结果可以变为 F*F*...*F

于是我们可以构建新的算法，对上面的两个衍生结果进行判断。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// a second try 
parse_E()
    parse_T()
    token = tokens[i++]  
    while(token == +)
        parse_T()
        token = tokens[i++]

parse_T()
    parse_F()
    token = tokens[i++]  
    while(token == *)
        parse_F()
        token = tokens[i++]