package main import ( "errors" ) var unexpectedEOF = errors.New("unexpected EOF") func (t *tokens) consumeToken() (token, bool) { if t.index >= len(t.toks) { tok, ok := <-t.src if !ok { return token{}, false } t.toks = append(t.toks, tok) } tok := t.toks[t.index] t.index++ return tok, true } func (t *tokens) unreadToken() { t.index-- } func (t *tokens) current() token { return t.toks[t.index-1] } func (t *tokens) eof() bool { _, ok := t.consumeToken() if ok { t.unreadToken() } return !ok } func (t *tokens) match(kind tokenKind) (bool, error) { tok, ok := t.consumeToken() if !ok { return false, unexpectedEOF } return tok.kind == kind, nil } func (t *tokens) mustMatch(kind tokenKind) error { ok, err := t.match(kind) if err != nil { return err } if !ok { return expected{want: kind, got: t.current()} } return nil } func parse(toks *tokens, root chan<- *rootExpr, errs chan<- error) { defer wg.Done() root <- parseRoot(toks, errs) } func parseRoot(toks *tokens, errs chan<- error) *rootExpr { toplevels := make([]expression, 0) for !toks.eof() { if toplevel := parseToplevel(toks, errs); toplevel != nil { toplevels = append(toplevels, toplevel) } } return &rootExpr{ toplevels: toplevels, } } func parseToplevel(toks *tokens, errs chan<- error) expression { function := parseFunction(toks, errs) if function == nil { errs <- expectedToplevel{got: toks.current()} return nil } return function } func parseFunction(toks *tokens, errs chan<- error) *functionExpr { var link linkage ok, err := toks.match(export) if err != nil { errs <- err return nil } if ok { link = exportLinkage } else { toks.unreadToken() } ok, err = toks.match(function) if err != nil { errs <- err return nil } if !ok { return nil } nameTok, ok := toks.consumeToken() if !ok { errs <- unexpectedEOF return nil } if nameTok.kind != identifier { errs <- expected{want: identifier, got: nameTok} return nil } if err := toks.mustMatch(lparen); err != nil { errs <- err return nil } var params *paramExpr ok, err = toks.match(rparen) if err != nil { errs <- err return nil } if !ok { toks.unreadToken() params, err = parseParam(toks) if err != nil { errs <- err return nil } if err := toks.mustMatch(rparen); err != nil { errs <- err return nil } } returnTypeTok, ok := toks.consumeToken() if !ok { errs <- unexpectedEOF return nil } if returnTypeTok.kind != identifier { errs <- expected{want: identifier, got: returnTypeTok} return nil } blk, err := parseBlock(toks) if err != nil { errs <- err return nil } return &functionExpr{ link: link, name: nameTok.value, params: params, returnType: returnTypeTok.value, blk: blk, } } func parseParam(toks *tokens) (*paramExpr, error) { nameTok, ok := toks.consumeToken() if !ok { return nil, unexpectedEOF } if nameTok.kind != identifier { return nil, expected{want: identifier, got: nameTok} } typeTok, ok := toks.consumeToken() if !ok { return nil, unexpectedEOF } if typeTok.kind != identifier { return nil, expected{want: identifier, got: typeTok} } var next *paramExpr ok, err := toks.match(comma) if err != nil { return nil, err } if ok { next, err = parseParam(toks) if err != nil { return nil, err } } else { toks.unreadToken() } return ¶mExpr{ name: nameTok.value, typ: typeTok.value, next: next, }, nil } func parseBlock(toks *tokens) (*blockExpr, error) { if err := toks.mustMatch(lbrace); err != nil { return nil, err } var expectStmt bool stmts := make([]statementExpr, 0) stmt, err := parseStatement(toks) if err != nil { return nil, err } if stmt != nil { stmts = append(stmts, stmt) } else { expectStmt = true } for stmt != nil { stmt, err = parseStatement(toks) if err != nil { return nil, err } if stmt == nil { expectStmt = true break } stmts = append(stmts, stmt) } if err := toks.mustMatch(rbrace); err != nil { if expectStmt { return nil, expectedStatement{got: toks.current()} } return nil, err } return &blockExpr{stmts: stmts}, nil } func parseStatement(toks *tokens) (statementExpr, error) { stmt, err := parseReturnStmt(toks) if err != nil { return nil, err } if stmt != nil { if err := toks.mustMatch(semicolon); err != nil { return nil, err } return stmt, nil } return nil, nil } func parseReturnStmt(toks *tokens) (*returnStmt, error) { ok, err := toks.match(ret) if err != nil { return nil, err } if !ok { toks.unreadToken() return nil, nil } expr, err := parseExpression(toks) if err != nil { return nil, err } return &returnStmt{value: expr, ln: toks.current().line}, nil } func parseExpression(toks *tokens) (exprExpr, error) { return parseEquality(toks) } func parseEquality(toks *tokens) (*equalityExpr, error) { lhs, err := parseComparison(toks) if err != nil { return nil, err } line := toks.current().line rhss := make([]*equalityRhs, 0) for { rhs, err := parseEqualityRhs(toks) if err != nil { return nil, err } if rhs == nil { break } rhss = append(rhss, rhs) } return &equalityExpr{lhs: lhs, rhs: rhss, ln: line}, nil } func parseEqualityRhs(toks *tokens) (*equalityRhs, error) { eq, err := toks.match(doubleEquals) if err != nil { return nil, err } if !eq { toks.unreadToken() } neq, err := toks.match(bangEquals) if err != nil { return nil, err } if !neq { toks.unreadToken() return nil, nil } value, err := parseComparison(toks) if err != nil { return nil, err } var op equalityOp if eq { op = equalTo } else if neq { op = notEqualTo } return &equalityRhs{op: op, value: value}, nil } func parseComparison(toks *tokens) (*comparisonExpr, error) { lhs, err := parseTerm(toks) if err != nil { return nil, err } line := toks.current().line rhs, err := parseComparisonRhs(toks) if err != nil { return nil, err } return &comparisonExpr{lhs: lhs, rhs: rhs, ln: line}, nil } func parseComparisonRhs(toks *tokens) (*comparisonRhs, error) { lt, err := toks.match(langle) if err != nil { return nil, err } if !lt { toks.unreadToken() } le, err := toks.match(langleEquals) if err != nil { return nil, err } if !le { toks.unreadToken() } gt, err := toks.match(rangle) if err != nil { return nil, err } if !gt { toks.unreadToken() } ge, err := toks.match(rangleEquals) if err != nil { return nil, err } if !ge { toks.unreadToken() return nil, nil } value, err := parseTerm(toks) if err != nil { return nil, err } var op comparisonOp if lt { op = lessThan } else if le { op = lessThanOrEqualTo } else if gt { op = greaterThan } else if ge { op = greaterThanOrEqualTo } return &comparisonRhs{op: op, value: value}, nil } func parseTerm(toks *tokens) (*termExpr, error) { lhs, err := parseNumeral(toks) if err != nil { return nil, err } line := toks.current().line rhss := make([]*termRhs, 0) for { rhs, err := parseTermRhs(toks) if err != nil { return nil, err } if rhs == nil { break } rhss = append(rhss, rhs) } return &termExpr{lhs: lhs, rhs: rhss, ln: line}, nil } func parseTermRhs(toks *tokens) (*termRhs, error) { lsh, err := toks.match(doubleLangle) if err != nil { return nil, err } if !lsh { toks.unreadToken() } rsh, err := toks.match(doubleRangle) if err != nil { return nil, err } if !rsh { toks.unreadToken() return nil, nil } value, err := parseNumeral(toks) if err != nil { return nil, err } var op shiftOp if lsh { op = shiftLeft } else if rsh { op = shiftRight } return &termRhs{op: op, value: value}, nil } func parseNumeral(toks *tokens) (*numeralExpr, error) { lhs, err := parseFactor(toks) if err != nil { return nil, err } line := toks.current().line rhss := make([]*numeralRhs, 0) for { rhs, err := parseNumeralRhs(toks) if err != nil { return nil, err } if rhs == nil { break } rhss = append(rhss, rhs) } return &numeralExpr{lhs: lhs, rhs: rhss, ln: line}, nil } func parseNumeralRhs(toks *tokens) (*numeralRhs, error) { doAdd, err := toks.match(plus) if err != nil { return nil, err } var doSubtract bool if !doAdd { toks.unreadToken() doSubtract, err = toks.match(minus) if err != nil { return nil, err } if !doSubtract { toks.unreadToken() return nil, nil } } value, err := parseFactor(toks) if err != nil { return nil, err } var op addSubOp if doAdd { op = add } else if doSubtract { op = subtract } return &numeralRhs{op: op, value: value}, nil } func parseFactor(toks *tokens) (*factorExpr, error) { lhs, err := parseUnary(toks) if err != nil { return nil, err } line := toks.current().line rhss := make([]*factorRhs, 0) for { rhs, err := parseFactorRhs(toks) if err != nil { return nil, err } if rhs == nil { break } rhss = append(rhss, rhs) } return &factorExpr{lhs: lhs, rhs: rhss, ln: line}, nil } func parseFactorRhs(toks *tokens) (*factorRhs, error) { mul, err := toks.match(star) if err != nil { return nil, err } var div bool if !mul { toks.unreadToken() div, err = toks.match(slash) if err != nil { return nil, err } if !div { toks.unreadToken() return nil, nil } } value, err := parseUnary(toks) if err != nil { return nil, err } var op mulDivOp if mul { op = multiply } else if div { op = divide } return &factorRhs{op: op, value: value}, nil } func parseUnary(toks *tokens) (*unaryExpr, error) { neg, err := toks.match(minus) if err != nil { return nil, err } line := toks.current().line if !neg { toks.unreadToken() } invLog, err := toks.match(bang) if err != nil { return nil, err } if !invLog { toks.unreadToken() } invBits, err := toks.match(tilde) if err != nil { return nil, err } if !invBits { toks.unreadToken() } value, err := parsePrimary(toks) if err != nil { return nil, err } var op unaryOp if neg { op = negate } else if invLog { op = invertLogical } else if invBits { op = invertBits } return &unaryExpr{op: op, value: value, ln: line}, nil } func parsePrimary(toks *tokens) (primaryExpr, error) { grp, err := parseGrouping(toks) if err != nil { return nil, err } if grp != nil { return grp, nil } lit, err := parseLiteral(toks) if err != nil { return nil, err } if lit != nil { return lit, nil } return nil, expectedPrimary{got: toks.current()} } func parseGrouping(toks *tokens) (*groupingExpr, error) { ok, err := toks.match(lparen) if err != nil { return nil, err } if !ok { toks.unreadToken() return nil, nil } line := toks.current().line expr, err := parseExpression(toks) if err != nil { return nil, err } if err := toks.mustMatch(rparen); err != nil { return nil, err } return &groupingExpr{inner: expr, ln: line}, nil } func parseLiteral(toks *tokens) (literalExpr, error) { s, err := parseString(toks) if err != nil { return nil, err } if s != nil { return s, nil } num, err := parseNumber(toks) if err != nil { return nil, err } if num != nil { return num, nil } return nil, nil } func parseString(toks *tokens) (*stringExpr, error) { tok, ok := toks.consumeToken() if !ok { return nil, unexpectedEOF } toks.unreadToken() segments := make([]string, 0) for { segment, err := parseStringSegment(toks) if err != nil { return nil, err } if segment == nil { break } segments = append(segments, *segment) } if len(segments) == 0 { return nil, nil } return &stringExpr{segments: segments, ln: tok.line}, nil } func parseStringSegment(toks *tokens) (*string, error) { tok, ok := toks.consumeToken() if !ok { return nil, unexpectedEOF } if tok.kind != str { toks.unreadToken() return nil, nil } return &tok.value, nil } func parseNumber(toks *tokens) (*numberExpr, error) { typeTok, ok := toks.consumeToken() if !ok { return nil, unexpectedEOF } if typeTok.kind != identifier { return nil, expected{want: identifier, got: typeTok} } if err := toks.mustMatch(lparen); err != nil { return nil, err } numTok, ok := toks.consumeToken() if !ok { return nil, unexpectedEOF } if numTok.kind != number { return nil, expected{want: number, got: numTok} } if err := toks.mustMatch(rparen); err != nil { return nil, err } return &numberExpr{typ: typeTok.value, s: numTok.value, ln: typeTok.line}, nil }