花心胡萝卜 花心胡萝卜工作室 递归向下法

递归向下法

递归向下法解析

针对于我们的四则运算, 我们将它拆解成 表达式(Expr), 项(Term) 和 因子(Factor) 三部分.
那么, 我们的规则如下:

// 表达式 是由一个 项 + 一个表达式, 或者由一个 项 - 一个表达式, 或者由一个 项 组成
Expr = Term + Expr
     = Term - Expr
     = Term

// 项 是由一个 因子 * 一个项, 或者由一个 因子 / 一个项, 或者由一个 因子 组成
Term = Factor * Term
     = Factor / Term
     = Factor

// 因子, 可能是一个 数值, 也可能是一个 负号 + 一个表达式, 也可能是 ( + 一个表达式 组成
Factor = Number
       = - Expr
       = ( Expr )

我们举个例子, 1 + 2 * (3 - 1)
解析过程如下

Expr = 1 + 2 * (3 - 1)
Expr = Term(1) + Expr(2 * (3 - 1))

Term = 1

Factor(1)

Factor = 1
Ret NumberNode(1)
Expr = 2 * (3 - 1)

Term(2 * (3 - 1))
Term = Factor(2) * Term((3 - 1))

Factor = 2
Ret NumberNode(2)
Term = (3 - 1)

Factor((3 - 1))
Factor = ( Expr(3 - 1))

Expr = 3 - 1)

Expr = Term(3) - Expr(1))

Term = 3

Factor(3)
Ret NumberNode(3)
Expr = 1)
Term(1))

Factor(1))
Factor = Factor(1) Expr())

Factor(1)
Ret NumberNode(1)

Expr())

Term())

Factory())

Ret

经过如上过程, 我们解析出了一个优先级最低的Node, 然后进行计算就可以了.

如有错误,请提出指正!谢谢.

本文由 花心胡萝卜 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2017-02-19 at 04:06 pm