Building Interpreters
如果无法正常显示，请先停止浏览器的去广告插件。
相关话题：
#zalando
1. Building Interpreters
Anunay Inuganti
@ianunay
@I_Anunay
2. https://interpreterbook.com/
The official Monkey logo
3. What?
●
●
Practical: implementation / no theory
Different steps involved
Why?
●
●
●
●
●
Design your own language & bring it to life
Used in many day to day tools
Deeper understanding of languages
Build your own sandboxed environments
Build your own DSL (Domain Specific Language)
4.
5.
6. Interpretation Process
Parsing
Evaluation
7. Interpretation Process
Tokenization
Tokens
Parsing
AST
Evaluation
8. Tokenization
let version = 5;
let add = fn(x, y){
x + y;
};
Tokenizer
{
{
{
{
{
type:
type:
type:
type:
type:
{ type:
{ type:
{ type:
{ type:
{ type:
...
tokens.LET, literal: "let" },
tokens.IDENT, literal: "version" },
tokens.ASSIGN, literal: "=" },
tokens.INT, literal: "5" },
tokens.SEMICOLON, literal: ";" },
tokens.LET, literal: "let" },
tokens.IDENT, literal: "add" },
tokens.ASSIGN, literal: "=" },
tokens.FUNCTION, literal: "fn" },
tokens.LPAREN, literal: "(" },
9. Approach
position
Tokens:
IDENT, INT, STRING ...
{
{
{
{
{
type:
type:
type:
type:
type:
1 + 2 + 3
tokens.INT, literal: "1" },
tokens.PLUS, literal: "+" },
tokens.INT, literal: "2" },
tokens.PLUS, literal: "+" },
tokens.INT, literal: "3" },
Operators:
ASSIGN: "=", PLUS: "+",
MINUS: "-", BANG: "!",
ASTERISK: "*", SLASH: "/" ...
Keywords:
read position
FUNCTION, LET, TRUE,
FALSE, IF, ELSE, RETURN,
10. Approach
position
Tokens:
IDENT, INT, STRING ...
{
{
{
{
{
type:
type:
type:
type:
type:
1 + 2 + 3
tokens.INT, literal: "1" },
tokens.PLUS, literal: "+" },
tokens.INT, literal: "2" },
tokens.PLUS, literal: "+" },
tokens.INT, literal: "3" },
Operators:
ASSIGN: "=", PLUS: "+",
MINUS: "-", BANG: "!",
ASTERISK: "*", SLASH: "/" ...
Keywords:
read position
FUNCTION, LET, TRUE,
FALSE, IF, ELSE, RETURN,
11. Approach
position
Tokens:
IDENT, INT, STRING ...
{
{
{
{
{
type:
type:
type:
type:
type:
tokens.LET, literal: "let" },
tokens.IDENT, literal: "version" },
tokens.ASSIGN, literal: "=" },
tokens.INT, literal: "5" },
tokens.SEMICOLON, literal: ";" }
let version = 5;
Operators:
ASSIGN: "=", PLUS: "+",
MINUS: "-", BANG: "!",
ASTERISK: "*", SLASH: "/" ...
Keywords:
read
position
FUNCTION, LET, TRUE,
FALSE, IF, ELSE, RETURN,
12. Pointers
Parser calls nextToken()
Skip white space
13. Parsing
{
{
{
{
{ type:
type:
type:
type:
type: tokens.LET, literal: "let" },
tokens.IDENT, literal: "version" },
tokens.ASSIGN, literal: "=" },
tokens.INT, literal: "5" },
tokens.SEMICOLON, literal: ";" },
{
{
{
{
{ type:
type:
type:
type:
type: tokens.LET, literal: "let" },
tokens.IDENT, literal: "add" },
tokens.ASSIGN, literal: "=" },
tokens.FUNCTION, literal: "fn" },
tokens.LPAREN, literal: "(" },
Abstract
Syntax
Tree
Program
Parser
Statement Statement
Let
Expression Let
Expression
IDENT =
version
value = 5
IDENT
= add
value =
function
expression
14. Parser Generators
● generate a parser based on
grammar
● yacc, bison, ANTLR,
tree-sitter, jison
part of ANTLR Context Free
Grammar for ECMAScript
15. Parser Generator in Skipper
eskip - Domain Specific Language
16. Parser Generator in Skipper
https://github.com/zalando/skipper/
blob/master/eskip/parser.y
17. Parser Approach
Statements:
Current Token
Peek Token
{
{
{
{
{ type:
type:
type:
type:
type: tokens.LET, literal: "let" },
tokens.IDENT, literal: "version" },
tokens.ASSIGN, literal: "=" },
tokens.INT, literal: "5" },
tokens.SEMICOLON, literal: ";" },
{
{
{
{
{ type:
type:
type:
type:
type: tokens.LET, literal: "let" },
tokens.IDENT, literal: "add" },
tokens.ASSIGN, literal: "=" },
tokens.FUNCTION, literal: "fn" },
tokens.LPAREN, literal: "(" },
LetStatement,
ReturnStatement,
ExpressionStatement ...
Literals:
IntegerLiteral,
StringLiteral,
ArrayLiteral ...
Expressions:
PrefixExpression,
InfixExpression,
IfExpression ...
18. Expression Parsing
Expression
let version = 3 + 5 * 4;
❌ ✅
(3 + 5) * 4 3 + (5 * 4)
19. Pratt parsing
https://dl.acm.org/doi/pdf/10.1145/512927.512931
20. Precedence:
Recursive Descent Parsing
LOWEST = 1,
EQUALS = 2, // ==
LESSGREATER = 3, // > or <
SUM = 4, // +
PRODUCT = 5, // *
PREFIX = 6, // -X or !X
CALL = 7, // myFunction(X)
INDEX = 8, // array[index]
Peek
Token
Infix
Expression
3 + 5 * 4
Left
Current
Token
Right
21. Precedence:
Recursive Descent Parsing
LOWEST = 1,
EQUALS = 2, // ==
LESSGREATER = 3, // > or <
SUM = 4, // +
PRODUCT = 5, // *
PREFIX = 6, // -X or !X
CALL = 7, // myFunction(X)
INDEX = 8, // array[index]
Peek
Token
Infix
Expression
3 + 5 * 4
3
Current
Token
Right
22. Precedence:
Recursive Descent Parsing
LOWEST = 1,
EQUALS = 2, // ==
LESSGREATER = 3, // > or <
SUM = 4, // +
PRODUCT = 5, // *
PREFIX = 6, // -X or !X
CALL = 7, // myFunction(X)
INDEX = 8, // array[index]
Peek
Token
Infix
Expression
3 + 5 * 4
Infix
Expression
3
Current
Token
5
4
23. Notes
- AST Explorer https://astexplorer.net/
- Prettier: Pretty prints an AST
24. Evaluation
●
●
●
Interpreter / Compiler ??
JIT compilation
Tree walking interpreter
25. Evaluation
Abstract
Syntax
Tree
Program
Eval
Statement Statement
Let
Expression Let
Expression
IDENT =
version
value = 5
IDENT
= add
value =
function
expression
Output
26. Evaluation
Program
Environment
let number = 5;
let add2 = fn(x){
x + 2;
};
add2(number)
Set Objects:
Get IntegerObject,
BooleanObject,
FunctionObject ...
27. Evaluation
Program
Environment
let number = 5;
let add2 = fn(x){
x + 2;
};
add2(number)
Set
Objects:
IntegerObject(5)
Get
28. Evaluation
Program
Environment
let number = 5;
let add2 = fn(x){
x + 2;
};
add2(number)
Set
Objects:
IntegerObject(5)
Get
FunctionObject(Exp)
29. Evaluation
Program
Environment
let number = 5;
let add2 = fn(x){
x + 2;
};
add2(number)
Set
Objects:
IntegerObject(5)
Get
FunctionObject(Exp)
30. Environment
Evaluation
Set
Objects:
IntegerObject(5)
Program
let init = fn(){
let name = "Hello ";
let sayName = fn(){
name + x;
};
sayName()
}
init()
Get
FunctionObject(Exp)
Parent
If "IDENT defined in ENV":
use IDENT
else "IDENT defined in Parent":
use Parent value
else:
undefined
31. Code - https://github.com/ianunay/monkey-lang-interpreter-ts
32. Thank You!
33. Experience
- Off by one errors