Program Parser

medium · compilers, parsing, ast, statements

Program Parser

Parse a token stream into an AST for the expanded language (v2).

Function signature

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

Grammar

program    -> decl* EOF

decl       -> funDecl | stmt
funDecl    -> "fn" IDENT "(" params? ")" block
params     -> IDENT ("," IDENT)*

stmt       -> varDecl
           | ifStmt
           | whileStmt
           | returnStmt
           | block
           | assignStmt
           | exprStmt

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

ifStmt     -> "if" "(" expr ")" block ("else" block)?
whileStmt  -> "while" "(" expr ")" block
returnStmt -> "return" expr? ";"

expr       -> equality

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

primary    -> NUMBER | STRING | TRUE | FALSE | NIL
           | IDENT ["(" args? ")"]
           | "(" expr ")"

args       -> expr ("," expr)*

IDENT may be followed by a call suffix in this module (f(...)). Full postfix operators come in later modules.

AST shape

Use the provided structs.

Program with Stmts []*Stmt
Stmt with Kind, VarKind, Name, Expr, Body, Else, Params
Expr with Kind, Value, Left, Right, Args

Rules

Parse mode

top-level parseDecl drives everything. fn at top level is special and always parses as function declaration.
other top-level tokens route to statement parsing.

Statement disambiguation

if current token is identifier and next token is =: parse assignment
otherwise parse expression statement

Function declarations

top-level only in this version; function bodies use statement parsing recursively.

Call parsing

callee is an identifier with optional argument list.

Error handling

return explicit errors for:
- unmatched parentheses/braces
- missing semicolons/equals and malformed params
- unexpected/unknown token in grammar position

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
	TokenComma
	TokenSemicolon
)

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

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

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