Rust 开发编译器速成（一）：计算解释器
在本系列的第一篇文章中，我们将学习如何使用 Rust 编写一个简单的计算解释器。本文的目标是让你理解如何使用 Pest 的 PEG 文法解析器生成器处理字符串。这个过程主要涉及到编译的前端，但基本只是调包，不需要太多的编译原理知识。
目标
我们会实现一个解释器，它能够解释如下的语句：
11 + 2;print(mem);
输出: 3
环境准备
首先，我们需要创建一个新的 Rust 项目。打开终端，输入以下命令：
1$ cargo new calc-comp
2 Created binary (application) `calc-comp` package
3$ code calc-comp
这样就能创建一个名为 calc-comp 的新项目，并用 Visual Studio Code 打开。
同时，编辑 Cargo.toml 安装如下依赖：
1[dependencies]
2lazy_static = "1.4.0"
3pest = "2.5.5"
4pest_derive = "2.5.5"
-
lazy_static用于定义静态模块全局变量。 -
pest是一个 PEG 文法解析器生成器。 -
pest_derive是pest的派生宏。
设计语法规则
在 src 目录下创建一个名为 calc.pest 的文件，该文件定义了语法规则。我们将使用一个名为 pest 的 Rust 库来定义语法规则。Pest 可以帮助我们将语法规则表达为一个简单易读的代码。
grammar = { trans_unit ~ EOI }
trans_unit = { block }
block = { stmt* }
stmt = { expr_stmt | print_stmt }
expr_stmt = { expr ~ ";" }
print_stmt = { "print" ~ expr ~ ";" }
expr = { prefix_op* ~ primary_expr ~ postfix_op* ~ (infix_op ~ prefix_op* ~ primary_expr ~ postfix_op* )* }
prefix_op = { "+" | "-" }
postfix_op = { "not_implemented" }
infix_op = _{ mul_op | add_op }
mul_op = { "*" | "/" }
add_op = { "+" | "-" }
primary_expr = { MEM | INT | "(" ~ expr ~ ")" }
INT = { ASCII_DIGIT+ }
MEM = { "mem" }
在这个文件中，我们使用了一种叫做 PEG 的语法来定义语法规则。其中，trans_unit 表示翻译单元，由一个 block 组成。block 由一系列语句（stmt）组成，每个语句以分号结束。
现在我们定义了一些基本的语法规则，如变量名 MEM 和整数 INT。我们还定义了一些操作符，包括前缀操作符 prefix_op，后缀操作符 postfix_op 和中缀操作符 infix_op。我们还定义了一些操作数，如变量 MEM 和整数 INT，以及括号中的表达式 primary_expr。
编写抽象语法树
现在我们需要定义一个抽象语法树（AST），用于在语法解析器中存储和操作解析结果。在 src 目录下创建一个名为 ast.rs 的新文件，该文件定义了 AST。我们将使用一个简单的树状结构来表示语法。在 ast.rs 中添加以下代码：
1pub struct TransUnit {
2 pub block: Block,
3}
4
5pub struct Block {
6 pub stmts: Vec<Stmt>,
7}
8
9pub enum Stmt {
10 ExprStmt(Expr),
11 PrintStmt(Expr),
12}
13pub enum Expr {
14 Primary(Box<PrimaryExpr>),
15 Prefix(Box<PrefixExpr>),
16 Infix(Box<InfixExpr>),
17}
18
19pub struct PrefixExpr {
20 pub op: PrefixOp,
21 pub expr: Box<Expr>,
22}
23
24pub struct InfixExpr {
25 pub lhs: Box<Expr>,
26 pub op: InfixOp,
27 pub rhs: Box<Expr>,
28}
29
30pub enum PrefixOp {
31 Plus,
32 Minus,
33}
34
35pub enum InfixOp {
36 Plus,
37 Minus,
38 Multiply,
39 Divide,
40}
41
42pub enum PrimaryExpr {
43 Mem,
44 Int(i64),
45 Expr(Box<Expr>),
46}
编写解释器
现在，我们需要一个解释器来执行代码。在 src 目录下创建一个名为 interpreter.rs 的新文件，该文件定义了解释器。我们将实现一个简单的计算解释器，该解释器可以解析和执行语句。
1use crate::ast::*;
2struct Env {
3 mem: i64,
4}
5
6impl Env {
7 fn new() -> Self {
8 Self {
9 mem: 0,
10 }
11 }
12
13 fn get_mem(&self) -> i64 {
14 self.mem
15 }
16
17 fn set_mem(&mut self, val: i64) {
18 self.mem = val;
19 }
20}
21
22pub fn interpret(tu: &TransUnit) {
23 let mut env = Env::new();
24 for stmt in &tu.block.stmts {
25 match stmt {
26 Stmt::ExprStmt(expr) => {
27 let ret = eval_expr(&mut env, expr);
28 env.set_mem(ret);
29 },
30 Stmt::PrintStmt(expr) => {
31 println!("{}", eval_expr(&mut env, expr));
32 }
33 }
34 }
35}
36
37fn eval_expr(env: &mut Env, expr: &Expr) -> i64 {
38 match expr {
39 Expr::Primary(e)=> eval_primary(env, e),
40 Expr::Prefix(e)=> eval_prefix(env, e),
41 Expr::Infix(e)=> eval_infix(env, e),
42 }
43}
44
45fn eval_primary(env: &mut Env, expr: &PrimaryExpr) -> i64 {
46 match expr {
47 PrimaryExpr::Mem => env.get_mem(),
48 PrimaryExpr::Int(i) => *i,
49 PrimaryExpr::Expr(e) => eval_expr(env, e),
50 }
51}
52
53fn eval_prefix(env: &mut Env, expr: &PrefixExpr) -> i64 {
54 let rhs = eval_expr(env, &expr.expr);
55 match expr.op {
56 PrefixOp::Plus => rhs,
57 PrefixOp::Minus => -rhs,
58 }
59}
60
61fn eval_infix(env: &mut Env, expr: &InfixExpr) -> i64 {
62 let lhs = eval_expr(env, &expr.lhs);
63 let rhs = eval_expr(env, &expr.rhs);
64 match expr.op {
65 InfixOp::Plus => lhs + rhs,
66 InfixOp::Minus => lhs - rhs,
67 InfixOp::Multiply => lhs * rhs,
68 InfixOp::Divide => lhs / rhs,
69 }
70}
解释器的状态保存到一个名为 Env 的结构体。在 Env 中，我们只定义了一个变量 mem，用于存储计算结果，这样两个不同的步骤之间，后一个就可以使用前一个的结果。
解释器还包含了一个 interpret 函数，它接受一个 TransUnit 对象，并循环执行其中的所有语句。对于每个语句，我们都将调用 eval_expr 函数来计算表达式的值，并将其保存在 mem 变量中。
最后，我们还定义了一些辅助函数，如 eval_primary、eval_prefix 和 eval_infix，用于计算操作数的值，并执行适当的操作符。
编写语法解析器
现在我们需要编写一个语法解析器来将代码解析为抽象语法树（AST）。在 src 目录下创建一个名为 parser.rs 的新文件，该文件将定义语法解析器。我们将使用 pest 库来编写语法解析器。
1use crate::ast::*;
2use pest::iterators::Pair;
3use pest::{pratt_parser::PrattParser, Parser};
4
5#[derive(Parser, Default)]
6#[grammar = "calc.pest"]
7pub struct CalcParser {}
8
9lazy_static::lazy_static! {
10 static ref PRATT_PARSER: PrattParser<Rule> = {
11 use pest::pratt_parser::{Assoc::*, Op};
12 // Precedence is defined lowest to highest
13 PrattParser::new()
14 .op(Op::postfix(Rule::postfix_op))
15 .op(Op::infix(Rule::add_op, Left))
16 .op(Op::infix(Rule::mul_op, Left))
17 .op(Op::prefix(Rule::prefix_op))
18 };
19}
20
21
22pub fn parse(src: &str) -> Result<TransUnit, pest::error::Error<Rule>> {
23 let mut grammar_pairs = CalcParser::parse(Rule::grammar, src)?;
24 let tu = parse_grammar(grammar_pairs.next().unwrap())?;
25 Ok(tu)
26}
27
28// grammar = { trans_unit ~ EOI }
29pub fn parse_grammar(pair: Pair<Rule>) -> Result<TransUnit, pest::error::Error<Rule>> {
30 let tu = pair.into_inner().next().unwrap();
31 parse_trans_unit(tu)
32}
33
34// trans_unit = { block }
35pub fn parse_trans_unit(pair: Pair<Rule>) -> Result<TransUnit, pest::error::Error<Rule>> {
36 let block = pair.into_inner().next().unwrap();
37 Ok(TransUnit {
38 block: parse_block(block)?,
39 })
40}
41
42// block = { "{" ~ stmts ~ "}" }
43fn parse_block(pair: Pair<Rule>) -> Result<Block, pest::error::Error<Rule>> {
44 let inner = pair.into_inner();
45
46 let mut statements = Vec::new();
47 for p in inner {
48 statements.push(parse_statement(p)?);
49 }
50 Ok(Block { stmts: statements })
51}
52
53// stmt = { expr_stmt | print_stmt }
54fn parse_statement(pair: Pair<Rule>) -> Result<Stmt, pest::error::Error<Rule>> {
55 let inner = pair.into_inner().next().unwrap();
56 match inner.as_rule() {
57 Rule::expr_stmt => parse_expr_statement(inner),
58 Rule::print_stmt => parse_print_statement(inner),
59 _ => unreachable!(),
60 }
61}
62
63// expr_stmt = { expr ~ ";" }
64fn parse_expr_statement(pair: Pair<Rule>) -> Result<Stmt, pest::error::Error<Rule>> {
65 let inner = pair.into_inner().next().unwrap();
66 let expr = parse_expr(inner)?;
67 Ok(Stmt::ExprStmt(expr))
68}
69
70// print_stmt = { "print" ~ expr ~ ";" }
71fn parse_print_statement(pair: Pair<Rule>) -> Result<Stmt, pest::error::Error<Rule>> {
72 let inner = pair.into_inner().next().unwrap();
73 let expr = parse_expr(inner)?;
74 Ok(Stmt::PrintStmt(expr))
75}
在 parse_expr 函数中，我们使用 PRATT_PARSER 对表达式进行解析。这个解析器是一种基于 Pratt 方法的解析器，能够高效地处理表达式的嵌套、优先级等问题。我的另一篇文章介绍了它的实现原理，感兴趣的读者可以参考一下。
1fn parse_expr(pair: Pair<Rule>) -> Result<Expr, pest::error::Error<Rule>> {
2 let inner = pair.into_inner();
3 let expr = PRATT_PARSER
4 .map_primary(|x| Expr::Primary(Box::new(parse_primary_expr(x).unwrap())))
5 .map_infix(|lhs, op, rhs| {
6 Expr::Infix(Box::new(InfixExpr {
7 lhs: Box::new(lhs),
8 op: parse_infix(op).unwrap(),
9 rhs: Box::new(rhs),
10 }))
11 })
12 .map_prefix(|op, rhs| {
13 Expr::Prefix(Box::new(PrefixExpr {
14 op: parse_prefix(op).unwrap(),
15 expr: Box::new(rhs),
16 }))
17 })
18 .parse(inner.into_iter());
19 Ok(expr)
20}
在 parse_expr 函数中，我们首先将输入转换为一个 Pair 类型的迭代器。然后，我们使用 PRATT_PARSER 进行解析。在解析器中，我们使用了三个函数：
-
map_primary: 解析基本表达式（如变量或常量）。 -
map_infix: 解析中缀运算符（如加、减、乘、除）。 -
map_prefix: 解析前缀运算符（如加、减）。
对于每种类型的表达式，我们都定义了一个对应的解析函数。这些函数将从输入的 Pair 类型对象中提取表达式，并将其转换为我们定义的 AST 节点类型。
1// prefix_op = { "+" | "-" }
2fn parse_prefix(op: Pair<Rule>) -> Result<PrefixOp, pest::error::Error<Rule>> {
3 match op.as_str() {
4 "+" => Ok(PrefixOp::Plus),
5 "-" => Ok(PrefixOp::Minus),
6 _ => unreachable!(),
7 }
8}
9
10// infix_op = { "+" | "-" | "*" | "/" }
11fn parse_infix(op: Pair<Rule>) -> Result<InfixOp, pest::error::Error<Rule>> {
12 match op.as_str() {
13 "+" => Ok(InfixOp::Plus),
14 "-" => Ok(InfixOp::Minus),
15 "*" => Ok(InfixOp::Multiply),
16 "/" => Ok(InfixOp::Divide),
17 _ => unreachable!(),
18 }
19}
20
21// primary_expr = { INT | "(" ~ expr ~ ")" }
22fn parse_primary_expr(pair: Pair<Rule>) -> Result<PrimaryExpr, pest::error::Error<Rule>> {
23 let inner = pair.into_inner().next().unwrap();
24 match inner.as_rule() {
25 Rule::MEM => Ok(PrimaryExpr::Mem),
26 Rule::INT => parse_int(inner),
27 Rule::expr => Ok(PrimaryExpr::Expr(Box::new(parse_expr(inner)?))),
28 _ => unreachable!(),
29 }
30}
31
32// INT = { ASCII_DIGIT+ }
33fn parse_int(pair: Pair<Rule>) -> Result<PrimaryExpr, pest::error::Error<Rule>> {
34 let int = pair.as_str().parse::<i64>().unwrap();
35 Ok(PrimaryExpr::Int(int))
36}
至此，我们已经能够成功地解析用户输入的表达式，并将其转换为 AST 中的节点。接下来，我们需要将 AST 中的节点转换为实际的计算结果。
在 interpreter.rs 文件中，我们定义了一个 interpret 函数，该函数接受一个 TransUnit 类型的 AST 节点，并对其进行求值。
1pub fn interpret(tu: &TransUnit) {
2 let mut env = Env::new();
3 for stmt in &tu.block.stmts {
4 match stmt {
5 Stmt::ExprStmt(expr) => {
6 env.set_mem(eval_expr(&mut env, expr));
7 },
8 Stmt::PrintStmt(expr) => {
9 println!("{}", eval_expr(&mut env, expr));
10 }
11 }
12 }
13}
我们创建了一个新的 Env 类型的对象，该对象包含了变量和内存等信息。在 for 循环中，我们遍历 AST 中的每个语句，并根据语句类型调用不同的函数进行求值。对于表达式语句，我们调用 eval_expr 函数求值，然后将结果存储在环境中的 mem 变量中。对于打印语句，我们直接打印表达式的值。
1fn eval_expr(env: &mut Env, expr: &Expr) -> i64 {
2 match expr {
3 Expr::Primary(e)=> eval_primary(env, e),
4 Expr::Prefix(e)=> eval_prefix(env, e),
5 Expr::Infix(e)=> eval_infix(env, e),
6 }
7}
8
9fn eval_primary(env: &mut Env, expr: &PrimaryExpr) -> i64 {
10 match expr {
11 PrimaryExpr::Mem => env.get_mem(),
12 PrimaryExpr::Int(i) => *i,
13 PrimaryExpr::Expr(e) => eval_expr(env, e),
14 }
15}
16
17fn eval_prefix(env: &mut Env, expr: &PrefixExpr) -> i64 {
18 let rhs = eval_expr(env, &expr.expr);
19 match expr.op {
20 PrefixOp::Plus => rhs,
21 PrefixOp::Minus => -rhs,
22 }
23}
24
25fn eval_infix(env: &mut Env, expr: &InfixExpr) -> i64 {
26 let lhs = eval_expr(env, &expr.lhs);
27 let rhs = eval_expr(env, &expr.rhs);
28 match expr.op {
29 InfixOp::Plus => lhs + rhs,
30 InfixOp::Minus => lhs - rhs,
31 InfixOp::Multiply => lhs * rhs,
32 InfixOp::Divide => lhs / rhs,
33 }
34}
我们定义了三个函数来分别对主要表达式、前缀表达式和中缀表达式进行求值。在 eval_expr 函数中，我们根据 AST 节点的类型调用不同的求值函数。对于主要表达式，我们返回内存中的值或常量值。对于前缀表达式，我们首先求出右侧表达式的值，然后应用相应的运算符。对于中缀表达式，我们首先求出左侧和右侧表达式的值，然后应用相应的运算符。
最后，我们在 main.rs 文件和 driver.rs 中添加代码，将用户输入的表达式转换为 AST 并求值。
1mod ast;
2mod parser;
3mod driver;
4mod interpreter;
5
6#[macro_use]
7extern crate pest_derive;
8use std::env;
9
10use driver::drive;
11
12fn main() {
13 let args: Vec<String> = env::args().collect();
14 let mut i = 1;
15 while i < args.len() {
16 match args[i].as_str() {
17 "-h" | "--help" => print!("Usage: calc -e EXPR\n"),
18 "-v" | "--version" => print!("calc 0.1.0\n"),
19 "-e" | "--expr" => {
20 i += 1;
21 drive(args[i].as_str());
22 }
23 _ => {
24 print!("calc: Unrecognized option '{}'\n", args[i])
25 }
26 }
27 i += 1;
28 }
29}
1use crate::{parser::parse, interpreter::interpret};
2
3pub fn drive(src: &str) {
4 let tu = parse(src);
5 if tu.is_err() {
6 println!("Error: {:?}", tu.err());
7 return;
8 }
9 interpret(&tu.unwrap());
10}
这样，我们就完成了一个简单的计算器，它可以解析并计算用户输入的表达式。
下一章，我们将解释放到 IR 层面进行。
PS：天天用 GPT。现在，感觉自己的语言风格也逐渐 GPT 化。