Program Parser v4

hard · compilers, parsing, ast, control flow

Program Parser v4

Parse tokens into an AST for the v4 language (for loops, break/continue, && / ||).

Function signature

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

Grammar

program     -> stmt* EOF

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 ("(" args? ")" | "[" expr "]")*
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 Stmts []*Stmt
Stmt with fields: Kind, VarKind, Name, Expr, Target, Body, Else, Params, Init, Post, Cond
Expr with fields: Kind, Value, Left, Right, Args, Elems, Pairs
MapPair with Key, Value

Rules

Functions are statements and can appear in any block.
An assignment statement must have a valid target: identifier or index expression.

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
	TokenTrue
	TokenFalse
	TokenNil
	TokenPlus
	TokenMinus
	TokenStar
	TokenSlash
	TokenAssign
	TokenEqual
	TokenNotEqual
	TokenLess
	TokenLessEqual
	TokenGreater
	TokenGreaterEqual
	TokenBang
	TokenAndAnd
	TokenOrOr
	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
	VarKind VarKind
	Name    string
	Expr    *Expr
	Target  *Expr
	Body    []*Stmt
	Else    []*Stmt
	Params  []string
	Init    *Stmt
	Post    *Stmt
	Cond    *Expr
}

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