從零開(kāi)始構(gòu)建編程語(yǔ)言的挑戰(zhàn)與樂(lè)趣

作者：劉汪洋 2024-02-23 09:00:00

大約 15 年前，當(dāng)我剛開(kāi)始職業(yè)生涯并偶然踏入編譯器構(gòu)建領(lǐng)域時(shí)，我的團(tuán)隊(duì)架構(gòu)師遞給我一本《龍書(shū)》，并強(qiáng)調(diào)這是一部經(jīng)典之作，需要倍加珍惜。不過(guò)不幸的是，有一天晚上我閱讀時(shí)不慎睡著，書(shū)本從手中滑落，重重地落在地板上。還書(shū)的時(shí)候，我非常希望他沒(méi)注意到封面上的那個(gè)小凹痕。

譯者 | 劉汪洋

審校 | 重樓

“這本書(shū)是經(jīng)典之作，要好好拜讀。”

《龍書(shū)》首版發(fā)行于 1986 年，那時(shí)構(gòu)建編譯器是一項(xiàng)極具挑戰(zhàn)性的任務(wù)，它集計(jì)算機(jī)科學(xué)和編程技術(shù)、藝術(shù)之大成。近四十年后，我再次面對(duì)這一挑戰(zhàn)。如今，這項(xiàng)任務(wù)的難度又是怎樣的呢？接下來(lái)，讓我們深入探討創(chuàng)建一種新語(yǔ)言所涉及的內(nèi)容，以及現(xiàn)代工具如何簡(jiǎn)化這一過(guò)程。

目標(biāo)語(yǔ)言

為了更明確我們的目標(biāo)，我們會(huì)構(gòu)建一個(gè)具體的語(yǔ)言。我發(fā)現(xiàn)用實(shí)際案例來(lái)說(shuō)明，比理論模型更有效。因此，我選擇了我們?cè)? ZenStack 開(kāi)發(fā)的 ZModel 語(yǔ)言作為例子。ZModel 是一種用于建模數(shù)據(jù)庫(kù)表和訪問(wèn)控制規(guī)則的領(lǐng)域特定語(yǔ)言（DSL）。為了保持文章的簡(jiǎn)潔，我只展示其中的部分功能。我們的目標(biāo)是編譯下面的代碼：

model User {
  id Int
  name String
  posts Post[]
}

model Post {
  id Int
  title String
  author User
  published Boolean

  @@allow('read', published == true)
}

這里簡(jiǎn)要說(shuō)明幾點(diǎn)：

model 關(guān)鍵字用于定義一個(gè)數(shù)據(jù)庫(kù)表，其字段對(duì)應(yīng)表中的列。
模型可以相互引用，構(gòu)建關(guān)系。在此例中，User 和 Post 模型構(gòu)成了一對(duì)多關(guān)系。
@@allow 關(guān)鍵字用于定義訪問(wèn)控制規(guī)則。它接受兩個(gè)參數(shù)：一個(gè)是訪問(wèn)類(lèi)型（“create”、“read”、“update”、“delete” 或 “all”），另一個(gè)是布爾表達(dá)式，用于判定是否允許該操作。

讓我們開(kāi)始動(dòng)手編譯這段代碼吧！

注：ZModel 是 Prisma Schema Language 的擴(kuò)展版本。

六個(gè)步驟構(gòu)建編程語(yǔ)言

第 1 步：從文本到語(yǔ)法樹(shù)

盡管多年來(lái)編譯器的構(gòu)建步驟基本保持不變，但一些高級(jí)語(yǔ)言構(gòu)建工具已經(jīng)能夠簡(jiǎn)化這些步驟。這些工具可以直接將文本轉(zhuǎn)換成語(yǔ)法樹(shù)。構(gòu)建過(guò)程首先需要一個(gè)詞法分析器（lexer），它將文本分解成標(biāo)記（tokens）。然后，解析器（parser）會(huì)將這些標(biāo)記組織成解析樹(shù)（parse tree）。現(xiàn)代工具往往可以將這兩個(gè)步驟整合，直接從文本生成語(yǔ)法樹(shù)。

我們采用了 Langium，這是一個(gè)基于 TypeScript 的開(kāi)源軟件工具包，專(zhuān)門(mén)用于語(yǔ)言構(gòu)建。Langium 提供了直觀的領(lǐng)域特定語(yǔ)言（DSL），讓我們能夠定義詞法和解析規(guī)則。

