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 xxxxxx 剖析出來,然而 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 不會去管 PrintParserRepeatParser 怎麼剖析,那是它們的事;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 喔!試試看吧!