2c:null 2d:["$","title",null,{"children":"Inside a Programming Language | Steffen Hänsch | Observable"}] 32:T6c3,md` # Inside a Programming Language After reading Mariko Kosaka's [blog post on how to create a compiler](https://medium.com/@kosamari/how-to-be-a-compiler-make-a-compiler-with-javascript-4a8a13d473b4) for a graphical programming language, I got inspired to create my own little language for data visualization. It should be as simple as typing \`\`\` CANVAS 300, 300 BARCHART: year,income 2015,1.7bn 2016,1.8bn 2017,2.1bn \`\`\` into a textfield and getting a visualisation right back: ${sampleImage} ### Roll your own Creating your own language lets you abstract away a lot of things in the background and instead focus on how to be **as clear as you can about what you want to achieve** using written language. Writing \`CANVAS 300, 300\` is probably the most minimal way of saying you want to have an image output with a size of 300 by 300 pixels. It's definitely shorter than typing: \`\`\` \`\`\` or even using a dedicated library like d3: \`\`\` d3.select("body").append("svg").attr("width", 300).attr("height", 300) \`\`\` The other benefit of rolling your own is that you can have a look at what is happening inside the compiler as you type. When looking at Mariko's [interactive demo](https://kosamari.github.io/sbn/), seeing the outputs of each phase while I typed was more fascinating to me than the actual generated image.

### What you need In order to create your own language interpreter, you need a **lexer** to weed out valid from invalid input, a **parser** to combine lexed tokens into a command and a **generator** to actually create code from the given commands. We will look at each of the steps in detail further down this article. `33:T492,md`

## The Lexer - seperating the good from the bad The lexer turns the input written into the textfield into series of tokens. It has to make sure, that the user only types in sequences of characters, that are digestible by the parser in the next step. It does not, however, judge the content of the input nor the composition of it. It only looks at the pure form of the provided characters and if they fit the pattern that the language author made up. In our case, for example, a semicolon will be treated as an invalid character, since it holds no meaning to the language. The tokens that will be passed to the parser will hold information about their content, their type and their position in the input string. So we expect an input of \`\`\` CANVAS 300 300 \`\`\` to become this: \`\`\` [ {type: "WORD_CAPITALIZED", value: "CANVAS", column: 0}, {type: "WHITESPACE", value: " ", column: 6}, {type: "NUMBER", value: "300", column: 7}, {type: "WHITESPACE", value: " ", column: 10}, {type: "NUMBER", value: "300", column: 11} ] \`\`\` Following are the types of input that we define as valid and the actual lexer function: `34:T4d2,function lexer (input, tokens, column) { // input check let matchLength = null; let matchContent = null; let matchType = null; let newString = null; let i; let columnIndex = column || 0; for (i = 0; i < validTokens.length; i += 1) { const match = validTokens[i].regex.exec(input); if (match) { matchLength = match[0].length; matchContent = match[0]; matchType = validTokens[i].tokenType; newString = input.substring(matchLength); } } // exit: invalid character if (!matchContent && input.length > 0) { throw new Error(`invalid character`); } // base case: empty string if (input.length === 0) { return tokens ? tokens : []; } // create new match token const newMatch = { type: matchType, value: matchContent, column: columnIndex, }; columnIndex += matchContent.length; // the function takes two parameters, an input string and an array of tokens. If // no token array is provided (initial call), an empty one will be created. const newTokenArray = tokens ? tokens.concat(newMatch) : [].concat(newMatch); // repeat with shortened string and appended array return lexer(newString, newTokenArray, columnIndex); }35:Tc8e,function parser (lexed) { const AST = []; const validCommands = [ 'CANVAS', 'TABLE', 'BARCHART', ]; let currentToken = null; let currentCommand = null; if (lexed.length === 0) throw new Error('no input to process'); else currentToken = lexed.shift(); const errMissArg = new Error('Missing arguments: command must be followed by arguments'); const errMissArgCanv = new Error('CANVAS command needs two numbers as arguments'); const checkUnexpectedEndOfLine = (lexed, handler) => { if (lexed.length === 0) { throw handler; } } // first token must be a command if (currentToken.type !== 'WORD_CAPITALIZED') { throw new Error(`A line must start with a command, you started with ${currentToken.type}`); } else if (validCommands.indexOf(currentToken.value) === -1) { throw new Error(`"${currentToken.value}" is not a valid command`); } else { currentCommand = currentToken.value; // memorize valid command switch (currentCommand) { case 'CANVAS': // create new canvas command const canvasCommand = { type: 'COMMAND', name: 'canvas', arguments: [], expected: 2, }; if (lexed.length === 0) { AST.push(canvasCommand); return AST; } currentToken = lexed.shift(); // command has to be followed by whitespace if (currentToken.type !== 'WHITESPACE') { throw new Error(`A command must be followed by a single whitespace, not by ${currentToken.type}`); } else { if (lexed.length === 0) { AST.push(canvasCommand); return AST; } currentToken = lexed.shift(); } if (currentToken.type !== 'NUMBER') { throw new Error('CANVAS command must be followed by a number'); } else { // add the current number as the first canvas argument canvasCommand.arguments.push(Number.parseInt(currentToken.value, 10)); if (lexed.length === 0) { AST.push(canvasCommand); return AST; } currentToken = lexed.shift(); if (currentToken.type === 'COMMA' || currentToken.type === 'WHITESPACE') { if (lexed.length === 0) { AST.push(canvasCommand); return AST; } currentToken = lexed.shift(); if (currentToken.type === 'WHITESPACE') { if (lexed.length === 0) { AST.push(canvasCommand); return AST; } currentToken = lexed.shift(); } // now expect number if (currentToken.type !== 'NUMBER') { throw new Error('CANVAS command needs a second number argument'); } else { canvasCommand.arguments.push(Number.parseInt(currentToken.value, 10)); } } else { throw new Error('first number of CANVAS command must be followed by comma, whitespace or a comma and whitespace'); } AST.push(canvasCommand); return AST; } default: return 'default'; } } }36:T4b2,TokenList = { // token const Token = { view: (vnode) => { return m('div', { class: `token-container${ vnode.attrs.index === vnode.attrs.state.activeIndex ? ' active' : '' }`, style: `width: ${vnode.attrs.token.value.length * 11}px; padding: 5px;`, onmouseover: function() { if (vnode.attrs.state) vnode.attrs.state.activeIndex = vnode.attrs.index; }, onmouseout: function() { if (vnode.attrs.state) vnode.attrs.state.activeIndex = -1; }, }, [ m('div', {class: 'line'}), m('p', {class: 'token-value'}, vnode.attrs.token.value === ' ' ? '▫' : vnode.attrs.token.value), m(InfoCard, {token: vnode.attrs.token, active: vnode.attrs.index === vnode.attrs.state.activeIndex}), ] ); } } // token list const _TokenList = { view: (vnode) => m('div', {class: 'token-list'}, vnode.attrs.tokens.map((t, i) => { return m(Token, { token: t, index: i, state: vnode.attrs.state, }); } )), }; return _TokenList; }37:T470,InfoCard = { const typeMap = { 'WORD_CAPITALIZED': { type: 'Word', subtype: 'Capital Letters', }, 'WHITESPACE': { type: 'Whitespace', subtype: 'Single Space', }, 'COMMA': { type: 'Seperator', subtype: 'Comma', }, 'NUMBER': { type: 'Number', subtype: 'Integer', }, }; // info card const _InfoCard = { view: (vnode) => m('div', {class: `info-card ${vnode.attrs.active ? 'active' : ''}`}, [ m('div', {class: 'row'}, m(KeyValue, { caption: 'value', value: vnode.attrs.token.value === ' ' ? '▫' : vnode.attrs.token.value, })), m('div', {class: 'row'}, [ m(KeyValue, {caption: 'type', value: typeMap[vnode.attrs.token.type].type}), m(KeyValue, {caption: 'subtype', value: typeMap[vnode.attrs.token.type].subtype}) ]), m('div', {class: 'row'}, [ m(KeyValue, {caption: 'line', value: 0}), m(KeyValue, {caption: 'column', value: vnode.attrs.token.column}), m(KeyValue, {caption: 'length', value: vnode.attrs.token.value.length}), ]), ]), } return _InfoCard; }38:Te58,html` `39:T13ac,sampleImage = ``3a:[] 30:{"id":"f6448d1681ef0306","slug":"inside-a-programming-language","title":"Inside a Programming Language","thumbnail":"84bce628fa26c8f99b49fef2facbff02b404d824b60ddec0401049c5b9b8f70e","access_level":"public","create_time":"$D2018-02-11T16:37:55.959Z","update_time":"$D2023-03-31T19:56:15.605Z","view_time":null,"first_public_time":"$D2018-02-28T17:32:18.475Z","has_unpublished_edits":null,"fork":false,"stars":5,"starred":false,"owner":{"type":"team","id":"9f0a5778a9e93283","login":"s-haensch","name":"Steffen Hänsch","avatar_url":"https://avatars-next.observableusercontent.com/f8ae573e8ef3303795b5c307e85b49753b498e72abbb8e91b0f4ba73e7327515","tier":"starter_2024"},"version":1069,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"54a3b46988329fc4","login":"s-haensch","name":"Steffen Hänsch","avatar_url":"https://avatars-next.observableusercontent.com/f8ae573e8ef3303795b5c307e85b49753b498e72abbb8e91b0f4ba73e7327515","tier":null}],"members":[{"type":"individual","id":"54a3b46988329fc4","login":"s-haensch","name":"Steffen Hänsch","avatar_url":"https://avatars-next.observableusercontent.com/f8ae573e8ef3303795b5c307e85b49753b498e72abbb8e91b0f4ba73e7327515","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Inside a Programming Language","cells":[{"id":0,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":81,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":93,"value":"validTokens = [\n { regex: /^[A-Z]+\\b/, tokenType: 'WORD_CAPITALIZED' },\n { regex: /^\\s+/, tokenType: 'WHITESPACE' },\n { regex: /^,/, tokenType: 'COMMA' },\n { regex: /^\\d+\\b/, tokenType: 'NUMBER' },\n]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":268,"value":"md`

\n### See it in action\nNow type something to see the lexer in action: \n_(no real error handling, REMEMBER: just use capital letters, numbers, whitespaces and comma. All other characters will throw an 'invalid character' error. You can hover the tokens to see information about them.)_`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":234,"value":"viewof input = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":406,"value":"{\n const localState = {\n activeIndex: null,\n activeToken: null,\n };\n \n const lexed = lexer(input);\n if (lexed.length > 0) {\n var LexerOutput = {\n view: function() {\n return m(\"main\", [\n m(TokenList, {tokens: lexed, state: localState}),\n ]);\n }\n }\n\n const container = DOM.element('div'); \n m.mount(container, LexerOutput)\n return container;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":543,"value":"lexer(input)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":680,"value":"md`↑ _expand the array above to see the array of tokens our lexer has returned._`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":275,"value":"md`\n

\n## The Parser - Turning input into commands\nAfter we made sure, that the type of input is correct, i.e. using only valid characters, we still have to make sure that the order and the combination of the tokens makes sense to our interpreter. So while starting a line with the number \\`300\\` would pass the lexer, our parser now has to say that it expects a line to begin with a command in capital letters.\n\nInside the parser, there is a big decision tree that checks the sequence of tokens against an expected scheme and has to provide an answer for every possible exception that can occur.\n\nTry to break the parser by giving it invalid or insufficient input. Once you typed the \\`CANVAS\\` keyword, you will see an unfinished commmand element with two blank circles, indicating that two arguments are missing.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":667,"value":"viewof input2 = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1062,"value":"parser(lexer(input2))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":331,"value":"{\n const lexed = lexer(input2);\n const parsed = parser(lexer(input2));\n \n\n var ParserOutput = {\n view: function() {\n return m(\"main\", m(CommandList, {parsed: parsed}));\n }\n }\n \n const container = DOM.element('div');\n m.mount(container, ParserOutput)\n return container;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":687,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":696,"value":"md`\n

\n## The Generator\nThe generator will turn every drawing command and its provided arguments into a visual component. After all of the input has been checked and abstracted into instructions, this is the execution part that will give you the result that you have actually asked for with your input.\n` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":758,"value":"viewof input3 = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":708,"value":"{\n const localState = {\n activeIndex: null,\n activeToken: null,\n };\n \n const generated = generator(parser(lexer(input3)));\n const container = DOM.element('div');\n m.mount(container, { \n view: () => m('main', [\n m(TokenList, {tokens: lexer(input3), state: localState}),\n m(CommandList, {parsed: parser(lexer(input3))}),\n generated\n \t])\n });\n return container;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":761,"value":"generator = (parsed) => {\n const SVG = {\n view: (vnode) => m(\n 'svg', \n {width: vnode.attrs.width, height: vnode.attrs.height},\n [m('rect', {width: '100%', height: '100%', fill: '#eee'})]\n ),\n }\n \n let [width, height] = _.find(parsed, o => o.name === 'canvas')\n ? _.find(parsed, o => o.name === 'canvas').arguments\n : [300, 300];\n \n \n if (width === undefined) width = 300;\n if (height === undefined) height = 300;\n\n return m(SVG, {width: width, height: height});\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1051,"value":"md`\n

\n## Nice, but where's my bar chart?\nAlright, I get it, this isn't much to look at. And it doesn't even hold the bar chart I promised in the beginning. Due to lack of time I ended the experiment at this point, but the process of creating your own programming language should become clear.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":692,"value":"md`\n

\n#### _libraries, components and stuff_\n_(nothing good to see here)_\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":510,"value":"m = require('mithril@1.1.6/mithril.js').catch(() => window.m)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1027,"value":"KeyValue = {\n const _KeyValue = {\n view: (vnode) =>\n m('div', {class: 'key-value-container'}, [\n m('p', {class: 'caption'}, vnode.attrs.caption),\n m('p', {class: 'text'}, vnode.attrs.value),\n ]),\n }\n \n return _KeyValue;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1032,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1035,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1047,"value":"CommandList = {\n const Command = {\n view: (vnode) => {\n const diff = vnode.attrs.command.expected - vnode.attrs.command.arguments.length;\n const missingArgs = [];\n for (let i = 0; i < diff; i += 1) {\n missingArgs.push(m('li', {class: 'command-argument missing'}));\n }\n\n return m('ul', {class: 'command-container'}, [\n m('li', {class: 'name'}, vnode.attrs.command.name),\n vnode.attrs.command.arguments.map((att) => m('li', {class: 'command-argument fulfilled'})),\n missingArgs,\n ])\n },\n }\n \n const _CommandList = {\n view: (vnode) =>\n m('ul',\n {class: 'command-list'},\n vnode.attrs.parsed.map((c, i) => m(Command, { command: c })))\n\n }\n \n return _CommandList;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":706,"value":"_ = require('lodash')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":513,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":867,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3a","stdlib":"1"}} 31:"$30:body"