概述

MLIR Toy Tutorial 的目標(biāo)是通過(guò)構(gòu)建一門編程語(yǔ)言編譯器的完整過(guò)程（包括前端和后端技術(shù)），教授如何使用 MLIR 的各個(gè)組件來(lái)實(shí)現(xiàn)語(yǔ)言的解析、轉(zhuǎn)換和代碼生成等功能。出于演示和教學(xué)目的，教程引入了一門簡(jiǎn)單的編程語(yǔ)言 -- Toy。

Chapter1 介紹了如何對(duì) Toy 語(yǔ)言進(jìn)行詞法分析和語(yǔ)法分析，將 Toy 語(yǔ)言的源文件解析成抽象語(yǔ)法樹(shù)（AST）。
源碼：https://github.com/llvm/llvm-project/tree/main/mlir/examples/toy/Ch1

詞法分析（Lexical Analysis）

通常來(lái)說(shuō)，詞法分析是編譯器開(kāi)始的第一項(xiàng)工作。編譯器讀代碼和我們讀文章的流程是類似的，文章是由一個(gè)個(gè)詞組成的，代碼則是由一個(gè)個(gè) token 組成，編譯器需要先把源碼中的 token 識(shí)別出來(lái)。

token 不等同于英文單詞，通過(guò)空格來(lái)生成，它通常通過(guò)正則文法規(guī)則來(lái)識(shí)別。比如，def func(){}，這里的 func(){} 中間沒(méi)有空格，編譯器需要識(shí)別出標(biāo)識(shí)符（函數(shù)名）是 func 而不是 func(){}。

Ch1 為 Toy 語(yǔ)言實(shí)現(xiàn)了一個(gè)詞法分析器模塊，Lexer，它定義了 Toy 語(yǔ)言支持的 token：

// List of Token returned by the lexer.
enum Token : int {
  tok_semicolon = ';',
  tok_parenthese_open = '(',
  tok_parenthese_close = ')',
  tok_bracket_open = '{',
  tok_bracket_close = '}',
  tok_sbracket_open = '[',
  tok_sbracket_close = ']',

  tok_eof = -1,

  // commands
  tok_return = -2,
  tok_var = -3,
  tok_def = -4,
  tok_struct = -5,

  // primary
  tok_identifier = -6,
  tok_number = -7,
};

可以看到它支持的 token 是很少的，除了各種括號(hào)、4個(gè)命令（關(guān)鍵字）和數(shù)字之外，其他的統(tǒng)統(tǒng)識(shí)別成標(biāo)識(shí)符（tok_identifier）。

以一個(gè)簡(jiǎn)單的例子為例：

def func(var a, var b) {
  return a + b;
}

def main() {
  var a = 1;
  var b = 2;
  print(func(a, b));
}

Lexer 可以識(shí)別出 token：

tok_def: "main", "func"
tok_var: "a", "b"
tok_identifier: "+", "print"
tok_number: "1", "2"
tok_bracket_open: "{", "{"
......

語(yǔ)法分析（Parsing）

編譯器下一個(gè)階段的工作是語(yǔ)法分析。詞法分析是從文本中識(shí)別出一個(gè)個(gè)單詞，而語(yǔ)法分析則是在這基礎(chǔ)上識(shí)別出這些單詞的語(yǔ)法結(jié)構(gòu)。語(yǔ)法結(jié)構(gòu)是由語(yǔ)法規(guī)則決定的。Toy 語(yǔ)言的語(yǔ)法分析器模塊，Parser，定義的語(yǔ)法規(guī)則如下：

• 程序（module）由函數(shù)（function）組成
• function 由 prototype 和 block（{}中的內(nèi)容）組成
• prototype 由函數(shù)名和參數(shù)列表組成
• block 由表達(dá)式列表組成
• ......

按照這些語(yǔ)法規(guī)則，源程序就可以自上而下地拆分成多個(gè)模塊，每個(gè)模塊又可以根據(jù)規(guī)則拆分子模塊，這樣我們就可以用一棵樹(shù)來(lái)表示源程序，樹(shù)的節(jié)點(diǎn)就是這些模塊，而這棵樹(shù)稱為抽象語(yǔ)法樹(shù)，AST。

