Hack Club is running a programming language jam from June 08 - 29, where you'll get to hack on and ship a programming language in the span of three weeks and possibly win a chance to get a signed copy of Crafting Interpreters. Sign up here before June 07!
High schooler? Get stickers!
Table of contents
Orpheus writes a parser
Ok. We have a bunch of nice tokens now.
Our lexer produces a bunch of tokens, but we still can't do much with them quite yet. The next step to solving this problem is to write a parser, which will turn our currently rather one-dimensional list of tokens into what's known as an abstract syntax tree.
Abstract syntax trees
Orpheus drew a diagram for us last chapter on how lexers turn a blob of text that's meant to be our program into a list of tokens.
Parsers take these tokens and in turn output a tree of sorts that describes how tokens apply to one another. Here's an example of such a transformation:
prepare rows as 50
We took four tokens and smooshed them into one node. The four tokens described the syntax of our program but the node describes what the syntax actually does - creates a variable with a value of 50!
We're going to write that parser now. It's actually, surprisingly, similar to how we wrote our lexer, except that we're working with a tree now, which means we'll need some form of recursion. We'll get to that. For now, let's start with the usual! Orpheus opens a file called parser.js and throws this in there:
import { EaselError } from './stdlib.js'
import { TOKENS } from './lexer.js'
export class Parser {
constructor(tokens) {
this.tokens = tokens
this.ast = []
this.current = 0
}
error(token, msg) {
throw new EaselError(
`Syntax error on ${token.line}:${token.column}: ${msg}`
)
}
}
Based on the diagram, the most intuitive next step is to loop through every token that we get. Let's do that in our parse() method:
export class Parser {
// ...
parse() {
while (this.peekType() !== TOKENS.EOF) continue // TODO
return this.ast
}
}
This is pretty similar to our scanTokens() method in our lexer, but last time, we dealt with each character at a time. Tokens have more information than that - being able to see the next token's type would also be pretty useful - so we have two helper peek() methods this time instead of one:
export class Parser {
// ...
peek() {
if (this.current >= this.tokens.length) return null
return this.tokens[this.current]
}
peekType() {
if (this.current >= this.tokens.length) return null
return this.tokens[this.current].type
}
parse() {
// ...
}
}
Cool! Now, what exactly do we do with these tokens?
Recursive descent
With our lexer, we looped through every character and checked if it could be a token or belong to a set of characters that would belong to a token. Here, we're going to do something different - we're going to define a grammar for what our program could look like and work our way up until we can describe an entire chunk of code.
First up: what do these have in common?
Orpheus has an answer! They're all super basic. They're what we'll call literals - we can't really break them down further, or they'd just be unintelligible chunks that we can't use, and they also happen to be the most basic values we can reference.
To give an exact definition we'll reference later when writing our parser, literals in Easel can be: strings, numbers, or booleans.
Ok, what's the next obvious step from here? I'm thinking like arrays, or data types that build off literals by collecting them and storing them together. In Easel, it's quite simple - I can think of two data types and those are arrays and structs (or maps or whatever you want to call them. Orpheus decided to stick to structs while editing this, although that might not semantically be the best.)
I bet you already have ideas forming in your head on how to parse these. Arrays? LeftBracket → parse stuff in between → RightBracket.
But let's not get too far ahead of ourselves yet. What is this stuff "in between"?
Well, I imagine we might have an array that looks like [2 + 3, 5, 7]. That first item in the array is not a literal anymore. It's a binary expression!
So things are kind of coming together now. Literals can form expressions. We don't just have to form binary expressions - we can also form unary ones. Bet those are more rare, but surely you've seen them before: the NOT operator !true, for example.
Ok. So we know literals can form expressions. What can expressions form? It turns out almost everything else we can think of, especially for a language like Easel. This is because everything else is a statement - a set of expressions. Let's see:
- Variables. Specifically, assignment!
prepare phoneVolume as 50is assigning a literal to a variable. - Structs. Specifically, defining what a struct looks like.
brush Phone has { phoneVolume }is a statement. - Functions are blocks of expressions with attached metadata of sorts, like what arguments we might need to pass in!
- Return statements
- For loops and while loops are blocks of expressions also with attached metadata too, like what condition we should check for every iteration.
- Last but not least in Easel - if-else statements are blocks of expressions with, you guessed it, attached metadata like what conditions we should check for.
Our job now is to write a parser that can understand this hierarchy. The parser will start by looking for statements, which are made of expressions, which are made of literals. In other words: basic recursive descent!
Back to writing code
Ok! Sturp talking! Let's get to smacking the keyboard instead. By then, it should be pretty obvious that we'll need another utility method we're desperately missing: the good ole' eat method for eating tokens up:
export class Parser {
// ...
eat(type) {
if (this.peekType() === type) return this.tokens[this.current++]
this.error(
this.peek(),
`Expected ${type} but got ${this.peekType().toString()}`
)
}
// ...
}
Now let's begin our descent... into the underworld writing of a parser! Let's start with this basic structure:
export class Parser {
simple() {}
expr() {
const left = this.simple()
// Let's deal with the right side later
return left
}
stmt() {
const next = this.peek()
switch (next.type) {
// Can you guess what's coming here later?
default: {
return this.expr()
}
}
}
}
Ok, understandable enough! Although this isn't going to do anything right now. Let's fix that by updating simple():
simple() {
const token = this.eat(this.peekType())
switch (token.type) {
case TOKENS.String:
case TOKENS.Number:
case TOKENS.Boolean: {
return new Ast.Literal(token.content)
}
}
this.error(token, "Expected expression but got " + token)
}
Notice how we throw an error if we don't get anything. Since this is the last method we reach when we're looking at a token, there must be a syntax error if we can't get a proper node.
Something we didn't consider ahead of time was how we would define how these nodes look like. We can do this really easily. Let's create a new file called ast.js, and put our first kind of node in there:
export class Literal {
constructor(value) {
this.type = 'Literal'
this.value = value
}
}
export default {
Literal
}
Make sure to import this in parser.js!
import Ast from './ast.js'
Perfect. Back to simple() now - we're going to add arrays now:
simple() {
let token = this.eat(this.peekType())
switch (token.type) {
// ...
case TOKENS.LeftBracket: {
let items = []
if (this.peekType() !== TOKENS.RightBracket) items = this.exprList()
this.eat(TOKENS.RightBracket)
return new Ast.Array(items)
}
}
this.error(token, "Expected expression but got " + token)
}
Our predictions were correct. We gobble up the left bracket, create a new array, and if we haven't already reached the right bracket (i.e. empty array), we grab the list of expressions in between.
Now, we make use of an extra helper called exprList() to do this.
exprList() {
let exprs = []
exprs.push(this.expr())
while (this.peekType() === TOKENS.Comma) {
this.eat(TOKENS.Comma)
exprs.push(this.expr())
}
return exprs
}
We'll also need to add a new kind of node:
export class Array {
constructor(value) {
this.type = 'Array'
this.value = value
}
}
export default {
Array,
// ...
}
One last thing we'll add for now to simple() is:
simple() {
// ...
switch (token.type) {
// ...
case TOKENS.Identifier: {
return new Ast.Var(token.value)
}
}
}
This might confuse you a bit - didn't we say variables were statements? Yes, but this is not that - this is referring to when we reference a variable, not direct assignment - e.g., the variable reference in ink(x).
This does make use of a new kind of node though, so let's add that to ast.js:
export class Var {
constructor(name, value) {
this.type = 'Var'
this.name = name
this.value = value
}
}
export default {
// ...,
Var
}
Cool. That takes care of simple() for now. Let's move up the hierarchy and tweak expr()! Right now, we've only grabbed the left side of what should be a binary operation. Let's grab the operator and the right side after that:
expr() {
// expr has two sides
const left = this.simple()
if (isOp(this.peekType())) {
const op = this.eat(this.peekType()).value
const right = this.expr()
return new Ast.Binary(left, op, right)
}
return left
}
Looks like we need an extra isOp function. Orpheus and I are going to put this at the top of parser.js:
const isOp = type =>
[
TOKENS.Or,
TOKENS.And,
TOKENS.Equiv,
TOKENS.NotEquiv,
TOKENS.Gt,
TOKENS.Gte,
TOKENS.Lt,
TOKENS.Lte,
TOKENS.Plus,
TOKENS.Minus,
TOKENS.Asterisk,
TOKENS.Slash
].includes(type)
Our binary expression node is pretty simple:
export class Binary {
constructor(left, operator, right) {
this.type = 'Binary'
this.left = left
this.operator = operator
this.right = right
}
}
export default {
// ...,
Binary
}
Ok, I think we've got enough here where we can test the parser out and see what happens. Let's remove that continue we had earlier in parse():
parse() {
while (this.peekType() !== TOKENS.EOF) this.ast.push(this.stmt())
return this.ast
}
We should, of course, start using our parser in easel.js:
import { Parser } from './parser.js'
// ...
if (location) {
const program = await readFile(location)
const lexer = new Lexer(program)
try {
lexer.scanTokens()
} catch (err) {
console.log(err)
process.exit(1)
} finally {
if (debug) await writeFile('tokens.json', JSON.stringify(lexer.tokens, null, 2))
}
const parser = new Parser(lexer.tokens)
try {
parser.parse()
} catch (err) {
console.log(err)
} finally {
if (debug) await writeFile('ast.json', JSON.stringify(parser.ast, null, 2))
}
}
// ...
Cool! Let's test this out with a test program in test.easel:
[4 + 21]
2006 / 4012 + 2
Try it out with node easel.js test.easel --dbg! It's not really a complete program because we haven't taken care of statements yet, but I digress. You'll get something like this ast.json:
[
{
type: 'Literal',
value: [
{
type: 'Binary',
left: { type: 'Literal', value: 4 },
operator: '+',
right: { type: 'Literal', value: 21 }
}
]
},
{
type: 'Binary',
left: { type: 'Literal', value: 2006 },
operator: '/',
right: {
type: 'Binary',
left: { type: 'Literal', value: 4012 },
operator: '+',
right: { type: 'Literal', value: 2 }
}
}
]
This looks right, but there's just one minor problem... if we run that second node, this is what we get:
Dealing with order of operations
Oopsies. We forgot about PEMDAS. We should fix that. Never fear! Orpheus has put on her wizard hat and come up with a rather ingenious way to tackle this.
First things first, all operators should have a precedence hierarchy. If I see an addition operator and a multiplication operator in the same expression, then I should combine the operators next to the multiplication operator first before moving on to the addition operator. But if we've already parsed the addition operator, we can do a little switcheroo. Orpheus wants to show you what she means by this. Read the following in what you might imagine to be her voice.
First things first, at the top of parser.js!
const opOrder = {
'<': 0,
'<=': 0,
'>': 0,
'>=': 0,
'!=': 0,
'==': 0,
'&&': 0,
'||': 0,
'+': 1,
'-': 1,
'*': 2,
'/': 2
}
Next, I am going to add a little if-statement that checks if right is also a binary expression node, and compare the operators if so:
expr() {
// expr has two sides
let left = this.simple()
if (isOp(this.peekType())) {
const op = this.eat(this.peekType()).value
let right = this.expr()
if (right instanceof Ast.Binary && opOrder[op] > opOrder[right.operator])
// Quick reordering based on precedence
return new Ast.Binary(
new Ast.Binary(left, op, right.left),
right.operator,
right.right
)
return new Ast.Binary(left, op, right)
}
return left
}
Ok. Back to me. I'll take the mic back. Thanks. [grabs mic]
And that fixes all our problems! Well, not all of our problems, of course. Right now it might also be a good time to deal with parentheses:
(15 + 15) / 3
If you run this currently, it'll throw a syntax error, because we haven't dealt with parentheses in this scenario! In this scenario, the parentheses represent an expression inside an expression that we should evaluate first. To take care of this precedence, we can place this in simple() to take care of this:
case TOKENS.LeftParen: {
const expr = this.expr()
this.eat(TOKENS.RightParen)
return expr
}
An expression inside an expression, essentially. This works because now expr() will call simple() and evaluate (15 + 15) on its own, before peeking at /. Now if we run our parser on this, we'll get the proper-looking AST and not a syntax error:
Statements
Ok, awesome cool. What's next? Statements! Let's take care of that now. Remember this earlier?
stmt() {
const next = this.peek()
switch (next.type) {
// Can you guess what's coming here later?
default: {
return this.expr()
}
}
}
Now we'll replace that comment with some actual code. What exactly is going there? Well, we're going to parse anything that could lead to a block of expressions or be used to store expressions.
Functions
Perhaps the best example to run through first is parsing functions, so let's take a look at that! The structure of a function is as follows: it starts with the sketch keyword, then an identifier that's the name of the function. If it takes in parameters, we'll know because the needs keyword will come afterwards, followed by a list of identifiers that represent the parameters. Of course, we have the braces and the body that follow afterwards.
We'll have a nested function inside stmt():
stmt() {
const funcStmt = () => {
this.eatKeyword('sketch')
const name = this.eat(TOKENS.Identifier).value
let params = []
if (this.peekKeyword('needs')) {
// Parameters
this.eatKeyword('needs')
this.eat(TOKENS.LeftParen)
params = this.identifierList()
this.eat(TOKENS.RightParen)
}
this.eat(TOKENS.LeftBrace)
let body = []
while (this.peekType() !== TOKENS.RightBrace) body.push(this.stmt())
this.eat(TOKENS.RightBrace)
return new Ast.Func(name, params, body)
}
const next = this.peek()
switch (next.type) {
case TOKENS.Keyword: {
switch (next.value) {
case 'sketch': {
return funcStmt()
}
//...
}
}
// ...
}
}
We need two extra utilities that wrap peek() and eat(): peekKeyword() and eatKeyword(). eatKeyword() will throw an error if the next token isn't a keyword or if it doesn't match up to the keyword provided:
peekKeyword(keyword) {
if (this.peekType() !== TOKENS.Keyword || this.peek().value !== keyword)
return null
return this.peek()
}
eatKeyword(keyword) {
if (this.peekType() !== TOKENS.Keyword)
this.error(
this.peek(),
`Expected ${TOKENS.Keyword} but got ${this.peekType()}`
)
else if (this.peek().value !== keyword)
this.error(
this.peek(),
`Expected keyword ${keyword} but got keyword ${this.peek().value}`
)
return this.eat(TOKENS.Keyword)
}
We also need an extra helper method, similar to exprList(), called identifierList():
identifierList() {
let identifiers = []
identifiers.push(this.eat(TOKENS.Identifier).value)
while (this.peekType() === TOKENS.Comma) {
this.eat(TOKENS.Comma)
identifiers.push(this.eat(TOKENS.Identifier).value)
}
return identifiers
}
Instead of returning a list of expressions by calling expr(), identifierList() just returns a list of identifiers by gobbling them up.
Of course, we also need Ast.Func in ast.js:
export class Func {
constructor(name, params, body) {
this.type = 'Func'
this.name = name
this.params = params
this.body = body
}
}
export {
Func,
// ...
}
With functions come return statements. Let's work on those next. They're really simple, just eat the return keyword and return an expression:
stmt() {
const returnStmt = () => {
this.eatKeyword('finished')
return new Ast.Return(this.expr())
}
// ...
const next = this.peek()
switch (next.type) {
case TOKENS.Keyword: {
switch (next.value) {
case 'finished':
return returnStmt()
// ...
}
}
// ...
}
}
Of course, Ast.Return:
export class Return {
constructor(value) {
this.type = 'Return'
this.value = value
}
}
export default {
// ...,
Return
}
Loops
Let's deal with the loops next. For loops will gobble up the loop keyword, grab the identifier we'll be using to keep track of the current iteration, the range, and of course, the body:
const forStmt = () => {
this.eatKeyword('loop')
const id = this.eat(TOKENS.Identifier).value
this.eatKeyword('through')
this.eat(TOKENS.LeftParen)
const range = this.exprList()
if (range.length !== 2)
this.error(
range[range.length - 1],
'Expected (start, end) range but received more arguments than expected'
)
this.eat(TOKENS.RightParen)
this.eat(TOKENS.LeftBrace)
let body = []
while (this.peekType() !== TOKENS.RightBrace) body.push(this.stmt())
this.eat(TOKENS.RightBrace)
return new Ast.For(id, range, body)
}
const next = this.peek()
switch (next.type) {
case TOKENS.Keyword: {
switch (next.value) {
case 'loop': {
return forStmt()
}
// ...
}
}
// ...
}
In ast.js:
export class For {
constructor(id, range, body) {
this.type = 'For'
this.id = id
this.range = range
this.body = body
}
}
export default {
// ...,
For
}
Lovely. While loops are simpler, all we have to do is grab the condition and the body afterwards:
const whileStmt = () => {
this.eatKeyword('while')
this.eat(TOKENS.LeftParen)
const condition = this.expr()
this.eat(TOKENS.RightParen)
this.eat(TOKENS.LeftBrace)
let body = []
while (this.peekType() !== TOKENS.RightBrace) body.push(this.stmt())
this.eat(TOKENS.RightBrace)
return new Ast.While(condition, body)
}
const next = this.peek()
switch (next.type) {
case TOKENS.Keyword: {
switch (next.value) {
case 'while': {
return whileStmt()
}
// ...
}
}
// ...
}
In ast.js:
export class While {
constructor(condition, body) {
this.type = 'While'
this.condition = condition
this.body = body
}
}
export default {
// ...,
While
}
Conditionals
Conditionals are also pretty intuitive. We'll do this recursively - we'll start by eating up the if keyword, parsing the condition, and the body. If elif or else pops up afterwards, we'll also deal with those by calling conditionalStmt again:
const conditionalStmt = keyword => {
this.eatKeyword(keyword)
let condition = new Ast.Literal(true)
if (keyword !== 'else') {
this.eat(TOKENS.LeftParen)
condition = this.expr()
this.eat(TOKENS.RightParen)
}
this.eat(TOKENS.LeftBrace)
let body = []
while (this.peekType() !== TOKENS.RightBrace) body.push(this.stmt())
this.eat(TOKENS.RightBrace)
let otherwise = []
while (this.peekKeyword('elif') || this.peekKeyword('else'))
otherwise.push(conditionalStmt(this.peek().value))
return new Ast.Conditional(condition, body, otherwise)
}
const next = this.peek()
switch (next.type) {
case TOKENS.Keyword: {
switch (next.value) {
case 'if': {
return conditionalStmt('if')
}
// ...
}
}
// ...
}
In ast.js:
export class Conditional {
constructor(condition, body, otherwise) {
this.type = 'Conditional'
this.condition = condition
this.body = body
this.otherwise = otherwise
}
}
export default {
// ...,
Conditional
}
Assignment
We should be able to assign values to a variable, but we should also be able to assign values to a property, like prepare cell.live as false. We can do this in the same function by simply checking that first identifier and checking if a Period token comes afterwards:
const assignStmt = () => {
this.eatKeyword('prepare')
const name = this.eat(TOKENS.Identifier).value
if (this.peekType() === TOKENS.Period) {
// Setter
this.eat(TOKENS.Period)
const property = this.eat(TOKENS.Identifier).value
this.eatKeyword('as')
const value = this.expr()
return new Ast.Set(name, property, value)
}
this.eatKeyword('as')
const value = this.expr()
return new Ast.Var(name, value)
}
const next = this.peek()
switch (next.type) {
case TOKENS.Keyword: {
switch (next.value) {
case 'prepare': {
return assignStmt()
}
// ...
}
}
// ...
}
Ast.Var exists, but Ast.Set doesn't, so let's add that in ast.js:
export class Set {
constructor(caller, property, value) {
this.type = 'Set'
this.caller = caller
this.property = property
this.value = value
}
}
export default {
// ...,
Set
}
Structs
Last but not least, structs! We need to have a statement for defining structs. Defining a struct looks like brush Cell has { x, y, live }, so we'll gobble up the brush keyword, get the name of the struct, gobble up the has keyword, the braces, and then get the members of the struct (a list of identifiers):
const structStmt = () => {
this.eatKeyword('brush')
const name = this.eat(TOKENS.Identifier).value
this.eatKeyword('has')
this.eat(TOKENS.LeftBrace)
const members = this.identifierList()
this.eat(TOKENS.RightBrace)
return new Ast.Struct(name, members)
}
const next = this.peek()
switch (next.type) {
case TOKENS.Keyword: {
switch (next.value) {
case 'brush':
return structStmt()
// ...
}
}
// ...
}
In ast.js:
export class Struct {
constructor(name, members) {
this.type = 'Struct'
this.name = name
this.members = members
}
}
export default {
// ...,
Struct
}
We haven't accounted for actual struct copies with values yet, so let's take care of that!
simple() {
let token = this.eat(this.peekType())
switch (token.type) {
case TOKENS.Keyword: {
if (token.value === 'prep') {
// Instance is essentially a struct copy
const id = this.eat(TOKENS.Identifier).value
this.eat(TOKENS.LeftParen)
let members = {}
while (this.peekType() !== TOKENS.RightParen) {
const member = this.eat(TOKENS.Identifier).value
this.eat(TOKENS.Colon)
members[member] = this.expr()
if (this.peekType() === TOKENS.Comma) this.eat(TOKENS.Comma)
}
this.eat(TOKENS.RightParen)
return new Ast.Instance(id, members)
}
break
// ...
}
}
this.error(token, 'Expected expression but got ' + token)
}
Let's add Instance to ast.js:
export class Instance {
constructor(name, members) {
this.type = 'Instance'
this.name = name
this.members = members
}
}
export default {
// ...,
Instance
}
What about calls?
Bring, bling! Bring, bring!
I think that's Orpheus' phone ringing. She's going to answer it.
Who is it, Orpheus?
Wait, our mysterious sender? Nah, beware of those scam calls. We've talked about this before!
What do you mean, he's telling me to stop drinking so much hot chocolate? [sputters] How does he even know about that? Why is he calling us? Wait, he's a he? Ok, so we know he's some random dude harassing us.
Just reminding us about... calls? Calls! Oh, right! We almost forgot about those! Our programming language would be pretty useful without those.
We're missing an extra step between binary expressions and simple literals, and that happens to be function calls and getters. I like to think of this like a chain, like orpheus.picksUp(phone).numbers[0]. It's an intermediate step between expr() and simple() because it can be one-half of an expression but evaluates down to a simple value.
call() {
let expr = this.simple()
while (true) {
if (this.peekType() === TOKENS.LeftParen) {
this.eat(TOKENS.LeftParen)
let args = []
if (this.peekType() !== TOKENS.RightParen) args = this.exprList()
this.eat(TOKENS.RightParen)
expr = new Ast.Call(expr, args)
} else if (this.peekType() === TOKENS.LeftBracket) {
// This is also a getter, but we accept an expression rather than just an identifier
this.eat(TOKENS.LeftBracket)
const property = this.expr()
this.eat(TOKENS.RightBracket)
expr = new Ast.Get(expr, property, true)
} else if (this.peekType() === TOKENS.Period) {
this.eat(TOKENS.Period)
const property = this.eat(TOKENS.Identifier).value
expr = new Ast.Get(expr, property)
} else break
}
return expr
}
expr() {
const left = this.call()
// ...
}
Once again, we have the cascading value. We call simple() first, and while we can keep chaining, we keep chaining and wrapping around that initial simple() with one of two kinds of nodes: Ast.Call, which represents a function call, or Ast.Get, which represents a property getter. Let's add them to ast.js now:
export class Call {
constructor(caller, args) {
this.type = 'Call'
this.caller = caller
this.args = args
}
}
export class Get {
constructor(caller, property, isExpr = false) {
this.type = 'Get'
this.caller = caller
this.property = property
this.isExpr = isExpr
}
}
export default {
// ...,
Call,
Get
}
Getting random calls from a stranger is kind of fun. You're right about that, Orpheus.
[Actually, I have a funny story. One time, one of my friends got his phone number changed, and some other bloke with the same name got his phone number. (What are the coincidences?) Anyways, a friend tried to text him but ended up texting this other person with the same name who played along for a solid two weeks. That's my funny story of the day.]
Unary operators
There's just one last token we haven't accounted for. I'll give you a moment to think about it. Which token could we possibly be forgetting about?
The NOT operator! That's right - our only unary operator. We haven't dealt with unary operators yet. Let's take care of that now. It makes the most sense to cascade from expr() (binary expressions) to unary expressions to call(), so let's first add a unary() method:
unary() {
// unary has one side
if (this.peekType() === TOKENS.Not) {
const op = this.eat(this.peekType()).value
return new Ast.Unary(op, this.unary())
}
return this.call()
}
In ast.js:
export class Unary {
constructor(operator, apply) {
this.type = 'Unary'
this.operator = operator
this.apply = apply
}
}
export default {
// ...,
Unary
}
Instead of calling call() in expr() now, we'll replace it with unary(), which will cascade down to call():
expr() {
const left = this.unary()
// ...
}
Let's test out everything we have so far. Try running node easel.js test.easel --dbg, and you'll get a new debug file containing the AST in ast.json. Mine looks something like this:
[
{
"type": "Var",
"name": "rows",
"value": { "type": "Literal", "value": 50 }
},
{
"type": "Var",
"name": "cols",
"value": { "type": "Literal", "value": 20 }
},
{ "type": "Struct", "name": "Cell", "members": ["x", "y", "live"] },
{
"type": "Func",
"name": "seed",
"params": [],
"body": [
{
"type": "Var",
"name": "cells",
"value": { "type": "Array", "value": [] }
},
{
"type": "For",
"id": "x",
"range": [
{ "type": "Literal", "value": 0 },
{ "type": "Var", "name": "rows" }
],
"body": [
{
"type": "For",
"id": "y",
"range": [
{ "type": "Literal", "value": 0 },
{ "type": "Var", "name": "cols" }
],
"body": [
{
"type": "Var",
"name": "live",
"value": { "type": "Literal", "value": false }
},
{
"type": "Var",
"name": "chance",
"value": {
"type": "Call",
"caller": { "type": "Var", "name": "random" },
"args": [
{ "type": "Literal", "value": 0 },
{ "type": "Literal", "value": 100 }
]
}
},
{
"type": "Conditional",
"condition": {
"type": "Binary",
"left": { "type": "Var", "name": "chance" },
"operator": "<",
"right": { "type": "Literal", "value": 20 }
},
"body": [
{
"type": "Var",
"name": "live",
"value": { "type": "Literal", "value": true }
}
],
"otherwise": []
},
{
"type": "Call",
"caller": {
"type": "Get",
"caller": { "type": "Var", "name": "cells" },
"property": "add",
"isExpr": false
},
"args": [
{
"type": "Instance",
"name": "Cell",
"members": {
"x": { "type": "Var", "name": "x" },
"y": { "type": "Var", "name": "y" },
"live": { "type": "Var", "name": "live" }
}
}
]
}
]
}
]
},
{ "type": "Return", "value": { "type": "Var", "name": "cells" } }
]
},
{
"type": "Var",
"name": "cells",
"value": {
"type": "Call",
"caller": { "type": "Var", "name": "seed" },
"args": []
}
},
{
"type": "Func",
"name": "getNeighbors",
"params": ["cells", "index"],
"body": [
{
"type": "Var",
"name": "neighbors",
"value": { "type": "Array", "value": [] }
},
{
"type": "Conditional",
"condition": {
"type": "Binary",
"left": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": "-",
"right": {
"type": "Binary",
"left": { "type": "Var", "name": "rows" },
"operator": "-",
"right": { "type": "Literal", "value": 1 }
}
},
"operator": ">",
"right": { "type": "Literal", "value": 0 }
},
"body": [
{
"type": "Call",
"caller": {
"type": "Get",
"caller": { "type": "Var", "name": "neighbors" },
"property": "add",
"isExpr": false
},
"args": [
{
"type": "Get",
"caller": { "type": "Var", "name": "cells" },
"property": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": "-",
"right": {
"type": "Binary",
"left": { "type": "Var", "name": "rows" },
"operator": "-",
"right": { "type": "Literal", "value": 1 }
}
},
"isExpr": true
}
]
}
],
"otherwise": []
},
{
"type": "Conditional",
"condition": {
"type": "Binary",
"left": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": "-",
"right": { "type": "Var", "name": "rows" }
},
"operator": ">",
"right": { "type": "Literal", "value": 0 }
},
"body": [
{
"type": "Call",
"caller": {
"type": "Get",
"caller": { "type": "Var", "name": "neighbors" },
"property": "add",
"isExpr": false
},
"args": [
{
"type": "Get",
"caller": { "type": "Var", "name": "cells" },
"property": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": "-",
"right": { "type": "Var", "name": "rows" }
},
"isExpr": true
}
]
}
],
"otherwise": []
},
{
"type": "Conditional",
"condition": {
"type": "Binary",
"left": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": "-",
"right": {
"type": "Binary",
"left": { "type": "Var", "name": "rows" },
"operator": "+",
"right": { "type": "Literal", "value": 1 }
}
},
"operator": ">",
"right": { "type": "Literal", "value": 0 }
},
"body": [
{
"type": "Call",
"caller": {
"type": "Get",
"caller": { "type": "Var", "name": "neighbors" },
"property": "add",
"isExpr": false
},
"args": [
{
"type": "Get",
"caller": { "type": "Var", "name": "cells" },
"property": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": "-",
"right": {
"type": "Binary",
"left": { "type": "Var", "name": "rows" },
"operator": "+",
"right": { "type": "Literal", "value": 1 }
}
},
"isExpr": true
}
]
}
],
"otherwise": []
},
{
"type": "Conditional",
"condition": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": ">",
"right": { "type": "Literal", "value": 0 }
},
"body": [
{
"type": "Call",
"caller": {
"type": "Get",
"caller": { "type": "Var", "name": "neighbors" },
"property": "add",
"isExpr": false
},
"args": [
{
"type": "Get",
"caller": { "type": "Var", "name": "cells" },
"property": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": "-",
"right": { "type": "Literal", "value": 1 }
},
"isExpr": true
}
]
}
],
"otherwise": []
},
{
"type": "Conditional",
"condition": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": "<",
"right": {
"type": "Binary",
"left": {
"type": "Get",
"caller": { "type": "Var", "name": "cells" },
"property": "length",
"isExpr": false
},
"operator": "-",
"right": { "type": "Literal", "value": 1 }
}
},
"body": [
{
"type": "Call",
"caller": {
"type": "Get",
"caller": { "type": "Var", "name": "neighbors" },
"property": "add",
"isExpr": false
},
"args": [
{
"type": "Get",
"caller": { "type": "Var", "name": "cells" },
"property": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": "+",
"right": { "type": "Literal", "value": 1 }
},
"isExpr": true
}
]
}
],
"otherwise": []
},
{
"type": "Conditional",
"condition": {
"type": "Binary",
"left": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": "+",
"right": {
"type": "Binary",
"left": { "type": "Var", "name": "rows" },
"operator": "-",
"right": { "type": "Literal", "value": 1 }
}
},
"operator": "<",
"right": {
"type": "Binary",
"left": {
"type": "Get",
"caller": { "type": "Var", "name": "cells" },
"property": "length",
"isExpr": false
},
"operator": "-",
"right": { "type": "Literal", "value": 1 }
}
},
"body": [
{
"type": "Call",
"caller": {
"type": "Get",
"caller": { "type": "Var", "name": "neighbors" },
"property": "add",
"isExpr": false
},
"args": [
{
"type": "Get",
"caller": { "type": "Var", "name": "cells" },
"property": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": "+",
"right": {
"type": "Binary",
"left": { "type": "Var", "name": "rows" },
"operator": "-",
"right": { "type": "Literal", "value": 1 }
}
},
"isExpr": true
}
]
}
],
"otherwise": []
},
{
"type": "Conditional",
"condition": {
"type": "Binary",
"left": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": "+",
"right": { "type": "Var", "name": "rows" }
},
"operator": "<",
"right": {
"type": "Binary",
"left": {
"type": "Get",
"caller": { "type": "Var", "name": "cells" },
"property": "length",
"isExpr": false
},
"operator": "-",
"right": { "type": "Literal", "value": 1 }
}
},
"body": [
{
"type": "Call",
"caller": {
"type": "Get",
"caller": { "type": "Var", "name": "neighbors" },
"property": "add",
"isExpr": false
},
"args": [
{
"type": "Get",
"caller": { "type": "Var", "name": "cells" },
"property": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": "+",
"right": { "type": "Literal", "value": 1 }
},
"isExpr": true
}
]
}
],
"otherwise": []
},
{
"type": "Conditional",
"condition": {
"type": "Binary",
"left": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": "+",
"right": {
"type": "Binary",
"left": { "type": "Var", "name": "rows" },
"operator": "+",
"right": { "type": "Literal", "value": 1 }
}
},
"operator": "<",
"right": {
"type": "Binary",
"left": {
"type": "Get",
"caller": { "type": "Var", "name": "cells" },
"property": "length",
"isExpr": false
},
"operator": "-",
"right": { "type": "Literal", "value": 1 }
}
},
"body": [
{
"type": "Call",
"caller": {
"type": "Get",
"caller": { "type": "Var", "name": "neighbors" },
"property": "add",
"isExpr": false
},
"args": [
{
"type": "Get",
"caller": { "type": "Var", "name": "cells" },
"property": {
"type": "Binary",
"left": { "type": "Var", "name": "index" },
"operator": "+",
"right": {
"type": "Binary",
"left": { "type": "Var", "name": "rows" },
"operator": "-",
"right": { "type": "Literal", "value": 1 }
}
},
"isExpr": true
}
]
}
],
"otherwise": []
},
{
"type": "Var",
"name": "alive",
"value": { "type": "Array", "value": [] }
},
{
"type": "For",
"id": "i",
"range": [
{ "type": "Literal", "value": 0 },
{
"type": "Get",
"caller": { "type": "Var", "name": "neighbors" },
"property": "length",
"isExpr": false
}
],
"body": [
{
"type": "Conditional",
"condition": {
"type": "Get",
"caller": {
"type": "Get",
"caller": { "type": "Var", "name": "neighbors" },
"property": { "type": "Var", "name": "i" },
"isExpr": true
},
"property": "live",
"isExpr": false
},
"body": [
{
"type": "Call",
"caller": {
"type": "Get",
"caller": { "type": "Var", "name": "alive" },
"property": "add",
"isExpr": false
},
"args": [
{
"type": "Get",
"caller": { "type": "Var", "name": "neighbors" },
"property": { "type": "Var", "name": "i" },
"isExpr": true
}
]
}
],
"otherwise": []
}
]
},
{ "type": "Return", "value": { "type": "Var", "name": "alive" } }
]
},
{
"type": "Func",
"name": "painting",
"params": [],
"body": [
{
"type": "For",
"id": "i",
"range": [
{ "type": "Literal", "value": 0 },
{
"type": "Get",
"caller": { "type": "Var", "name": "cells" },
"property": "length",
"isExpr": false
}
],
"body": [
{
"type": "Var",
"name": "cell",
"value": {
"type": "Get",
"caller": { "type": "Var", "name": "cells" },
"property": { "type": "Var", "name": "i" },
"isExpr": true
}
},
{
"type": "Var",
"name": "neighbors",
"value": {
"type": "Call",
"caller": { "type": "Var", "name": "getNeighbors" },
"args": [
{ "type": "Var", "name": "cells" },
{ "type": "Var", "name": "i" }
]
}
},
{
"type": "Conditional",
"condition": {
"type": "Get",
"caller": { "type": "Var", "name": "cell" },
"property": "live",
"isExpr": false
},
"body": [
{
"type": "Conditional",
"condition": {
"type": "Binary",
"left": {
"type": "Get",
"caller": { "type": "Var", "name": "neighbors" },
"property": "length",
"isExpr": false
},
"operator": "<",
"right": {
"type": "Binary",
"left": { "type": "Literal", "value": 2 },
"operator": "||",
"right": {
"type": "Binary",
"left": {
"type": "Get",
"caller": { "type": "Var", "name": "neighbors" },
"property": "length",
"isExpr": false
},
"operator": ">",
"right": { "type": "Literal", "value": 3 }
}
}
},
"body": [
{
"type": "Set",
"caller": "cell",
"property": "live",
"value": { "type": "Literal", "value": false }
}
],
"otherwise": [
{
"type": "Conditional",
"condition": {
"type": "Unary",
"operator": "!",
"apply": {
"type": "Binary",
"left": {
"type": "Get",
"caller": { "type": "Var", "name": "cell" },
"property": "live",
"isExpr": false
},
"operator": "&&",
"right": {
"type": "Binary",
"left": { "type": "Var", "name": "neighbors" },
"operator": "==",
"right": { "type": "Literal", "value": 3 }
}
}
},
"body": [
{
"type": "Set",
"caller": "cell",
"property": "live",
"value": { "type": "Literal", "value": true }
}
],
"otherwise": []
}
]
}
],
"otherwise": []
},
{
"type": "Conditional",
"condition": {
"type": "Get",
"caller": { "type": "Var", "name": "cell" },
"property": "live",
"isExpr": false
},
"body": [
{
"type": "Var",
"name": "color",
"value": {
"type": "Instance",
"name": "Color",
"members": {
"r": { "type": "Literal", "value": 0 },
"g": { "type": "Literal", "value": 255 },
"b": { "type": "Literal", "value": 0 }
}
}
},
{
"type": "Call",
"caller": {
"type": "Get",
"caller": { "type": "Var", "name": "Canvas" },
"property": "fill",
"isExpr": false
},
"args": [
{
"type": "Get",
"caller": { "type": "Var", "name": "cell" },
"property": "x",
"isExpr": false
},
{
"type": "Get",
"caller": { "type": "Var", "name": "cell" },
"property": "y",
"isExpr": false
}
]
},
{
"type": "Call",
"caller": { "type": "Var", "name": "ink" },
"args": [
{
"type": "Call",
"caller": {
"type": "Get",
"caller": { "type": "Var", "name": "Canvas" },
"property": "get",
"isExpr": false
},
"args": [
{
"type": "Get",
"caller": { "type": "Var", "name": "cell" },
"property": "x",
"isExpr": false
},
{
"type": "Get",
"caller": { "type": "Var", "name": "cell" },
"property": "y",
"isExpr": false
}
]
}
]
}
],
"otherwise": [
{
"type": "Conditional",
"condition": { "type": "Literal", "value": true },
"body": [
{
"type": "Call",
"caller": {
"type": "Get",
"caller": { "type": "Var", "name": "Canvas" },
"property": "erase",
"isExpr": false
},
"args": [
{
"type": "Get",
"caller": { "type": "Var", "name": "cell" },
"property": "x",
"isExpr": false
},
{
"type": "Get",
"caller": { "type": "Var", "name": "cell" },
"property": "y",
"isExpr": false
}
]
},
{
"type": "Call",
"caller": { "type": "Var", "name": "ink" },
"args": [
{
"type": "Call",
"caller": {
"type": "Get",
"caller": { "type": "Var", "name": "Canvas" },
"property": "get",
"isExpr": false
},
"args": [
{
"type": "Get",
"caller": { "type": "Var", "name": "cell" },
"property": "x",
"isExpr": false
},
{
"type": "Get",
"caller": { "type": "Var", "name": "cell" },
"property": "y",
"isExpr": false
}
]
}
]
}
],
"otherwise": []
}
]
}
]
}
]
},
{
"type": "Call",
"caller": { "type": "Var", "name": "painting" },
"args": []
}
]
Awesome! We've got a parser working. Clap yourself on the back - that wasn't so hard, was it?
That was definitely longer than writing a lexer, for sure, but rev up - we're going to see our programming language in action in the next part and get Conway's Game of Life running (eventually)!
The complete code here is at parser.js.