 |
My Tree-Walker Lox interpreter |
|
2024-03-22 |
|
Last edit: 2024-03-22 |
|
--------------------- |
|
|
|
I wanted to learn more about designing an interpreter, so I looked around and f… |
|
|
|
I read parts I and II, which focus on concepts, common techniques and language … |
|
|
|
The aim was to have a Lox interpreter that at least supported functions and clo… |
|
|
|
## What is lox ? |
|
|
|
To sum up |
 |
this page |
|
, Lox is a small, high-level scripting language, with dynamic types and automat… |
|
|
|
A cool fact is that Lox is Turing complete, it means it is able to run a Turing… |
|
|
|
## Essentials basics |
|
|
|
I've learned some important key concepts, and here are a few of the most import… |
|
|
|
### Scanning |
|
|
|
Scanning is also known as lexing or lexical analysis. It takes a linear stream … |
|
|
|
The scanner must group characters into the smalles possible sequence that repre… |
|
|
|
### Parsing |
|
|
|
It takes the flat sequence of tokens and builds a tree structure that represent… |
|
|
|
The Lox interpreter I made is a Tree-Walk Interpreter, it means it traverses th… |
|
|
|
### Context-Free Grammars |
|
|
|
It is a formal grammar, it allows us to define an infinite set of rules that ar… |
|
|
|
### Rules for grammars |
|
|
|
We use rules to generate strings that are in the grammar, it is called derivati… |
|
|
|
> *The rules are called productions because they produce strings in the grammar* |
|
|
|
Each production has a head (its name) and a body (a list of symbols). |
|
|
|
A symbol can be: |
|
- A terminal, it is like an endpoint, it simply produces it. |
|
- A non-terminal, it refers to other rule in the grammar. |
|
|
|
A grammar example from the book, see below. |
|
|
|
```python |
|
breakfast → protein ( "with" breakfast "on the side" )? |
|
| bread ; |
|
|
|
protein → "really"+ "crispy" "bacon" |
|
| "sausage" |
|
| ( "scrambled" | "poached" | "fried" ) "eggs" ; |
|
|
|
bread → "toast" | "biscuits" | "English muffin" ; |
|
``` |
|
|
|
The ponctuations is based on the regex behaviors, as example, the `?` means it … |
|
|
|
So here, a valid strings could be the one below. |
|
|
|
```python |
|
"poached" "eggs" "with" "toast" "on the side" |
|
``` |
|
|
|
### Recursive Descent Parsing |
|
|
|
The best explanation here is probably the one in the book. |
|
|
|
> *Recursive descent is considered a top-down parser because it starts from the… |
|
|
|
## Examples |
|
|
|
Here are some Lox examples that can be evaluated by my interpreter. |
|
|
|
```text |
|
var b = 1; |
|
var a = "hello"; |
|
|
|
{ |
|
var a = b + b; |
|
|
|
print a; |
|
} |
|
|
|
print a; |
|
|
|
fun fibonacci(n) { |
|
if (n <= 1) return n; |
|
return fibonacci(n - 1) + fibonacci(n - 2); |
|
} |
|
|
|
print fibonacci(5); |
|
|
|
print "helo" + "world"; |
|
|
|
fun echo(n) { |
|
print n; |
|
return n; |
|
} |
|
|
|
print echo(echo(1) + echo(2)) + echo(echo(4) + echo(5)); |
|
``` |
|
|
|
## Links |
|
|
|
https://github.com/theobori/tinylox |
|
