[TOC] ## 递归法求抽象语法树 ``` Expr -> Expr + 1 | 1 ``` - 非终结符(递归)函数:parseExpr (生成一个非叶子节点) - 终结符函数:parseNumber(生成一个叶子节点) 采用递归向下方法,每个产生式的非终结符对应一个函数 ``` E() ,E_(),U(),F() E:代表表达式 E_:左右递归互相转换 U:一元表达式 ,如:(E) | ++E | --E F:因子 ``` 产生式的关系对应一个高阶函数 ``` 合并关系,如:E()E_()-> combine(0->E0,0->E0) 竟争关系,如:E|F->race(()->E(),()->F()) ``` ## 右递归 ``` Expr -> 1+Expr | 1 ``` 解析1+1+1+1的过程如下: ``` parseExpr(1+1+1+1) eat(1);eat(+); parseExpr(1+1+1) eat(1);eat(+); parseExpr(1+1) eat(1);eat(+); parseNumber(1) ```  >[warning] 左递归会陷入无限递归 ## 左递归转有递归 ``` 左递归 E(k) -> E(k) op(k) E(k+1) |E(k+1) 转为有右递归: E(k) -> E(k+1) E_(k) // var e =new Expr(); e.left = E(k+1);e.op=op(k);e.right=E(k+1)E_(k) E_(k) -> op(k) E(k+1) E_(k) | ε (标识为空) 最高优先级: E(t) -> F E_(k) | U E_(k) E_(t) -> op(t) E(t) E_(t) | ε ```