create-your-own-programming-language-net.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Create Your First Programming Language That Runs on .NET\n",
    "\n",
    "> Write a mini programming language that outputs valid CIL in a notebook in under an hour\n",
    "<div>\n",
    "<style>\n",
    "@scope {\n",
    "    p {\n",
    "        margin: 0;\n",
    "    }\n",
    "}\n",
    "</style>\n",
    "<div style=\"display: flex; justify-content: space-between; align-items: center;\">\n",
    "<time datetime=\"2023-11-10\">November 10, 2023</time>\n",
    "<div style=\"display: flex; flex-flow: wrap; align-items: center; flex: 1; margin-bottom: 4px; justify-content: end; margin-left: 1em; column-gap: 0.5em;\">\n",
    "<div style=\"margin-bottom: 1px;\">\n",
    "\n",
    "[![Open in VS Code](media/open-in-vscode.svg)](vscode://vscode.git/clone?url=https://github.com/johnW-ret/blog)\n",
    "</div>\n",
    "<div>\n",
    "\n",
    "[![Open in GitHub Codespaces](https://github.com/codespaces/badge.svg)](https://github.com/codespaces/new?template_repository=johnW-ret/blog)\n",
    "</div>\n",
    "</div>\n",
    "</div>\n",
    "</div>\n",
    "\n",
    "---\n",
    "\n",
    "> Note: as of this writing, C# 11 is the latest version of C# to be released. C# 12 includes a feature that would make a lot of this code more concise - [collection expressions](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/proposals/csharp-12.0/collection-expressions), however, I don't want to figure out how to get preview versions of .NET to work in a notebook. As such, I plan to update this when C# 12 releases.\n",
    "\n",
    "Compilers can be a tricky topic to get into. There are [plenty](https://github.com/sandersn/mini-typescript) of [resources](https://archive.org/details/aho-compilers-principles-techniques-and-tools-2e_202203) available to learn compilers, but nothing I've found as small as a notebook.\n",
    "\n",
    "This purpose of this notebook is to demonstrate an example of a tiny compiler.\n",
    "\n",
    "Goals:\n",
    "------\n",
    "- Runs on .NET runtime as its own executable!\n",
    "- variables, assignment, integer expression evaluation\n",
    "- runs without the need of parser generators\n",
    "\n",
    "Plan\n",
    "----\n",
    "This compiler follows 4 main phases of a canonical compiler:\n",
    "1. Lexer\n",
    "2. Parser\n",
    "3. Semantic Analysis\n",
    "4. Codegen\n",
    "\n",
    "> Note: This language is extremely underwhelming. It supports no functions, only a single class of the most basic operators, has a single type of `int`, gives *zero* helpful error messages (it either works or it doesn't), and despite running on .NET, you can't explicitly import or call any of the .NET methods."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lexer\n",
    "The first step in a compiler is a lexer. The idea is to take string text and convert it into a sequence of tokens, kind of like how you can take an English sentence and split it into words with `string.Split(\" \")`.\n",
    "\n",
    "We can't use `string.Split(\" \")` for tokens, though, because sometimes tokens are not separated by spaces. For example, `x = 3` and `x=3` are both valid Python programs. Instead, we'll use something called regular expressions (`Regex`).\n",
    "\n",
    "## Regex\n",
    "A regex is a pattern with which we can test whether another string conforms to that pattern. For example, the string `name` matches the pattern `name`. In a regex, the unescaped `.` means \"match any single character\". So therefore, `name` also matches the pattern `n.me`, as well as the strings `nome` and `neme`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/csv": [
       "String,IsMatch\r\n",
       "name,True\r\n",
       "neme,True\r\n",
       "nome,True\r\n",
       "neem,False\r\n"
      ],
      "text/html": [
       "<table><thead><tr><td><span>String</span></td><td><span>IsMatch</span></td></tr></thead><tbody><tr><td>name</td><td><div class=\"dni-plaintext\"><pre>True</pre></div></td></tr><tr><td>neme</td><td><div class=\"dni-plaintext\"><pre>True</pre></div></td></tr><tr><td>nome</td><td><div class=\"dni-plaintext\"><pre>True</pre></div></td></tr><tr><td>neem</td><td><div class=\"dni-plaintext\"><pre>False</pre></div></td></tr></tbody></table><style>\r\n",
       ".dni-code-hint {\r\n",
       "    font-style: italic;\r\n",
       "    overflow: hidden;\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview {\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview td {\r\n",
       "    vertical-align: top;\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "details.dni-treeview {\r\n",
       "    padding-left: 1em;\r\n",
       "}\r\n",
       "table td {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "table tr { \r\n",
       "    vertical-align: top; \r\n",
       "    margin: 0em 0px;\r\n",
       "}\r\n",
       "table tr td pre \r\n",
       "{ \r\n",
       "    vertical-align: top !important; \r\n",
       "    margin: 0em 0px !important;\r\n",
       "} \r\n",
       "table th {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "</style>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "using System.Text.RegularExpressions;\n",
    "\n",
    "string[] words = [\"name\", \"neme\", \"nome\", \"neem\"];\n",
    "string pattern = \"n.me\";\n",
    "\n",
    "words.Select(w => new { String = w, IsMatch = Regex.IsMatch(w, pattern) }).DisplayTable()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Another reason we might want to use `Regex` to break strings into tokens (\"sentence into words\") is because it helps us classify our tokens into *types* or *categories*. In English sentences, words are classified into \"parts of speech\", like \"verb\" and \"noun\". In a naive example where words fall into one part of speech, we can look up words in a sentence in a dictionary to find their parts of speech. For example, in `I ran to the store`, `I` is a noun, `ran` is a past-tense verb, etc. With regex, we actually have it a bit easier, as we can classify tokens based on their *patterns* instead of looking them up in a dictionary. For example, the pattern `-?[0-9]+` matches integers like `1` and `626`, and the pattern `^[a-zA-Z]+[0-9a-zA-Z]*` matches IDs like `index` and `age`. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, we'll define our token types using an `enum`, and a `record struct` to store our token type, along with an `int Start` and `ReadOnlyMemory<char> Memory` to reference where it lives in memory.\n",
    "\n",
    "> (we could use this information in the future for error reporting, though we do not in this example) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "dotnet_interactive": {
     "language": "pwsh"
    },
    "polyglot_notebook": {
     "kernelName": "pwsh"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "MSBuild version 17.8.3+195e7f5a3 for .NET\n",
      "  Determining projects to restore...\n",
      "  All projects are up-to-date for restore.\n",
      "  learn -> C:\\Users\\retru\\source\\repos\\johnW-ret\\Retruate.Languages\\learn\\bin\\Release\\net8.0\\learn.dll\n",
      "\n",
      "Build succeeded.\n",
      "    0 Warning(s)\n",
      "    0 Error(s)\n",
      "\n",
      "Time Elapsed 00:00:01.45\n"
     ]
    }
   ],
   "source": [
    "dotnet build -c Release"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "#r \"bin/Release/net8.0/learn.dll\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also want to associate token types with their corresponding `Regex` rules.\n",
    "\n",
    "We could use a `Dictionary` (hashmap) here, but as we'll see, we'll be iterating through our collection of rules, so it makes more sense to just define them as a list of tuples. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "(TokenType Type, Regex Pattern)[] rules = [\n",
    "    (TokenType.Semicolon,           new(@\"^;\", RegexOptions.Compiled)),\n",
    "    (TokenType.Assignment,          new(@\"^=\", RegexOptions.Compiled)),\n",
    "    (TokenType.LeftParenthesis,     new(@\"^\\(\", RegexOptions.Compiled)),\n",
    "    (TokenType.RightParenthesis,    new(@\"^\\)\", RegexOptions.Compiled)),\n",
    "    (TokenType.Add,                 new(@\"^\\+\", RegexOptions.Compiled)),\n",
    "    (TokenType.Subtract,            new(@\"^\\-\", RegexOptions.Compiled)),\n",
    "    (TokenType.Multiply,            new(@\"^\\*\", RegexOptions.Compiled)),\n",
    "    (TokenType.Divide,              new(@\"^/\", RegexOptions.Compiled)),\n",
    "    (TokenType.Id,                  new(@\"^[a-zA-Z]+[0-9a-zA-Z]*\", RegexOptions.Compiled)),\n",
    "    (TokenType.Integer,             new(@\"^-?[0-9]+\", RegexOptions.Compiled)),\n",
    "    (TokenType.Whitespace,          new(@\"^[ \\n\\t\\r]\", RegexOptions.Compiled))\n",
    "];"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In our case, we can modify our use of `Regex` to \"pull tokens off\" when we have at least one match.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "With this knowledge, we can imagine a simple algorithm to break off tokens:\n",
    "```\n",
    "tokens = []\n",
    "\n",
    "while input string s not empty\n",
    "    for each (type, regex pattern) in rules\n",
    "        search for first match m in regex pattern\n",
    "        if m exists\n",
    "            add (m, type) to tokens\n",
    "        if m not exists\n",
    "            error\n",
    "\n",
    "return tokens\n",
    "```\n",
    "\n",
    "which is exactly what we do below"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we define our input string:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "ReadOnlyMemory<char> input =\n",
    "    \"\"\"\n",
    "    a = 2;\n",
    "    b = 3;\n",
    "    c = (3 + a) * b;\n",
    "\n",
    "    c\n",
    "    \"\"\".AsMemory();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You'll note that instead of using a `string` directly, we call `AsMemory` and store it as a `ReadOnlyMemory<char>`.\n",
    "\n",
    "`ReadOnlyMemory<char>` and `ReadOnlySpan<char>` allow us to create wrappers over our original input string and slice the front off each time we pull off a token without passing an `int` pointer or and without copying any of the input string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><thead><tr><th><i>index</i></th><th>value</th></tr></thead><tbody><tr><td>0</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 0, Memory = a, Type = Id }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>0</pre></div></td></tr><tr><td>Memory</td><td><span>a</span></td></tr><tr><td>Type</td><td><span>Id</span></td></tr></tbody></table></div></details></td></tr><tr><td>1</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 2, Memory = =, Type = Assignment }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>2</pre></div></td></tr><tr><td>Memory</td><td><span>=</span></td></tr><tr><td>Type</td><td><span>Assignment</span></td></tr></tbody></table></div></details></td></tr><tr><td>2</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 4, Memory = 2, Type = Integer }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>4</pre></div></td></tr><tr><td>Memory</td><td><span>2</span></td></tr><tr><td>Type</td><td><span>Integer</span></td></tr></tbody></table></div></details></td></tr><tr><td>3</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 5, Memory = ;, Type = Semicolon }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>5</pre></div></td></tr><tr><td>Memory</td><td><span>;</span></td></tr><tr><td>Type</td><td><span>Semicolon</span></td></tr></tbody></table></div></details></td></tr><tr><td>4</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 7, Memory = b, Type = Id }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>7</pre></div></td></tr><tr><td>Memory</td><td><span>b</span></td></tr><tr><td>Type</td><td><span>Id</span></td></tr></tbody></table></div></details></td></tr><tr><td>5</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 9, Memory = =, Type = Assignment }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>9</pre></div></td></tr><tr><td>Memory</td><td><span>=</span></td></tr><tr><td>Type</td><td><span>Assignment</span></td></tr></tbody></table></div></details></td></tr><tr><td>6</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 11, Memory = 3, Type = Integer }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>11</pre></div></td></tr><tr><td>Memory</td><td><span>3</span></td></tr><tr><td>Type</td><td><span>Integer</span></td></tr></tbody></table></div></details></td></tr><tr><td>7</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 12, Memory = ;, Type = Semicolon }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>12</pre></div></td></tr><tr><td>Memory</td><td><span>;</span></td></tr><tr><td>Type</td><td><span>Semicolon</span></td></tr></tbody></table></div></details></td></tr><tr><td>8</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 14, Memory = c, Type = Id }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>14</pre></div></td></tr><tr><td>Memory</td><td><span>c</span></td></tr><tr><td>Type</td><td><span>Id</span></td></tr></tbody></table></div></details></td></tr><tr><td>9</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 16, Memory = =, Type = Assignment }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>16</pre></div></td></tr><tr><td>Memory</td><td><span>=</span></td></tr><tr><td>Type</td><td><span>Assignment</span></td></tr></tbody></table></div></details></td></tr><tr><td>10</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 18, Memory = (, Type = LeftParenthesis }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>18</pre></div></td></tr><tr><td>Memory</td><td><span>(</span></td></tr><tr><td>Type</td><td><span>LeftParenthesis</span></td></tr></tbody></table></div></details></td></tr><tr><td>11</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 19, Memory = 3, Type = Integer }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>19</pre></div></td></tr><tr><td>Memory</td><td><span>3</span></td></tr><tr><td>Type</td><td><span>Integer</span></td></tr></tbody></table></div></details></td></tr><tr><td>12</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 21, Memory = +, Type = Add }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>21</pre></div></td></tr><tr><td>Memory</td><td><span>+</span></td></tr><tr><td>Type</td><td><span>Add</span></td></tr></tbody></table></div></details></td></tr><tr><td>13</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 23, Memory = a, Type = Id }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>23</pre></div></td></tr><tr><td>Memory</td><td><span>a</span></td></tr><tr><td>Type</td><td><span>Id</span></td></tr></tbody></table></div></details></td></tr><tr><td>14</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 24, Memory = ), Type = RightParenthesis }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>24</pre></div></td></tr><tr><td>Memory</td><td><span>)</span></td></tr><tr><td>Type</td><td><span>RightParenthesis</span></td></tr></tbody></table></div></details></td></tr><tr><td>15</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 26, Memory = *, Type = Multiply }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>26</pre></div></td></tr><tr><td>Memory</td><td><span>*</span></td></tr><tr><td>Type</td><td><span>Multiply</span></td></tr></tbody></table></div></details></td></tr><tr><td>16</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 28, Memory = b, Type = Id }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>28</pre></div></td></tr><tr><td>Memory</td><td><span>b</span></td></tr><tr><td>Type</td><td><span>Id</span></td></tr></tbody></table></div></details></td></tr><tr><td>17</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 29, Memory = ;, Type = Semicolon }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>29</pre></div></td></tr><tr><td>Memory</td><td><span>;</span></td></tr><tr><td>Type</td><td><span>Semicolon</span></td></tr></tbody></table></div></details></td></tr><tr><td>18</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 32, Memory = c, Type = Id }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>32</pre></div></td></tr><tr><td>Memory</td><td><span>c</span></td></tr><tr><td>Type</td><td><span>Id</span></td></tr></tbody></table></div></details></td></tr></tbody></table><style>\r\n",
       ".dni-code-hint {\r\n",
       "    font-style: italic;\r\n",
       "    overflow: hidden;\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview {\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview td {\r\n",
       "    vertical-align: top;\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "details.dni-treeview {\r\n",
       "    padding-left: 1em;\r\n",
       "}\r\n",
       "table td {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "table tr { \r\n",
       "    vertical-align: top; \r\n",
       "    margin: 0em 0px;\r\n",
       "}\r\n",
       "table tr td pre \r\n",
       "{ \r\n",
       "    vertical-align: top !important; \r\n",
       "    margin: 0em 0px !important;\r\n",
       "} \r\n",
       "table th {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "</style>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#nullable enable\n",
    "public List<Token>? Lex(ReadOnlyMemory<char> feed) \n",
    "{\n",
    "    List<Token> tokens = new();\n",
    "\n",
    "    while (feed.Length > 0)\n",
    "    {\n",
    "        // get the first match\n",
    "        foreach (var rule in rules)\n",
    "        {\n",
    "            var match = rule.Pattern.EnumerateMatches(feed.Span);\n",
    "            if (match.MoveNext())\n",
    "            {\n",
    "                tokens.Add(new Token(input.Length - feed.Length, feed[0..match.Current.Length], rule.Type));\n",
    "                feed = feed[match.Current.Length..];\n",
    "                goto next;\n",
    "            }\n",
    "        }\n",
    "        \n",
    "        // tokens[^1] switch { _ => ... }\n",
    "        Console.WriteLine(\"Error at: \" + ((Func<Token, string>)(t => $\"{t.Start} {t.Type} {t.Memory}\"))(tokens[^1]));\n",
    "        return null;\n",
    "        next:;\n",
    "    }\n",
    "\n",
    "    // remove whitespace\n",
    "    return tokens.Where(t => t.Type != TokenType.Whitespace).ToList();\n",
    "}\n",
    "\n",
    "var tokens = Lex(input);\n",
    "tokens"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great! Our input was an input `string` and now we have a `List<Token> tokens`!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parser\n",
    "Once we have our string of tokens, the next step is the parser.\n",
    "\n",
    "The input of the parser is our string of tokens, and the output is something called an **Abstract Syntax Tree (AST)**. Our parser is going to be a method that looks something like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "record DummyProgram(); // dummy AST\n",
    "static DummyProgram Parse(ReadOnlySpan<Token> tokens) => \n",
    "    // replace with parser logic\n",
    "    new();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this case, `DummyProgram` is our AST type. Then we can get our AST like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "DummyProgram dummyProgram = Parse(Lex(\"abcd\".AsMemory()).ToArray().AsSpan());"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The AST represents the source file as a tree. It is useful, because we can use it as input to another method to generate code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "static string Emit(DummyProgram program) => \n",
    "    // replace with emit logic\n",
    "    string.Empty;\n",
    "\n",
    "static void DummyWriteEmittedCodeToExecutable(string code) { }\n",
    "\n",
    "DummyWriteEmittedCodeToExecutable(Emit(dummyProgram));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To understand how the AST is generated, we have to understand grammar."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grammar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Imagine we have a string and we'd like to check whether it exists in a language:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "string sentence = \"i run to the store\";"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can imagine a method that checks whether that given string exists in a language:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "bool Validate(string sentence) =>\n",
    "    // replace with validation rules\n",
    "    true;\n",
    "\n",
    "Validate(sentence);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A *grammar* simply defines the rules of a language, and we can use those rules to validate whether a given string is valid.\n",
    "\n",
    "Every language has a grammar, for example, take a possible subset of English grammar:\n",
    "```\n",
    "Prepositional Phrase -> to the Noun\n",
    "Noun        -> store | post office\n",
    "```\n",
    "\n",
    "The capital letters are called *non-terminals*, which means that they have one or more *production rules*, and can be *expanded* into the right hand side of one of their production rules. The lowercase letters are called *terminals* which is basically just the same thing as tokens honestly in that they cannot be expanded with production rules and therefore make up the final sentence of the grammar.\n",
    "\n",
    "We can take the `Noun` rule and encode it as a method, which can directly be used to validate a sentence:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"dni-plaintext\"><pre>True</pre></div><style>\r\n",
       ".dni-code-hint {\r\n",
       "    font-style: italic;\r\n",
       "    overflow: hidden;\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview {\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview td {\r\n",
       "    vertical-align: top;\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "details.dni-treeview {\r\n",
       "    padding-left: 1em;\r\n",
       "}\r\n",
       "table td {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "table tr { \r\n",
       "    vertical-align: top; \r\n",
       "    margin: 0em 0px;\r\n",
       "}\r\n",
       "table tr td pre \r\n",
       "{ \r\n",
       "    vertical-align: top !important; \r\n",
       "    margin: 0em 0px !important;\r\n",
       "} \r\n",
       "table th {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "</style>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "bool IsNoun(string subsentence) => subsentence is \"store\" or \"post office\";\n",
    "\n",
    "IsNoun(\"store\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That was easy enough. We can do another one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"dni-plaintext\"><pre>True</pre></div><style>\r\n",
       ".dni-code-hint {\r\n",
       "    font-style: italic;\r\n",
       "    overflow: hidden;\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview {\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview td {\r\n",
       "    vertical-align: top;\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "details.dni-treeview {\r\n",
       "    padding-left: 1em;\r\n",
       "}\r\n",
       "table td {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "table tr { \r\n",
       "    vertical-align: top; \r\n",
       "    margin: 0em 0px;\r\n",
       "}\r\n",
       "table tr td pre \r\n",
       "{ \r\n",
       "    vertical-align: top !important; \r\n",
       "    margin: 0em 0px !important;\r\n",
       "} \r\n",
       "table th {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "</style>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "bool IsSpace(string subsentence) => subsentence is \" \";\n",
    "bool IsPrepositionalPhrase(string subsentence) => true || subsentence[0..6] is \"to the\" && IsSpace(subsentence[7..8]) && IsNoun(subsentence[7..]);\n",
    "\n",
    "IsPrepositionalPhrase(\"to the store\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You may note that `subsentence` is a `string`, and using the range operator on a `string` in C# allocates another `string` (like `string.Split`),"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span><a href=\"https://docs.microsoft.com/dotnet/api/system.string?view=net-7.0\">System.String</a></span>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "\"to the \"[0..3].GetType()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "so from now on, I'm going to use `ReadOnlySpan<char>` and `ReadOnlyMemory<char>`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "static bool IsPrepositionalPhrase(ReadOnlySpan<char> subsentence) => subsentence[0..7] is \"to the \" && IsNoun(subsentence[7..]);\n",
    "static bool IsNoun(ReadOnlySpan<char> subsentence) => subsentence is \"store\" or \"post office\";"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can create more rules and encode them as methods:\n",
    "\n",
    "```\n",
    "Sentence    -> Subject Verb Object\n",
    "Subject     -> i | he | they\n",
    "Verb        -> run | drive\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "static bool IsSentence(ReadOnlySpan<char> subsentence) => IsSubject(subsentence) /* ... ??? */;\n",
    "static bool IsSubject(ReadOnlySpan<char> subsentence) => subsentence is \"i\" or \"he\" or \"they\";"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our general \"algorithm\" so far is \"try the first of each rule until one works\", but you might notice that we run into a bit of a problem. Our rules are unable to \"peel off\" matches from our input. Specifically, in the above code, if `IsSubject` succeeds, `IsSentence` doesn't know where to slice to pass the rest of the unmatched input.\n",
    "\n",
    "There are several ways you could solve this problem. For simplicity, we're just going to return `ReadOnlySpan<char>` instead of `bool` for all productions other than Sentence, and simply return `\"~\"` for cases that fail, that will in turn, cause all following matches to fail (for our grammar, because `~` is not valid in our grammar). This isn't the greatest for error handling, but it's the simplest way I could think of that doesn't introduce global state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/csv": [
       "Input,Result\r\n",
       "\"i run store\",True\r\n",
       "\"i switch ran\",False\r\n"
      ],
      "text/html": [
       "<table><thead><tr><td><span>Input</span></td><td><span>Result</span></td></tr></thead><tbody><tr><td>i run store</td><td><div class=\"dni-plaintext\"><pre>True</pre></div></td></tr><tr><td>i switch ran</td><td><div class=\"dni-plaintext\"><pre>False</pre></div></td></tr></tbody></table><style>\r\n",
       ".dni-code-hint {\r\n",
       "    font-style: italic;\r\n",
       "    overflow: hidden;\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview {\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview td {\r\n",
       "    vertical-align: top;\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "details.dni-treeview {\r\n",
       "    padding-left: 1em;\r\n",
       "}\r\n",
       "table td {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "table tr { \r\n",
       "    vertical-align: top; \r\n",
       "    margin: 0em 0px;\r\n",
       "}\r\n",
       "table tr td pre \r\n",
       "{ \r\n",
       "    vertical-align: top !important; \r\n",
       "    margin: 0em 0px !important;\r\n",
       "} \r\n",
       "table th {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "</style>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "static bool IsSentence(this ReadOnlySpan<char> subsentence) => subsentence.PeelSubject().PeelSpace().PeelVerb().PeelSpace() is \"store\";\n",
    "\n",
    "static ReadOnlySpan<char> PeelSpace(this ReadOnlySpan<char> subsentence) => subsentence.StartsWith(\" \") ? subsentence[1..] : \"~\";\n",
    "\n",
    "static ReadOnlySpan<char> PeelSubject(this ReadOnlySpan<char> subsentence) => subsentence switch\n",
    "{\n",
    "    _ when subsentence.StartsWith(\"i\") => subsentence[1..],\n",
    "    _ when subsentence.StartsWith(\"he\") => subsentence[2..],\n",
    "    _ when subsentence.StartsWith(\"they\") => subsentence[4..],\n",
    "    _  => \"~\"\n",
    "};\n",
    "\n",
    "static ReadOnlySpan<char> PeelVerb(this ReadOnlySpan<char> subsentence) => subsentence switch\n",
    "{\n",
    "    _ when subsentence.StartsWith(\"run\") => subsentence[3..],\n",
    "    _ when subsentence.StartsWith(\"drive\") => subsentence[5..],\n",
    "    _  => \"~\"\n",
    "};\n",
    "\n",
    "new[] { new { Input = \"i run store\", Result = IsSentence(\"i run store\") }, new { Input = \"i switch ran\", Result = IsSentence(\"i switch ran\") } }.DisplayTable()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, adding a rule for Object:\n",
    "\n",
    "```\n",
    "Object      -> Prepositional Phrase | Noun\n",
    "```\n",
    "\n",
    "and completing all our rules:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/csv": [
       "Input,Result\r\n",
       "\"i run to the store\",True\r\n",
       "\"i switch ran\",False\r\n"
      ],
      "text/html": [
       "<table><thead><tr><td><span>Input</span></td><td><span>Result</span></td></tr></thead><tbody><tr><td>i run to the store</td><td><div class=\"dni-plaintext\"><pre>True</pre></div></td></tr><tr><td>i switch ran</td><td><div class=\"dni-plaintext\"><pre>False</pre></div></td></tr></tbody></table><style>\r\n",
       ".dni-code-hint {\r\n",
       "    font-style: italic;\r\n",
       "    overflow: hidden;\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview {\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview td {\r\n",
       "    vertical-align: top;\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "details.dni-treeview {\r\n",
       "    padding-left: 1em;\r\n",
       "}\r\n",
       "table td {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "table tr { \r\n",
       "    vertical-align: top; \r\n",
       "    margin: 0em 0px;\r\n",
       "}\r\n",
       "table tr td pre \r\n",
       "{ \r\n",
       "    vertical-align: top !important; \r\n",
       "    margin: 0em 0px !important;\r\n",
       "} \r\n",
       "table th {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "</style>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "static ReadOnlySpan<char> PeelNoun(this ReadOnlySpan<char> subsentence) => subsentence switch\n",
    "{\n",
    "    _ when subsentence.StartsWith(\"store\") => subsentence[5..],\n",
    "    _ when subsentence.StartsWith(\"post office\") => subsentence[11..],\n",
    "    _  => \"~\"\n",
    "};\n",
    "\n",
    "static ReadOnlySpan<char> PeelPrepositionalPhrase(this ReadOnlySpan<char> subsentence) => subsentence switch\n",
    "{\n",
    "    _ when subsentence.StartsWith(\"to the\") => subsentence[6..],\n",
    "    _  => \"~\"\n",
    "};\n",
    "\n",
    "static ReadOnlySpan<char> PeelObject(this ReadOnlySpan<char> subsentence) => subsentence switch\n",
    "{\n",
    "    _ when subsentence.PeelPrepositionalPhrase() is not \"~\" and { } rest\n",
    "        && rest.PeelSpace().PeelNoun() is not \"~\" and { } _rest => _rest,\n",
    "    _ when subsentence.PeelNoun() is not \"~\" and { } rest => rest,\n",
    "    _  => \"~\"\n",
    "};\n",
    "\n",
    "static bool IsSentence(this ReadOnlySpan<char> subsentence) => subsentence.PeelSubject().PeelSpace().PeelVerb().PeelSpace().PeelObject() is { Length: 0 };\n",
    "\n",
    "new[] { new { Input = sentence, Result = IsSentence(sentence) }, new { Input = \"i switch ran\", Result = IsSentence(\"i switch ran\") } }.DisplayTable()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What we did here is actually create a mini parser for a subset of the English language. The parser is very bad - it doesn't give any good error reporting, but it validates whether a sentence conforms to our language."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Parse Tree\n",
    "If you step through a debugger, you will see the path our string `i run to the store` took to get through our parser is as follows:\n",
    "\n",
    "```\n",
    "in `IsSentence`\n",
    "  in `PeelSubject`\n",
    "  out\n",
    "  in `PeelVerb`\n",
    "  out\n",
    "  in `PeelObject`\n",
    "      in `PeelPrepositionalPhrase`\n",
    "      out\n",
    "      in `PeelNoun`\n",
    "      out\n",
    "  out\n",
    "out\n",
    "```\n",
    "\n",
    "This path can also be represented with a tree, as illustrated below:\n",
    "\n",
    "(does not render on GitHub preview as of 2023-11-27 - click outside of the preview and press `.` to view in [vscode.dev](https://vscode.dev), or copy-paste below cell into [mermaid.dev](https://mermaid.live))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "dotnet_interactive": {
     "language": "mermaid"
    },
    "polyglot_notebook": {
     "kernelName": "mermaid"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"mermaidMarkdownContainer\" style=\"background-color:white\">\r\n",
       "<link rel=\"stylesheet\" href=\"https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.2.0/css/all.min.css\">\r\n",
       "<div id=\"8333224c90464b12a77215ae2af9f634\"></div>\r\n",
       "<script type=\"module\">\r\n",
       "\r\n",
       "            import mermaid from 'https://cdn.jsdelivr.net/npm/mermaid@10.6.1/dist/mermaid.esm.min.mjs';\r\n",
       "            let renderTarget = document.getElementById('8333224c90464b12a77215ae2af9f634');\r\n",
       "            try {\r\n",
       "                const {svg, bindFunctions} = await mermaid.mermaidAPI.render( \r\n",
       "                    'mermaid_8333224c90464b12a77215ae2af9f634', \r\n",
       "                    `graph TD\n",
       "    A[Sentence] --> B[Subject]\n",
       "    A --> C[Verb]\n",
       "    A --> D[Object]\n",
       "    B --> E[i]\n",
       "    C --> F[run]\n",
       "    D --> G[Prepositional Phrase]\n",
       "    G --> H[to the]\n",
       "    G --> I[Noun]\n",
       "    I --> J[store]`);\r\n",
       "                renderTarget.innerHTML = svg;\r\n",
       "                bindFunctions?.(renderTarget);\r\n",
       "            }\r\n",
       "            catch (error) {\r\n",
       "                console.log(error);\r\n",
       "            }\r\n",
       "</script>\r\n",
       "</div>\r\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "graph TD\n",
    "    A[Sentence] --> B[Subject]\n",
    "    A --> C[Verb]\n",
    "    A --> D[Object]\n",
    "    B --> E[i]\n",
    "    C --> F[run]\n",
    "    D --> G[Prepositional Phrase]\n",
    "    G --> H[to the]\n",
    "    G --> I[Noun]\n",
    "    I --> J[store]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This tree is called a **parse tree**, and it represents the derivation from the start non-terminal, through productions, to a final sentence.\n",
    "\n",
    "The parser we wrote is called a *recrusive-descent* parser. In a recrusive-descent parser, the path taken (without walkbacks) to validate a string is the parse tree for that string.\n",
    "\n",
    "I say without walkbacks, because in our algorithm, we always try the first rule for each production, and the string `i run to the store` is what you get by always expanding the first production. If our string was `i run store`, our code path would look like this\n",
    "\n",
    "```\n",
    "in `IsSentence`\n",
    "  in `PeelSubject`\n",
    "  out\n",
    "  in `PeelVerb`\n",
    "  out\n",
    "  in `PeelObject`\n",
    "      // we try this rule of `Object`\n",
    "      in `PeelPrepositionalPhrase`\n",
    "      out\n",
    "      in `PeelNoun`\n",
    "      out\n",
    "      // but it fails so we try the next\n",
    "      in `PeelNoun`\n",
    "      out\n",
    "  out\n",
    "out\n",
    "```\n",
    "\n",
    "but our parse tree would look like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "dotnet_interactive": {
     "language": "mermaid"
    },
    "polyglot_notebook": {
     "kernelName": "mermaid"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"mermaidMarkdownContainer\" style=\"background-color:white\">\r\n",
       "<link rel=\"stylesheet\" href=\"https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.2.0/css/all.min.css\">\r\n",
       "<div id=\"63cdfaa756f047dc91126e81f37550d1\"></div>\r\n",
       "<script type=\"module\">\r\n",
       "\r\n",
       "            import mermaid from 'https://cdn.jsdelivr.net/npm/mermaid@10.6.1/dist/mermaid.esm.min.mjs';\r\n",
       "            let renderTarget = document.getElementById('63cdfaa756f047dc91126e81f37550d1');\r\n",
       "            try {\r\n",
       "                const {svg, bindFunctions} = await mermaid.mermaidAPI.render( \r\n",
       "                    'mermaid_63cdfaa756f047dc91126e81f37550d1', \r\n",
       "                    `graph TD\n",
       "    A[Sentence] --> B[Subject]\n",
       "    A --> C[Verb]\n",
       "    A --> D[Object]\n",
       "    B --> E[i]\n",
       "    C --> F[run]\n",
       "    D --> G[Noun]\n",
       "    G --> H[store]`);\r\n",
       "                renderTarget.innerHTML = svg;\r\n",
       "                bindFunctions?.(renderTarget);\r\n",
       "            }\r\n",
       "            catch (error) {\r\n",
       "                console.log(error);\r\n",
       "            }\r\n",
       "</script>\r\n",
       "</div>\r\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "graph TD\n",
    "    A[Sentence] --> B[Subject]\n",
    "    A --> C[Verb]\n",
    "    A --> D[Object]\n",
    "    B --> E[i]\n",
    "    C --> F[run]\n",
    "    D --> G[Noun]\n",
    "    G --> H[store]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is a draft grammar for our language:\n",
    "```\n",
    "Program                 -> Statements Expression\n",
    "Statements              -> Statements Statement\n",
    "Statement               -> AssignmentStatement\n",
    "AssignmentStatement    -> id = Expression;\n",
    "Expression   ->\n",
    "    (Expression)\n",
    "  | Expression * Expression\n",
    "  | Expression / Expression\n",
    "  | Expression + Expression\n",
    "  | Expression - Expression\n",
    "  | id\n",
    "  | int\n",
    "```\n",
    "\n",
    "A general description is a list of statements followed by a single expression. All statements end with a `;`, and the program is ended with an expression (which we will evaluate and print to the console, though this isn't related to the grammar).\n",
    "\n",
    "If you recall our input string:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span>a = 2;\n",
       "b = 3;\n",
       "c = (3 + a) * b;\n",
       "\n",
       "c</span>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "input"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see it conforms to our grammar:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "dotnet_interactive": {
     "language": "mermaid"
    },
    "polyglot_notebook": {
     "kernelName": "mermaid"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"mermaidMarkdownContainer\" style=\"background-color:white\">\r\n",
       "<link rel=\"stylesheet\" href=\"https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.2.0/css/all.min.css\">\r\n",
       "<div id=\"e3af73fa45c34484b30a267a1eef2eda\"></div>\r\n",
       "<script type=\"module\">\r\n",
       "\r\n",
       "            import mermaid from 'https://cdn.jsdelivr.net/npm/mermaid@10.6.1/dist/mermaid.esm.min.mjs';\r\n",
       "            let renderTarget = document.getElementById('e3af73fa45c34484b30a267a1eef2eda');\r\n",
       "            try {\r\n",
       "                const {svg, bindFunctions} = await mermaid.mermaidAPI.render( \r\n",
       "                    'mermaid_e3af73fa45c34484b30a267a1eef2eda', \r\n",
       "                    `graph TD\n",
       "    A[Program] --> B[Statements]\n",
       "    A --> C[Expression]\n",
       "    B --> D[Statements]\n",
       "    B --> E[Statement]\n",
       "    D --> F[...]\n",
       "    E --> G[AssignmentStatement]\n",
       "    G --> H[c]\n",
       "    G --> I[=]\n",
       "    G --> J[Expression]\n",
       "    J --> K[...]\n",
       "    G --> L[;]\n",
       "    C --> Z[c]`);\r\n",
       "                renderTarget.innerHTML = svg;\r\n",
       "                bindFunctions?.(renderTarget);\r\n",
       "            }\r\n",
       "            catch (error) {\r\n",
       "                console.log(error);\r\n",
       "            }\r\n",
       "</script>\r\n",
       "</div>\r\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "graph TD\n",
    "    A[Program] --> B[Statements]\n",
    "    A --> C[Expression]\n",
    "    B --> D[Statements]\n",
    "    B --> E[Statement]\n",
    "    D --> F[...]\n",
    "    E --> G[AssignmentStatement]\n",
    "    G --> H[c]\n",
    "    G --> I[=]\n",
    "    G --> J[Expression]\n",
    "    J --> K[...]\n",
    "    G --> L[;]\n",
    "    C --> Z[c]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Left Recursion\n",
    "We have a **big** problem though... actually, two of them!\n",
    "\n",
    "Let's take a look at `Statements`\n",
    "\n",
    "```\n",
    "Statements              -> Statements Statement\n",
    "```\n",
    "\n",
    "and what it could look like in code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "static ReadOnlySpan<char> PeelStatements(this ReadOnlySpan<char> input) => input.PeelStatements().PeelStatement();\n",
    "static ReadOnlySpan<char> PeelStatement(this ReadOnlySpan<char> input) => \n",
    "    // replace with statement validation logic\n",
    "    input[1..];"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is infinite recursion!\n",
    "\n",
    "We can fix this by modifying our grammar:\n",
    "```\n",
    "Statements              -> Statement Statements\n",
    "```\n",
    "\n",
    "This changes the order of derivation and therefore our parse tree, but that's not a problem here.\n",
    "\n",
    "In general, **you never want recursion to be in the same direction as your derivation**. If you have left derivation (you try the left-most rules first), you *don't* want left recursion."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ambiguity\n",
    "We still have one more problem though, and it's with the `Expression` rule:\n",
    "\n",
    "```\n",
    "Expression   ->\n",
    "    (Expression)\n",
    "  | Expression * Expression\n",
    "  | Expression / Expression\n",
    "  | Expression + Expression\n",
    "  | Expression - Expression\n",
    "  | id\n",
    "  | int\n",
    "```\n",
    "\n",
    "This grammar is also left recursive, but more than that, it's ambiguous, in that for a single sentence, there are multiple derivations / parse trees you could construct."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "dotnet_interactive": {
     "language": "mermaid"
    },
    "polyglot_notebook": {
     "kernelName": "mermaid"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"mermaidMarkdownContainer\" style=\"background-color:white\">\r\n",
       "<link rel=\"stylesheet\" href=\"https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.2.0/css/all.min.css\">\r\n",
       "<div id=\"acc085a2cf974f7db4626d6800cb3d5a\"></div>\r\n",
       "<script type=\"module\">\r\n",
       "\r\n",
       "            import mermaid from 'https://cdn.jsdelivr.net/npm/mermaid@10.6.1/dist/mermaid.esm.min.mjs';\r\n",
       "            let renderTarget = document.getElementById('acc085a2cf974f7db4626d6800cb3d5a');\r\n",
       "            try {\r\n",
       "                const {svg, bindFunctions} = await mermaid.mermaidAPI.render( \r\n",
       "                    'mermaid_acc085a2cf974f7db4626d6800cb3d5a', \r\n",
       "                    `graph TD\n",
       "    A[Expression] --> B[Expression]\n",
       "    A --> C[*]\n",
       "    A --> D[Expression]\n",
       "    E --> F[1]\n",
       "    B --> E[Expression]\n",
       "    B --> G[+]\n",
       "    B --> H[Expression]\n",
       "    H --> J[2]\n",
       "    D --> I[3]\n",
       "\n",
       "    _A[Expression] --> _B[Expression]\n",
       "    _A --> _C[+]\n",
       "    _A --> _D[Expression]\n",
       "    _B --> _I[1]\n",
       "    _D --> _E[Expression]\n",
       "    _E --> _F[2]\n",
       "    _D --> _G[*]\n",
       "    _D --> _H[Expression]\n",
       "    _H --> _J[3]`);\r\n",
       "                renderTarget.innerHTML = svg;\r\n",
       "                bindFunctions?.(renderTarget);\r\n",
       "            }\r\n",
       "            catch (error) {\r\n",
       "                console.log(error);\r\n",
       "            }\r\n",
       "</script>\r\n",
       "</div>\r\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "graph TD\n",
    "    A[Expression] --> B[Expression]\n",
    "    A --> C[*]\n",
    "    A --> D[Expression]\n",
    "    E --> F[1]\n",
    "    B --> E[Expression]\n",
    "    B --> G[+]\n",
    "    B --> H[Expression]\n",
    "    H --> J[2]\n",
    "    D --> I[3]\n",
    "\n",
    "    _A[Expression] --> _B[Expression]\n",
    "    _A --> _C[+]\n",
    "    _A --> _D[Expression]\n",
    "    _B --> _I[1]\n",
    "    _D --> _E[Expression]\n",
    "    _E --> _F[2]\n",
    "    _D --> _G[*]\n",
    "    _D --> _H[Expression]\n",
    "    _H --> _J[3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Both parse trees above are legal productions of the grammar, but it's easy to see that their differences are non-negligible (`(1 + 2) * 3 = 9` `!=` `1 + (2 * 3) = 7`).\n",
    "\n",
    "To illustrate this problem, I'd translate the grammar to code again, but we'd run into the immediate issue of infinite left recursion. There are several ways to solve left recursion, but the underlying problem here is that of operator precedence, which is why we have a problem with ambiguity as well. Sometimes we can solve both problems at once by introducing new non-terminals, which is what we'll do:\n",
    "\n",
    "```\n",
    "Expression   ->\n",
    "    Term + Expression\n",
    "    Term - Expression\n",
    "    Term\n",
    "Term   ->\n",
    "    Factor * Term\n",
    "    Factor / Term\n",
    "    Factor\n",
    "Factor  ->\n",
    "    (Expression) | id | int\n",
    "```\n",
    "\n",
    "When we split the grammar into multiple rules like so, we try to match for operators of lower precedence first, which means matching farther away from the leaves and closer to the root. The above Mermaid diagram hopefully helps demonstrate how the closer a subexpression is to the leaves, the higher precedence it has."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Note: I think it's important to note here that I am skipping over entire classes of parsers and grammars.\n",
    "> \n",
    "> The grammar I am describing here is called \"**LL**\", which means it reads tokens from left-to-right and constructs a \"left-most derivation\" (just tries doing all the rules and stuff from the left first), and the parser I am writing is called \"manual recursive descent\". It is also \"top-down\", meaning it starts from the first non-terminal and tries to produce a matching sentence.\n",
    "> \n",
    "> A point of inefficiency for the parser I'm writing is that it tries all the rules until it finds a match, meaning that if it does *not* find a match, it tries every single navigation of productions before giving up. This isn't *terrible*, as production compilers often use a mixture of parsing techniques with recursive descent often being the primary one because of the flexibility it provides, but it is worth mentioning that there are other parsing techniques that eliminate some of these inefficiencies by requiring you to be stricter with how you define your grammar."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Abstract Syntax Trees\n",
    "\n",
    "The next step would be to translate our grammar into code as we did our English example, but you'll note that we're missing a key goal that we desired from the outset of our parser, and that is the AST - the representation of our code in tree form.\n",
    "\n",
    "For your research, the preferred method of building an AST is with \"semantic actions\", but in our case, we can just build an AST as we parse our input by returning each subtree with each parsing method.\n",
    "\n",
    "If this sounds complicated, it's my fault for being unable to explain it clearly, because it's really not, but if we directly try to implement it with code, we'll run into another issue.\n",
    "\n",
    "Take our definition of PeelNoun from earlier:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "static ReadOnlySpan<char> PeelNoun(this ReadOnlySpan<char> subsentence) => subsentence switch\n",
    "{\n",
    "    _ when subsentence.StartsWith(\"store\") => subsentence[5..],\n",
    "    _ when subsentence.StartsWith(\"post office\") => subsentence[11..],\n",
    "    _  => \"~\"\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we return some type of `Noun` data structure instead of a `ReadOnlySpan<char>`, the caller method won't know where in the `char` stream to resume reading input from.\n",
    "\n",
    "A logical step would be to return both values in a tuple, but tuples under the hood are of type `System.ValueTuple<T1, T2, ...>` and `ref struct` types, of which `ReadOnlySpan<T>` is one, can't be generic type parameters because that could potentially allow them to leak onto the heap. The scope of this issue is beyond that of this notebook, but the gist is that if we want to return multiple parameters along with `ref structs`, we have to include them in another `ref struct` and return that or use `out` parameters... and `out` parameters are ugly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But before I can show our example, what of our AST data structure? For this, I'm currently using `record`s. They're kind of like classes in that they're reference types, but they can be concisely defined in a single statement and have structural equality. The member definitions passed in the `()`s become `readonly` auto-properties, meaning they are immutable.\n",
    "\n",
    "I was trying to get some interop with F# to work in this notebook, and unfortunately, sharing custom data types across .NET Interactive doesn't work too well, so I've decided to define the types in the [Program.cs](Program.cs) in the same directory as this notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a simple example for parsing a literal value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<details open=\"open\" class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>IntLiteralExpression { Value = 3 }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Value</td><td><div class=\"dni-plaintext\"><pre>3</pre></div></td></tr></tbody></table></div></details><style>\r\n",
       ".dni-code-hint {\r\n",
       "    font-style: italic;\r\n",
       "    overflow: hidden;\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview {\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview td {\r\n",
       "    vertical-align: top;\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "details.dni-treeview {\r\n",
       "    padding-left: 1em;\r\n",
       "}\r\n",
       "table td {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "table tr { \r\n",
       "    vertical-align: top; \r\n",
       "    margin: 0em 0px;\r\n",
       "}\r\n",
       "table tr td pre \r\n",
       "{ \r\n",
       "    vertical-align: top !important; \r\n",
       "    margin: 0em 0px !important;\r\n",
       "} \r\n",
       "table th {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "</style>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#nullable enable\n",
    "ref struct ParseResult\n",
    "{\n",
    "    public Node? Result { get; set; }\n",
    "    public ReadOnlySpan<Token> Rest { get; set; }\n",
    "}\n",
    "\n",
    "static ParseResult ParseLiteral(ReadOnlySpan<Token> tokens)\n",
    "    => tokens switch\n",
    "    {\n",
    "        [{ Type: TokenType.Integer } token, ..var _rest] when int.TryParse(token.Memory.Span, out int value)\n",
    "            => new() { Rest = _rest, Result = new IntLiteralExpression(value) },\n",
    "        _ => new() { Rest = tokens, Result = null }\n",
    "    };\n",
    "\n",
    "ParseLiteral(Lex(\"3\".AsMemory()).ToArray().AsSpan()).Result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The process is very similar to our English subset example, except that we, of course, need to return an AST, but we also use our `ReadOnlySpan<Token> tokens` instead of a direct `ReadOnlySpan<char>` character stream. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can build on our above work to parse an `Expression`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<details open=\"open\" class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>BinaryExpression { Left = IntLiteralExpression { Value = 3 }, Operator = Token { Start = 29, Memory = +, Type = Add }, Right = IntLiteralExpression { Value = 4 } }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Left</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>IntLiteralExpression { Value = 3 }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Value</td><td><div class=\"dni-plaintext\"><pre>3</pre></div></td></tr></tbody></table></div></details></td></tr><tr><td>Operator</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 29, Memory = +, Type = Add }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>29</pre></div></td></tr><tr><td>Memory</td><td><span>+</span></td></tr><tr><td>Type</td><td><span>Add</span></td></tr></tbody></table></div></details></td></tr><tr><td>Right</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>IntLiteralExpression { Value = 4 }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Value</td><td><div class=\"dni-plaintext\"><pre>4</pre></div></td></tr></tbody></table></div></details></td></tr></tbody></table></div></details><style>\r\n",
       ".dni-code-hint {\r\n",
       "    font-style: italic;\r\n",
       "    overflow: hidden;\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview {\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview td {\r\n",
       "    vertical-align: top;\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "details.dni-treeview {\r\n",
       "    padding-left: 1em;\r\n",
       "}\r\n",
       "table td {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "table tr { \r\n",
       "    vertical-align: top; \r\n",
       "    margin: 0em 0px;\r\n",
       "}\r\n",
       "table tr td pre \r\n",
       "{ \r\n",
       "    vertical-align: top !important; \r\n",
       "    margin: 0em 0px !important;\r\n",
       "} \r\n",
       "table th {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "</style>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#nullable enable\n",
    "static ParseResult ParseExpression(ReadOnlySpan<Token> tokens)\n",
    "    => ParseTerm(tokens) switch\n",
    "    {\n",
    "        { Result: Expression left, Rest: var rest } => rest switch\n",
    "            {\n",
    "                [{ Type: TokenType.Add or TokenType.Subtract } op, ..var _rest] => ParseTerm(_rest) switch\n",
    "                {\n",
    "                    { Result: Expression right, Rest: var __rest } =>\n",
    "                        new() { Result = new BinaryExpression(left, op, right), Rest = __rest },\n",
    "                    _ => new() { Result = null, Rest = _rest }\n",
    "                },\n",
    "                _ => new() { Rest = rest, Result = left }\n",
    "            },\n",
    "        _ => new() { Rest = tokens, Result = null }\n",
    "    };\n",
    "\n",
    "static ParseResult ParseTerm(ReadOnlySpan<Token> tokens)\n",
    "    => ParseFactor(tokens) switch\n",
    "    {\n",
    "        { Result: Expression left, Rest: var rest } => rest switch\n",
    "            {\n",
    "                [{ Type: TokenType.Multiply or TokenType.Divide } op, ..var _rest] => ParseTerm(_rest) switch\n",
    "                    {\n",
    "                        { Result: Expression right, Rest: var __rest } => \n",
    "                            new() { Result = new BinaryExpression(left, op, right), Rest = __rest },\n",
    "                        _ => new() { Result = null, Rest = _rest }\n",
    "                    },\n",
    "                _ => new() { Result = left, Rest = rest }\n",
    "            },\n",
    "        _ => new() { Result = null, Rest = tokens }\n",
    "    };\n",
    "\n",
    "static ParseResult ParseFactor(ReadOnlySpan<Token> tokens)\n",
    "    => tokens switch\n",
    "    {\n",
    "        { } when ParseWrappedExpression(tokens) is { Result: { } expression, Rest: var rest } =>\n",
    "            new() { Result = expression, Rest = rest },\n",
    "        { } when ParseLiteral(tokens) is { Result: { } expression, Rest: var rest } =>\n",
    "            new() { Result = expression, Rest = rest },\n",
    "        [{ Type: TokenType.Id }, ..var _rest] =>\n",
    "            new() { Result = new NameExpression(tokens[0]), Rest = _rest },\n",
    "    };\n",
    "\n",
    "static ParseResult ParseWrappedExpression(ReadOnlySpan<Token> tokens)\n",
    "    => tokens switch\n",
    "    {\n",
    "        [{ Type: TokenType.LeftParenthesis } left, ..var rest] => \n",
    "            ParseExpression(rest) switch\n",
    "            {\n",
    "                { Result: Expression expression, Rest: var _rest } => _rest switch\n",
    "                    {\n",
    "                        [{ Type: TokenType.RightParenthesis } right, ..var __rest]\n",
    "                            => new() { Rest = __rest, Result = expression },\n",
    "                        _ => new() { Rest = _rest, Result = null }\n",
    "                    },\n",
    "                { Rest: var _rest, Result: null } => new() { Rest = _rest, Result = null }\n",
    "            },\n",
    "        _ => new() { Rest = tokens, Result = null }\n",
    "    };\n",
    "\n",
    "ParseExpression(Lex(\"(3 + 4)\".AsMemory()).ToArray().AsSpan()).Result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And statements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<details open=\"open\" class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>AssignmentStatement { Identifier = Token { Start = 17, Memory = c, Type = Id }, Expression = BinaryExpression { Left = BinaryExpression { Left = IntLiteralExpression { Value = 3 }, Operator = Token { Start = 24, Memory = +, Type = Add }, Right = NameExpression { Identifier = Token { Start = 26, Memo...</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Identifier</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 17, Memory = c, Type = Id }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>17</pre></div></td></tr><tr><td>Memory</td><td><span>c</span></td></tr><tr><td>Type</td><td><span>Id</span></td></tr></tbody></table></div></details></td></tr><tr><td>Expression</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>BinaryExpression { Left = BinaryExpression { Left = IntLiteralExpression { Value = 3 }, Operator = Token { Start = 24, Memory = +, Type = Add }, Right = NameExpression { Identifier = Token { Start = 26, Memory = a, Type = Id } } }, Operator = Token { Start = 29, Memory = *, Type = Multiply }, Right ...</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Left</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>BinaryExpression { Left = IntLiteralExpression { Value = 3 }, Operator = Token { Start = 24, Memory = +, Type = Add }, Right = NameExpression { Identifier = Token { Start = 26, Memory = a, Type = Id } } }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Left</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>IntLiteralExpression { Value = 3 }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Value</td><td><div class=\"dni-plaintext\"><pre>3</pre></div></td></tr></tbody></table></div></details></td></tr><tr><td>Operator</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 24, Memory = +, Type = Add }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>24</pre></div></td></tr><tr><td>Memory</td><td><span>+</span></td></tr><tr><td>Type</td><td><span>Add</span></td></tr></tbody></table></div></details></td></tr><tr><td>Right</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>NameExpression { Identifier = Token { Start = 26, Memory = a, Type = Id } }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Identifier</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 26, Memory = a, Type = Id }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>26</pre></div></td></tr><tr><td>Memory</td><td><span>a</span></td></tr><tr><td>Type</td><td><span>Id</span></td></tr></tbody></table></div></details></td></tr></tbody></table></div></details></td></tr></tbody></table></div></details></td></tr><tr><td>Operator</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 29, Memory = *, Type = Multiply }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>29</pre></div></td></tr><tr><td>Memory</td><td><span>*</span></td></tr><tr><td>Type</td><td><span>Multiply</span></td></tr></tbody></table></div></details></td></tr><tr><td>Right</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>NameExpression { Identifier = Token { Start = 31, Memory = b, Type = Id } }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Identifier</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 31, Memory = b, Type = Id }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>31</pre></div></td></tr><tr><td>Memory</td><td><span>b</span></td></tr><tr><td>Type</td><td><span>Id</span></td></tr></tbody></table></div></details></td></tr></tbody></table></div></details></td></tr></tbody></table></div></details></td></tr></tbody></table></div></details><style>\r\n",
       ".dni-code-hint {\r\n",
       "    font-style: italic;\r\n",
       "    overflow: hidden;\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview {\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview td {\r\n",
       "    vertical-align: top;\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "details.dni-treeview {\r\n",
       "    padding-left: 1em;\r\n",
       "}\r\n",
       "table td {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "table tr { \r\n",
       "    vertical-align: top; \r\n",
       "    margin: 0em 0px;\r\n",
       "}\r\n",
       "table tr td pre \r\n",
       "{ \r\n",
       "    vertical-align: top !important; \r\n",
       "    margin: 0em 0px !important;\r\n",
       "} \r\n",
       "table th {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "</style>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "using System.Collections.Immutable;\n",
    "\n",
    "#nullable enable\n",
    "static ParseResult ParseStatements(ReadOnlySpan<Token> tokens)\n",
    "    => ParseStatement(tokens) switch\n",
    "        {\n",
    "            { Result: null } => new () { Result = new Statements(ImmutableList<Statement>.Empty), Rest = tokens },\n",
    "            { Result: Statement statement, Rest: var rest } => \n",
    "                ParseStatements(rest) is { Result: Statements statements, Rest: var _rest } ?\n",
    "                new() { Result = new Statements(statements.StatementList.Insert(0, statement)), Rest = _rest }\n",
    "                : new() { Result = null, Rest = rest }\n",
    "        };\n",
    "\n",
    "static ParseResult ParseStatement(ReadOnlySpan<Token> tokens) => ParseAssignment(tokens);\n",
    "\n",
    "static ParseResult ParseAssignment(ReadOnlySpan<Token> tokens)\n",
    "    =>  tokens switch\n",
    "    {\n",
    "        [{ Type: TokenType.Id }, { Type: TokenType.Assignment }, ..var rest] => ParseExpression(rest) switch\n",
    "        {\n",
    "            { Result: Expression expression, Rest: var _rest } => _rest switch\n",
    "            {\n",
    "                [{ Type: TokenType.Semicolon }, ..var __rest] => new() { Result = new AssignmentStatement(tokens[0], expression), Rest = __rest },\n",
    "                _ => new() { Result = null, Rest = _rest }\n",
    "            },\n",
    "            _ => new() { Result = null, Rest = rest }\n",
    "        },\n",
    "        _ => new() { Result = null, Rest = tokens }\n",
    "    };\n",
    "\n",
    "ParseStatement(Lex(\"c = (3 + a) * b;\".AsMemory()).ToArray().AsSpan()).Result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And finally our entire program:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<details open=\"open\" class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Program { Statements = Statements { StatementList = System.Collections.Immutable.ImmutableList`1[Statement] }, Eval = NameExpression { Identifier = Token { Start = 32, Memory = c, Type = Id } } }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Statements</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Statements { StatementList = System.Collections.Immutable.ImmutableList`1[Statement] }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>StatementList</td><td><table><thead><tr><th><i>index</i></th><th>value</th></tr></thead><tbody><tr><td>0</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>AssignmentStatement { Identifier = Token { Start = 0, Memory = a, Type = Id }, Expression = IntLiteralExpression { Value = 2 } }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Identifier</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 0, Memory = a, Type = Id }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>0</pre></div></td></tr><tr><td>Memory</td><td><span>a</span></td></tr><tr><td>Type</td><td><span>Id</span></td></tr></tbody></table></div></details></td></tr><tr><td>Expression</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>IntLiteralExpression { Value = 2 }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Value</td><td><div class=\"dni-plaintext\"><pre>2</pre></div></td></tr></tbody></table></div></details></td></tr></tbody></table></div></details></td></tr><tr><td>1</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>AssignmentStatement { Identifier = Token { Start = 7, Memory = b, Type = Id }, Expression = IntLiteralExpression { Value = 3 } }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Identifier</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 7, Memory = b, Type = Id }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>7</pre></div></td></tr><tr><td>Memory</td><td><span>b</span></td></tr><tr><td>Type</td><td><span>Id</span></td></tr></tbody></table></div></details></td></tr><tr><td>Expression</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>IntLiteralExpression { Value = 3 }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Value</td><td><div class=\"dni-plaintext\"><pre>3</pre></div></td></tr></tbody></table></div></details></td></tr></tbody></table></div></details></td></tr><tr><td>2</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>AssignmentStatement { Identifier = Token { Start = 14, Memory = c, Type = Id }, Expression = BinaryExpression { Left = BinaryExpression { Left = IntLiteralExpression { Value = 3 }, Operator = Token { Start = 21, Memory = +, Type = Add }, Right = NameExpression { Identifier = Token { Start = 23, Memo...</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Identifier</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 14, Memory = c, Type = Id }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>14</pre></div></td></tr><tr><td>Memory</td><td><span>c</span></td></tr><tr><td>Type</td><td><span>Id</span></td></tr></tbody></table></div></details></td></tr><tr><td>Expression</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>BinaryExpression { Left = BinaryExpression { Left = IntLiteralExpression { Value = 3 }, Operator = Token { Start = 21, Memory = +, Type = Add }, Right = NameExpression { Identifier = Token { Start = 23, Memory = a, Type = Id } } }, Operator = Token { Start = 26, Memory = *, Type = Multiply }, Right ...</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Left</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>BinaryExpression { Left = IntLiteralExpression { Value = 3 }, Operator = Token { Start = 21, Memory = +, Type = Add }, Right = NameExpression { Identifier = Token { Start = 23, Memory = a, Type = Id } } }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Left</td><td>IntLiteralExpression { Value = 3 }</td></tr><tr><td>Operator</td><td>Token { Start = 21, Memory = +, Type = Add }</td></tr><tr><td>Right</td><td>NameExpression { Identifier = Token { Start = 23, Memory = a, Type = Id } }</td></tr></tbody></table></div></details></td></tr><tr><td>Operator</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 26, Memory = *, Type = Multiply }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td>26</td></tr><tr><td>Memory</td><td>*</td></tr><tr><td>Type</td><td>Multiply</td></tr></tbody></table></div></details></td></tr><tr><td>Right</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>NameExpression { Identifier = Token { Start = 28, Memory = b, Type = Id } }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Identifier</td><td>Token { Start = 28, Memory = b, Type = Id }</td></tr></tbody></table></div></details></td></tr></tbody></table></div></details></td></tr></tbody></table></div></details></td></tr></tbody></table></td></tr></tbody></table></div></details></td></tr><tr><td>Eval</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>NameExpression { Identifier = Token { Start = 32, Memory = c, Type = Id } }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Identifier</td><td><details class=\"dni-treeview\"><summary><span class=\"dni-code-hint\"><code>Token { Start = 32, Memory = c, Type = Id }</code></span></summary><div><table><thead><tr></tr></thead><tbody><tr><td>Start</td><td><div class=\"dni-plaintext\"><pre>32</pre></div></td></tr><tr><td>Memory</td><td><span>c</span></td></tr><tr><td>Type</td><td><span>Id</span></td></tr></tbody></table></div></details></td></tr></tbody></table></div></details></td></tr></tbody></table></div></details><style>\r\n",
       ".dni-code-hint {\r\n",
       "    font-style: italic;\r\n",
       "    overflow: hidden;\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview {\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview td {\r\n",
       "    vertical-align: top;\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "details.dni-treeview {\r\n",
       "    padding-left: 1em;\r\n",
       "}\r\n",
       "table td {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "table tr { \r\n",
       "    vertical-align: top; \r\n",
       "    margin: 0em 0px;\r\n",
       "}\r\n",
       "table tr td pre \r\n",
       "{ \r\n",
       "    vertical-align: top !important; \r\n",
       "    margin: 0em 0px !important;\r\n",
       "} \r\n",
       "table th {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "</style>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#nullable enable\n",
    "static ParseResult Parse(ReadOnlySpan<Token> tokens) => ParseStatements(tokens) switch\n",
    "    {\n",
    "        { Result: Statements statements, Rest: var rest } => ParseExpression(rest) switch\n",
    "        {\n",
    "            { Result: Expression expression, Rest: var _rest } => new() { Result = new Program(statements, expression), Rest = _rest },\n",
    "            _ => new() { Result = null, Rest = rest }\n",
    "        },\n",
    "        _ => new() { Result = null, Rest = tokens }\n",
    "    };\n",
    "\n",
    "public (Program? program, string? error) res => Parse(tokens.ToArray().AsSpan()) switch\n",
    "{\n",
    "    { Result: Program program, Rest: { IsEmpty: true } } => (program, null),\n",
    "    { Result: Program program, Rest: { IsEmpty: false } rest } => (program, $\"Error at {rest[0]}\")\n",
    "};\n",
    "\n",
    "if (res is (_, string error))\n",
    "{\n",
    "    Console.WriteLine(error);\n",
    "    throw new Exception();\n",
    "}\n",
    "\n",
    "if (res is not (Program program, _))\n",
    "    throw new Exception();\n",
    "\n",
    "program"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Semantic Analysis\n",
    "Now that we have our AST, the next phase of the compiler is semantic analysis.\n",
    "\n",
    "The role of semantic analysis can change depending on how you define your language. Your language, like F#, might provide rich type inference and strict type checking, and here is where you'll do most of that checking. You can also do some high-level optimization during this phase, like [constant folding](https://en.wikipedia.org/wiki/Constant_folding), for example.\n",
    "\n",
    "For our purposes, we're just going to do the important yet humble act of making sure we don't use a variable before it is defined and don't define one multiple times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"dni-plaintext\"><pre>[ a, b, c ]</pre></div><style>\r\n",
       ".dni-code-hint {\r\n",
       "    font-style: italic;\r\n",
       "    overflow: hidden;\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview {\r\n",
       "    white-space: nowrap;\r\n",
       "}\r\n",
       ".dni-treeview td {\r\n",
       "    vertical-align: top;\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "details.dni-treeview {\r\n",
       "    padding-left: 1em;\r\n",
       "}\r\n",
       "table td {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "table tr { \r\n",
       "    vertical-align: top; \r\n",
       "    margin: 0em 0px;\r\n",
       "}\r\n",
       "table tr td pre \r\n",
       "{ \r\n",
       "    vertical-align: top !important; \r\n",
       "    margin: 0em 0px !important;\r\n",
       "} \r\n",
       "table th {\r\n",
       "    text-align: start;\r\n",
       "}\r\n",
       "</style>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#nullable enable\n",
    "static List<string>? GetSymbols(Program program)\n",
    "{\n",
    "    var symbols = new List<string>();\n",
    "\n",
    "    foreach (Statement statement in program.Statements.StatementList)\n",
    "    {\n",
    "        if (statement is AssignmentStatement assignment)\n",
    "        {\n",
    "            // multiply defined\n",
    "            if (symbols.Contains(assignment.Identifier.Memory.ToString()))\n",
    "                return null;\n",
    "            \n",
    "            if (IsValidExpression(symbols, assignment.Expression) is false)\n",
    "                return null;\n",
    "            \n",
    "            // check expression\n",
    "            symbols.Add(assignment.Identifier.Memory.ToString());\n",
    "        }\n",
    "    }\n",
    "\n",
    "    return symbols;\n",
    "\n",
    "    static bool IsValidExpression(List<string> symbols, Expression expression)\n",
    "        => expression switch\n",
    "        {\n",
    "            NameExpression name => symbols.Contains(name.Identifier.Memory.ToString()),\n",
    "            BinaryExpression binary => IsValidExpression(symbols, binary.Left) \n",
    "                && IsValidExpression(symbols, binary.Right),\n",
    "            IntLiteralExpression _ => true,\n",
    "            _ => false\n",
    "        };\n",
    "}\n",
    "\n",
    "var symbols = GetSymbols(program);\n",
    "\n",
    "symbols"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Codegen\n",
    "For codegen, we're going to be using [AsmResolver](https://github.com/Washi1337/AsmResolver) to emit [CIL](https://en.wikipedia.org/wiki/Common_Intermediate_Language)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div><div></div><div></div><div><strong>Installed Packages</strong><ul><li><span>AsmResolver.DotNet, 5.4.0</span></li></ul></div></div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#r \"nuget: AsmResolver.DotNet, 5.4.0\"\n",
    "\n",
    "using AsmResolver.DotNet;\n",
    "using AsmResolver.DotNet.Code.Cil;\n",
    "using AsmResolver.DotNet.Signatures;\n",
    "using AsmResolver.DotNet.Signatures.Types;\n",
    "using AsmResolver.PE.DotNet.Cil;\n",
    "using AsmResolver.PE.DotNet.Metadata.Tables.Rows;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're going to need to write some boilerplate to define an assembly and module, and define our entry point."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "var assembly = new AssemblyDefinition(\n",
    "    name: \"MyAssembly\",\n",
    "    version: new(1, 0, 0, 0));\n",
    "\n",
    "var runtime = DotNetRuntimeInfo.Parse(\".NETCoreApp,Version=v7.0\");\n",
    "var module = new ModuleDefinition(\"MyAssembly.exe\", runtime.GetDefaultCorLib());\n",
    "var factory = module.CorLibTypeFactory;\n",
    "\n",
    "assembly.Modules.Add(module);\n",
    "\n",
    "var programType = new TypeDefinition(\n",
    "    ns: \"\", \n",
    "    name: \"Program\", \n",
    "    TypeAttributes.Class,\n",
    "    baseType: factory.Object.Type);\n",
    "\n",
    "module.TopLevelTypes.Add(programType);\n",
    "\n",
    "var mainMethod = new MethodDefinition(\n",
    "    name: \"Main\",\n",
    "    MethodAttributes.Public | MethodAttributes.Static,\n",
    "    signature: MethodSignature.CreateStatic(returnType: module.CorLibTypeFactory.Void));\n",
    "\n",
    "var methodBody = new CilMethodBody(mainMethod);\n",
    "mainMethod.CilMethodBody = methodBody;\n",
    "\n",
    "var write = \n",
    "    module.DefaultImporter.ImportType(typeof(Console))\n",
    "    .CreateMemberReference(\"Write\", MethodSignature.CreateStatic(\n",
    "        factory.Void, factory.Int32))\n",
    "    .ImportWith(module.DefaultImporter);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Symbol Table\n",
    "CIL uses a [stack evaluation model](https://en.wikipedia.org/wiki/Stack_machine), meaning that we have a stack to store values on and an \"unlimited\" (256) number of local variables. The .NET runtime then converts this IL to assembly code at runtime, though it is possible to compile it to native code ahead of time (AOT).\n",
    "\n",
    "Inside our method body, we need to initialize our symbols as stack local variables, and then setup a `Dictionary<string, int>` to reference them by when generating code.\n",
    "\n",
    "What I am creating with this `Dictionary` is something called a **symbol table**, but a very simplified watered down version. In real programming languages, you can have any number of scopes, and variables can be defined with the same name as another as long as they are uniquely defined in their own scope. A data structure for this model looks a lot more like a `Dictionary` where each value is a list.\n",
    "\n",
    "> Note: In most languges, module-like scopes can be named, meaning that identifiers inside modules must be *qualified* with the name of their containing scope. Some languages, like F#, Java and TypeScript, have a notion of \"opening\" a module which means adding all the items inside it to the lexical environment it's opened in."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "var symbolTuples = symbols.Select((s, i) => (Var: new CilLocalVariable(factory.Int32), Id: s, Index: i));\n",
    "\n",
    "foreach (var tpl in symbolTuples)\n",
    "{\n",
    "    methodBody.LocalVariables.Add(tpl.Var);\n",
    "}\n",
    "\n",
    "var symbolTable = symbolTuples.ToDictionary(k => k.Id, v => v.Index);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we're ready to start generating code.\n",
    "\n",
    "> You might recall that our language always ends with an expression. This type of pattern is common when using languages in a scripting environment, such as Python in an interactive environment and [C# Script](https://learn.microsoft.com/en-us/archive/msdn-magazine/2016/january/essential-net-csharp-scripting). For our purposes, I didn't want to go through the work / add the complexity of implementing calling .NET methods, so in every program, `Console.Write` is called on this final expression. This gives us an easy way to test our programs, but is obviously lacking, as we cannot call `Console.Write` in various points of our code. \n",
    "\n",
    "We have `n` statements and one expression at the end, and it would make sense that - since we don't have functions - we generate code for our language in order.\n",
    "\n",
    "So our general algorithm would look something like\n",
    "```\n",
    "for each statement s\n",
    "    codegen(s)\n",
    "codegen(final expression)\n",
    "codegen(call `Console.Write`)\n",
    "```\n",
    "\n",
    "The way a stack evaluation model works, is that the \"current\" value is always at the top of the stack. Looking at the last two instructions above, we see we never \"pass\" the final expression to `Console.Write`, but instead push the argument onto the stack and then call `Console.Write`. This is also how we can handle assignment statements - by pushing the expression onto the stack and then popping it into the local variable being assigned to."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, we define a method for evaluating expressions and pushing them onto the stack: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "List<CilInstruction> Codegen(Expression expression)\n",
    "    => expression switch\n",
    "    {\n",
    "        NameExpression s => new List<CilInstruction>()\n",
    "        {\n",
    "            new CilInstruction(CilOpCodes.Ldloc_S, methodBody.LocalVariables[symbolTable[s.Identifier.Memory.ToString()]]),\n",
    "        },\n",
    "        BinaryExpression s => ((Func<List<CilInstruction>>)(() =>\n",
    "        {    \n",
    "            var l = new List<CilInstruction>();\n",
    "            l.AddRange(Codegen(s.Left));\n",
    "            l.AddRange(Codegen(s.Right));\n",
    "            l.Add(new CilInstruction(s.Operator.Type switch\n",
    "            {\n",
    "                TokenType.Add => CilOpCodes.Add,\n",
    "                TokenType.Subtract => CilOpCodes.Sub,\n",
    "                TokenType.Multiply => CilOpCodes.Mul,\n",
    "                TokenType.Divide => CilOpCodes.Div,\n",
    "                _ => throw new NotImplementedException()\n",
    "            }));\n",
    "\n",
    "            return l;\n",
    "        }))(),\n",
    "        IntLiteralExpression s => new List<CilInstruction>()\n",
    "        {\n",
    "            new CilInstruction(CilOpCodes.Ldc_I4, s.Value),\n",
    "        },\n",
    "        _ => throw new NotImplementedException()\n",
    "    };"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then to generate code for each statement, where every statement is an assignment statement, we generate code to push the expression onto the stack, then code to pop the stack into a local variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "var il = methodBody.Instructions;\n",
    "\n",
    "il.AddRange(\n",
    "    program.Statements.StatementList\n",
    "        .SelectMany(s => s switch\n",
    "            {\n",
    "                AssignmentStatement { Identifier: { Memory: var memory }, Expression: Expression expression } => ((Func<List<CilInstruction>>)(() =>\n",
    "                {    \n",
    "                    var l = new List<CilInstruction>();\n",
    "                    l.AddRange(Codegen(expression));\n",
    "                    l.Add(new CilInstruction(CilOpCodes.Stloc_S, methodBody.LocalVariables[symbolTable[memory.ToString()]]));\n",
    "\n",
    "                    return l;\n",
    "                }))(),\n",
    "                _ => throw new NotImplementedException()\n",
    "            }    \n",
    "        )\n",
    ");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And finally, the evaluate the last expression and call `Console.Write`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "il.AddRange(Codegen(program.Eval));\n",
    "il.Add(CilOpCodes.Call, write);\n",
    "il.Add(new CilInstruction(CilOpCodes.Ret));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can set our `mainMethod` as our entry point"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "programType.Methods.Add(mainMethod);\n",
    "module.ManagedEntryPointMethod = mainMethod;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And write our assembly (it is a framework-dependent assembly, so we also need to write a `*.runtimeconfig.json`)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [],
   "source": [
    "assembly.Write(\"MyAssembly.exe\");\n",
    "System.IO.File.WriteAllText(\"MyAssembly.runtimeconfig.json\",\n",
    "\"\"\"\n",
    "{\n",
    "   \"runtimeOptions\": {\n",
    "     \"tfm\": \"net8.0\",\n",
    "     \"framework\": {\n",
    "       \"name\": \"Microsoft.NETCore.App\",\n",
    "       \"version\": \"8.0.0\"\n",
    "     }\n",
    "   }\n",
    "}\n",
    "\"\"\"\n",
    ");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, if we run our assembly with PowerShell:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "dotnet_interactive": {
     "language": "pwsh"
    },
    "polyglot_notebook": {
     "kernelName": "pwsh"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\r\n"
     ]
    }
   ],
   "source": [
    "dotnet MyAssembly.exe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For seeing our compiled code, I prefer using [ILSpy](https://github.com/icsharpcode/ILSpy) (can install on Windows with `winget install ILSpy`), but if you don't want to install that tool, we can pretty print our instructions with AsmResolver like so (taken from [here](https://docs.washi.dev/asmresolver/guides/dotnet/managed-method-bodies.html#pretty-printing-cil-instructions)):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "dotnet_interactive": {
     "language": "csharp"
    },
    "polyglot_notebook": {
     "kernelName": "csharp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "IL_0000: ldc.i4 2\n",
      "IL_0005: stloc.s V_0\n",
      "IL_0007: ldc.i4 3\n",
      "IL_000C: stloc.s V_1\n",
      "IL_000E: ldc.i4 3\n",
      "IL_0013: ldloc.s V_0\n",
      "IL_0015: add\n",
      "IL_0016: ldloc.s V_1\n",
      "IL_0018: mul\n",
      "IL_0019: stloc.s V_2\n",
      "IL_001B: ldloc.s V_2\n",
      "IL_001D: call System.Void System.Console::Write(System.Int32)\n",
      "IL_0022: ret\n"
     ]
    }
   ],
   "source": [
    "var formatter = new CilInstructionFormatter();\n",
    "foreach (CilInstruction instruction in methodBody.Instructions)\n",
    "    Console.WriteLine(formatter.FormatInstruction(instruction));"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".NET (C#)",
   "language": "C#",
   "name": ".net-csharp"
  },
  "language_info": {
   "name": "polyglot-notebook"
  },
  "polyglot_notebook": {
   "kernelInfo": {
    "defaultKernelName": "csharp",
    "items": [
     {
      "aliases": [],
      "languageName": "csharp",
      "name": "csharp"
     }
    ]
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}