'use strict'; /** * TTTTTTTTTTTTTTTTTTTTTTTHHHHHHHHH HHHHHHHHHEEEEEEEEEEEEEEEEEEEEEE * T:::::::::::::::::::::TH:::::::H H:::::::HE::::::::::::::::::::E * T:::::::::::::::::::::TH:::::::H H:::::::HE::::::::::::::::::::E * T:::::TT:::::::TT:::::THH::::::H H::::::HHEE::::::EEEEEEEEE::::E * TTTTTT T:::::T TTTTTT H:::::H H:::::H E:::::E EEEEEE * T:::::T H:::::H H:::::H E:::::E * T:::::T H::::::HHHHH::::::H E::::::EEEEEEEEEE * T:::::T H:::::::::::::::::H E:::::::::::::::E * T:::::T H:::::::::::::::::H E:::::::::::::::E * T:::::T H::::::HHHHH::::::H E::::::EEEEEEEEEE * T:::::T H:::::H H:::::H E:::::E * T:::::T H:::::H H:::::H E:::::E EEEEEE * TT:::::::TT HH::::::H H::::::HHEE::::::EEEEEEEE:::::E * T:::::::::T H:::::::H H:::::::HE::::::::::::::::::::E * T:::::::::T H:::::::H H:::::::HE::::::::::::::::::::E * TTTTTTTTTTT HHHHHHHHH HHHHHHHHHEEEEEEEEEEEEEEEEEEEEEE * * SSSSSSSSSSSSSSS UUUUUUUU UUUUUUUUPPPPPPPPPPPPPPPPP EEEEEEEEEEEEEEEEEEEEEERRRRRRRRRRRRRRRRR * SS:::::::::::::::SU::::::U U::::::UP::::::::::::::::P E::::::::::::::::::::ER::::::::::::::::R * S:::::SSSSSS::::::SU::::::U U::::::UP::::::PPPPPP:::::P E::::::::::::::::::::ER::::::RRRRRR:::::R * S:::::S SSSSSSSUU:::::U U:::::UUPP:::::P P:::::PEE::::::EEEEEEEEE::::ERR:::::R R:::::R * S:::::S U:::::U U:::::U P::::P P:::::P E:::::E EEEEEE R::::R R:::::R * S:::::S U:::::U U:::::U P::::P P:::::P E:::::E R::::R R:::::R * S::::SSSS U:::::U U:::::U P::::PPPPPP:::::P E::::::EEEEEEEEEE R::::RRRRRR:::::R * SS::::::SSSSS U:::::U U:::::U P:::::::::::::PP E:::::::::::::::E R:::::::::::::RR * SSS::::::::SS U:::::U U:::::U P::::PPPPPPPPP E:::::::::::::::E R::::RRRRRR:::::R * SSSSSS::::S U:::::U U:::::U P::::P E::::::EEEEEEEEEE R::::R R:::::R * S:::::S U:::::U U:::::U P::::P E:::::E R::::R R:::::R * S:::::S U::::::U U::::::U P::::P E:::::E EEEEEE R::::R R:::::R * SSSSSSS S:::::S U:::::::UUU:::::::U PP::::::PP EE::::::EEEEEEEE:::::ERR:::::R R:::::R * S::::::SSSSSS:::::S UU:::::::::::::UU P::::::::P E::::::::::::::::::::ER::::::R R:::::R * S:::::::::::::::SS UU:::::::::UU P::::::::P E::::::::::::::::::::ER::::::R R:::::R * SSSSSSSSSSSSSSS UUUUUUUUU PPPPPPPPPP EEEEEEEEEEEEEEEEEEEEEERRRRRRRR RRRRRRR * * TTTTTTTTTTTTTTTTTTTTTTTIIIIIIIIIINNNNNNNN NNNNNNNNYYYYYYY YYYYYYY * T:::::::::::::::::::::TI::::::::IN:::::::N N::::::NY:::::Y Y:::::Y * T:::::::::::::::::::::TI::::::::IN::::::::N N::::::NY:::::Y Y:::::Y * T:::::TT:::::::TT:::::TII::::::IIN:::::::::N N::::::NY::::::Y Y::::::Y * TTTTTT T:::::T TTTTTT I::::I N::::::::::N N::::::NYYY:::::Y Y:::::YYY * T:::::T I::::I N:::::::::::N N::::::N Y:::::Y Y:::::Y * T:::::T I::::I N:::::::N::::N N::::::N Y:::::Y:::::Y * T:::::T I::::I N::::::N N::::N N::::::N Y:::::::::Y * T:::::T I::::I N::::::N N::::N:::::::N Y:::::::Y * T:::::T I::::I N::::::N N:::::::::::N Y:::::Y * T:::::T I::::I N::::::N N::::::::::N Y:::::Y * T:::::T I::::I N::::::N N:::::::::N Y:::::Y * TT:::::::TT II::::::IIN::::::N N::::::::N Y:::::Y * T:::::::::T I::::::::IN::::::N N:::::::N YYYY:::::YYYY * T:::::::::T I::::::::IN::::::N N::::::N Y:::::::::::Y * TTTTTTTTTTT IIIIIIIIIINNNNNNNN NNNNNNN YYYYYYYYYYYYY * * CCCCCCCCCCCCC OOOOOOOOO MMMMMMMM MMMMMMMMPPPPPPPPPPPPPPPPP IIIIIIIIIILLLLLLLLLLL EEEEEEEEEEEEEEEEEEEEEERRRRRRRRRRRRRRRRR * CCC::::::::::::C OO:::::::::OO M:::::::M M:::::::MP::::::::::::::::P I::::::::IL:::::::::L E::::::::::::::::::::ER::::::::::::::::R * CC:::::::::::::::C OO:::::::::::::OO M::::::::M M::::::::MP::::::PPPPPP:::::P I::::::::IL:::::::::L E::::::::::::::::::::ER::::::RRRRRR:::::R * C:::::CCCCCCCC::::CO:::::::OOO:::::::OM:::::::::M M:::::::::MPP:::::P P:::::PII::::::IILL:::::::LL EE::::::EEEEEEEEE::::ERR:::::R R:::::R * C:::::C CCCCCCO::::::O O::::::OM::::::::::M M::::::::::M P::::P P:::::P I::::I L:::::L E:::::E EEEEEE R::::R R:::::R * C:::::C O:::::O O:::::OM:::::::::::M M:::::::::::M P::::P P:::::P I::::I L:::::L E:::::E R::::R R:::::R * C:::::C O:::::O O:::::OM:::::::M::::M M::::M:::::::M P::::PPPPPP:::::P I::::I L:::::L E::::::EEEEEEEEEE R::::RRRRRR:::::R * C:::::C O:::::O O:::::OM::::::M M::::M M::::M M::::::M P:::::::::::::PP I::::I L:::::L E:::::::::::::::E R:::::::::::::RR * C:::::C O:::::O O:::::OM::::::M M::::M::::M M::::::M P::::PPPPPPPPP I::::I L:::::L E:::::::::::::::E R::::RRRRRR:::::R * C:::::C O:::::O O:::::OM::::::M M:::::::M M::::::M P::::P I::::I L:::::L E::::::EEEEEEEEEE R::::R R:::::R * C:::::C O:::::O O:::::OM::::::M M:::::M M::::::M P::::P I::::I L:::::L E:::::E R::::R R:::::R * C:::::C CCCCCCO::::::O O::::::OM::::::M MMMMM M::::::M P::::P I::::I L:::::L LLLLLL E:::::E EEEEEE R::::R R:::::R * C:::::CCCCCCCC::::CO:::::::OOO:::::::OM::::::M M::::::MPP::::::PP II::::::IILL:::::::LLLLLLLLL:::::LEE::::::EEEEEEEE:::::ERR:::::R R:::::R * CC:::::::::::::::C OO:::::::::::::OO M::::::M M::::::MP::::::::P I::::::::IL::::::::::::::::::::::LE::::::::::::::::::::ER::::::R R:::::R * CCC::::::::::::C OO:::::::::OO M::::::M M::::::MP::::::::P I::::::::IL::::::::::::::::::::::LE::::::::::::::::::::ER::::::R R:::::R * CCCCCCCCCCCCC OOOOOOOOO MMMMMMMM MMMMMMMMPPPPPPPPPP IIIIIIIIIILLLLLLLLLLLLLLLLLLLLLLLLEEEEEEEEEEEEEEEEEEEEEERRRRRRRR RRRRRRR * * ======================================================================================================================================================================= * ======================================================================================================================================================================= * ======================================================================================================================================================================= * ======================================================================================================================================================================= */ /** * Today we're going to write a compiler together. But not just any compiler... A * super duper teeny tiny compiler! A compiler that is so small that if you * remove all the comments this file would only be ~200 lines of actual code. * * We're going to compile some lisp-like function calls into some C-like * function calls. * * If you are not familiar with one or the other. I'll just give you a quick intro. * * If we had two functions `add` and `subtract` they would be written like this: * * LISP C * * 2 + 2 (add 2 2) add(2, 2) * 4 - 2 (subtract 4 2) subtract(4, 2) * 2 + (4 - 2) (add 2 (subtract 4 2)) add(2, subtract(4, 2)) * * Easy peezy right? * * Well good, because this is exactly what we are going to compile. While this * is neither a complete LISP or C syntax, it will be enough of the syntax to * demonstrate many of the major pieces of a modern compiler. */ /** * Most compilers break down into three primary stages: Parsing, Transformation, * and Code Generation * * 1. *Parsing* is taking raw code and turning it into a more abstract * representation of the code. * * 2. *Transformation* takes this abstract representation and manipulates to do * whatever the compiler wants it to. * * 3. *Code Generation* takes the transformed representation of the code and * turns it into new code. */ /** * Parsing * ------- * * Parsing typically gets broken down into two phases: Lexical Analysis and * Syntactic Analysis. * * 1. *Lexical Analysis* takes the raw code and splits it apart into these things * called tokens by a thing called a tokenizer (or lexer). * * Tokens are an array of tiny little objects that describe an isolated piece * of the syntax. They could be numbers, labels, punctuation, operators, * whatever. * * 2. *Syntactic Analysis* takes the tokens and reformats them into a * representation that describes each part of the syntax and their relation * to one another. This is known as an intermediate representation or * Abstract Syntax Tree. * * An Abstract Syntax Tree, or AST for short, is a deeply nested object that * represents code in a way that is both easy to work with and tells us a lot * of information. * * For the following syntax: * * (add 2 (subtract 4 2)) * * Tokens might look something like this: * * [ * { type: 'paren', value: '(' }, * { type: 'name', value: 'add' }, * { type: 'number', value: '2' }, * { type: 'paren', value: '(' }, * { type: 'name', value: 'subtract' }, * { type: 'number', value: '4' }, * { type: 'number', value: '2' }, * { type: 'paren', value: ')' }, * { type: 'paren', value: ')' }, * ] * * And an Abstract Syntax Tree (AST) might look like this: * * { * type: 'Program', * body: [{ * type: 'CallExpression', * name: 'add', * params: [{ * type: 'NumberLiteral', * value: '2', * }, { * type: 'CallExpression', * name: 'subtract', * params: [{ * type: 'NumberLiteral', * value: '4', * }, { * type: 'NumberLiteral', * value: '2', * }] * }] * }] * } */ /** * Transformation * -------------- * * The next type of stage for a compiler is transformation. Again, this just * takes the AST from the last step and makes changes to it. It can manipulate * the AST in the same language or it can translate it into an entirely new * language. * * Let’s look at how we would transform an AST. * * You might notice that our AST has elements within it that look very similar. * There are these objects with a type property. Each of these are known as an * AST Node. These nodes have defined properties on them that describe one * isolated part of the tree. * * We can have a node for a "NumberLiteral": * * { * type: 'NumberLiteral', * value: '2', * } * * Or maybe a node for a "CallExpression": * * { * type: 'CallExpression', * name: 'subtract', * params: [...nested nodes go here...], * } * * When transforming the AST we can manipulate nodes by * adding/removing/replacing properties, we can add new nodes, remove nodes, or * we could leave the existing AST alone and create an entirely new one based * on it. * * Since we’re targeting a new language, we’re going to focus on creating an * entirely new AST that is specific to the target language. * * Traversal * --------- * * In order to navigate through all of these nodes, we need to be able to * traverse through them. This traversal process goes to each node in the AST * depth-first. * * { * type: 'Program', * body: [{ * type: 'CallExpression', * name: 'add', * params: [{ * type: 'NumberLiteral', * value: '2' * }, { * type: 'CallExpression', * name: 'subtract', * params: [{ * type: 'NumberLiteral', * value: '4' * }, { * type: 'NumberLiteral', * value: '2' * }] * }] * }] * } * * So for the above AST we would go: * * 1. Program - Starting at the top level of the AST * 2. CallExpression (add) - Moving to the first element of the Program's body * 3. NumberLiteral (2) - Moving to the first element of CallExpression's params * 4. CallExpression (subtract) - Moving to the second element of CallExpression's params * 5. NumberLiteral (4) - Moving to the first element of CallExpression's params * 6. NumberLiteral (2) - Moving to the second element of CallExpression's params * * If we were manipulating this AST directly, instead of creating a separate AST, * we would likely introduce all sorts of abstractions here. But just visiting * each node in the tree is enough for what we're trying to do. * * The reason I use the word "visiting" is because there is this pattern of how * to represent operations on elements of an object structure. * * Visitors * -------- * * The basic idea here is that we are going to create a “visitor” object that * has methods that will accept different node types. * * var visitor = { * NumberLiteral() {}, * CallExpression() {}, * }; * * When we traverse our AST, we will call the methods on this visitor whenever we * "enter" a node of a matching type. * * In order to make this useful we will also pass the node and a reference to * the parent node. * * var visitor = { * NumberLiteral(node, parent) {}, * CallExpression(node, parent) {}, * }; * * However, there also exists the possibility of calling things on "exit". Imagine * our tree structure from before in list form: * * - Program * - CallExpression * - NumberLiteral * - CallExpression * - NumberLiteral * - NumberLiteral * * As we traverse down, we're going to reach branches with dead ends. As we * finish each branch of the tree we "exit" it. So going down the tree we * "enter" each node, and going back up we "exit". * * -> Program (enter) * -> CallExpression (enter) * -> Number Literal (enter) * <- Number Literal (exit) * -> Call Expression (enter) * -> Number Literal (enter) * <- Number Literal (exit) * -> Number Literal (enter) * <- Number Literal (exit) * <- CallExpression (exit) * <- CallExpression (exit) * <- Program (exit) * * In order to support that, the final form of our visitor will look like this: * * var visitor = { * NumberLiteral: { * enter(node, parent) {}, * exit(node, parent) {}, * } * }; */ /** * Code Generation * --------------- * * The final phase of a compiler is code generation. Sometimes compilers will do * things that overlap with transformation, but for the most part code * generation just means take our AST and string-ify code back out. * * Code generators work several different ways, some compilers will reuse the * tokens from earlier, others will have created a separate representation of * the code so that they can print nodes linearly, but from what I can tell most * will use the same AST we just created, which is what we’re going to focus on. * * Effectively our code generator will know how to “print” all of the different * node types of the AST, and it will recursively call itself to print nested * nodes until everything is printed into one long string of code. */ /** * And that's it! That's all the different pieces of a compiler. * * Now that isn’t to say every compiler looks exactly like I described here. * Compilers serve many different purposes, and they might need more steps than * I have detailed. * * But now you should have a general high-level idea of what most compilers look * like. * * Now that I’ve explained all of this, you’re all good to go write your own * compilers right? * * Just kidding, that's what I'm here to help with :P * * So let's begin... */ /** * ============================================================================ * (/^▽^)/ * THE TOKENIZER! * ============================================================================ */ /** * We're gonna start off with our first phase of parsing, lexical analysis, with * the tokenizer. * * We're just going to take our string of code and break it down into an array * of tokens. * * (add 2 (subtract 4 2)) => [{ type: 'paren', value: '(' }, ...] */ // We start by accepting an input string of code, and we're gonna set up two // things... function tokenizer(input) { // A `current` variable for tracking our position in the code like a cursor. let current = 0; // And a `tokens` array for pushing our tokens to. let tokens = []; // We start by creating a `while` loop where we are setting up our `current` // variable to be incremented as much as we want `inside` the loop. // // We do this because we may want to increment `current` many times within a // single loop because our tokens can be any length. while (current < input.length) { // We're also going to store the `current` character in the `input`. let char = input[current]; // The first thing we want to check for is an open parenthesis. This will // later be used for `CallExpression` but for now we only care about the // character. // // We check to see if we have an open parenthesis: if (char === '(') { // If we do, we push a new token with the type `paren` and set the value // to an open parenthesis. tokens.push({ type: 'paren', value: '(', }); // Then we increment `current` current++; // And we `continue` onto the next cycle of the loop. continue; } // Next we're going to check for a closing parenthesis. We do the same exact // thing as before: Check for a closing parenthesis, add a new token, // increment `current`, and `continue`. if (char === ')') { tokens.push({ type: 'paren', value: ')', }); current++; continue; } // Moving on, we're now going to check for whitespace. This is interesting // because we care that whitespace exists to separate characters, but it // isn't actually important for us to store as a token. We would only throw // it out later. // // So here we're just going to test for existence and if it does exist we're // going to just `continue` on. let WHITESPACE = /\s/; if (WHITESPACE.test(char)) { current++; continue; } // The next type of token is a number. This is different than what we have // seen before because a number could be any number of characters and we // want to capture the entire sequence of characters as one token. // // (add 123 456) // ^^^ ^^^ // Only two separate tokens // // So we start this off when we encounter the first number in a sequence. let NUMBERS = /[0-9]/; if (NUMBERS.test(char)) { // We're going to create a `value` string that we are going to push // characters to. let value = ''; // Then we're going to loop through each character in the sequence until // we encounter a character that is not a number, pushing each character // that is a number to our `value` and incrementing `current` as we go. while (NUMBERS.test(char)) { value += char; char = input[++current]; } // After that we push our `number` token to the `tokens` array. tokens.push({ type: 'number', value }); // And we continue on. continue; } // We'll also add support for strings in our language which will be any // text surrounded by double quotes ("). // // (concat "foo" "bar") // ^^^ ^^^ string tokens // // We'll start by checking for the opening quote: if (char === '"') { // Keep a `value` variable for building up our string token. let value = ''; // We'll skip the opening double quote in our token. char = input[++current]; // Then we'll iterate through each character until we reach another // double quote. while (char !== '"') { value += char; char = input[++current]; } // Skip the closing double quote. char = input[++current]; // And add our `string` token to the `tokens` array. tokens.push({ type: 'string', value }); continue; } // The last type of token will be a `name` token. This is a sequence of // letters instead of numbers, that are the names of functions in our lisp // syntax. // // (add 2 4) // ^^^ // Name token // let LETTERS = /[a-z]/i; if (LETTERS.test(char)) { let value = ''; // Again we're just going to loop through all the letters pushing them to // a value. while (LETTERS.test(char)) { value += char; char = input[++current]; } // And pushing that value as a token with the type `name` and continuing. tokens.push({ type: 'name', value }); continue; } // Finally if we have not matched a character by now, we're going to throw // an error and completely exit. throw new TypeError('I dont know what this character is: ' + char); } // Then at the end of our `tokenizer` we simply return the tokens array. return tokens; } /** * ============================================================================ * ヽ/❀o ل͜ o\ﾉ * THE PARSER!!! * ============================================================================ */ /** * For our parser we're going to take our array of tokens and turn it into an * AST. * * [{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] } */ // Okay, so we define a `parser` function that accepts our array of `tokens`. function parser(tokens) { // Again we keep a `current` variable that we will use as a cursor. let current = 0; // But this time we're going to use recursion instead of a `while` loop. So we // define a `walk` function. function walk() { // Inside the walk function we start by grabbing the `current` token. let token = tokens[current]; // We're going to split each type of token off into a different code path, // starting off with `number` tokens. // // We test to see if we have a `number` token. if (token.type === 'number') { // If we have one, we'll increment `current`. current++; // And we'll return a new AST node called `NumberLiteral` and setting its // value to the value of our token. return { type: 'NumberLiteral', value: token.value, }; } // If we have a string we will do the same as number and create a // `StringLiteral` node. if (token.type === 'string') { current++; return { type: 'StringLiteral', value: token.value, }; } // Next we're going to look for CallExpressions. We start this off when we // encounter an open parenthesis. if ( token.type === 'paren' && token.value === '(' ) { // We'll increment `current` to skip the parenthesis since we don't care // about it in our AST. token = tokens[++current]; // We create a base node with the type `CallExpression`, and we're going // to set the name as the current token's value since the next token after // the open parenthesis is the name of the function. let node = { type: 'CallExpression', name: token.value, params: [], }; // We increment `current` *again* to skip the name token. token = tokens[++current]; // And now we want to loop through each token that will be the `params` of // our `CallExpression` until we encounter a closing parenthesis. // // Now this is where recursion comes in. Instead of trying to parse a // potentially infinitely nested set of nodes we're going to rely on // recursion to resolve things. // // To explain this, let's take our Lisp code. You can see that the // parameters of the `add` are a number and a nested `CallExpression` that // includes its own numbers. // // (add 2 (subtract 4 2)) // // You'll also notice that in our tokens array we have multiple closing // parenthesis. // // [ // { type: 'paren', value: '(' }, // { type: 'name', value: 'add' }, // { type: 'number', value: '2' }, // { type: 'paren', value: '(' }, // { type: 'name', value: 'subtract' }, // { type: 'number', value: '4' }, // { type: 'number', value: '2' }, // { type: 'paren', value: ')' }, <<< Closing parenthesis // { type: 'paren', value: ')' }, <<< Closing parenthesis // ] // // We're going to rely on the nested `walk` function to increment our // `current` variable past any nested `CallExpression`. // So we create a `while` loop that will continue until it encounters a // token with a `type` of `'paren'` and a `value` of a closing // parenthesis. while ( (token.type !== 'paren') || (token.type === 'paren' && token.value !== ')') ) { // we'll call the `walk` function which will return a `node` and we'll // push it into our `node.params`. node.params.push(walk()); token = tokens[current]; } // Finally we will increment `current` one last time to skip the closing // parenthesis. current++; // And return the node. return node; } // Again, if we haven't recognized the token type by now we're going to // throw an error. throw new TypeError(token.type); } // Now, we're going to create our AST which will have a root which is a // `Program` node. let ast = { type: 'Program', body: [], }; // And we're going to kickstart our `walk` function, pushing nodes to our // `ast.body` array. // // The reason we are doing this inside a loop is because our program can have // `CallExpression` after one another instead of being nested. // // (add 2 2) // (subtract 4 2) // while (current < tokens.length) { ast.body.push(walk()); } // At the end of our parser we'll return the AST. return ast; } /** * ============================================================================ * ⌒(❀>◞౪◟<❀)⌒ * THE TRAVERSER!!! * ============================================================================ */ /** * So now we have our AST, and we want to be able to visit different nodes with * a visitor. We need to be able to call the methods on the visitor whenever we * encounter a node with a matching type. * * traverse(ast, { * Program: { * enter(node, parent) { * // ... * }, * exit(node, parent) { * // ... * }, * }, * * CallExpression: { * enter(node, parent) { * // ... * }, * exit(node, parent) { * // ... * }, * }, * * NumberLiteral: { * enter(node, parent) { * // ... * }, * exit(node, parent) { * // ... * }, * }, * }); */ // So we define a traverser function which accepts an AST and a // visitor. Inside we're going to define two functions... function traverser(ast, visitor) { // A `traverseArray` function that will allow us to iterate over an array and // call the next function that we will define: `traverseNode`. function traverseArray(array, parent) { array.forEach(child => { traverseNode(child, parent); }); } // `traverseNode` will accept a `node` and its `parent` node. So that it can // pass both to our visitor methods. function traverseNode(node, parent) { // We start by testing for the existence of a method on the visitor with a // matching `type`. let methods = visitor[node.type]; // If there is an `enter` method for this node type we'll call it with the // `node` and its `parent`. if (methods && methods.enter) { methods.enter(node, parent); } // Next we are going to split things up by the current node type. switch (node.type) { // We'll start with our top level `Program`. Since Program nodes have a // property named body that has an array of nodes, we will call // `traverseArray` to traverse down into them. // // (Remember that `traverseArray` will in turn call `traverseNode` so we // are causing the tree to be traversed recursively) case 'Program': traverseArray(node.body, node); break; // Next we do the same with `CallExpression` and traverse their `params`. case 'CallExpression': traverseArray(node.params, node); break; // In the cases of `NumberLiteral` and `StringLiteral` we don't have any // child nodes to visit, so we'll just break. case 'NumberLiteral': case 'StringLiteral': break; // And again, if we haven't recognized the node type then we'll throw an // error. default: throw new TypeError(node.type); } // If there is an `exit` method for this node type we'll call it with the // `node` and its `parent`. if (methods && methods.exit) { methods.exit(node, parent); } } // Finally we kickstart the traverser by calling `traverseNode` with our ast // with no `parent` because the top level of the AST doesn't have a parent. traverseNode(ast, null); } /** * ============================================================================ * ⁽(◍˃̵͈̑ᴗ˂̵͈̑)⁽ * THE TRANSFORMER!!! * ============================================================================ */ /** * Next up, the transformer. Our transformer is going to take the AST that we * have built and pass it to our traverser function with a visitor and will * create a new ast. * * ---------------------------------------------------------------------------- * Original AST | Transformed AST * ---------------------------------------------------------------------------- * { | { * type: 'Program', | type: 'Program', * body: [{ | body: [{ * type: 'CallExpression', | type: 'ExpressionStatement', * name: 'add', | expression: { * params: [{ | type: 'CallExpression', * type: 'NumberLiteral', | callee: { * value: '2' | type: 'Identifier', * }, { | name: 'add' * type: 'CallExpression', | }, * name: 'subtract', | arguments: [{ * params: [{ | type: 'NumberLiteral', * type: 'NumberLiteral', | value: '2' * value: '4' | }, { * }, { | type: 'CallExpression', * type: 'NumberLiteral', | callee: { * value: '2' | type: 'Identifier', * }] | name: 'subtract' * }] | }, * }] | arguments: [{ * } | type: 'NumberLiteral', * | value: '4' * ---------------------------------- | }, { * | type: 'NumberLiteral', * | value: '2' * | }] * (sorry the other one is longer.) | } * | } * | }] * | } * ---------------------------------------------------------------------------- */ // So we have our transformer function which will accept the lisp ast. function transformer(ast) { // We'll create a `newAst` which like our previous AST will have a program // node. let newAst = { type: 'Program', body: [], }; // Next I'm going to cheat a little and create a bit of a hack. We're going to // use a property named `context` on our parent nodes that we're going to push // nodes to their parent's `context`. Normally you would have a better // abstraction than this, but for our purposes this keeps things simple. // // Just take note that the context is a reference *from* the old ast *to* the // new ast. ast._context = newAst.body; // We'll start by calling the traverser function with our ast and a visitor. traverser(ast, { // The first visitor method accepts any `NumberLiteral` NumberLiteral: { // We'll visit them on enter. enter(node, parent) { // We'll create a new node also named `NumberLiteral` that we will push to // the parent context. parent._context.push({ type: 'NumberLiteral', value: node.value, }); }, }, // Next we have `StringLiteral` StringLiteral: { enter(node, parent) { parent._context.push({ type: 'StringLiteral', value: node.value, }); }, }, // Next up, `CallExpression`. CallExpression: { enter(node, parent) { // We start creating a new node `CallExpression` with a nested // `Identifier`. let expression = { type: 'CallExpression', callee: { type: 'Identifier', name: node.name, }, arguments: [], }; // Next we're going to define a new context on the original // `CallExpression` node that will reference the `expression`'s arguments // so that we can push arguments. node._context = expression.arguments; // Then we're going to check if the parent node is a `CallExpression`. // If it is not... if (parent.type !== 'CallExpression') { // We're going to wrap our `CallExpression` node with an // `ExpressionStatement`. We do this because the top level // `CallExpression` in JavaScript are actually statements. expression = { type: 'ExpressionStatement', expression: expression, }; } // Last, we push our (possibly wrapped) `CallExpression` to the `parent`'s // `context`. parent._context.push(expression); }, } }); // At the end of our transformer function we'll return the new ast that we // just created. return newAst; } /** * ============================================================================ * ヾ（〃＾∇＾）ﾉ♪ * THE CODE GENERATOR!!!! * ============================================================================ */ /** * Now let's move onto our last phase: The Code Generator. * * Our code generator is going to recursively call itself to print each node in * the tree into one giant string. */ function codeGenerator(node) { // We'll break things down by the `type` of the `node`. switch (node.type) { // If we have a `Program` node. We will map through each node in the `body` // and run them through the code generator and join them with a newline. case 'Program': return node.body.map(codeGenerator) .join('\n'); // For `ExpressionStatement` we'll call the code generator on the nested // expression and we'll add a semicolon... case 'ExpressionStatement': return ( codeGenerator(node.expression) + ';' // << (...because we like to code the *correct* way) ); // For `CallExpression` we will print the `callee`, add an open // parenthesis, we'll map through each node in the `arguments` array and run // them through the code generator, joining them with a comma, and then // we'll add a closing parenthesis. case 'CallExpression': return ( codeGenerator(node.callee) + '(' + node.arguments.map(codeGenerator) .join(', ') + ')' ); // For `Identifier` we'll just return the `node`'s name. case 'Identifier': return node.name; // For `NumberLiteral` we'll just return the `node`'s value. case 'NumberLiteral': return node.value; // For `StringLiteral` we'll add quotations around the `node`'s value. case 'StringLiteral': return '"' + node.value + '"'; // And if we haven't recognized the node, we'll throw an error. default: throw new TypeError(node.type); } } /** * ============================================================================ * (۶* ‘ヮ’)۶” * !!!!!!!!THE COMPILER!!!!!!!! * ============================================================================ */ /** * FINALLY! We'll create our `compiler` function. Here we will link together * every part of the pipeline. * * 1. input => tokenizer => tokens * 2. tokens => parser => ast * 3. ast => transformer => newAst * 4. newAst => generator => output */ function compiler(input) { let tokens = tokenizer(input); let ast = parser(tokens); let newAst = transformer(ast); let output = codeGenerator(newAst); // and simply return the output! return output; } /** * ============================================================================ * (๑˃̵ᴗ˂̵)و * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!YOU MADE IT!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! * ============================================================================ */ // Now I'm just exporting everything... module.exports = { tokenizer, parser, traverser, transformer, codeGenerator, compiler, };