Chapter 1: AST Node Generation & Context-Free Grammars | Course Notes

Abstract Syntax Trees (ASTs) represent the core compiler syntax mapping layer. In this chapter, we outline token generation, grammar definitions, and AST tree node structures.

Lexing & Parsing Flow

Source code is a stream of characters. The Lexer groups these characters into semantic units called tokens (e.g. keywords, identifiers, literals). The Parser validates this token stream against a context-free grammar to produce the AST hierarchy.

AST Node Structure

An AST represents operators and operands. Unlike parse trees, parenthetical groupings and concrete punctuation symbols are discarded because the tree hierarchy implicitly represents precedence.

#include <string>
#include <memory>

enum class NodeType { BinaryOp, Literal, Variable };

struct ASTNode {
    NodeType type;
    std::string value;
    std::unique_ptr<ASTNode> left;
    std::unique_ptr<ASTNode> right;
};