Program Parser v5

hard · compilers, parsing, modules

Program Parser v5

Parse tokens into an AST for the v5 language (modules, imports, exports, member access).

Function signature

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

Grammar

program     -> moduleDecl* EOF | stmt* EOF   (implicit main)

moduleDecl  -> "module" IDENT "{" moduleItem* "}"
moduleItem  -> importStmt | exportDecl | stmt
importStmt  -> "import" IDENT ("as" IDENT)? ";"
exportDecl  -> "export" (fnDecl | varDecl)

stmt        -> varDecl
            | ifStmt
            | whileStmt
            | forStmt
            | breakStmt
            | continueStmt
            | returnStmt
            | block
            | fnDecl
            | assignOrExpr

fnDecl      -> "fn" IDENT "(" params? ")" block
params      -> IDENT ("," IDENT)*

varDecl     -> ("let" | "var" | "const") IDENT ("=" expr)? ";"
assignOrExpr-> expr ("=" expr)? ";"
block       -> "{" stmt* "}"

ifStmt      -> "if" "(" expr ")" block ("else" block)?
whileStmt   -> "while" "(" expr ")" block
forStmt     -> "for" "(" forInit? ";" expr? ";" forPost? ")" block
forInit     -> varDeclNoSemi | assignOrExprNoSemi
forPost     -> assignOrExprNoSemi
breakStmt   -> "break" ";"
continueStmt-> "continue" ";"
returnStmt  -> "return" expr? ";"

expr        -> or
or          -> and ("||" and)*
and         -> equality ("&&" equality)*

equality    -> comparison ( ("==" | "!=") comparison )*
comparison  -> term ( ("<" | "<=" | ">" | ">=") term )*
term        -> factor ( ("+" | "-") factor )*
factor      -> unary ( ("*" | "/") unary )*

unary       -> ("!" | "-") unary | postfix
postfix     -> primary (call | index | member)*
call        -> "(" args? ")"
index       -> "[" expr "]"
member      -> "." IDENT
args        -> expr ("," expr)*

primary     -> NUMBER | STRING | TRUE | FALSE | NIL | IDENT
            | "(" expr ")"
            | array
            | map

array       -> "[" (expr ("," expr)*)? "]"
map         -> "{" (pair ("," pair)*)? "}"
pair        -> expr ":" expr

AST shape

Use the provided structs:

Program with Modules []*Module
Module with Name, Imports, and Stmts
Import with Name and Alias
Stmt gains Exported bool
Expr gains ExprMember for a.b

Rules

If the file has no module keyword, wrap statements into an implicit module main.
export is only valid before fn or let/var/const at the module top level.
An assignment target must be an identifier or index expression (not member access).

Errors

Return a non-nil error if:

tokens do not match the grammar
parentheses or braces are unbalanced
an assignment target is not valid
extra tokens remain after parsing

Notes

Keep the parser readable. A simple recursive descent is perfect.

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
	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
	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
}

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