notes

Personal notes
git clone git://git.laack.co/notes.git
Log | Files | Refs

commit 8cdf860813fb9e67979d56d82f9c8811ad5e77bd
parent fd9e47084a5d54f6f6d26bee6e9c9996258bcd56
Author: Andrew Laack <andrew@laack.co>
Date:   Fri, 23 Oct 2026 21:09:18 -0500

Interpreters

Diffstat:
Mdocs/CraftingInterpreters.md | 29+++++++++++++++++++++++++++++
Adocs/TreeWalkInterpreter.md | 20++++++++++++++++++++
2 files changed, 49 insertions(+), 0 deletions(-)

diff --git a/docs/CraftingInterpreters.md b/docs/CraftingInterpreters.md @@ -4,6 +4,10 @@ ## Links +- [Tree Walk Interpreter](TreeWalkInterpreter.md) + +## Concepts + - Lox - Lexing - scanning @@ -56,3 +60,28 @@ - jit - this is what the jvm is, clr (common language runtime from MS), and js (in browsers) use - quite complex, considers hotspots during execution to determine if further optimizations are warranted to generated code +- expression vs statement + - an expression evaluates to a value while a statement has an effect +- context-free grammars + - we used a regular language for our lexical grammar, but we need something more powerful for parsing + - this more powerful form is context-free grammars, which allow arbitrarily deep nesting, unlike regular languages + - each production in a context free grammar is a head, the starting point, and a body, describing what it generates + - the body is a list of symbols, some of which may be terminals and some of which may be non-terminals + - non-terminals is a reference to another rule in the grammar. if this is a reference to the current rule, we notice we have recursion which can't exist in regular languages. + - example: + - breakfast→ protein "with" breakfast "on the side" ; + - breakfast→ protein ; + - breakfast→ bread ; + - protein→ crispiness "crispy" "bacon" ; + - protein→ "sausage" ; + - protein→ cooked "eggs" ; + - crispiness → "really" ; + - crispiness → "really" crispiness ; + - cooked→ "scrambled" ; + - cooked→ "poached" ; + - cooked→ "fried" ; + - bread→ "toast" ; + - bread→ "biscuits" ; + - bread→ "English muffin" ; + - each line above is a production, and derivations are evaluations of a given production + - during derivation, we may need to evaluate further productions, as is the case for breakfast which requires the derivation of a protein or bread. diff --git a/docs/TreeWalkInterpreter.md b/docs/TreeWalkInterpreter.md @@ -0,0 +1,20 @@ +# Tree Walk Interpreter + +**Source:** Crafting Interpreters + +**Definition:** A tree walk interpreter is an interpreter that builds an AST and walks it (executing instructions as it goes). + +Many modern interpreters favor bytecode / VMs. + +## Parts + +- Lexer + - Converts source code to tokens + - Token parts + - Lexeme + - The smallest\* sequence of characters that means something + - Adheres to maximal munch principle so things like "orchid" don't become the reserved word "or". + - Token type + - Token types are just the kind of thing it is, so it could be a specific keyword, a type of literal, or any number of other things +- Parser + - Parses tokens into an AST