值得一提的是，Langium DSL 本身也是用 Langium 構(gòu)建的。這種自我遞歸的過(guò)程，在編譯器領(lǐng)域被稱(chēng)為自舉（bootstrapping）。通常，編譯器的最初版本需要用另一種語(yǔ)言或工具來(lái)編寫(xiě)。

下面是我們的 ZModel 語(yǔ)言的正式語(yǔ)法定義：

grammar ZModel

entry Schema:
    (models+=Model)*;

Model:
    'model' name=ID '{'
        (fields+=Field)+
        (rules+=Rule)*
    '}';

Field:
    name=ID type=(Type | ModelReference) (isArray?='[' ']')?;

ModelReference:
    target=[Model];

Type returns string:
    'Int' | 'String' | 'Boolean';

Rule:
    '@@allow' '('
        accessType=STRING ',' condition=Condition
    ')';

Condition:
    field=SimpleExpression '==' value=SimpleExpression;

SimpleExpression:
    FieldReference | Boolean;

FieldReference:
    target=[Field];

Boolean returns boolean:
    'true' | 'false';

hidden terminal WS: /\s+/;
terminal ID: /[_a-zA-Z][\w_]*/;
terminal STRING: /"(\\.|[^"\\])*"|'(\\.|[^'\\])*'/;

這個(gè)語(yǔ)法定義清晰且易于理解，包含兩個(gè)主要部分：

詞法規(guī)則
底部的終結(jié)符規(guī)則定義了如何將源文本分解為標(biāo)記。我們的簡(jiǎn)單語(yǔ)言包含標(biāo)識(shí)符（ID）和字符串（STRING）兩種標(biāo)記類(lèi)型。空格字符在這里被忽略。
解析規(guī)則
其他部分是解析規(guī)則，決定了如何將標(biāo)記流組織成一棵樹(shù)。解析規(guī)則中也包含關(guān)鍵字（如 Int、@@allow），這些關(guān)鍵字同樣參與詞法分析。在更復(fù)雜的語(yǔ)言中，可能會(huì)出現(xiàn)遞歸的解析規(guī)則（例如，嵌套表達(dá)式），這需要特別注意設(shè)計(jì)，但我們的示例語(yǔ)言結(jié)構(gòu)較為簡(jiǎn)單，暫不涉及此類(lèi)情況。

通過(guò)定義好的語(yǔ)言規(guī)則，我們可以利用 Langium 的 API 將示例代碼轉(zhuǎn)換成如下解析樹(shù)：

第 2 步：從語(yǔ)法樹(shù)構(gòu)建鏈接樹(shù)

解析樹(shù)極大地幫助我們理解源代碼的語(yǔ)義。但為了進(jìn)一步完善解析樹(shù)，我們還需要進(jìn)行一些額外的步驟。

在我們的 ZModel 語(yǔ)言中，出現(xiàn)了“循環(huán)引用”的情況。例如，User 模型的字段被 Post 模型的 author 字段引用。當(dāng)我們?yōu)g覽解析樹(shù)時(shí)，會(huì)遇到引用“Post”這個(gè)名字的節(jié)點(diǎn)，但無(wú)法直接得知“Post”具體指代什么。雖然可以進(jìn)行特定的搜索來(lái)找到匹配的模型名稱(chēng)，但更系統(tǒng)的做法是執(zhí)行一次“鏈接”操作，將這些引用解析并鏈接到它們的目標(biāo)節(jié)點(diǎn)。完成這一鏈接后，我們的解析樹(shù)將轉(zhuǎn)變?yōu)槿缦滤荆榱撕?jiǎn)化展示，這里只展示樹(shù)的一部分）：

從技術(shù)角度看，此時(shí)的結(jié)構(gòu)更像是圖而非樹(shù)，但我們依舊習(xí)慣性地稱(chēng)之為解析樹(shù)。

Langium 在這方面有顯著優(yōu)勢(shì)，它能自動(dòng)完成大部分鏈接工作。這個(gè)工具遵循解析節(jié)點(diǎn)的嵌套層次，利用這一結(jié)構(gòu)構(gòu)建“作用域”。它解析遇到的名稱(chēng)，并將它們鏈接到正確的目標(biāo)節(jié)點(diǎn)。在語(yǔ)言較為復(fù)雜的場(chǎng)景中，可能會(huì)遇到需要特別處理的情況。Langium 允許用戶(hù)自定義實(shí)現(xiàn)幾個(gè)服務(wù)，從而簡(jiǎn)化這個(gè)過(guò)程，讓鏈接操作更加高效。

