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.go b/parser/parser.go
new file mode 100644
index 0000000..c7be53b
--- /dev/null
+++ b/parser/parser.go
@@ -0,0 +1,125 @@
+package parser
+
+import (
+ "fmt"
+ "matheval/ast"
+ "matheval/token"
+ "strconv"
+)
+
+// Parse converts a slice of tokens into an AST.
+// Returns an error for malformed expressions.
+func Parse(tokens []token.Token) (ast.Node, error) {
+ p := &parser{tokens: tokens}
+ node, err := p.expr()
+ if err != nil {
+ return nil, err
+ }
+ // Ensure all tokens have been consumed (only EOF remains).
+ if p.current().Type != token.EOF {
+ tok := p.current()
+ return nil, fmt.Errorf("unexpected token %v at position %d", tok.Type, tok.Pos)
+ }
+ return node, nil
+}
+
+// parser holds the state for a single parse operation.
+type parser struct {
+ tokens []token.Token
+ pos int
+}
+
+// current returns the token at the current position.
+func (p *parser) current() token.Token {
+ if p.pos >= len(p.tokens) {
+ return token.Token{Type: token.EOF}
+ }
+ return p.tokens[p.pos]
+}
+
+// advance moves to the next token and returns the previous one.
+func (p *parser) advance() token.Token {
+ tok := p.current()
+ p.pos++
+ return tok
+}
+
+// expect consumes a token of the given type or returns an error.
+func (p *parser) expect(typ token.Type) (token.Token, error) {
+ tok := p.current()
+ if tok.Type != typ {
+ return tok, fmt.Errorf("expected %v but got %v at position %d", typ, tok.Type, tok.Pos)
+ }
+ p.advance()
+ return tok, nil
+}
+
+// expr → term (('+' | '-') term)*
+func (p *parser) expr() (ast.Node, error) {
+ left, err := p.term()
+ if err != nil {
+ return nil, err
+ }
+ for p.current().Type == token.Plus || p.current().Type == token.Minus {
+ op := p.advance()
+ right, err := p.term()
+ if err != nil {
+ return nil, err
+ }
+ left = &ast.BinaryExpr{
+ Op: op.Type,
+ Left: left,
+ Right: right,
+ }
+ }
+ return left, nil
+}
+
+// term → factor (('*' | '/') factor)*
+func (p *parser) term() (ast.Node, error) {
+ left, err := p.factor()
+ if err != nil {
+ return nil, err
+ }
+ for p.current().Type == token.Star || p.current().Type == token.Slash {
+ op := p.advance()
+ right, err := p.factor()
+ if err != nil {
+ return nil, err
+ }
+ left = &ast.BinaryExpr{
+ Op: op.Type,
+ Left: left,
+ Right: right,
+ }
+ }
+ return left, nil
+}
+
+// factor → NUMBER | '(' expr ')'
+func (p *parser) factor() (ast.Node, error) {
+ tok := p.current()
+ switch tok.Type {
+ case token.Number:
+ p.advance()
+ val, err := strconv.ParseFloat(tok.Literal, 64)
+ if err != nil {
+ return nil, fmt.Errorf("invalid number %q at position %d: %w", tok.Literal, tok.Pos, err)
+ }
+ return &ast.NumberLit{Value: val}, nil
+
+ case token.LParen:
+ p.advance() // consume '('
+ node, err := p.expr()
+ if err != nil {
+ return nil, err
+ }
+ if _, err := p.expect(token.RParen); err != nil {
+ return nil, fmt.Errorf("missing closing parenthesis at position %d", p.current().Pos)
+ }
+ return node, nil
+
+ default:
+ return nil, fmt.Errorf("unexpected token %v at position %d", tok.Type, tok.Pos)
+ }
+}