complie

start.rs

use std::collections::HashSet;
use std::io::{Error, ErrorKind, Result};
use std::iter::Peekable;
use std::rc::Rc;
use std::sync::LazyLock;

static KEYWORDS_MAP: LazyLock<HashSet<&str>> = LazyLock::new(|| HashSet::from(["int"]));

#[derive(Debug, PartialEq, Eq)]
#[non_exhaustive]
enum TokenTy {
    /// 初始化类型
    Initial,
    /// 整型字面量
    IntLiteral,
    /// 标识符
    Identifier,
    GE,
    GT,
    Assignment,
    // 算数运算
    Plus,
    Minus,
    Star,
    Slash,
    // 关键字
    INT,
}

impl From<char> for TokenTy {
    fn from(c: char) -> Self {
        if c.is_alphabetic() {
            return Self::Identifier;
        }
        if c.is_numeric() {
            return Self::IntLiteral;
        }
        if c == '>' {
            return Self::GT;
        }
        if c == '=' {
            return Self::Assignment;
        }
        if c == '+' {
            return Self::Plus;
        }
        if c == '-' {
            return Self::Minus;
        }
        if c == '*' {
            return Self::Star;
        }
        if c == '/' {
            return Self::Slash;
        }
        Self::Initial
    }
}

struct Token {
    ty: TokenTy,
    content: Option<String>,
}

impl std::fmt::Debug for Token {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.content.is_none() {
            return write!(f, "<{:?}>", self.ty);
        }
        write!(f, "<{:?}>(\"{}\")", self.ty, self.content.as_ref().unwrap())
    }
}

impl Token {
    fn new(ty: TokenTy) -> Self {
        Token { ty, content: None }
    }

    fn from_str(ty: TokenTy, content: &str) -> Self {
        match ty {
            TokenTy::GT | TokenTy::GE | TokenTy::Initial => Self::new(ty),
            TokenTy::Identifier => {
                // 需要判断关键字
                if KEYWORDS_MAP.contains(content) {
                    Self::new(TokenTy::INT)
                } else {
                    Self {
                        ty,
                        content: Some(content.into()),
                    }
                }
            }
            _ => Self {
                ty,
                content: if content.is_empty() { None } else { Some(content.into()) },
            },
        }
    }
}

#[derive(Debug)]
enum AstNodeTy {
    /// 程序入口，根节点
    Program,

    /// 整型变量声明
    IntDeclaration,
    /// 表达式语句，即表达式后面跟个分号
    ExpressionStmt,
    /// 赋值语句
    AssignmentStmt,

    /// 基础表达式
    Primary,
    /// 乘法表达式
    Multiplicative,
    /// 加法表达式
    Additive,

    /// 标识符
    Identifier,
    /// 整型字面量
    IntLiteral,
}

#[derive(Debug)]
struct AstNode {
    ty: AstNodeTy,
    content: Option<String>,
    child: Option<Vec<Rc<AstNode>>>,
}

impl AstNode {
    fn new(ty: AstNodeTy) -> Self {
        Self { ty, content: None, child: None }
    }

    fn from_content(ty: AstNodeTy, content: &str) -> Self {
        Self {
            ty,
            content: if content.is_empty() { None } else { Some(content.into()) },
            child: None,
        }
    }

    fn add_children(&mut self, node: Rc<AstNode>) {
        if let Some(ref mut c) = self.child {
            c.push(node);
        } else {
            self.child = Some(vec![node]);
        }
    }

    fn print_ast_tree(&self, depth: usize) {
        let indent = "  ".repeat(depth);
        println!("{}{}", indent, self);

        if let Some(ref children) = self.child {
            for child_node in children {
                AstNode::print_ast_tree(child_node, depth + 1);
            }
        }
    }

    fn evaluate(&self) -> Result<i32> {
        let mut result = 0;
        match self.ty {
            AstNodeTy::Program => {
                if let Some(ref cs) = self.child {
                    for c in cs {
                        result += AstNode::evaluate(c)?;
                    }
                }
            }
            AstNodeTy::Additive => {
                if let Some(ref cs) = self.child {
                    for c in cs {
                        result += AstNode::evaluate(c)?;
                    }
                }
            }
            AstNodeTy::Multiplicative => {
                let mut r_tmp = 1;
                if let Some(ref cs) = self.child {
                    for c in cs {
                        r_tmp *= AstNode::evaluate(c)?;
                    }
                }
                result += r_tmp
            }
            AstNodeTy::IntLiteral => {
                if let Some(ref c) = self.content {
                    result = c.parse().map_err(|e| Error::new(ErrorKind::InvalidData, e))?;
                }
            }
            _ => {}
        };

        Ok(result)
    }
}

impl std::fmt::Display for AstNode {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "<{:?}>[{}]", self.ty, if let Some(ref c) = self.child { c.len() } else { 0 })?;
        if let Some(ref c) = self.content {
            write!(f, "\t\"{}\"", c)?;
        }
        Ok(())
    }
}

