CraftingInterpreters.md (4685B)
1 # Crafting Interpreters 2 3 **Source:** [craftinginterpreters.com](https://craftinginterpreters.com) 4 5 ## Links 6 7 - [Tree Walk Interpreter](TreeWalkInterpreter.md) 8 9 ## Concepts 10 11 - Lox 12 - Lexing 13 - scanning 14 - lexical analysis 15 - Lexer 16 - A lexer takes a stream of characters and groups them together into tokens 17 - Token 18 - Chunk of characters with syntactic meaning in the language 19 - Parsing 20 - We go from syntax to grammar by generating an AST 21 - Static Analysis 22 - The above two steps are fairly consistent across languages, this one is not 23 - Some common static analysis steps 24 - binding / resolution 25 - find identifier definitions and associate them 26 - this has to consider scopes, and in statically typed languages we'd perform type checking here 27 - all of the above are considered the "frontend". below is the "middle end" (an addition at some point as compilers got more complex, making frontend and backend unsatisfactory). 28 - The middle end is focused on intermediate representations, not tied to the source or destination forms 29 - optimization 30 - constant folding 31 - at compile time compute computable values 32 - u32Max = (2**32) - 1 33 - -> u32Max = 4294967295 34 - ctr = (7 - 12) * (20 + 29) 35 - -> ctr = -245 36 - backend 37 - code generation 38 - this is the final step of compilation, where we generate the target code 39 - asm 40 - timeless 41 - bytecode 42 - named as so due to these instructions frequently being one byte in size 43 - options 44 - vm 45 - run the code on a vm that supports the bytecode as it's isa 46 - specifically these are process or language virtual machines, not to be confused with system virtual machines 47 - small compiler to go directly to machine 48 49 - runtime 50 - in the context of compiled languages, like go, the runtime would be stuff like the gc which is baked into the executable 51 - for interpreted languages, this is often something like the python interpreter, which manages some program state 52 - broadly, the runtime is the set of things provided by the language that help out during execution time 53 - single pass compilers 54 - category of compiler that doesn't generate an ast, instead parsing and code gening in one pass 55 - this is actually something that dictated design decisions for c, causing it to have things like only allowing references to functions defined above the current function 56 - tree walk interpreter 57 - simple interpreter approach that generates an ast, and than walks it while executing the program 58 - transpiler 59 - disagree with the word because it is just a compiler with a specific target, but this is basically the general idea of using IRs as an easy exit without doing the hard work in the backend 60 - jit 61 - this is what the jvm is, clr (common language runtime from MS), and js (in browsers) use 62 - quite complex, considers hotspots during execution to determine if further optimizations are warranted to generated code 63 - expression vs statement 64 - an expression evaluates to a value while a statement has an effect 65 - context-free grammars 66 - we used a regular language for our lexical grammar, but we need something more powerful for parsing 67 - this more powerful form is context-free grammars, which allow arbitrarily deep nesting, unlike regular languages 68 - each production in a context free grammar is a head, the starting point, and a body, describing what it generates 69 - the body is a list of symbols, some of which may be terminals and some of which may be non-terminals 70 - 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. 71 - example: 72 - breakfast→ protein "with" breakfast "on the side" ; 73 - breakfast→ protein ; 74 - breakfast→ bread ; 75 - protein→ crispiness "crispy" "bacon" ; 76 - protein→ "sausage" ; 77 - protein→ cooked "eggs" ; 78 - crispiness → "really" ; 79 - crispiness → "really" crispiness ; 80 - cooked→ "scrambled" ; 81 - cooked→ "poached" ; 82 - cooked→ "fried" ; 83 - bread→ "toast" ; 84 - bread→ "biscuits" ; 85 - bread→ "English muffin" ; 86 - each line above is a production, and derivations are evaluations of a given production 87 - during derivation, we may need to evaluate further productions, as is the case for breakfast which requires the derivation of a protein or bread.