第 3 步：從鏈接樹(shù)到語(yǔ)義正確性檢查

如果源文件包含詞法或解析錯(cuò)誤，編譯器會(huì)報(bào)錯(cuò)并終止處理。

例如：

model {
  id
  title String
}

編譯器可能會(huì)報(bào)如下錯(cuò)誤：

期望的是 'ID' 類(lèi)型的標(biāo)記，但實(shí)際發(fā)現(xiàn) `{`。[第1行，第7列]

但是，代碼即使沒(méi)有詞法或解析錯(cuò)誤，也不一定在語(yǔ)義上正確。以以下代碼為例，它在語(yǔ)法上是有效的，但在語(yǔ)義上卻是錯(cuò)誤的。原因是將 title 與 true 進(jìn)行比較是無(wú)意義的操作。

model Post {
  id Int
  title String
  author User
  published Boolean

  @@allow('read', title == true) // <- 這類(lèi)比較應(yīng)當(dāng)是無(wú)效的
}

語(yǔ)義規(guī)則通常是特定于語(yǔ)言的，并且工具很難自動(dòng)處理這些規(guī)則。Langium 解決這個(gè)問(wèn)題的方法是，為不同節(jié)點(diǎn)類(lèi)型提供驗(yàn)證鉤子。

例如：

export function registerValidationChecks(services: ZModelServices) {
    const registry = services.validation.ValidationRegistry;
    const validator = services.validation.ZModelValidator;
    const checks: ValidationChecks<ZModelAstType> = {
        SimpleExpression: validator.checkExpression,
    };
    registry.register(checks, validator);
}

export class ZModelValidator {
    checkExpression(expr: SimpleExpression, accept: ValidationAcceptor): void {
        if (isFieldReference(expr) && expr.target.ref?.type !== 'Boolean') {
            accept('error', '條件中只允許使用布爾字段', {
                node: expr,
            });
        }
    }
}

現(xiàn)在，我們可以針對(duì)語(yǔ)義問(wèn)題，得到更準(zhǔn)確的錯(cuò)誤提示：

條件中只允許使用布爾字段 [第7行，第19列]

與詞法分析、解析和鏈接過(guò)程不同，語(yǔ)義檢查通常不是非常聲明式或系統(tǒng)化的。對(duì)于復(fù)雜的語(yǔ)言，你可能需要編寫(xiě)許多命令式代碼規(guī)則。

圖片引用自《特征工程的方法和原理》

第 4 步：優(yōu)化開(kāi)發(fā)者體驗(yàn)

在當(dāng)今軟件開(kāi)發(fā)領(lǐng)域，為開(kāi)發(fā)者提供優(yōu)秀的工具體驗(yàn)非常重要。一個(gè)成功的開(kāi)發(fā)工具不僅要運(yùn)行良好，還要提供出色的用戶(hù)體驗(yàn)。在語(yǔ)言和編譯器開(kāi)發(fā)中，關(guān)注開(kāi)發(fā)者體驗(yàn)（DX）主要涉及以下幾個(gè)方面：

IDE 支持

優(yōu)秀的集成開(kāi)發(fā)環(huán)境（IDE）支持，如語(yǔ)法高亮、代碼格式化、自動(dòng)補(bǔ)全等，可以顯著降低學(xué)習(xí)曲線，提高開(kāi)發(fā)者的工作效率。Langium 的一個(gè)重要優(yōu)勢(shì)是支持 Language Server Protocol（語(yǔ)言服務(wù)器協(xié)議）。這意味著你的解析規(guī)則和驗(yàn)證檢查可以自動(dòng)轉(zhuǎn)換為一個(gè)基礎(chǔ)的 LSP 實(shí)現(xiàn)，兼容 Visual Studio Code 和最新的JetBrains IDEs（有限制）。但要提供卓越的 IDE 體驗(yàn)，你還需擴(kuò)展 Langium 默認(rèn)的 LSP 相關(guān)服務(wù)，進(jìn)行深度優(yōu)化。

錯(cuò)誤報(bào)告

你的驗(yàn)證邏輯會(huì)在多種情況下生成錯(cuò)誤消息。這些消息的準(zhǔn)確性和實(shí)用性極大地影響了開(kāi)發(fā)者理解和修復(fù)錯(cuò)誤的速度。

