Getting the basics down: compiler from scratch pt. 1

 1public abstract sealed class Ast permits BlockAst, ExprAst, FunctionAst,
 2        IdentAst, ProgramAst, StmtAst, TyAst, VarDeclAst {
 3
 4    // An AST has a parent node, unless it is the root `ProgramAst`
 5    private Ast parent;
 6
 7    // An AST has zero or more children, all of which are also AST nodes
 8    public abstract List<? extends Ast> getChildren();
 9
10    // Utility to search down the AST
11    public <T extends Ast> T findDescendant(Class<T> cls) {
12        // ...
13    }
14
15    // Utility to search up the AST
16    public <T extends Ast> T findAncestor(Class<T> cls) {
17        // ...
18    }
19}

 1public final class FunctionAst extends Ast {
 2
 3    private IdentAst name;
 4
 5    // VarDecl means variable declaration
 6    private List<VarDeclAst> params;
 7
 8    private TyAst returnTy;
 9
10    private BlockAst body;
11
12    public FunctionAst(IdentAst name, List<VarDeclAst> params,
13            TyAst returnTy, BlockAst body) {
14        this.name = name;
15        this.params = new ArrayList<>(params);
16        this.returnTy = returnTy;
17        this.body = body;
18    }
19
20    @Override
21    public List<? extends Ast> getChildren() {
22        var results = new ArrayList<Ast>();
23        results.add(name);
24        results.addAll(params);
25        results.add(returnTy);
26        results.add(body);
27        return results;
28    }
29}

 1public abstract sealed class Ast
 2        permits /* ... */ {
 3
 4    // ...
 5
 6    public void assignParents() {
 7        for (var child : getChildren()) {
 8            child.setParent(this);
 9            child.assignParents();
10        }
11    }
12}

 1public class Lexer {
 2
 3    // The characters that are ignored by the lexer
 4    private static final Set<Character> WHITESPACE =
 5        Set.of(' ', '\t', '\n', '\r');
 6
 7    // Tokens that always match up to the same string
 8    private static final Map<String, Token> SYMBOLS =
 9        Map.of(
10            "(", new OpenParenToken(),
11            ")", new CloseParenToken(),
12            "{", new OpenBraceToken(),
13            "}", new CloseBraceToken(),
14            ";", new SemicolonToken(),
15            ",", new CommaToken(),
16            "=", new EqualsToken());
17
18    // Keywords that should be used instead of an identifier
19    // where applicable
20    private static final Map<String, Token> KEYWORDS =
21        Map.of(
22            "int", new KwIntToken(),
23            "return", new KwReturnToken());
24
25    // The entire input source code
26    private final String input;
27
28    // The index into the source code we are currently up to
29    private int position = 0;
30
31    public Lexer(String input) {
32        this.input = input;
33    }
34
35    // Creates a copy of the lexer so we can rewind
36    public Lexer(Lexer other) {
37        this.input = other.input;
38        this.position = other.position;
39    }
40
41    public Token peek() throws LexException {
42        return new Lexer(this).next();
43    }
44
45    public Token next() throws LexException {
46        // ...
47    }
48
49    private Token lexSymbol() {
50        // ...
51    }
52
53    private Token lexWord() {
54        // ..
55    }
56
57    private Token lexIntLiteral() {
58        // ..
59    }
60
61    private void skipWhitespace() {
62        // ..
63    }
64}

  1public class Parser {
  2
  3    private Lexer lexer;
  4
  5    public Parser(Lexer lexer) {
  6        this.lexer = lexer;
  7    }
  8
  9    // Each piece of syntax has its own function, and most of
 10    // those functions conform to this interface
 11    private interface ParseFunction<T extends Ast> {
 12
 13        // This attempts to parse out a piece of syntax
 14        // by advancing the lexer. If there is an error
 15        // (e.g. missing semicolon), then we throw an
 16        // exception. Given an error, we might like to
 17        // try to reset/rewind the lexer and try parsing
 18        // something else, but this method is not
 19        // responsible for this resetting/rewinding
 20        T parse(Parser parser) throws ParseException;
 21    }
 22
 23    public static ProgramAst parse(String syntax)
 24            throws ParseException {
 25        return new Parser(new Lexer(syntax)).parse();
 26    }
 27
 28    public ProgramAst parse() throws ParseException {
 29        var ast = parseProgram();
 30        // The `parent` field doesn't get assigned in the
 31        // constructor, so we must fix it up here
 32        ast.assignParents();
 33        return ast;
 34    }
 35
 36    // This is what we will use for parsing individual tokens
 37    private <T extends Token> T expect(Class<T> cls)
 38            throws ParseException {
 39        var next = lexer.peek();
 40
 41        if (!cls.isInstance(next)) {
 42            throw new ParseException(
 43                "expected " + cls + " but found " + next);
 44        }
 45
 46        return (T) lexer.next();
 47    }
 48
 49    // Sometimes we don't want to catch a parsing exception
 50    // and try something else. For example, if we cant parse
 51    // an assignment, maybe we want to parse an integer
 52    // literal instead? This handles catching the exception
 53    // and putting the lexer back in its original state. We
 54    // use this to implement "A / B" rules from the PEG grammar
 55    private <T extends Ast> T attempt(ParseFunction<T> f) {
 56        var copy = new Parser(new Lexer(lexer));
 57
 58        try {
 59            var result = f.parse(copy);
 60            lexer = copy.lexer;
 61            return result;
 62        } catch (ParseException e) {
 63            return null;
 64        }
 65    }
 66
 67    public ProgramAst parseProgram() throws ParseException {
 68        // ...
 69    }
 70
 71    private FunctionAst parseFunction() throws ParseException {
 72        var returnTy = parseTy();
 73        var name = parseIdent();
 74        var params = new ArrayList<VarDeclAst>();
 75
 76        expect(OpenParenToken.class);
 77
 78        // This is how we parse "VarDecl (`,` VarDecl)*"
 79        while (!(lexer.peek() instanceof CloseParenToken)) {
 80            if (!params.isEmpty()) {
 81                expect(CommaToken.class);
 82            }
 83
 84            params.add(parseVarDecl());
 85        }
 86
 87        expect(CloseParenToken.class);
 88
 89        var body = parseBlock();
 90
 91        return new FunctionAst(name, params, returnTy, body);
 92    }
 93
 94    private VarDeclAst parseVarDecl() throws ParseException {
 95        // ...
 96    }
 97
 98    private TyAst parseTy() throws ParseException {
 99        // ...
100    }
101
102    private TyAst parseKwTy() throws ParseException {
103        // ...
104    }
105
106    private BlockAst parseBlock() throws ParseException {
107        // ...
108    }
109
110    private StmtAst parseStmt() throws ParseException {
111        // ...
112    }
113
114    private VarDeclStmtAst parseVarDeclStmt()
115            throws ParseException {
116        // ...
117    }
118
119    private ReturnStmtAst parseReturnStmt()
120            throws ParseException {
121        // ...
122    }
123
124    private ExprStmtAst parseExprStmt() throws ParseException {
125        // ...
126    }
127
128    private ExprAst parseExpr() throws ParseException {
129        // This is how we parse
130        // "AssignmentExpr / VarExpr / IntLiteralExpr"
131
132        AssignmentExprAst assignment =
133            attempt(Parser::parseAssignmentExpr);
134        if (assignment != null) return assignment;
135
136        VarExprAst variable =
137            attempt(Parser::parseVariableExpr);
138        if (variable != null) return variable;
139
140        IntLiteralExprAst intLiteral =
141            attempt(Parser::parseIntLiteralExpr);
142        if (intLiteral != null) return intLiteral;
143
144        throw new ParseException("no valid expression");
145    }
146
147    private VarExprAst parseVariableExpr()
148            throws ParseException {
149        // ...
150    }
151
152    private AssignmentExprAst parseAssignmentExpr()
153            throws ParseException {
154        // ...
155    }
156
157    private IntLiteralExprAst parseIntLiteralExpr()
158            throws ParseException {
159        // ..
160    }
161
162    private IdentAst parseIdent() throws ParseException {
163        var token = expect(IdentToken.class);
164        return new IdentAst(token.getContent());
165    }
166}

 1public interface AstVisitor {
 2
 3    private void visitChildren(Ast node)
 4            throws AnalysisException {
 5        for (var child : node.getChildren()) {
 6            child.accept(this);
 7        }
 8    }
 9
10    default void visitProgram(ProgramAst ast)
11            throws AnalysisException {
12        visitChildren(ast);
13    }
14
15    default void visitFunction(FunctionAst ast)
16            throws AnalysisException {
17        visitChildren(ast);
18    }
19
20    default void visitVarDecl(VarDeclAst ast)
21            throws AnalysisException {
22        visitChildren(ast);
23    }
24
25    // Etc...
26}