fn main() -> Result<()> {
    // let pg = "int age >= 666";
    // let pg = "aaa bbb";
    // let pg = "2 + 3 * 100";
    let pg = "2+3*7+3*8";
    // let pg = "2*100";
    let mut c_state = TokenTy::Initial;
    let mut c_token_content = String::new();
    let mut tokens: Vec<Token> = vec![];

    for c in pg.chars() {
        match c_state {
            TokenTy::Initial => {
                if !c.is_whitespace() {
                    c_token_content.push(c);
                    c_state = TokenTy::from(c);
                }
            }
            TokenTy::Identifier => {
                if c.is_alphabetic() {
                    c_token_content.push(c);
                    continue;
                }

                tokens.push(Token::from_str(c_state, &c_token_content));
                c_state = TokenTy::from(c);
                c_token_content.clear();
                if !c.is_whitespace() {
                    c_token_content.push(c);
                }
            }
            TokenTy::IntLiteral => {
                if c.is_numeric() {
                    c_token_content.push(c);
                    continue;
                }

                tokens.push(Token::from_str(c_state, &c_token_content));
                c_state = TokenTy::from(c);
                c_token_content.clear();
                if !c.is_whitespace() {
                    c_token_content.push(c);
                }
            }
            TokenTy::GT => {
                if c == '=' {
                    c_token_content.push(c);
                    c_state = TokenTy::GE;
                    continue;
                }

                tokens.push(Token::new(c_state));
                c_state = TokenTy::from(c);
                c_token_content.clear();
                if !c.is_whitespace() {
                    c_token_content.push(c);
                }
            }
            t => {
                tokens.push(Token::new(t));
                c_state = TokenTy::from(c);
                c_token_content.clear();
                if !c.is_whitespace() {
                    c_token_content.push(c);
                }
            }
        }
    }

    tokens.push(Token::from_str(c_state, &c_token_content));

    let root_ast_node = prog(&mut tokens.into_iter().peekable())?;

    // println!("{:#?}", root_ast_node);

    if let Some(ref n) = root_ast_node {
        n.print_ast_tree(0);
        println!("计算结果: {:?}", n.evaluate());
    }

    Ok(())
}

fn prog(tk_iter: &mut Peekable<impl Iterator<Item = Token>>) -> Result<Option<Rc<AstNode>>> {
    let mut root_node = AstNode::new(AstNodeTy::Program);
    if let Some(child) = additive(tk_iter)? {
        root_node.add_children(child);
    }
    Ok(Some(Rc::new(root_node)))
}

fn additive(tk_iter: &mut Peekable<impl Iterator<Item = Token>>) -> Result<Option<Rc<AstNode>>> {
    let root_node_1 = multiplicative(tk_iter)?;
    let final_node = root_node_1.clone();
    let c_token = tk_iter.peek();

    if let (Some(node_1), /*                */ Some(c_token_peeked)) = (root_node_1, c_token) {
        //       ^^^^^^                             ^^^^^^^^^^^^^^
        // additiveExpression                            ???
        //
        // c_token_peeked 不为 None 则需要判定匹配加法表达式
        // additiveExpression : multiplicativeExpression | multiplicativeExpression Plus additiveExpression
        // 中的 multiplicativeExpression Star IntLiteral 情况，即 ??? 部分是否为 Plus
        if c_token_peeked.ty == TokenTy::Plus || c_token_peeked.ty == TokenTy::Minus {
            // 先消耗Token
            tk_iter.next();
            // root_node_2 即可能匹配的剩余的 additiveExpression 部分
            let root_node_2 = additive(tk_iter);
            if let Ok(Some(node_2)) = root_node_2 {
                // 至此乘法表达式匹配成功
                let mut node = AstNode::new(AstNodeTy::Additive);
                node.add_children(node_1);
                node.add_children(node_2);
                return Ok(Some(Rc::new(node)));
            }
            return Err(Error::new(ErrorKind::InvalidData, "乘法表达式无法匹配 IntLiteral"));
        }
    }
    Ok(final_node)
}

fn multiplicative(tk_iter: &mut Peekable<impl Iterator<Item = Token>>) -> Result<Option<Rc<AstNode>>> {
    let root_node_1 = primary(tk_iter)?;
    let final_node = root_node_1.clone();
    let c_token = tk_iter.peek();

    if let (Some(node_1), /*                */ Some(c_token_peeked)) = (root_node_1, c_token) {
        //       ^^^^^^                             ^^^^^^^^^^^^^^
        //  multiplicativeExpression                      ???
        //
        // c_token_peeked 不为 None 则需要判定匹配乘法表达式
        // multiplicativeExpression : IntLiteral | multiplicativeExpression Star IntLiteral
        // 中的 multiplicativeExpression Star IntLiteral 情况，即 ??? 部分是否为 Star
        if c_token_peeked.ty == TokenTy::Star || c_token_peeked.ty == TokenTy::Slash {
            // 先消耗Token
            tk_iter.next();
            // root_node_2 即可能匹配的剩余的 IntLiteral 部分
            let root_node_2 = multiplicative(tk_iter);
            if let Ok(Some(node_2)) = root_node_2 {
                // 至此乘法表达式匹配成功
                let mut node = AstNode::new(AstNodeTy::Multiplicative);
                node.add_children(node_1);
                node.add_children(node_2);
                return Ok(Some(Rc::new(node)));
            }
            return Err(Error::new(ErrorKind::InvalidData, "乘法表达式无法匹配 IntLiteral"));
        }
    }
    Ok(final_node)
}

fn primary(tk_iter: &mut Peekable<impl Iterator<Item = Token>>) -> Result<Option<Rc<AstNode>>> {
    let mut c_node = None;
    let c_token = tk_iter.peek();

    if let Some(token) = c_token {
        match token.ty {
            TokenTy::IntLiteral => {
                c_node = Some(Rc::new(AstNode::from_content(
                    AstNodeTy::IntLiteral,
                    token.content.as_ref().expect("无法从整型字面量Token内提取信息"),
                )));
                tk_iter.next();
            }
            TokenTy::Identifier => {
                c_node = Some(Rc::new(AstNode::from_content(
                    AstNodeTy::Identifier,
                    token.content.as_ref().expect("无法从标识符Token内提取信息"),
                )));
            }
            _ => {}
        };
    }
    Ok(c_node)
}