三、創建 Abstract Syntax Tree
這裡需要考慮到2個不同的正常情況:
1、不同級別的操作符:+和-的優先等級比較低,×和/的優先等級比較高
2、同級別的操作符,操作的順序。比如,+和-的優先順序是從左往右。
從最簡單的情況開始考慮:分析 1 + 2 + 3 + 4
首先,AST 樹是空的, Root = NULL。
當把 NumToken 1 插入樹的時候,簡單的設置該 Token 為根即可。
當把 OpToken + 插入樹的時候,我們就需要挪動樹,把 + 設置成根:
當把 NumToken 2 插入樹的時候,我們就把數字 2 插入樹的右側:
當把 OpToken + 插入樹的時候(同級別的操作符,順序是左到右),我們就需要把最新的 OpToken 設置成根,當前樹設置成新根的左側: