Program Parser v3

hard · compilers, parsing, ast, collections, functions

Program Parser v3

Parse tokens into an AST for the v3 language (nested functions, postfix calls/indexing, array/map literals).

Function signature

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

Grammar

program     -> stmt* EOF

stmt        -> varDecl
            | ifStmt
            | whileStmt
            | 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
returnStmt  -> "return" expr? ";"

expr        -> equality

postfix     -> primary ("(" args? ")" | "[" expr "]")*
args        -> expr ("," expr)*

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

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

Equality and precedence chain

expr -> equality -> comparison -> term -> factor -> unary -> postfix -> primary

This parser must keep * / / before + / - and all binary operators at their intended precedence.

AST shape

Use the provided structs.

Program with Stmts []*Stmt
Stmt fields: Kind, VarKind, Name, Expr, Target, Body, Else, Params
Expr fields: Kind, Value, Left, Right, Args, Elems, Pairs

Behavioral rules

Function declarations are statements and may appear in blocks.
Assignment target for = must be valid:
- identifier
- index expression
- nested index forms like a[0][i] are accepted as valid target shape when on left side
L-value checks run before semicolon handling for assignment form.
Blocks are formed by { ... } in statement position.
map/array parse in primary expression position, including empty forms.

Errors

Return non-nil error for:

token/grammar mismatch
unbalanced braces/brackets/parentheses
invalid assignment target
malformed map colon/dividers
missing semicolons and missing trailing tokens

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
	TokenReturn
	TokenTrue
	TokenFalse
	TokenNil
	TokenPlus
	TokenMinus
	TokenStar
	TokenSlash
	TokenAssign
	TokenEqual
	TokenNotEqual
	TokenLess
	TokenLessEqual
	TokenGreater
	TokenGreaterEqual
	TokenBang
	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
	StmtReturn
	StmtBlock
	StmtFn
)

type Stmt struct {
	Kind    StmtKind
	VarKind VarKind
	Name    string
	Expr    *Expr
	Target  *Expr
	Body    []*Stmt
	Else    []*Stmt
	Params  []string
}

type Program struct {
	Stmts []*Stmt
}

type ExprKind int

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

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