Initial commit

1 files changed, 766 insertions, 0 deletions

diff --git a/parse.go b/parse.go
new file mode 100644
index 0000000..2abd111
--- /dev/null
+++ b/parse.go
@@ -0,0 +1,766 @@
+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 &paramExpr{
+		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
+}