[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) | ε ```