調(diào)試

如果你的語(yǔ)言支持“執(zhí)行”（這一點(diǎn)我們將在下一節(jié)詳細(xì)討論），提供調(diào)試工具就非常重要。調(diào)試的具體內(nèi)容取決于語(yǔ)言特性。對(duì)于包含語(yǔ)句和控制流的命令式語(yǔ)言，可能需要支持步進(jìn)調(diào)試和狀態(tài)檢查。而對(duì)于聲明式語(yǔ)言，調(diào)試可能意味著提供可視化工具，幫助理解復(fù)雜結(jié)構(gòu)，如規(guī)則和表達(dá)式等。

第 5 步：發(fā)揮實(shí)際應(yīng)用價(jià)值

解析出一個(gè)無(wú)錯(cuò)誤的解析樹(shù)是非常有趣的，但這本身并不足以產(chǎn)生實(shí)際應(yīng)用價(jià)值。從這一步開(kāi)始，你有幾個(gè)選項(xiàng)來(lái)生成實(shí)際的應(yīng)用價(jià)值：

1.就此停止

你可以選擇在此階段停止，將解析樹(shù)作為最終成果，并讓用戶(hù)決定如何使用它。

2.轉(zhuǎn)換成其他語(yǔ)言

通常一種語(yǔ)言會(huì)有一個(gè)“后端”來(lái)將解析樹(shù)轉(zhuǎn)換成更低級(jí)的語(yǔ)言。舉個(gè)例子，Java 編譯器的后端生成 JVM 字節(jié)碼，TypeScript 的后端生成 JavaScript 代碼。在 ZenStack 中，我們將 ZModel 轉(zhuǎn)換成 Prisma Schema Language，并由目標(biāo)語(yǔ)言的工具或運(yùn)行時(shí)進(jìn)行處理。

3.實(shí)現(xiàn)可插拔的轉(zhuǎn)換機(jī)制

另一種選擇是實(shí)現(xiàn)一個(gè)插件機(jī)制。使用這樣語(yǔ)言的用戶(hù)就可以提供他們自己的后端轉(zhuǎn)換。與僅提供解析樹(shù)相比，這是一種更有結(jié)構(gòu)的方法。

4.構(gòu)建一個(gè)執(zhí)行解析樹(shù)的運(yùn)行時(shí)

這可能是構(gòu)建語(yǔ)言的最全面方法。你可以實(shí)現(xiàn)一個(gè)解釋器來(lái)“運(yùn)行”解析后的代碼。具體的“運(yùn)行”意義取決于你的定義。在 ZenStack 中，我們不僅將 ZModel 轉(zhuǎn)換成 Prisma Schema Language，還實(shí)現(xiàn)了一個(gè)運(yùn)行時(shí)。這個(gè)運(yùn)行時(shí)解釋和執(zhí)行訪問(wèn)控制規(guī)則，在數(shù)據(jù)訪問(wèn)期間生效。

第 6 步：推廣使用

恭喜你！你已經(jīng)完成了創(chuàng)建新語(yǔ)言工作的20%。就像大多數(shù)創(chuàng)新一樣，最具挑戰(zhàn)性的部分通常是推廣它——即使它是免費(fèi)的。如果這種語(yǔ)言?xún)H供你自己或團(tuán)隊(duì)內(nèi)部使用，那不如不做。但如果你的語(yǔ)言面向公眾，那么你需要投入大量努力進(jìn)行市場(chǎng)推廣。這通常占據(jù)了剩余的 80% 工作量??。

最后的思考

考慮到軟件工程在過(guò)去幾十年的迅速發(fā)展，編譯器構(gòu)建似乎成為了一門(mén)古老的藝術(shù)。然而，我認(rèn)為這是每個(gè)認(rèn)真的開(kāi)發(fā)者都應(yīng)該嘗試的事情。它能帶來(lái)獨(dú)特的經(jīng)驗(yàn)，并很好地反映了編程的二元性——美學(xué)與實(shí)用主義的結(jié)合。一個(gè)優(yōu)秀的軟件系統(tǒng)通常基于一個(gè)優(yōu)雅的概念模型，但在其表面之下，你會(huì)發(fā)現(xiàn)許多實(shí)際操作中的不太完美之處。

你應(yīng)該嘗試構(gòu)建一種語(yǔ)言，這是一個(gè)值得挑戰(zhàn)的有趣項(xiàng)目。