Parser 為上述語(yǔ)法規(guī)則提供了 parseModule()、parseDefinition()、parsePrototype() 和 parseBlock() 等方法來(lái)生成相應(yīng)的樹(shù)節(jié)點(diǎn) -- ASTNode。

  /// Parse a function definition, we expect a prototype initiated with the
  /// `def` keyword, followed by a block containing a list of expressions.
  ///
  /// definition ::= prototype block
  std::unique_ptr<FunctionAST> parseDefinition() {
    ......
  }

  /// Parse a block: a list of expression separated by semicolons and wrapped in
  /// curly braces.
  ///
  /// block ::= { expression_list }
  /// expression_list ::= block_expr ; expression_list
  /// block_expr ::= decl | "return" | expr
  std::unique_ptr<ExprASTList> parseBlock() {
    ......
    while (lexer.getCurToken() != '}' && lexer.getCurToken() != tok_eof) {
      if (lexer.getCurToken() == tok_var) {
        // Variable declaration
        auto varDecl = parseDeclaration();
        ......
      } else if (lexer.getCurToken() == tok_return) {
        // Return statement
        auto ret = parseReturn();
        ......
      } else {
        // General expression
        auto expr = parseExpression();
        ......
      }
      ......
    }
  }

我們以構(gòu)建 function 節(jié)點(diǎn)為例來(lái)看一下 AST 的生成過(guò)程。function 是由 prototype 和 block 這兩個(gè)節(jié)點(diǎn)組成的：definition ::= prototype block，因此，parseDefinition() 它會(huì)調(diào)用 parsePrototype() 和 parseBlock()來(lái)生成 prototype 和 block 節(jié)點(diǎn)。

我們重點(diǎn)看 block，block ::= { expression_list }，只有當(dāng) {} 中的內(nèi)容識(shí)別出是表達(dá)式列表的時(shí)候，它才是一個(gè)正確的block，而 expression_list 則會(huì)被構(gòu)造成 block 節(jié)點(diǎn) -- ExprASTList 并返回給 parseDefinition() 用于構(gòu)造 function 節(jié)點(diǎn) -- FunctionAST。

而 ExprASTList 構(gòu)造的前提是 expression_list ::= block_expr ; expression_list，即一組數(shù)量>=1并以 ; 分隔的 block_expr。

而 block_expr 又可以表示為三種節(jié)點(diǎn)，block_expr ::= decl | "return" | expr，它們以 token 來(lái)區(qū)分，例如 var a = 1;，它會(huì)調(diào)用 parseDeclaration() 來(lái)創(chuàng)建變量節(jié)點(diǎn)。

從上述例子的看到，AST 的構(gòu)造過(guò)程是先根據(jù)語(yǔ)法規(guī)則向下匹配子節(jié)點(diǎn)，直至葉子結(jié)點(diǎn)，再向上回朔，這種算法也稱為遞歸下降算法。

為什么要生成AST

對(duì)于機(jī)器來(lái)說(shuō)，自然語(yǔ)言無(wú)法執(zhí)行，但樹(shù)結(jié)構(gòu)可以。在 Chapter2，MLIR 會(huì)執(zhí)行 Chapter1 生成的 AST，將 ASTNode 翻譯成 MLIR IR，用于后續(xù)的編譯。

總結(jié)

MLIR Toy Tutorial 是一個(gè)通過(guò)構(gòu)建編程語(yǔ)言編譯器的完整過(guò)程，教授如何使用 MLIR 的教程。教程引入了一門簡(jiǎn)單的編程語(yǔ)言 Toy，并通過(guò)詞法分析 (Lexer) 和語(yǔ)法分析 (Parser) 模塊將 Toy 語(yǔ)言的源文件解析成抽象語(yǔ)法樹(shù)（AST）。詞法分析器模塊定義了 Toy 語(yǔ)言支持的 token，而語(yǔ)法分析器模塊定義了語(yǔ)法規(guī)則，并生成相應(yīng)的 AST 節(jié)點(diǎn)。AST 的生成過(guò)程是通過(guò)遞歸下降算法實(shí)現(xiàn)的。生成的 AST 可以被執(zhí)行，將 ASTNode 翻譯成 MLIR IR，用于后續(xù)的編譯過(guò)程。

END