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",
),
),
),
),