從零開始寫個編譯器吧 - tao 語言的文法定義（上）

各位久等了，本系列在新一年的連載中，形式會加入少許變化。首先，我會將 tao 語言編譯器（以及運行環境）的全部內容貼在 GitHub 上，在閱讀本系列的時候，需要對照 GitHub 上的內容。以取代之前一段一段貼代碼的這種形式。此外，本系列也不會像之前那樣貼出每一行代碼，並對其進行講解，取而待之，僅僅對核心代碼和有代表性的代碼進行講解。如有疑問，歡迎評論。

GitHub 中的 tao 語言編譯器項目

目前為止，我們已經寫好了如下幾個文件：

- com.taozeyu.taolan.analysisn|- FirstSetConstructorn|- LexicalAnalysisn|- LexicalAnalysisExceptionn|- NonTerminalSymboln|- SignParsern|- TerminalSymboln|- Tokenn

上一章中 NonTerminalSymbol.java 文件中留著一個 TODO，現在我把它填上：

static enum Exp {n //空白n SplitSpaceSign, SpaceOrEnter, Space,n //基本單元n Enter, This, Null, Boolean,n Number, Variable, String, RegEx,n Element,n //表達式相關n L0Expression, L0ParamExpression, L0Sign,n L1Expression, L1ParamExpression,n L2Expression, L2ParamExpression, L2Sign,n L3Expression, L3ParamExpression, L3Sign,n L4Expression, L4ParamExpression, L4Sign,n L5Expression, L5ParamExpression, L5Sign,n L6Expression, L6ParamExpression, L6Sign,n L7Expression, L7ParamExpression, L7Sign,n L8Expression, L8ParamExpression, L8Sign,n L9Expression, L9ParamExpression, L9Sign,n L10Expression, L10ParamExpression, L10Tail, L10TailOperation,n L11Expression,n //控制流語法n Chunk, StartChunk, Line,n Command, Operate, When,n DefineVariable, DefineVariableElement,n DefineFunction, ParamsList,n IfElseChunk, TryCatch,n WhileChunk, DoUntilChunk,n ForEachChunk, ForEachCommand, ForEachCondition,n //語法糖n Lambda,n List, Map, MapEntry,n Invoker, InvokerBraceless, InvokerBanLambda, InvokerBracelessBanLambda,n ParamList, ParamListBanTokens ,n Array, Container,n }n

這個 Exp 的枚舉類型代表著一系列被命名了的非終結符。

之後，我們需要做以下幾個工作：

1. 定義出 tao 語言的文法。

2. 寫一個 Complier-complier，並用它分析之前定義的 tao 語言文法，得出一部分必要的信息，並將這些信息保存在 NonTerminalSymbol 節點中。

3. 寫一個 Parser，結合文法定義，以及 Complier-complier 分析出的信息，將一段 tao 語言的源代碼分析成語法樹。

OK，上面列出的清單就是一個寫出一個可用的 Parser 的一個大致計划了。我們一步一步來吧。

首先，我們先寫出一個 SyntacticDefine.java 文件。

源代碼我就不貼了，請大家自行打開連接觀看。（PS：之後的源代碼文件會越來越長，我不一定會貼全部，請大家適應通過打開 GitHub 頁面查看源代碼的方式。）

可以看出，SyntacticDefine.java 中這個巨大的 static 塊中定義了 tao 語言的全部內容。

在此，我稍微解釋一下我是如何定義 tao 語言的文法的。例如：

node(Exp.Line).or(Exp.Command)n .or(Exp.Operate)n .or(Exp.DefineVariable)n .or(Exp.DefineFunction)n .or(Exp.IfElseChunk)n .or(Exp.WhileChunk)n .or(Exp.DoUntilChunk)n .or(Exp.ForEachChunk)n .or(Exp.TryCatch)n

每一個 Exp 枚舉類型都代表一個被命名的非終結符，如上這個定義代表如下一組展開式：

Line -> Command | Operate | DefineVariable ...

注意到，Line 這個非終結符存在很多中展開式，即它可能被展開為多種形式，因此在 static 塊中，使用 or() 方法將其並列。

node(Exp.Array).or(token(Type.Sign, "["), Exp.SpaceOrEnter, Exp.List, Exp.SpaceOrEnter, token(Type.Sign, "]"))n

一個非終結符可以被展開稱為一個串，如上定義便是將 Array 這個非終結符展開稱為一個又終結符和非終結符混合而成的串。

我使用 token() 這個方法來定義終結符，例如 token(Type.Sign, "[") 則定義了一個左方括弧的終結符。由於 Array 只有一種展開形式，因此只調用了一次 or 方法。

node(Exp.SplitSpaceSign).or(token(Type.Space)).sign(+)n

對非終結符可以使用量詞進行修飾，我使用 sign() 方法來代表量詞。如上這行定義，代表 SplitSpaceSign 這個非終結符可以展開為 1~N 個 space 類型的終結符。（特別注意：我定義的 sign() 方法僅僅用於修飾非終結符，而非展開式，雖然這個例子中我的 sign 方法更靠近 or 方法，但並意味著 sign 用於修飾展開式。）

node(Exp.L2ParamExpression).or(Exp.L3ParamExpression, node().or(Exp.L2Sign, Exp.L3ParamExpression).sign(*))n

在展開式中可以加入匿名非終結符，即調用 node 方法，但參數留空。匿名非終結符可以讓我很方便的定義某些只在展開式中出現一次的非終結符，這樣我就沒有必要為每一個非終結符起一個名字了。

被命名的非終結符和匿名非終結符沒有任何區別，它們僅僅就是形式上的不同罷了，請勿把它們當成有實質不同的東西。