Crafting Interpreters

A must-read book by Robert Nystrom.

Collection of links and notes from my reading of the book.

eBNF - notation used to describe the syntax of programming languages wikipedia

Unrestricted grammar - wikipedia

Formal grammar - wikipedia

Chomsky hierarchy - a containment hierarchy of classes of formal grammars. wikipedia

Please Excuse My Dear Aunt Sally (PEMDAS - Parens, Exponents, Multiplication / Division, Addition / Subtraction) - mnemonic wikipedia

Separation of Concerns - wikipedia

Interpreter pattern wikipedia

Church-Turing thesis - Lambda calculus and Turing machines are equivalent. wikipedia

Russell's paradox - wikipedia

Computable function - wikipedia

Mathematics Foundational Crisis - wikipedia

The dangling else problem - universal answer is to bind the if to the closest else. wikipedia

Multiple dispatch - one of the ways to implement OOP wikipedia

Amortized analysis - how doing an expensive thing every so often can average out to being not expensive when looked at over a sufficient period of time. wikipedia

The constant pool in the JVM - spec

Just-in-time compilation - what one needs to implement to really go fast. wikipedia

IP or PC register - tracking which instruction is currently being executed. wikipedia

Test suite for the lox programming language github

Run-length encoding - an encoding to use to reduce the memory consumption of the line number associations in the lox virtual machine. wikipedia

Register allocation - wikipedia

The implementation of Lue 5.0 pdf

clox uses a trie to identify keywords. wikipedia

A trie is an example of a deterministic finite automation (DFA). wikipedia

Syntax diagrams used to be used to document a language's grammar. These days BNFs are used. wikipedia

The Smalltalk Bluebook has a syntax diagram inside the back cover that provides the grammar for the language.

The Dragon Book documents how to convert a regular expression into a DFA.

A trie is essentially what is used to parse JavaScript in V8. source

Pratt Parsing: Expression Parsing Made Easy blog

Struct inheritance is an example of type punning. wikipedia

Flexible array members can be used to avoid requiring two pointer indirections to access characters in an ObjString. wikipedia

20.2 - "The birthday paradox tells us that as the number of entries in the hash table increases, the chance of collision increases very quickly." wikipedia

20.2 - "The pigeonhole principle tells us we can never eliminate collisions entirely." wikipedia