龙书读书笔记 0x01: 例程 2-27

上次看书看到了第二章，书中实现了一个简单的中缀到后缀的翻译器。这个例程在书中图2-27，本身是 Java 代码，如果用 C 或 C++ 来实现，那是相当简单的，几乎就是抄过来，正好我也在学习 Rust 语言，于是想到了使用 Rust 来实现书中的例程。

这个翻译器只能处理一位数字间不带括号的加减法，其产生式为：

expr -> expr + term
expr -> expr - term
term -> [0-9] # 直接使用正则来节省篇幅，就不展开了

代码在 gist 上保存了，也搬运在这里：

use std::io::{Read, Error, ErrorKind};
use std::fmt;

enum ParseError {
    SyntaxError,
    Parse(Error)
}

impl fmt::Display for ParseError {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match *self {
            ParseError::SyntaxError => write!(f, "syntax error"),
            ParseError::Parse(ref e) => e.fmt(f),
        }
    }
}

struct Parser {
    lookahead: u8,
}

impl Parser {
    pub fn new() -> Self {
        let ch = read_char().expect("Cannot read charactor from input!");
        Self {
            lookahead: ch,
        }
    }

    pub fn expr(&mut self) -> Result<(), ParseError> {
        if let Err(e) = self.term() {
            return Err(e);
        }
        loop {
            if self.lookahead == b'+' {
                if let Err(e) = self.pmatch(b'+') {
                    return Err(e);
                }
                if let Err(e) = self.term() {
                    return Err(e);
                }
                print!("+");
            } else if self.lookahead == b'-' {
                if let Err(e) = self.pmatch(b'-') {
                    return Err(e);
                }
                if let Err(e) = self.term() {
                    return Err(e);
                }
                print!("-");
            } else {
                return Ok(());
            }
        }
    }

    pub fn term(&mut self) -> Result<(), ParseError> {
        if self.lookahead.is_ascii_digit() {
            print!("{}", char::from(self.lookahead));
            self.pmatch(self.lookahead)
        } else {
            Err(ParseError::SyntaxError)
        }
    }

    pub fn pmatch(&mut self, t: u8) -> Result<(), ParseError> {
        if self.lookahead == t {
            let input = read_char();
            match input {
                Ok(ch) => {
                    self.lookahead = ch;
                    Ok(())
                },
                Err(e) => Err(ParseError::Parse(e)),
            }
        } else {
            Err(ParseError::SyntaxError)
        }
    }
}

fn read_char() -> Result<u8, Error> {
    std::io::stdin().bytes().next()
        .unwrap_or(Err(Error::new(ErrorKind::Other, "Cannot read from stdin!")))
}

fn main() {
    let mut parse = Parser::new();
    match parse.expr() {
        Ok(_) => println!(""),
        Err(e) => println!("{}", e),
    };
}

顺手也写了一个 Python 版本：

import readchar

class Parser:
    def __init__(self):
        self.lookahead = readchar.readchar()

    def expr(self):
        self.term()
        while True:
            if self.lookahead == b'+':
                self.match(b'+')
                self.term()
                print('+', end='')
            elif self.lookahead == b'-':
                self.match(b'-')
                self.term()
                print('-', end='')
            else:
                return

    def term(self):
        if self.lookahead.isdigit():
            print(self.lookahead.decode("utf-8"), end='')
            self.match(self.lookahead)
        else:
            raise Exception("syntax error")

    def match(self, t):
        if self.lookahead == t:
            self.lookahead = readchar.readchar()
        else:
            raise Exception("syntax error")

if __name__ == '__main__':
    parse = Parser()
    parse.expr()
    print("")