| 1 | package calc |
| 2 | |
| 3 | import ( |
| 4 | "fmt" |
| 5 | "strings" |
| 6 | ) |
| 7 | |
| 8 | // Parse compiles a formula's source text (without a leading "=") into an |
| 9 | // AST. Errors report only a byte position and a reason; the formula's own |
| 10 | // content never appears in an error string. |
| 11 | // |
| 12 | // Precedence, loosest to tightest: comparison (= <> < <= > >=), then |
| 13 | // concatenation (&), then + -, then * /, then ^ (right-associative), then |
| 14 | // unary minus, then primary. Unary minus binding tighter than ^ matches |
| 15 | // spreadsheet convention (Excel: -2^2 = 4, not -4), which is the reverse |
| 16 | // of most programming languages and is easy to get wrong later, so it is |
| 17 | // pinned by TestParseUnaryBindsTighterThanPower. |
| 18 | func Parse(src string) (Node, error) { |
| 19 | toks, err := lex(src) |
| 20 | if err != nil { |
| 21 | return nil, err |
| 22 | } |
| 23 | p := &parser{toks: toks} |
| 24 | p.cur = toks[0] |
| 25 | |
| 26 | n, err := p.parseComparison() |
| 27 | if err != nil { |
| 28 | return nil, err |
| 29 | } |
| 30 | if p.cur.kind != tEOF { |
| 31 | return nil, p.errorf("unexpected trailing input") |
| 32 | } |
| 33 | return n, nil |
| 34 | } |
| 35 | |
| 36 | type parser struct { |
| 37 | toks []token |
| 38 | pos int |
| 39 | cur token |
| 40 | } |
| 41 | |
| 42 | func (p *parser) advance() { |
| 43 | p.pos++ |
| 44 | if p.pos < len(p.toks) { |
| 45 | p.cur = p.toks[p.pos] |
| 46 | } else { |
| 47 | p.cur = token{kind: tEOF, pos: p.cur.pos} |
| 48 | } |
| 49 | } |
| 50 | |
| 51 | func (p *parser) errorf(reason string) error { |
| 52 | return fmt.Errorf("calc: parse error at position %d: %s", p.cur.pos, reason) |
| 53 | } |
| 54 | |
| 55 | var comparisonOps = map[string]bool{"=": true, "<>": true, "<": true, "<=": true, ">": true, ">=": true} |
| 56 | var concatOps = map[string]bool{"&": true} |
| 57 | var additiveOps = map[string]bool{"+": true, "-": true} |
| 58 | var termOps = map[string]bool{"*": true, "/": true} |
| 59 | |
| 60 | // parseBinaryLevel implements one left-associative precedence level shared |
| 61 | // by comparison, concatenation, addition and multiplication: parse one |
| 62 | // operand via next, then fold in any run of same-level operators. |
| 63 | func (p *parser) parseBinaryLevel(ops map[string]bool, next func() (Node, error)) (Node, error) { |
| 64 | left, err := next() |
| 65 | if err != nil { |
| 66 | return nil, err |
| 67 | } |
| 68 | for p.cur.kind == tOp && ops[p.cur.op] { |
| 69 | op := p.cur.op |
| 70 | p.advance() |
| 71 | right, err := next() |
| 72 | if err != nil { |
| 73 | return nil, err |
| 74 | } |
| 75 | left = &Binary{Op: op, Left: left, Right: right} |
| 76 | } |
| 77 | return left, nil |
| 78 | } |
| 79 | |
| 80 | func (p *parser) parseComparison() (Node, error) { |
| 81 | return p.parseBinaryLevel(comparisonOps, p.parseConcat) |
| 82 | } |
| 83 | |
| 84 | func (p *parser) parseConcat() (Node, error) { |
| 85 | return p.parseBinaryLevel(concatOps, p.parseAdditive) |
| 86 | } |
| 87 | |
| 88 | func (p *parser) parseAdditive() (Node, error) { |
| 89 | return p.parseBinaryLevel(additiveOps, p.parseTerm) |
| 90 | } |
| 91 | |
| 92 | func (p *parser) parseTerm() (Node, error) { |
| 93 | return p.parseBinaryLevel(termOps, p.parsePower) |
| 94 | } |
| 95 | |
| 96 | // parsePower is right-associative: 2^3^2 = 2^(3^2). |
| 97 | func (p *parser) parsePower() (Node, error) { |
| 98 | left, err := p.parseUnary() |
| 99 | if err != nil { |
| 100 | return nil, err |
| 101 | } |
| 102 | if p.cur.kind == tOp && p.cur.op == "^" { |
| 103 | p.advance() |
| 104 | right, err := p.parsePower() |
| 105 | if err != nil { |
| 106 | return nil, err |
| 107 | } |
| 108 | return &Binary{Op: "^", Left: left, Right: right}, nil |
| 109 | } |
| 110 | return left, nil |
| 111 | } |
| 112 | |
| 113 | // parseUnary binds tighter than parsePower: see the precedence note on Parse. |
| 114 | func (p *parser) parseUnary() (Node, error) { |
| 115 | if p.cur.kind == tOp && p.cur.op == "-" { |
| 116 | p.advance() |
| 117 | x, err := p.parseUnary() |
| 118 | if err != nil { |
| 119 | return nil, err |
| 120 | } |
| 121 | return &Unary{Op: "-", X: x}, nil |
| 122 | } |
| 123 | return p.parsePrimary() |
| 124 | } |
| 125 | |
| 126 | func (p *parser) parsePrimary() (Node, error) { |
| 127 | switch p.cur.kind { |
| 128 | case tNum: |
| 129 | v := p.cur.num |
| 130 | p.advance() |
| 131 | return &Num{V: v}, nil |
| 132 | case tStr: |
| 133 | v := p.cur.str |
| 134 | p.advance() |
| 135 | return &Str{V: v}, nil |
| 136 | case tRef: |
| 137 | return p.parseRefOrRange() |
| 138 | case tLParen: |
| 139 | p.advance() |
| 140 | inner, err := p.parseComparison() |
| 141 | if err != nil { |
| 142 | return nil, err |
| 143 | } |
| 144 | if p.cur.kind != tRParen { |
| 145 | return nil, p.errorf("expected closing parenthesis") |
| 146 | } |
| 147 | p.advance() |
| 148 | return inner, nil |
| 149 | case tIdent: |
| 150 | return p.parseIdentOrCall() |
| 151 | default: |
| 152 | return nil, p.errorf("unexpected token, want expression") |
| 153 | } |
| 154 | } |
| 155 | |
| 156 | func (p *parser) parseRefOrRange() (Node, error) { |
| 157 | from := refNode(p.cur.ref) |
| 158 | p.advance() |
| 159 | if p.cur.kind != tColon { |
| 160 | return from, nil |
| 161 | } |
| 162 | p.advance() |
| 163 | if p.cur.kind != tRef { |
| 164 | return nil, p.errorf("expected reference after ':'") |
| 165 | } |
| 166 | to := refNode(p.cur.ref) |
| 167 | p.advance() |
| 168 | return &Range{From: from, To: to}, nil |
| 169 | } |
| 170 | |
| 171 | func refNode(r refToken) *Ref { |
| 172 | return &Ref{ColPos: r.colPos, RowPos: r.rowPos, AbsCol: r.absCol, AbsRow: r.absRow} |
| 173 | } |
| 174 | |
| 175 | func (p *parser) parseIdentOrCall() (Node, error) { |
| 176 | name := p.cur.ident |
| 177 | p.advance() |
| 178 | |
| 179 | switch strings.ToUpper(name) { |
| 180 | case "TRUE": |
| 181 | return &Bool{V: true}, nil |
| 182 | case "FALSE": |
| 183 | return &Bool{V: false}, nil |
| 184 | } |
| 185 | |
| 186 | if p.cur.kind != tLParen { |
| 187 | return nil, p.errorf("unexpected identifier, want function call") |
| 188 | } |
| 189 | args, err := p.parseCallArgs() |
| 190 | if err != nil { |
| 191 | return nil, err |
| 192 | } |
| 193 | return &Call{Name: strings.ToUpper(name), Args: args}, nil |
| 194 | } |
| 195 | |
amadan