Expression Parser

Parse a sequence of tokens into an AST for a tiny expression language.

You will receive a token slice (including EOF). Your job is to build an AST that respects precedence and associativity.

Function signature

func Parse(tokens []Token) (*Expr, error)

Grammar

expr       -> equality

equality   -> comparison ( ("==" | "!=") comparison )*
comparison -> term ( ("<" | "<=" | ">" | ">=") term )*
term       -> factor ( ("+" | "-") factor )*
factor     -> unary ( ("*" | "/") unary )*

unary      -> ("!" | "-") unary | primary
primary    -> NUMBER | IDENT | "(" expr ")" | call
call       -> IDENT "(" args? ")"
args       -> expr ( "," expr )*

AST shape

Use the provided Expr struct with the following conventions:

• ExprNumber: Value holds the number lexeme
• ExprIdent: Value holds the identifier name
• ExprUnary: Value holds the operator, Left holds the operand
• ExprBinary: Value holds the operator, Left and Right hold operands
• ExprCall: Value holds the function name, Args holds arguments

Errors

Return a non-nil error if:

• The tokens do not match the grammar
• Parentheses are unbalanced
• Extra tokens remain after parsing an expression

Notes

• Calls are only allowed on identifiers (foo(1, 2)), not on arbitrary expressions.
• Keep the parser readable. A simple recursive descent is perfect here.