Program Parser

medium · compilers, parsing, ast, statements

Program Parser

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

You will receive a token slice (including EOF). Your job is to build a Program that contains top-level declarations and statements.

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? ";"

Expression grammar is the same as earlier modules:

expr       -> equality

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

unary      -> ("!" | "-") unary | primary
primary    -> NUMBER | STRING | TRUE | FALSE | NIL | IDENT | "(" expr ")" | call
call       -> IDENT "(" args? ")"
args       -> expr ( "," expr )*

AST shape

Use the provided structs:

Program with Stmts []*Stmt
Stmt with a Kind enum and fields: Name, Expr, Body, Else, Params, VarKind
Expr with a Kind enum and fields: Value, Left, Right, Args

Rules

Function declarations are top-level only (not inside blocks).
Assignment statements are only of the form IDENT = expr;.

Errors

Return a non-nil error if:

tokens do not match the grammar
parentheses or braces are unbalanced
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
	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")
}