How do I implement precedence climbing correctly in rust

56 views Asked by At

I am writing a compiler in rust and I am stuck trying to implement a precedence climbing algorithm. The structure of the parse tree generates correctly but the infix operator in the tree are wrong.


struct ExpressionParser {
    iterator: IntoIter<TokenKind>,
    current_precedence: u8,
}

impl ExpressionParser {
    fn new(iterator: IntoIter<TokenKind>) -> Self {
        Self {
            iterator: iterator,
            current_precedence: 1,
        }
    }

    fn parse_expression(&mut self, current_token: TokenKind) -> Result<ExpressionNode> {
        let mut expr = match current_token {
            TokenKind::Int(_) => Self::parse_expression_token(current_token),
            TokenKind::VarName(_) => Self::parse_expression_token(current_token),
            _ => Err(new_error("syntax error: invalid expression")),
        };
        let op_token = match self.iterator.next() {
            Some(op_token) => op_token,
            None => {
                return expr;
            }
        };

        loop {
            let infix = match op_token {
                TokenKind::Operator(ref infix) => Ok(infix.as_str()),
                _ => Err(new_error("syntax error: invalid expression")),
            }?;
            let precedence: u8 = match infix {
                "+" | "-" => Ok(1),
                "*" | "/" => Ok(2),
                _ => Err(new_error("syntax error: unknown operator")),
            }?;
            //infix is overwritten because of this
            if precedence < self.current_precedence {
                self.current_precedence = 1;
                break expr;
            }
            // is there another
            let next_token = match self.iterator.next() {
                Some(token) => token,
                None => {
                    self.current_precedence = 1;
                    break expr;
                }
            };
            self.current_precedence = precedence;
            let rh_expr = self.parse_expression(next_token);
            expr = Ok(Self::make_infix(expr?, rh_expr?, infix.to_string()));
        }
    }

    fn parse_expression_token(token: TokenKind) -> Result<ExpressionNode> {
        match token {
            TokenKind::Int(value) => Ok(ExpressionNode::Value(value)),
            TokenKind::VarName(name) => Ok(ExpressionNode::Var(name)),
            _ => Err(new_error("syntax error: balse")),
        }
    }

    fn make_infix(lh: ExpressionNode, rh: ExpressionNode, infix: String) -> ExpressionNode {
        ExpressionNode::Infix(Box::new(lh), infix.to_string(), Box::new(rh))
    }
}

heres my attempt

This is the tree generated for. 1 + 2 * 3 + 4 * 5 as you can see the structure is good but the infix between the 2 multiplication expressions is wrong.

 Expression(
            Infix(
                Value(
                    "1",
                ),
                "+",
                Infix(
                    Infix(
                        Value(
                            "2",
                        ),
                        "*",
                        Value(
                            "3",
                        ),
                    ),
                    "*",
                    Infix(
                        Value(
                            "4",
                        ),
                        "*",
                        Value(
                            "5",
                        ),
                    ),
                ),
            ),
0

There are 0 answers