likes
comments
collection
share

用一道 Leetcode 水题迈入编译器的殿堂

作者站长头像
站长
· 阅读数 37

恐怕大部分程序员都会感到编译器神秘莫测，而且只能由技艺超群的大师创建。没有多少人会直接打开编辑器说：“来吧，我要构建一个编译器！”。的确，编译器往往非常庞大，例如，GNU 编译器 GCC 项目的代码量高达 1500 万行。

但本文偏要为一道 Leetcode 水题编写一个微型编译器。

别看又是“微型”，又是“水题”，似乎接下来的内容一点也不实用，而且通过自制编译器来解答简单的 Leetcode 题目难道不是花拳绣腿、多此一举吗？

但是，实现哪怕一个很小的编译器都能帮助我们理解编译原理相关的知识和方法，而这些知识和方法是掌握更加复杂的编译器的基础。

所以，“来吧，我要写一个编译器！”。

为什么选择 Leetcode 657 这道水题呢

“Leetcode 657. 机器人能否返回原点”（leetcode.cn/problems/ro… (0, 0)上，给它一串向上、下、左、右走一步的移动指令，问机器人按照指令移动后最终能否回到原点。

用一道 Leetcode 水题迈入编译器的殿堂

之所以要为这么一道题编写编译器，是因为这题刚好与编译原理经典教材“龙书”中的一个示例（中文版第 1 版 P23，例 2.7）相似，只不过书中是问机器人的最终位置。借助此题，我们可以将”龙书“中的理论转换成可执行的代码，再利用 Leetcode 网站上丰富的测试用例检查代码的正确性（避免装逼失败），以此来加深对理论的理解。

“龙书”即《编译原理》（Compilers: Principles, Techniques, and Tools），因封面上的龙而得名“龙书”，是编译器设计和实现领域的经典参考书籍，深受学术界和工业界的欢迎和推崇。

这题和编译器之间有什么关系

“编译器”的定义其实非常宽泛。像 gcc、javac 或 go 等将特定编程语言转换成可执行文件的程序当然是编译器，但其实编译器就是翻译器，本质上只是完成了或多或少、可能很简单也可能异常复杂的转换工作。甚至可以认为，能进行某种转换的程序就是编译器。

对于 Leetcode 657 这道题，我们要实现的微型编译器也是实现转换——只需将移动指令的序列转换为机器人的位置，即 x, y := compile(instructions)。之后再判断 (x, y) == (0, 0) 即可解答这道题。

尽管这么看来编译器似乎可大可小、形态各异，但构成编译器（确切说是编译器前端）的模块却是相对固定的。在将输入的字符串（某种编程语言的代码或本例中的移动指令序列）转换成某种形式的输出（可执行文件或坐标）的过程中，需要依次经过词法分析器和语法分析器的处理。

词法分析器（lexer，也叫作 lexical analyzer 或 scanner）的主要任务是将输入的字符串转换成一系列的词法单元（token，也叫作符号或记号）。编程语言中的关键字、标识符、常量和操作符等都是词法单元。语法分析器（parser）的任务是为词法分析器生成的词法单元构建语法树。

在 Leetcode 657 这道题中，每一个表示移动指令的字符都是一个词法单元。虽然直接根据移动指令更新表示横纵坐标的 2 个变量即可解答这道题，但为了体验自制编译器的“乐趣”，我们还是要构建出一棵语法树，并从这棵树中分析出机器人的最终位置。

如何描述移动指令序列的语法

该如何描述移动指令序列的语法呢？也就是如何描述指令序列长什么样呢？

根据 Leetcode 657 的题目描述：移动指令序列由字符串 moves 表示，字符 move[i] 表示机器人第 i 次移动。有效的指令 4 种： R（右），L（左），U（上）和 D（下）。

那不难想到，可以用正则表达式 [RLUD]* 描述这个指令序列。不过，在编译原理中，通常使用产生式（production）或范式（normal form）方式来描述语法（确切说是context-free grammar，上下文无关文法）。例如，指令序列的产生式如下所示，

seq   -> seq instr | '^'
instr -> 'R' | 'L' | 'U' | 'D'

这 2 个产生式可以这样解读：

  • 指令序列 seq （sequence 的缩写）可以由另一个序列后面跟一个指令 instr（instruction 的缩写）构成，也可以（暂时）是空序列，特殊字符 ^表示序列的开始
  • 指令 instr 可以是 'R'（右）、'L'（左）、'U'（上）或 'D'（下）

