Precedence climbing

preced_climb_parser.rs

// Precedence climbing
//
// Source: https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing
//
//
// Eparser is
//    var t : Tree
//    t := Exp( 0 )
//    expect( end )
//    return t
// Exp( p ) is
//     var t : Tree
//     t := P
//     while next is a binary operator and prec(binary(next)) >= p
//        const op := binary(next)
//        consume
//        const q := case associativity(op)
//                   of Right: prec( op )
//                      Left:  1+prec( op )
//        const t1 := Exp( q )
//        t := mkNode( op, t, t1)
//     return t
// P is
//     if next is a unary operator
//          const op := unary(next)
//          consume
//          q := prec( op )
//          const t := Exp( q )
//          return mkNode( op, t )
//     else if next = "("
//          consume
//          const t := Exp( 0 )
//          expect ")"
//          return t
//     else if next is a v
//          const t := mkLeaf( next )
//          consume
//          return t
//     else
//          error

#[derive(Clone, Copy, Debug)]
enum Op {
    Plus,
    Minus,
    Div,
    Mul,
}

impl Op {
    fn prec(&self) -> u8 {
        match self {
            Self::Plus | Self::Minus => 1,
            Self::Div | Self::Mul => 2,
        }
    }

    fn is_left_assoc(&self) -> bool {
        true
    }
}

impl From<Token> for Op {
    fn from(value: Token) -> Self {
        match value {
            Token::Minus => Self::Minus,
            Token::Plus => Self::Plus,
            Token::Slash => Self::Div,
            Token::Star => Self::Mul,
            _ => panic!("incorrect token"),
        }
    }
}

#[derive(Debug)]
struct BinExpr {
    op: Op,
    lhs: Option<Box<Node>>,
    rhs: Option<Box<Node>>,
}

#[derive(Debug)]
struct UnaryExpr {
    op: Op,
    rhs: Option<Box<Node>>,
}

#[derive(Debug)]
enum Node {
    Bin(BinExpr),
    Unary(UnaryExpr),
    Lit(f64),
}

#[derive(Clone, Copy, Debug, PartialEq)]
enum Token {
    Number(f64),
    Plus,
    Minus,
    Star,
    Slash,
    LParen,
    RParen,
    Semicolon,
    Eof,
}

struct Parser<'a> {
    tokens: &'a Vec<Token>,
    cur: usize,
}

impl<'a> Parser<'a> {
    fn new(tokens: &'a Vec<Token>) -> Self {
        Self { tokens, cur: 0 }
    }

    fn next(&self) -> Token {
        if self.cur >= self.tokens.len() {
            return Token::Eof;
        }
        self.tokens[self.cur]
    }

    fn consume(&mut self) {
        self.cur += 1;
    }

    fn expect(&mut self, tok: Token) {
        let n = self.next();
        if n == tok {
            self.consume();
        } else {
            panic!("expected tok: {:?} but n: {:?}", tok, n);
        }
    }

    fn P(&mut self) -> Option<Box<Node>> {
        let n = self.next();
        match n {
            Token::Minus => {
                self.consume();
                let op = Op::Minus;
                Some(Box::new(Node::Unary(UnaryExpr {
                    op,
                    rhs: self.expr(op.prec()),
                })))
            }
            Token::LParen => {
                self.consume();
                let t = self.expr(0);
                self.expect(Token::RParen);
                t
            }
            Token::Number(n) => {
                let t = Node::Lit(n);
                self.consume();
                Some(Box::new(t))
            }
            _ => {
                panic!("unexpected token: {:?}", n);
            }
        }
    }

    fn expr(&mut self, prec: u8) -> Option<Box<Node>> {
        let mut t = self.P();
        let mut n = self.next();
        loop {
            if !matches!(n, Token::Minus | Token::Plus | Token::Slash | Token::Star) {
                break;
            }

            let op = Op::from(n);
            if !(op.prec() >= prec) {
                break;
            }

            self.consume();
            let t1 = self.expr(op.prec() + 1);
            t = Some(Box::new(Node::Bin(BinExpr {
                op: op,
                lhs: t,
                rhs: t1,
            })));

            n = self.next();
        }
        t
    }

    fn parse(&mut self) -> Option<Box<Node>> {
        let t = self.expr(0);
        self.expect(Token::Semicolon);
        t
    }
}

fn main() {
    let toks = vec![
        Token::LParen,
        Token::Number(1 as f64),
        Token::Plus,
        Token::Number(2 as f64),
        Token::RParen,
        Token::Slash,
        Token::Number(3 as f64),
        Token::Semicolon,
    ];
    let mut p = Parser::new(&toks);
    let tree = p.parse();
    println!("{:?}", tree);
}