Program Parser v5

hard · compilers, parsing, modules

Program Parser v5

Build a parser for the v5 language (modules, imports, exports, and member access).

Function signature

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

Parse mode split

Parse must decide unit shape once at the start:

If first token is module, parse module mode: repeated moduleDecl until EOF.
Otherwise parse implicit main mode: parse statements and wrap them in Program.Modules = [{Name: "main", ...}].

There is no mid-stream switch between these modes.

Grammar

program     -> moduleDecl* | stmts (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)*)? "]"
pair        -> expr ":" expr
map         -> "{" (pair ("," pair)*)? "}"

AST shape

Use exactly the provided shapes.

Program has Modules []*Module
Module{Name string, Imports []Import, Stmts []*Stmt}
Import{Name, Alias string} (default alias is import name when as is missing)
Stmt has Exported bool
ExprMember for dotted access nodes (a.b) using Left + Value

Behavioral rules (what to enforce)

Module boundaries

in module mode: parse module by module; inside module parse imports/exports/items.
module body accepts import/export statements and normal statements.
outside module mode (implicit main), there are only module-level statements.

Exports

export accepted only before function and variable declarations.
export if (...) {} and export import ... must be rejected by parser.

Imports

import name uses alias name
import name as alias; sets alias
import declarations require semicolon and reject missing semicolons

Member access and postfix chaining

parse a.b, f()[0], m.get(1).x[2] as one chain through postfix loop.
chain is left associative by iterative parse.

Assignment target constraint

only identifier or index may be assignment target.
member access is not treated as a parse-time l-value.

Errors

Return non-nil error if any of the following happen:

tokens mismatch grammar
unmatched braces/parentheses/brackets
assignment target is not valid
unexpected tokens remain
import/export statement shape invalid

Before implementation

Use the module’s worked reconstruction and independent debugging lab to predict an intermediate artifact first. Preserve one failing counterexample while implementing the stated API. The lesson’s transfer task uses a fresh case after the guided trace.

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