前言：之前我們不是太艱難地將字符流轉(zhuǎn)換成了 token 流梯嗽，今天我們將嘗試將 token 流轉(zhuǎn)換成「抽象語法樹」阐污，本系列博客大部分內(nèi)容來自 http://www.craftinginterpreters.com/获诈，以下只是我的學(xué)習(xí)筆記。
0X00 基礎(chǔ)理論
這次實(shí)現(xiàn)的抽象語法樹只包括基礎(chǔ)表達(dá)式肾胯，比如：
1+2*3 轉(zhuǎn)換成如下的抽象語法樹：
（非常建議和我一樣在實(shí)現(xiàn)這個解釋器的小伙伴闲勺，先去學(xué)習(xí)理論（華保健老師 編譯原理前 8 章）再動手實(shí)現(xiàn)這個解釋器）
基礎(chǔ)理論——上下文無關(guān)文法
首先我們來感性地認(rèn)識什么是「上下文無關(guān)文法」：
上下文無關(guān)文法沒啥特別的意思，無非就是一種文法規(guī)則灯变。比如我們定義了這樣幾條規(guī)則：
句子 -> 名詞 動詞 名詞
名詞 -> 羊
| 草
| 老虎
動詞 -> 吃
| 喝
這就是上下文無關(guān)文法殴玛。用這個文法我們可以構(gòu)造出來：
羊（名詞）吃（動詞）草（名詞）
老虎（名詞）吃（動詞）羊（名詞）
羊（名詞）吃（動詞）老虎（名詞）
...
接著我們用數(shù)學(xué)的手段描述一下上下文無關(guān)文法：
上下文無關(guān)文法是一個四元組：G(T, N, P, S)
- T 是終結(jié)符
- N 是非終結(jié)符
- P 是產(chǎn)生式規(guī)則
- S 是唯一的開始符號
套用上面的中文的例子：
T 是「羊 草 老虎 吃 喝」這樣不能被替換的詞
N 是「動詞 名詞」這樣能夠被替換的詞
P 是「句子 -> 名詞 動詞 名詞」這樣描述替換的規(guī)則
S 是 一切的開始
基礎(chǔ)理論——優(yōu)先級和符號關(guān)聯(lián)性
這樣我們就能寫一些有關(guān)本章的「上下文無關(guān)文法」：
expression → equality ;
equality → comparison ( ( "!=" | "==" ) comparison )* ;
comparison → addition ( ( ">" | ">=" | "<" | "<=" ) addition )* ;
addition → multiplication ( ( "-" | "+" ) multiplication )* ;
multiplication → unary ( ( "/" | "*" ) unary )* ;
unary → ( "!" | "-" ) unary
| primary ;
primary → NUMBER | STRING | "false" | "true" | "nil"
| "(" expression ")" ;
這是實(shí)現(xiàn)本章 token 流與抽象語法樹轉(zhuǎn)換的關(guān)鍵，其中 * 是可重復(fù)的意思添祸。比如 1 * 2 * 3 * 4
完全理解之前滚粟，我們得先弄懂兩個基本概念：「優(yōu)先級」和「符號關(guān)聯(lián)性」
- 優(yōu)先級
這一點(diǎn)不用說，* 比 + 高刃泌。這里的符號優(yōu)先級與 C 語言類似凡壤，且在上面那個「上下文無關(guān)文法」中署尤，越在上面的符號，優(yōu)先級越低也就是
( "!=" | "==" ) < ( ">" | ">=" | "<" | "<=") < ( "-" | "+" ) < ( "/" | "*" ) < ( "!" | "-" )
- 符號關(guān)聯(lián)性
除了 "!" "-" 這兩個符號亚侠，其他符號都是左關(guān)聯(lián)曹体。
-1 !0 右關(guān)聯(lián)
1 + 2 + 3 左關(guān)聯(lián)
0X01 代碼實(shí)現(xiàn)
接著我們要憑借著：
expression → equality ;
equality → comparison ( ( "!=" | "==" ) comparison )* ;
comparison → addition ( ( ">" | ">=" | "<" | "<=" ) addition )* ;
addition → multiplication ( ( "-" | "+" ) multiplication )* ;
multiplication → unary ( ( "/" | "*" ) unary )* ;
unary → ( "!" | "-" ) unary
| primary ;
primary → NUMBER | STRING | "false" | "true" | "nil"
| "(" expression ")" ;
實(shí)現(xiàn)抽象語法樹了！注意盖奈，按照這個實(shí)現(xiàn)語法樹混坞，就會完成的符號的優(yōu)先級了，而對于符號的關(guān)聯(lián)性只需要在代碼中具體實(shí)現(xiàn)就好了钢坦！
用的方法很簡單究孕，掃描 token，自頂向下建立抽象語法樹
基本框架
先寫出基本框架：從 parse() 解析 expression 開始：
public class Parser {
private final List<Token> tokens;
private int current = 0;
Parser(List<Token> tokens) {
this.tokens = tokens;
}
Expr parse() {
return expression();
}
}
根據(jù)文法寫出替換
我們看到前兩個替換：
expression → equality ;
equality → comparison ( ( "!=" | "==" ) comparison )* ;
所以代碼寫成：
private Expr equality() {
// equality → comparison ( ( "!=" | "==" ) comparison )* ;
Expr expr = comparison();
if (match(BANG_EQUAL, EQUAL_EQUAL)) {
Token operator = previous();
Expr right = comparison();
expr = new Expr.Binary(expr, operator, right);
return expr;
}
return expr;
}
private Expr expression() {
// expression → equality ;
return equality();
}
一路順下來就可以寫出最后的代碼見：https://github.com/TensShinet/toy_compiler/blob/master/code/MyLox/src/app/Parser.java爹凹。
最后解釋一下 Expr.Binary 這個是什么
由于現(xiàn)在是簡單的表達(dá)式：1+2*3 這樣的厨诸，所以表達(dá)式的種類并不多。
只有四種：
- Unary 一元表達(dá)式禾酱。-1
- Binary 二元表達(dá)式 1 + 2
- Group 組 (expression)
- Literal 值 現(xiàn)在只有 數(shù)字 字符串 true false null