1public abstract sealed class Ast
2        permits /* ... */ {
3
4    // ...
5
6    public abstract void accept(AstVisitor visitor)
7        throws AnalysisException;
8}

 1public class CollectNames implements AstVisitor {
 2
 3    private Map<IdentAst, FunctionAst> functions
 4        = new HashMap<>();
 5
 6    private Map<NameInFunction, VarDeclAst> variables
 7        = new HashMap<>();
 8
 9    private record NameInFunction(IdentAst function,
10        IdentAst variable) {}
11
12    public FunctionAst getFunction(IdentAst ident) {
13        return functions.get(ident);
14    }
15
16    public VarDeclAst getVariable(IdentAst function,
17            IdentAst ident) {
18        return variables.get(new NameInFunction(function, ident));
19    }
20
21    @Override
22    public void visitFunction(FunctionAst ast)
23            throws AnalysisException {
24        var functionName = ast.getName();
25
26        if (functions.put(functionName, ast) != null) {
27            throw new AnalysisException(
28                "function " + functionName + " already exists");
29        }
30
31        AstVisitor.super.visitFunction(ast);
32    }
33
34    @Override
35    public void visitVarDecl(VarDeclAst ast)
36            throws AnalysisException {
37        var function = ast.findAncestor(FunctionAst.class);
38        var nameInFunction = new NameInFunction(
39            function.getName(), ast.getName());
40
41        if (variables.put(nameInFunction, ast) != null) {
42            throw new AnalysisException(
43                "variable " + ast.getName() + " already exists");
44        }
45
46        AstVisitor.super.visitVarDecl(ast);
47    }
48}

 1public class ResolveNames implements AstVisitor {
 2
 3    private final CollectNames collected;
 4
 5    public ResolveNames(CollectNames collected) {
 6        this.collected = collected;
 7    }
 8
 9    @Override
10    public void visitAssignmentExpr(AssignmentExprAst ast)
11            throws AnalysisException {
12        var function = ast.findAncestor(FunctionAst.class);
13        var decl = collected.getVariable(
14            function.getName(), ast.getVariable());
15
16        if (decl == null) {
17            throw new AnalysisException(
18                "use of undeclared variable " + ast.getVariable());
19        }
20
21        ast.setDecl(decl);
22        AstVisitor.super.visitAssignmentExpr(ast);
23    }
24
25    @Override
26    public void visitVariableExpr(VarExprAst ast)
27            throws AnalysisException {
28        var function = ast.findAncestor(FunctionAst.class);
29        var decl = collected.getVariable(
30            function.getName(), ast.getName());
31
32        if (decl == null) {
33            throw new AnalysisException(
34                "use of undeclared variable " + ast.getName());
35        }
36
37        ast.setDecl(decl);
38        AstVisitor.super.visitVariableExpr(ast);
39    }
40}

 1public class Interpreter {
 2
 3    private final ProgramAst ast;
 4
 5    // When a function is called, a stack-frame holds all the local
 6    // variables. We store the stack frames as maps in a stack
 7    private Deque<Map<IdentAst, Value>> stack = new ArrayDeque<>();
 8
 9    public Interpreter(ProgramAst ast) {
10      this.ast = ast;
11    }
12
13    private Value runFunction(FunctionAst ast, List<Value> args)
14            throws InterpretException {
15        var variables = new HashMap<IdentAst, Value>();
16        stack.push(variables);
17
18        // Copy over any paramters
19        for (var i = 0; i < args.size(); i++) {
20            var param = ast.getParams().get(i);
21            var value = args.get(i);
22            variables.put(param.getName(), value);
23        }
24
25        try {
26            return runBlock(ast.getBody());
27        } finally {
28            stack.pop();
29        }
30    }
31
32    private Value runBlock(BlockAst ast)
33            throws InterpretException {
34        for (var stmt : ast.getStmts()) {
35            switch (stmt) {
36                case VarDeclStmtAst ignored -> {}
37                case ReturnStmtAst returnStmt -> {
38                    return evalExpr(returnStmt.getValue());
39                }
40                case ExprStmtAst exprStmt ->
41                    evalExpr(exprStmt.getExpr());
42          }
43        }
44
45        throw new InterpretException("function did not return");
46    }
47
48    private Value evalExpr(ExprAst ast) throws InterpretException {
49        return switch (ast) {
50            case VarExprAst variable ->
51                stack.peek().get(variable.getName());
52            case IntLiteralExprAst intLiteral ->
53                new IntValue(intLiteral.getValue());
54            case AssignmentExprAst assignment -> {
55                var value = evalExpr(assignment.getValue());
56                stack.peek().put(assignment.getVariable(), value);
57                yield value;
58            }
59        };
60    }
61}