parser: implement recursive-descent parser with tests
- Parse([]token.Token) (ast.Node, error) converts tokens to AST
- Grammar: expr → term ((+|-) term)*, term → factor ((*|/) factor)*, factor → NUMBER | '(' expr ')'
- Correct operator precedence (* / before + -)
- Left-associative operators
- Error handling: empty input, missing/unexpected parens, trailing tokens, consecutive operators
- 19 unit tests covering success and error cases
diff --git a/parser/parser_test.go b/parser/parser_test.go
new file mode 100644
index 0000000..521455b
--- /dev/null
+++ b/parser/parser_test.go
@@ -0,0 +1,473 @@
+package parser
+
+import (
+ "matheval/ast"
+ "matheval/token"
+ "testing"
+)
+
+// helper: tokenize inline for concise tests
+func tokens(toks ...token.Token) []token.Token {
+ return toks
+}
+
+func tok(typ token.Type, lit string, pos int) token.Token {
+ return token.Token{Type: typ, Literal: lit, Pos: pos}
+}
+
+// --- Success cases ---
+
+func TestParseSingleNumber(t *testing.T) {
+ toks := tokens(
+ tok(token.Number, "42", 0),
+ tok(token.EOF, "", 2),
+ )
+ node, err := Parse(toks)
+ if err != nil {
+ t.Fatalf("unexpected error: %v", err)
+ }
+ num, ok := node.(*ast.NumberLit)
+ if !ok {
+ t.Fatalf("expected *ast.NumberLit, got %T", node)
+ }
+ if num.Value != 42 {
+ t.Fatalf("expected 42, got %f", num.Value)
+ }
+}
+
+func TestParseDecimalNumber(t *testing.T) {
+ toks := tokens(
+ tok(token.Number, "3.14", 0),
+ tok(token.EOF, "", 4),
+ )
+ node, err := Parse(toks)
+ if err != nil {
+ t.Fatalf("unexpected error: %v", err)
+ }
+ num, ok := node.(*ast.NumberLit)
+ if !ok {
+ t.Fatalf("expected *ast.NumberLit, got %T", node)
+ }
+ if num.Value != 3.14 {
+ t.Fatalf("expected 3.14, got %f", num.Value)
+ }
+}
+
+func TestParseAddition(t *testing.T) {
+ // 1 + 2
+ toks := tokens(
+ tok(token.Number, "1", 0),
+ tok(token.Plus, "+", 2),
+ tok(token.Number, "2", 4),
+ tok(token.EOF, "", 5),
+ )
+ node, err := Parse(toks)
+ if err != nil {
+ t.Fatalf("unexpected error: %v", err)
+ }
+ expr, ok := node.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected *ast.BinaryExpr, got %T", node)
+ }
+ if expr.Op != token.Plus {
+ t.Fatalf("expected Plus, got %v", expr.Op)
+ }
+ assertNumber(t, expr.Left, 1)
+ assertNumber(t, expr.Right, 2)
+}
+
+func TestParseSubtraction(t *testing.T) {
+ // 5 - 3
+ toks := tokens(
+ tok(token.Number, "5", 0),
+ tok(token.Minus, "-", 2),
+ tok(token.Number, "3", 4),
+ tok(token.EOF, "", 5),
+ )
+ node, err := Parse(toks)
+ if err != nil {
+ t.Fatalf("unexpected error: %v", err)
+ }
+ expr, ok := node.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected *ast.BinaryExpr, got %T", node)
+ }
+ if expr.Op != token.Minus {
+ t.Fatalf("expected Minus, got %v", expr.Op)
+ }
+ assertNumber(t, expr.Left, 5)
+ assertNumber(t, expr.Right, 3)
+}
+
+func TestParseMultiplication(t *testing.T) {
+ // 2 * 3
+ toks := tokens(
+ tok(token.Number, "2", 0),
+ tok(token.Star, "*", 2),
+ tok(token.Number, "3", 4),
+ tok(token.EOF, "", 5),
+ )
+ node, err := Parse(toks)
+ if err != nil {
+ t.Fatalf("unexpected error: %v", err)
+ }
+ expr, ok := node.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected *ast.BinaryExpr, got %T", node)
+ }
+ if expr.Op != token.Star {
+ t.Fatalf("expected Star, got %v", expr.Op)
+ }
+ assertNumber(t, expr.Left, 2)
+ assertNumber(t, expr.Right, 3)
+}
+
+func TestParseDivision(t *testing.T) {
+ // 6 / 2
+ toks := tokens(
+ tok(token.Number, "6", 0),
+ tok(token.Slash, "/", 2),
+ tok(token.Number, "2", 4),
+ tok(token.EOF, "", 5),
+ )
+ node, err := Parse(toks)
+ if err != nil {
+ t.Fatalf("unexpected error: %v", err)
+ }
+ expr, ok := node.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected *ast.BinaryExpr, got %T", node)
+ }
+ if expr.Op != token.Slash {
+ t.Fatalf("expected Slash, got %v", expr.Op)
+ }
+ assertNumber(t, expr.Left, 6)
+ assertNumber(t, expr.Right, 2)
+}
+
+func TestParsePrecedence(t *testing.T) {
+ // 1 + 2 * 3 → 1 + (2 * 3)
+ toks := tokens(
+ tok(token.Number, "1", 0),
+ tok(token.Plus, "+", 2),
+ tok(token.Number, "2", 4),
+ tok(token.Star, "*", 6),
+ tok(token.Number, "3", 8),
+ tok(token.EOF, "", 9),
+ )
+ node, err := Parse(toks)
+ if err != nil {
+ t.Fatalf("unexpected error: %v", err)
+ }
+ // Root should be Plus
+ expr, ok := node.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected *ast.BinaryExpr, got %T", node)
+ }
+ if expr.Op != token.Plus {
+ t.Fatalf("expected Plus at root, got %v", expr.Op)
+ }
+ assertNumber(t, expr.Left, 1)
+ // Right should be Star
+ right, ok := expr.Right.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected right to be *ast.BinaryExpr, got %T", expr.Right)
+ }
+ if right.Op != token.Star {
+ t.Fatalf("expected Star, got %v", right.Op)
+ }
+ assertNumber(t, right.Left, 2)
+ assertNumber(t, right.Right, 3)
+}
+
+func TestParsePrecedenceMulFirst(t *testing.T) {
+ // 2 * 3 + 1 → (2 * 3) + 1
+ toks := tokens(
+ tok(token.Number, "2", 0),
+ tok(token.Star, "*", 2),
+ tok(token.Number, "3", 4),
+ tok(token.Plus, "+", 6),
+ tok(token.Number, "1", 8),
+ tok(token.EOF, "", 9),
+ )
+ node, err := Parse(toks)
+ if err != nil {
+ t.Fatalf("unexpected error: %v", err)
+ }
+ expr, ok := node.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected *ast.BinaryExpr, got %T", node)
+ }
+ if expr.Op != token.Plus {
+ t.Fatalf("expected Plus at root, got %v", expr.Op)
+ }
+ left, ok := expr.Left.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected left to be *ast.BinaryExpr, got %T", expr.Left)
+ }
+ if left.Op != token.Star {
+ t.Fatalf("expected Star, got %v", left.Op)
+ }
+ assertNumber(t, left.Left, 2)
+ assertNumber(t, left.Right, 3)
+ assertNumber(t, expr.Right, 1)
+}
+
+func TestParseLeftAssociativity(t *testing.T) {
+ // 1 - 2 - 3 → (1 - 2) - 3
+ toks := tokens(
+ tok(token.Number, "1", 0),
+ tok(token.Minus, "-", 2),
+ tok(token.Number, "2", 4),
+ tok(token.Minus, "-", 6),
+ tok(token.Number, "3", 8),
+ tok(token.EOF, "", 9),
+ )
+ node, err := Parse(toks)
+ if err != nil {
+ t.Fatalf("unexpected error: %v", err)
+ }
+ // Root: (1 - 2) - 3
+ expr, ok := node.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected *ast.BinaryExpr, got %T", node)
+ }
+ if expr.Op != token.Minus {
+ t.Fatalf("expected Minus at root, got %v", expr.Op)
+ }
+ assertNumber(t, expr.Right, 3)
+ left, ok := expr.Left.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected left to be *ast.BinaryExpr, got %T", expr.Left)
+ }
+ if left.Op != token.Minus {
+ t.Fatalf("expected Minus, got %v", left.Op)
+ }
+ assertNumber(t, left.Left, 1)
+ assertNumber(t, left.Right, 2)
+}
+
+func TestParseParentheses(t *testing.T) {
+ // (1 + 2) * 3
+ toks := tokens(
+ tok(token.LParen, "(", 0),
+ tok(token.Number, "1", 1),
+ tok(token.Plus, "+", 3),
+ tok(token.Number, "2", 5),
+ tok(token.RParen, ")", 6),
+ tok(token.Star, "*", 8),
+ tok(token.Number, "3", 10),
+ tok(token.EOF, "", 11),
+ )
+ node, err := Parse(toks)
+ if err != nil {
+ t.Fatalf("unexpected error: %v", err)
+ }
+ expr, ok := node.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected *ast.BinaryExpr, got %T", node)
+ }
+ if expr.Op != token.Star {
+ t.Fatalf("expected Star at root, got %v", expr.Op)
+ }
+ assertNumber(t, expr.Right, 3)
+ left, ok := expr.Left.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected left to be *ast.BinaryExpr, got %T", expr.Left)
+ }
+ if left.Op != token.Plus {
+ t.Fatalf("expected Plus, got %v", left.Op)
+ }
+ assertNumber(t, left.Left, 1)
+ assertNumber(t, left.Right, 2)
+}
+
+func TestParseNestedParentheses(t *testing.T) {
+ // ((1 + 2))
+ toks := tokens(
+ tok(token.LParen, "(", 0),
+ tok(token.LParen, "(", 1),
+ tok(token.Number, "1", 2),
+ tok(token.Plus, "+", 4),
+ tok(token.Number, "2", 6),
+ tok(token.RParen, ")", 7),
+ tok(token.RParen, ")", 8),
+ tok(token.EOF, "", 9),
+ )
+ node, err := Parse(toks)
+ if err != nil {
+ t.Fatalf("unexpected error: %v", err)
+ }
+ expr, ok := node.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected *ast.BinaryExpr, got %T", node)
+ }
+ if expr.Op != token.Plus {
+ t.Fatalf("expected Plus, got %v", expr.Op)
+ }
+ assertNumber(t, expr.Left, 1)
+ assertNumber(t, expr.Right, 2)
+}
+
+func TestParseComplexExpression(t *testing.T) {
+ // 1 + 2 * 3 - 4 / 2 → (1 + (2*3)) - (4/2)
+ toks := tokens(
+ tok(token.Number, "1", 0),
+ tok(token.Plus, "+", 2),
+ tok(token.Number, "2", 4),
+ tok(token.Star, "*", 5),
+ tok(token.Number, "3", 6),
+ tok(token.Minus, "-", 8),
+ tok(token.Number, "4", 10),
+ tok(token.Slash, "/", 11),
+ tok(token.Number, "2", 12),
+ tok(token.EOF, "", 13),
+ )
+ node, err := Parse(toks)
+ if err != nil {
+ t.Fatalf("unexpected error: %v", err)
+ }
+ // Root: (1 + (2*3)) - (4/2)
+ root, ok := node.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected *ast.BinaryExpr, got %T", node)
+ }
+ if root.Op != token.Minus {
+ t.Fatalf("expected Minus at root, got %v", root.Op)
+ }
+ // Left: 1 + (2*3)
+ left, ok := root.Left.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected left to be *ast.BinaryExpr, got %T", root.Left)
+ }
+ if left.Op != token.Plus {
+ t.Fatalf("expected Plus, got %v", left.Op)
+ }
+ assertNumber(t, left.Left, 1)
+ mul, ok := left.Right.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected *ast.BinaryExpr, got %T", left.Right)
+ }
+ if mul.Op != token.Star {
+ t.Fatalf("expected Star, got %v", mul.Op)
+ }
+ assertNumber(t, mul.Left, 2)
+ assertNumber(t, mul.Right, 3)
+ // Right: 4/2
+ div, ok := root.Right.(*ast.BinaryExpr)
+ if !ok {
+ t.Fatalf("expected right to be *ast.BinaryExpr, got %T", root.Right)
+ }
+ if div.Op != token.Slash {
+ t.Fatalf("expected Slash, got %v", div.Op)
+ }
+ assertNumber(t, div.Left, 4)
+ assertNumber(t, div.Right, 2)
+}
+
+// --- Error cases ---
+
+func TestParseEmptyInput(t *testing.T) {
+ toks := tokens(
+ tok(token.EOF, "", 0),
+ )
+ _, err := Parse(toks)
+ if err == nil {
+ t.Fatal("expected error for empty input")
+ }
+}
+
+func TestParseMissingRParen(t *testing.T) {
+ // (1 + 2
+ toks := tokens(
+ tok(token.LParen, "(", 0),
+ tok(token.Number, "1", 1),
+ tok(token.Plus, "+", 3),
+ tok(token.Number, "2", 5),
+ tok(token.EOF, "", 6),
+ )
+ _, err := Parse(toks)
+ if err == nil {
+ t.Fatal("expected error for missing right paren")
+ }
+}
+
+func TestParseUnexpectedRParen(t *testing.T) {
+ // ) 1
+ toks := tokens(
+ tok(token.RParen, ")", 0),
+ tok(token.Number, "1", 2),
+ tok(token.EOF, "", 3),
+ )
+ _, err := Parse(toks)
+ if err == nil {
+ t.Fatal("expected error for unexpected right paren")
+ }
+}
+
+func TestParseTrailingOperator(t *testing.T) {
+ // 1 +
+ toks := tokens(
+ tok(token.Number, "1", 0),
+ tok(token.Plus, "+", 2),
+ tok(token.EOF, "", 3),
+ )
+ _, err := Parse(toks)
+ if err == nil {
+ t.Fatal("expected error for trailing operator")
+ }
+}
+
+func TestParseTrailingTokens(t *testing.T) {
+ // 1 2
+ toks := tokens(
+ tok(token.Number, "1", 0),
+ tok(token.Number, "2", 2),
+ tok(token.EOF, "", 3),
+ )
+ _, err := Parse(toks)
+ if err == nil {
+ t.Fatal("expected error for trailing tokens")
+ }
+}
+
+func TestParseConsecutiveOperators(t *testing.T) {
+ // 1 + * 2
+ toks := tokens(
+ tok(token.Number, "1", 0),
+ tok(token.Plus, "+", 2),
+ tok(token.Star, "*", 4),
+ tok(token.Number, "2", 6),
+ tok(token.EOF, "", 7),
+ )
+ _, err := Parse(toks)
+ if err == nil {
+ t.Fatal("expected error for consecutive operators")
+ }
+}
+
+func TestParseEmptyParens(t *testing.T) {
+ // ()
+ toks := tokens(
+ tok(token.LParen, "(", 0),
+ tok(token.RParen, ")", 1),
+ tok(token.EOF, "", 2),
+ )
+ _, err := Parse(toks)
+ if err == nil {
+ t.Fatal("expected error for empty parentheses")
+ }
+}
+
+// --- Helper ---
+
+func assertNumber(t *testing.T, node ast.Node, expected float64) {
+ t.Helper()
+ num, ok := node.(*ast.NumberLit)
+ if !ok {
+ t.Fatalf("expected *ast.NumberLit, got %T", node)
+ }
+ if num.Value != expected {
+ t.Fatalf("expected %f, got %f", expected, num.Value)
+ }
+}