Interpreter
January 8, 2022你有想過自己創造一個程式語言嗎？在〈打造玩具語言〉，我試著土炮過一個玩具語言，試著將一些現代語言的元素實現出來，儘管沒什麼實用性，不過是個很有趣的經驗，也從中學到許多東西。
打造一門語言看來好像很難，然而就實驗而言，志向不要太遠大，從最簡單的語法開始練習，有想法再加入調整，以我個人的經驗來說，是個不錯的方式，你會遇上一些難題，然後試著解決，最後覺得做法不完美，這過程得到的東西，在你閱讀語言實作的相關書籍或文件時，會有很大的幫助，你會比較清楚它們在談什麼。
抽象語法樹
那麼這邊就來個更簡單陽春的語言吧！首先，這門語言有 print 指令，可以指定要顯示的文字，例如，想在主控台顯示 caterpillar，可以這麼寫：
print caterpillar
先別管怎麼剖析這個語言，如果要用個物件來代表 print 指令，你需要能封裝文字，然後執行時顯示文字，因此可以設計：
class Print {
private String text;
Print(String text) {
this.text = text;
}
void execute() {
System.out.println(text);
}
}
若要能對應方才寫的 print caterpillar，你可以撰寫程式：
new Print("caterpillar").execute();
如果有兩行以上的指令呢？
print Justin
print Monica
print Irene
你可以建立三個 Print 實例，封裝對應的文字，然後依序呼叫：
var cmd1 = new Print("Justin");
var cmd2 = new Print("Monica");
var cmd3 = new Print("Irene");
cmd1.execute();
cmd2.execute();
cmd3.execute();
建立 Print 實例的動作是必須的，然而 execute 的動作重複了，你想了一下，這是一串指令組成的指令區塊，那麼來設計一個 Block：
import java.util.*;
interface Command {
void execute();
}
// print 指令
class Print implements Command {
private String text;
Print(String text) {
this.text = text;
}
public void execute() {
System.out.println(text);
}
}
// 指令區塊也是指令
class Block implements Command {
private List<Command> cmdlt = new ArrayList<>();
void add(Command command) {
cmdlt.add(command);
}
public void execute() {
for(var command : cmdlt) {
command.execute();
}
}
}
這麼一來，你就可以這麼撰寫程式：
var block = new Block();
block.add(new Print("Justin"))
block.add(new Print("Monica"));
block.add(new Print("Irene"));
block.execute();
如果你想重複執行指令呢？或許有個 repeat 指令：
repeat 3
print dog
這會將其中的指令重複執行三次，為此可設計一個 Repeat，封裝次數與指令：
class Repeat implements Command {
private int times;
private Command command;
Repeat(int times, Command command) {
this.times = times;
this.command = command;
}
public void execute() {
for(var i = 0; i < times; i++) {
command.execute();
}
}
}
這麼一來就可以如下執行：
var block = new Block();
block.add(
new Repeate(3, new Print("dog"))
);
block.execute();
如果是這個程式呢？
repeat 3
print dog
print cat
別忘了，指令區塊也是指令，那麼遇到 repeat 時，乾脆建個 Block 好了：
// 主區塊
var main = new Block();
// repeat 區塊
var repeatBlock = new Block();
repeatBlock.add(new Print("dog"));
repeatBlock.add(new Print("cat"));
var repeat = new Repeate(3, repeatBlock);
main.add(repeat);
main.execute();
這個簡單的語言還可以巢狀：
repeat 3
print --------
repeat 2
print dog
print cat
對應的指令物件該怎麼組合呢？想設計一門語言，如何組合這些物件是必須思考的過程，物件若視為節點，這些物件的組合視為一棵樹，有發現嗎？一旦建立這棵樹，只要呼叫根節點的 execute，就是在執行程式了，這棵被稱為抽象語法樹（abstract syntax tree）。
自動建立語法樹
只不過，以上是手動建立語法樹，也就是說，把自己當成是直譯器（interpreter）了，有沒有辦法自動化呢？如果沒有 repeat 的話也許還好，因為只要逐行剖析，將每 print xxx 的 xxx 剖析出來，然而 repeat 構成了巢狀，也就是可能構成更複雜的遞迴結構：
repeat 3
print --------
repeat 2
print dog
print cat
repeat 2
print |XDXDXDXD|
print |OrzOrzOrz|
這時該怎麼剖析呢？這門語言已經超簡單了，沒有考慮程式碼的前後文，也就是還沒考慮有這個功能：
repeat 3
print --------
repeat 2
print dog
print cat
print --------
在語言要考慮前後文、有更複雜指令的情況下，撰寫出來的程式碼就會有更複雜的結構，該怎麼剖析程式碼，自動建立語法樹呢？這其實是很大的議題，現代有各式各樣的剖析器，依語言想達到的特性，也有各種不同的方式，因為採用不同的方式，想採用這些剖析器，制定語言文法時的規範也就各不相同。
因此，如果你想要使用某個現成的剖析器，得先瞭解它採取的方式，然後知道在其架構上，該如何定義語言的文法，這也就是為什麼，一些語言實作的書，談沒多久，就會開始定義文法了。
如果真有心做個實用的語言，務實的方法確實是使用這些剖析器，畢竟基於擴充性、穩定性、效率等各方面來考量，實在不用重新打造輪子。
然而，自己動手實作一個剖析器，依舊是個有趣的課題，這可以讓你知道，一門語言是如何構造，也可以稍微接觸一下抽象語法樹，如果你工作上的語言，有提供介面，可以讓你接觸它的抽象語法樹的話，這些經驗就會很有用，可以讓你玩許多魔法。
各自的職責
那就來看看，方才這個簡單到不行的語言，如何實作個剖析器吧！只要掌握一個基本，想想看遞迴，如果你覺得遞迴難以掌握，那一定是你在每次遞迴時，做了太多不是該次遞迴要做的事，遞迴的精神在於，每次只做好自己份內的事，不要管上一次遞迴做了什麼，也不要管下次遞迴要做什麼。
在剖析程式碼的時候也是如此，如果你在剖析 print，就別去管 repeat，如果你在剖析 repeat，那就只要管 repeat 該怎麼剖析，Gof 的 Interpreter 模式想傳達的概念，只是如此罷了。
來具體看看吧！因為方才的語言很簡單，只要依空白、換行等切出程式碼裡的文字符號就可以了，來定義一個 Source 做這件事：
class Source {
private Scanner scanner;
Source(String code) {
scanner = new Scanner(code);
}
boolean hasNextToken() {
return scanner.hasNext();
}
String nextToken() {
return scanner.next();
}
}
這看來很簡單，是因為要實現的語言很簡單，如果你的語言需要考慮前後文、有更複雜的語法，Source 要處理的任務就會變多就是了…接下來定義 Parser 的行為，剖析時的 parse 方法可接受 Source，從 Source 取得文字符號，然後傳回抽象語法樹的節點，也就是 Command 實例：
interface Parser {
Command parse(Source source);
}
為了簡化問題，以下會忽略 Parser 在剖析過程時，如果遇到使用者程式碼寫錯時，該怎麼處理的問題；程式碼一開始，其實就是個指令區塊，可以包含許多指令，遇上 print 就建立負責剖析後續程式碼的 PrintParser，遇上 repeat 就建立負責剖析後續程式碼的 RepeatParser，會有個 Block 實例將剖析完的 Command 實例收集起來然後傳回：
class BlockParser implements Parser {
@Override
public Command parse(Source source) {
var block = new Block();
while(source.hasNextToken()) {
var cmd = source.nextToken();
if(cmd.equals("print")) {
block.add(new PrintParser().parse(source));
}
else if(cmd.equals("repeat")) {
block.add(new RepeatParser().parse(source));
}
}
return block;
}
}
BlockParser 不會去管 PrintParser、RepeatParser 怎麼剖析，那是它們的事；PrintParser 負責剖析 print 接受的文字，它不會有子節點了，因此實作上很簡單，取得下個文字符號，建立 Print 封裝就好了：
class PrintParser implements Parser {
@Override
public Command parse(Source source) {
return new Print(source.nextToken());
}
}
RepeatParser 需要將 repeat 時需要的次數剖析為整數，每個 repeat 實際上會建立一個指令區塊，不過那是 BlockParser 的事，RepeatParser 只要將 BlockParser 剖析後傳回的 Command 一併封裝起來就可以了：
class RepeatParser implements Parser {
@Override
public Command parse(Source source) {
var times = Integer.parseInt(source.nextToken());
return new Repeat(times, new BlockParser().parse(source));
}
}
程式一開始就是指令區塊，因此建立一個 BlockParser，然後把 Source 丟進去，就會傳回一棵抽象語法樹：
var code = """
repeat 2
print dog
repeat 2
print |----XD
print |----Orz
""";
var ast = new BlockParser().parse(new Source(code));
ast.execute();
執行之後就會顯示以下的結果：
dog
|----XD
|----Orz
|----XD
|----Orz
dog
|----XD
|----Orz
|----XD
|----Orz
有沒有想挑戰更多語法的玩具語言呢？野心不要太大，可以有變數、可以運算 +、-、*、/、可以運算費式數之類的，你會怎麼寫呢？
〈打造玩具語言〉裡的語言，一開始也只是這 300 多行的 gist 喔！試試看吧！
