Program Parser v6

hard · compilers, parsing, types

Program Parser v6

Parse tokens into an AST for the v6 language (modules + type annotations).

Function signature

func Parse(tokens []Token) (*Program, error)

New syntax

let x: number = 1;
fn add(a: number, b: number) -> number { return a + b; }
let xs: array<number> = [1,2];
let m: map<string, number> = {"k": 1};

Type grammar

type       -> simple | fnType
simple     -> number | bool | string | nil
           | array<type>
           | map<type, type>
fnType     -> fn("typeList?") -> type

AST additions

Type tree
Stmt.TypeAnn *Type for variables
Stmt.ParamTypes []*Type and Stmt.ReturnType *Type for functions

Rules

Function parameters must include type annotations.
Function return type is required after ->.
Type names are identifiers (number, bool, string, array, map).

Other grammar rules match v5.

package solution

import "fmt"

type TokenKind int

const (
	TokenEOF TokenKind = iota
	TokenIdent
	TokenNumber
	TokenString
	TokenLet
	TokenVar
	TokenConst
	TokenFn
	TokenIf
	TokenElse
	TokenWhile
	TokenFor
	TokenReturn
	TokenBreak
	TokenContinue
	TokenModule
	TokenImport
	TokenExport
	TokenAs
	TokenTrue
	TokenFalse
	TokenNil
	TokenPlus
	TokenMinus
	TokenStar
	TokenSlash
	TokenAssign
	TokenEqual
	TokenNotEqual
	TokenLess
	TokenLessEqual
	TokenGreater
	TokenGreaterEqual
	TokenBang
	TokenAndAnd
	TokenOrOr
	TokenDot
	TokenArrow
	TokenLParen
	TokenRParen
	TokenLBrace
	TokenRBrace
	TokenLBracket
	TokenRBracket
	TokenComma
	TokenSemicolon
	TokenColon
)

type Token struct {
	Kind   TokenKind
	Lexeme string
}

type VarKind int

const (
	VarLet VarKind = iota
	VarVar
	VarConst
)

type StmtKind int

const (
	StmtVar StmtKind = iota
	StmtAssign
	StmtExpr
	StmtIf
	StmtWhile
	StmtFor
	StmtBreak
	StmtContinue
	StmtReturn
	StmtBlock
	StmtFn
)

type Stmt struct {
	Kind       StmtKind
	Exported   bool
	VarKind    VarKind
	Name       string
	Expr       *Expr
	Target     *Expr
	Body       []*Stmt
	Else       []*Stmt
	Params     []string
	ParamTypes []*Type
	ReturnType *Type
	TypeAnn    *Type
	Init       *Stmt
	Post       *Stmt
	Cond       *Expr
}

type Program struct {
	Modules []*Module
}

type Module struct {
	Name    string
	Imports []Import
	Stmts   []*Stmt
}

type Import struct {
	Name  string
	Alias string
}

type ExprKind int

const (
	ExprNumber ExprKind = iota
	ExprString
	ExprBool
	ExprNil
	ExprIdent
	ExprUnary
	ExprBinary
	ExprCall
	ExprArray
	ExprMap
	ExprIndex
	ExprMember
)

type MapPair struct {
	Key   *Expr
	Value *Expr
}

type Expr struct {
	Kind  ExprKind
	Value string
	Left  *Expr
	Right *Expr
	Args  []*Expr
	Elems []*Expr
	Pairs []MapPair
}

type TypeKind int

const (
	TypeNumber TypeKind = iota
	TypeBool
	TypeString
	TypeNil
	TypeArray
	TypeMap
	TypeFunc
)

type Type struct {
	Kind   TypeKind
	Elem   *Type
	Key    *Type
	Value  *Type
	Params []*Type
	Return *Type
}

// Parse turns tokens into a program AST.
func Parse(tokens []Token) (*Program, error) {
	// TODO: implement the parser.
	return nil, fmt.Errorf("not implemented")
}