递归法求抽象语法树
最后更新于：2022-04-02 04:07:59
[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) | ε
```
';