概述

MLIR Toy Tutorial 的目标是通过构建一门编程语言编译器的完整过程（包括前端和后端技术），教授如何使用 MLIR 的各个组件来实现语言的解析、转换和代码生成等功能。出于演示和教学目的，教程引入了一门简单的编程语言 -- Toy。

Chapter1 介绍了如何对 Toy 语言进行词法分析和语法分析，将 Toy 语言的源文件解析成抽象语法树（AST）。
源码：https://github.com/llvm/llvm-project/tree/main/mlir/examples/toy/Ch1

词法分析（Lexical Analysis）

通常来说，词法分析是编译器开始的第一项工作。编译器读代码和我们读文章的流程是类似的，文章是由一个个词组成的，代码则是由一个个 token 组成，编译器需要先把源码中的 token 识别出来。

token 不等同于英文单词，通过空格来生成，它通常通过正则文法规则来识别。比如，def func(){}，这里的 func(){} 中间没有空格，编译器需要识别出标识符（函数名）是 func 而不是 func(){}。

Ch1 为 Toy 语言实现了一个词法分析器模块，Lexer，它定义了 Toy 语言支持的 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 是很少的，除了各种括号、4个命令（关键字）和数字之外，其他的统统识别成标识符（tok_identifier）。

以一个简单的例子为例：

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

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

Lexer 可以识别出 token：

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

语法分析（Parsing）

编译器下一个阶段的工作是语法分析。词法分析是从文本中识别出一个个单词，而语法分析则是在这基础上识别出这些单词的语法结构。语法结构是由语法规则决定的。Toy 语言的语法分析器模块，Parser，定义的语法规则如下：

• 程序（module）由函数（function）组成
• function 由 prototype 和 block（{}中的内容）组成
• prototype 由函数名和参数列表组成
• block 由表达式列表组成
• ......

按照这些语法规则，源程序就可以自上而下地拆分成多个模块，每个模块又可以根据规则拆分子模块，这样我们就可以用一棵树来表示源程序，树的节点就是这些模块，而这棵树称为抽象语法树，AST。

Parser 为上述语法规则提供了 parseModule()、parseDefinition()、parsePrototype() 和 parseBlock() 等方法来生成相应的树节点 -- 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();
        ......
      }
      ......
    }
  }

我们以构建 function 节点为例来看一下 AST 的生成过程。function 是由 prototype 和 block 这两个节点组成的：definition ::= prototype block，因此，parseDefinition() 它会调用 parsePrototype() 和 parseBlock()来生成 prototype 和 block 节点。

我们重点看 block，block ::= { expression_list }，只有当 {} 中的内容识别出是表达式列表的时候，它才是一个正确的block，而 expression_list 则会被构造成 block 节点 -- ExprASTList 并返回给 parseDefinition() 用于构造 function 节点 -- FunctionAST。

而 ExprASTList 构造的前提是 expression_list ::= block_expr ; expression_list，即一组数量>=1并以 ; 分隔的 block_expr。

而 block_expr 又可以表示为三种节点，block_expr ::= decl | "return" | expr，它们以 token 来区分，例如 var a = 1;，它会调用 parseDeclaration() 来创建变量节点。

从上述例子的看到，AST 的构造过程是先根据语法规则向下匹配子节点，直至叶子结点，再向上回朔，这种算法也称为递归下降算法。

为什么要生成AST

对于机器来说，自然语言无法执行，但树结构可以。在 Chapter2，MLIR 会执行 Chapter1 生成的 AST，将 ASTNode 翻译成 MLIR IR，用于后续的编译。

总结

MLIR Toy Tutorial 是一个通过构建编程语言编译器的完整过程，教授如何使用 MLIR 的教程。教程引入了一门简单的编程语言 Toy，并通过词法分析 (Lexer) 和语法分析 (Parser) 模块将 Toy 语言的源文件解析成抽象语法树（AST）。词法分析器模块定义了 Toy 语言支持的 token，而语法分析器模块定义了语法规则，并生成相应的 AST 节点。AST 的生成过程是通过递归下降算法实现的。生成的 AST 可以被执行，将 ASTNode 翻译成 MLIR IR，用于后续的编译过程。

END