乍看之下，这种描述方法似乎没有正则表达式直观，而且seq -> seq instr还是递归的写法，不太好理解。下面就结合一个具体的指令序列 ^LD 来看一看如何解读这两个产生式。

我们先试着用产生式 -> 右侧的部分替换左侧的符号（就像在代数中把算式或数值代入变量那样），从 seq 开始

seq             （将 seq instr 代入 seq）
seq instr       （再次将 seq instr 代入 seq）
seq instr instr （得到 2 个 instr 了，将 'D' 带入最后一个 instr）
seq instr D     （将 'L' 带入 instr）
seq L D         （将 '^' 带入 seq）
^ L D

经过逐步替换我们得到了指令序列 ^LD。其实还可以反过来替换（术语是归约），即用产生式 -> 左侧的部分替换右侧的符号，

^ L D           （将 ^ 归约为 seq）
seq L D         （将 'L' 归约为 instr）
seq instr D     （将 seq instr 归约为 seq）
seq D           （将 'D' 归约为 instr）
seq instr       （再次将 seq instr 归约为 seq）
seq

这样就又由一个具体的指令序列归约回了符号 seq，而这个过程正是构建语法树的过程！

用一道 Leetcode 水题迈入编译器的殿堂

从最左侧的叶子节点 '^'开始，按照“兄弟节点——父节点——父节点的兄弟节点——父节点的父节点”的顺序（反向的 Z 字形）“看”上去，就能到达树根 seq节点，即产生式的开始符号。而反过来，从树根一路向下，从左到右的所有叶子节点就组成了一个具体的指令序列 ^LD。

这棵语法树有什么用呢

得到了这么一棵树又有什么用呢，别忘了我们最终的目标可是要做个编译器出来，将指令序列转换为坐标，即compile("^LD") == (-1, -1)。

其实语法树有两个特性有助于我们实现编译器。第一个特性是每个节点都可以具有若干属性，第二个特性是这些属性是可以参与计算的。

我们先把每个节点的属性标记出来。对于 seq 类节点，它们的属性是表示机器人当前的坐标 x 和 y ；而对于 instr 类节点，它们的属性是 dx 和 dy，分表表示在 x 和 y 坐标上的变化量。

用一道 Leetcode 水题迈入编译器的殿堂

如图所示，标记出属性后我们就可以跟踪机器人的位置了，特别是根节点的 x 和 y 就是机器人的最终位置。那每个 seq 类节点上的 x 和 y 又是怎么计算出来的呢？通过观察不难发现如下规律：

seq.x = left_child_seq.x + right_child_instr.dx
seq.y = left_child_seq.y + right_child_instr.dy

即是由左右子节点的（对应的）属性相加得到的。

好了，理论方面的知识就先介绍到这里，下面就赶快用 Go 语言来实现这个微型编译器吧。

用 Go 语言实现微型编译器

通过前面的讲解，我们知道编译器（编译器前端）由词法分析器和语法分析器构成：

  • 词法分析器

    • 输入：字符串（在 Leetcode 657 这道题中是指令序列）
    • 输出：词法单元的列表，即表示指令的一系列字符

  • 语法分析器

    • 输入：表示指令的一系列字符
    • 输出：带属性的语法树

因此代码中需要定义与它们对应的结构。另外，还需要定义表示语法树中节点的数据类型。

我们先来实现词法分析器（由于篇幅有限，这里仅列出代码片段，完整的代码可参考 go.dev/play/p/-U7O…

type Lexer struct {
  input string
  pos   int
}

