将 brainf*ck 代码解析为 Rust 中的树

Question

我正在尝试用 Rust 编写一个优化的 brainfuck 编译器。目前它将标记存储在一个平面向量中，这是有效的，但我无法将其更改为使用语法树：

#[derive(Clone, PartialEq, Eq)]
pub enum Token {
    Output,
    Input,
    Loop(Vec<Token>),
    Move(i32),
    Add(i32, i32),
    LoadOut(i32, i32),
}
use Token::*;

pub fn parse(code: &str) -> Vec<Token> {
    let mut alltokens = Vec::new();
    let mut tokens = &mut alltokens;
    let mut tokvecs: Vec<&mut Vec<Token>> = Vec::new();
    for i in code.chars() {
        match i {
            '+' => tokens.push(Add(0, 1)),
            '-' => tokens.push(Add(0, -1)),
            '>' => tokens.push(Move(1)),
            '<' => tokens.push(Move(-1)),
            '[' => {
                tokens.push(Loop(Vec::new()));
                tokvecs.push(&mut tokens);
                if let &mut Loop(mut newtokens) = tokens.last_mut().unwrap() {
                    tokens = &mut newtokens;
                }
            },
            ']' => {
                tokens = tokvecs.pop().unwrap();
            },
            ',' => tokens.push(Input),
            '.' => {
                tokens.push(LoadOut(0, 0));
                tokens.push(Output);
            }
            _ => (),
        };
    }

    alltokens
}

我无法弄清楚如何处理 [ 命令。代码中的当前实现是我尝试过的几种之一，但都失败了。我认为它可能需要使用 Rust 的 Box，但我不太明白它是如何使用的。

处理[命令的分支可能完全错误，但我不确定应该如何完成。它将包含向量的 Loop（Token 枚举的变体）推送到 tokens 向量。问题是然后在 Loop 中获取向量的可变借用，if let 语句应该这样做。

代码无法编译，因为 newtokens 没有超过 if let 块的末尾。是否有可能获得对 Loop 内向量的可变引用，并为其设置 tokens？如果没有，可以做些什么？

Answer 1

好的，上次我已经很接近了；看来我错过了 ref 关键字：

if let &mut Loop(ref mut newtokens) = (&mut tokens).last_mut().unwrap()

我错过了，因为到处都有其他借用检查器错误。我决定简化您的代码来解决这些问题：

pub fn parse(code: &str) -> Vec<Token> {
    let mut tokens = Vec::new();
    for i in code.chars() {
        match i {
            '+' => tokens.push(Add(0, 1)),
            '-' => tokens.push(Add(0, -1)),
            '>' => tokens.push(Move(1)),
            '<' => tokens.push(Move(-1)),
            '[' => {
                tokens.push(Loop(Vec::new()));
                if let &mut Loop(ref mut newtokens) = (&mut tokens).last_mut().unwrap() {
                    let bracket_tokens: &mut Vec<Token> = newtokens;
                }
            },
            ']' => {
                ()
            },
            ',' => tokens.push(Input),
            '.' => {
                tokens.push(LoadOut(0, 0));
                tokens.push(Output);
            }
            _ => unreachable!(),
        };
    }

    tokens
}

我合并了所有的标记变量（你并不真的需要它们）并将 tokens = &mut newtokens; 更改为 let bracket_tokens: &mut Vec<Token> = newtokens;（我认为这或多或少是你的意图）。这允许您在 Loop.

中操作 Vector

然而，这段代码仍然存在问题，无法解析 brainf*ck 的循环；我想让它发挥作用，但它需要对方法进行重大改变。欢迎您尝试进一步扩展此变体，但这可能是一次痛苦的经历，尤其是如果您还不太熟悉借用检查器的规则。

我建议看看其他人的 brainf*ck 解释器实现（例如 this one）（虽然不是太旧，因为 Rust 的语法在 1.0 上线之前已经改变）以了解如何做到这一点.

Answer 2

我通过递归函数使代码工作：

#[derive(Clone, PartialEq, Eq)]
pub enum Token {
    Output,
    Input,
    Loop(Vec<Token>),
    Move(i32),
    Add(i32, i32),
    LoadOut(i32, i32),
}
use Token::*;

pub fn parse(code: &str) -> Vec<Token> {
    _parse(&mut code.chars())
}

fn _parse(chars: &mut std::str::Chars) -> Vec<Token> {
    let mut tokens = Vec::new();
    while let Some(i) = chars.next() {
        match i {
            '+' => tokens.push(Add(0, 1)),
            '-' => tokens.push(Add(0, -1)),
            '>' => tokens.push(Move(1)),
            '<' => tokens.push(Move(-1)),
            '[' => tokens.push(Loop(_parse(chars))),
            ']' => { break; }
            ',' => tokens.push(Input),
            '.' => {
                tokens.push(LoadOut(0, 0));
                tokens.push(Output);
            }
            _ => (),
        };
    }

    tokens
}

它似乎有效，而且相当简单和优雅（我仍然有兴趣看到一个不使用递归的解决方案）。

将 brainf*ck 代码解析为 Rust 中的树

Parsing brainf*ck code to tree in Rust

parsing

brainfuck

rust