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

wuyangchun 發(fā)布于2019-08-14 15:15 / 1518人閱讀

摘要：一個非終結符可以被展開稱為一個串，如上定義便是將這個非終結符展開稱為一個又終結符和非終結符混合而成的串。特別注意我定義的方法僅僅用于修飾非終結符，而非展開式，雖然這個例子中我的方法更靠近方法，但并意味著用于修飾展開式。

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

GitHub 中的 tao 語言編譯器項目

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

- com.taozeyu.taolan.analysis
|- FirstSetConstructor
|- LexicalAnalysis
|- LexicalAnalysisException
|- NonTerminalSymbol
|- SignParser
|- TerminalSymbol
|- Token

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

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

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

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

定義出 tao 語言的文法。

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

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

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

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

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

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

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

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

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

Line -> Command | Operate | DefineVariable ...

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

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

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

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

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

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

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

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

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

GPU云服務器云服務器從零開始的郵件服務器從零開始 linux從零開始 python從零開始

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://systransis.cn/yun/65516.html

從零開始寫個編譯器吧 - LL(1)

摘要：希臘字母表示空，這個產生式表明非終結符可以產生一個空。此外，對于一個文法之中的非終結符，還有集集的概念。對于一個非終結符而言，它的集指可能展開的各種形式中，位于第一的所有終結符所組成的集合。上一章中，我說 Parser 的工作就是依據文法定義，找到一個與源代碼匹配的展開方案就可以了。聽起來我們只要先給出一個 tao 語言的文法定義，然后寫一個找匹配方案的的程序就可以了。然而事情情況...

Tony 2019-08-14 12:03 評論0 收藏0
從零開始寫個編譯器吧 - tao 語言的文法定義（下）

摘要：目前為止我們創(chuàng)建的文件列表新上一章中我們提到了個方法它們可以用來描述非終結符和展開式的形式，那么它們又是如何工作的呢文件中定義了一些方法。特別的，注意如下代碼這個方法可以紀錄被掉的一組非終結符，紀錄這些東西有什么用，將在隨后的章節(jié)介紹。目前為止我們創(chuàng)建的文件列表： |- com.taozeyu.taolan.analysis |- FirstSetConstructor ...

Michael_Lin 2019-08-14 15:16 評論0 收藏0
從零開始寫個編譯器吧 - 程序流控制

摘要：從展開式中，可以看出，除了這個非終結符，還有其他一些非終結符。是可能展開的形式之一，在語言中，如下代碼就是一行典型的從表達式來看，它是由一個級表達式和一個類型的非終結符組成。但特別注意結尾的數量詞表明，整個非終結符都是可選的。目前為止我們創(chuàng)建的文件列表： |- com.taozeyu.taolan.analysis |- FirstSetConstructor |- ...

huangjinnan 2019-08-14 15:15 評論0 收藏0
從零開始寫個編譯器吧系列

摘要：是的，這個系列將呈現一個完整的編譯器從無到有的過程。但在寫這個編譯器的過程中，我可不會偷工減料，該有的一定會寫上的。該語言的虛擬機將運行于之上，同時編譯器將使用實現。我早有寫編譯器的想法之前沒寫過，故希望一邊寫編譯器一邊完成這個系列。是的，這個系列將呈現一個完整的編譯器從無到有的過程。當然，為了保證該系列內容的簡潔（也為了降低難度），僅僅保證編譯器的最低要求，即僅能用。但在寫這個編譯...

genedna 2019-08-14 11:58 評論0 收藏0
從零開始寫個編譯器吧 - 文法簡介

摘要：而，稱之為非終結符。而這個展開方案中對各個非終結符產生式的選擇過程，即是對源代碼中每一個部分的定性過程。這個過程讓能夠理解源代碼各個部分表示的含義，并以此生成對應的語法樹。我需要定義出 tao 語言的細節(jié)，在此，需要引出文法這一概念。所謂文法，即是用于描述語言的一種工具。例如，一個賦值語句可能寫成如下形式： variable = 1 + 3 如何充分定義這個賦值語句的形...

stormzhang 2019-08-14 12:03 評論0 收藏0