func (lexer *Lexer) Next() (byte, bool) {

这里定义了一个词法分析器（Lexer）结构体，并实现 Next() 方法来读取下一个词法单元。该方法返回的布尔值表示是否读完了所有指令。

接下来定义语法树的结构。你有没有注意到 seq -> seq instr 对应的语法树中，右侧的子节点总是 instr 类的节点呢？

// SeqNode 表示指令序列节点
type SeqNode struct {
  x     int        // 当前位置的 x 坐标
  y     int        // 当前位置的 y 坐标
  left  *SeqNode   // 左子节点，指向另一个指令序列节点 `SeqNode`
  right *InstrNode // 右子节点，指向一个指令节点 `InstrNode`
}

// InstrNode 表示指令节点
type InstrNode struct {
  dx int // x 方向上的增量
  dy int // y 方向上的增量
}

然后就该轮到编译器的重头戏，能够生成语法树的语法分析器了。

func parse(input string) *SeqNode {
  lexer := &Lexer{input: input}
  instrNodeMap := map[byte]*InstrNode{
    'U': &InstrNode{dx: 0, dy: 1},
    'D': &InstrNode{dx: 0, dy: -1},
    'L': &InstrNode{dx: -1, dy: 0},
    'R': &InstrNode{dx: 1, dy: 0},
  }
  seqNode := &SeqNode{
    x: 0,
    y: 0,
  }

  for {
    token, found := lexer.Next()
    if !found {
      break
    }
    instrNode := instrNodeMap[token]
    parent := &SeqNode{
      x:     seqNode.x + instrNode.dx,
      y:     seqNode.y + instrNode.dy,
      left:  seqNode,
      right: instrNode,
    }
    seqNode = parent
  }

  return seqNode
}

parse() 函数负责语法解析，流程如下：

  1. 创建词法分析器 Lexer 的实例来获取词法单元（token）的列表
  2. 定义一个 Map，将指令（'U', 'D', 'L', 'R'）映射到相应的 InstrNode 的实例（对象）
  3. 初始化一个 SeqNode，表示起始位置 (0, 0)。
  4. 循环读取指令序列，为每条指令构造新的 SeqNode 节点，作为当前 SeqNode 节点和 InstrNode 节点的父节点，并更新当前位置（新 SeqNode 节点的 x 属性和 y属性）
  5. 将新创建的 SeqNode 作为当前节点
  6. 反复步骤 4 和 步骤 5，直到词法分析器的 Next() 方法返回 false

不算太难吧，那我们来测试一下，

func main() {
	rootNode := parse("LD")
	fmt.Printf("Current Position: (%d, %d)\n", rootNode.x, rootNode.y)
	// Current Position: (-1, -1)
}

大功告成！根节点的 x 属性和 y属性就是机器人的当前坐标。提交到 Leetcode 上看一看，虽然完全正确，但排名垫底了。别看垫底了，但咱有成就感，我可是实现了一个编译器啊！

用一道 Leetcode 水题迈入编译器的殿堂

编译过程可以很复杂，如将一门新语言转化为可执行的程序，也可以很简单，如仅仅改变输入字符串的格式，或者像本文这样将移动指令序列转换为坐标。

我打开了编辑器，实现了一个编译器。现在是不是很有成就感呢，多少也算知道编译器的宫殿什么样了。

胡译胡说 软件工程师、技术图书译者。译有《图解云计算架构》《图解量子计算机》《图解TCP/IP（第6版）》《计算机是怎样跑起来的》《自制搜索引擎》等。

附 微型编译器的代码

package main

import "fmt"

type Lexer struct {
	input string
	pos   int
}

func (lexer *Lexer) Next() (byte, bool) {
	if lexer.pos == len(lexer.input) {
		return 0, false
	}

	next := lexer.input[lexer.pos]
	lexer.pos++
	return next, true
}

// SeqNode 表示指令序列节点
type SeqNode struct {
	x     int        // 当前位置的 x 坐标
	y     int        // 当前位置的 y 坐标
	left  *SeqNode   // 左子节点，指向另一个指令序列节点
	right *InstrNode // 右子节点，指向一个指令节点
}

// InstrNode 表示指令节点
type InstrNode struct {
	dx int // x 方向上的增量
	dy int // y 方向上的增量
}

func parse(input string) *SeqNode {
	lexer := &Lexer{input: input}
	instrNodeMap := map[byte]*InstrNode{
		'U': &InstrNode{dx: 0, dy: 1},
		'D': &InstrNode{dx: 0, dy: -1},
		'L': &InstrNode{dx: -1, dy: 0},
		'R': &InstrNode{dx: 1, dy: 0},
	}
	seqNode := &SeqNode{
		x: 0,
		y: 0,
	}

	for {
		token, found := lexer.Next()
		if !found {
			break
		}
		instrNode := instrNodeMap[token]
		parent := &SeqNode{
			x:     seqNode.x + instrNode.dx,
			y:     seqNode.y + instrNode.dy,
			left:  seqNode,
			right: instrNode,
		}
		seqNode = parent
	}

	return seqNode
}

func judgeCircle(moves string) bool {
	rootNode := parse(moves)
	return rootNode.x == 0 && rootNode.y == 0
}

func main() {
	rootNode := parse("LD")
	fmt.Printf("Current Position: (%d, %d)\n", rootNode.x, rootNode.y)
	// Current Position: (-1, -1)
}
转载自:https://juejin.cn/post/7382537293582762010
评论
请登录