Building a Modern MUSH with Typescript Part 6: The Mushcode parser!
Tags: typescript, tutorial, node, mush
Published: 2020-03-25 15:39:08

Welcome back! In [Part 5](https://dev.to/lcanady/building-a-modern-mush-with-typescript-part-5-creating-the-command-handler-422j) we built the database adapter and actually got the game booted up! Today we're covering my favorite part - the Mushcode interpreter!  We'll also build a function as well as a command that makes use of the mushcode engine.  It's a kind of code dense, but we'll get through it!

## Making a Grammar
I decided early on that I was going to go a different direction than the destructive parser that's popular in other MU* engines.  Instead, I went with a library called [PEGJS](pegjs.org), or a [Parsing Expression Grammar](https://en.wikipedia.org/wiki/Parsing_expression_grammar). It lexes down expressions into an Abstract Syntax Tree (AST).  From there we recursively walk the tree until we've parsed the entire expression.

### Disclaimer
I've never taken any sort of language design coursework, I've had to crash course myself on this part.  My grammar is messy!

**With that said, here we go!**

## The Grammar
```JavaScript
// mushcode Grammar
// Author: Lemuel Canady, Jr 2020
// This grammar is really basic, but it gets the job done!
// Builds an AST to be processed by the game server.
 
function =  _ call: word "(" _ a: (args)? _ ")" _  
{ 
    const loc = location()
    return {
    	type: "function", 
        operator: {type: "word", value:call},
        location: loc,
        args: Array.isArray(a) ? a : [a]
   }
} /

_ "[" _ call: word "(" _ a: (args)? _ ")" _ "]" _  
{ 
    const loc = location()
    return {
    	type: "function", 
        operator: {type: "word", value:call},
        location: loc,
        args: Array.isArray(a) ? a : [a]
   }
}


args = 	a:(arg arg)+ _ t:args* {
   return [{type: "list", list: a.flat()},...t].flat()
}/ 

a: arg* _ "," _ "," _ t: (args)* 
{ 
    const loc = location();
    return [[
        a,{type: "word", value: null, location:loc}
    ].flat(),t.flat()].flat() 
}/
    
a: arg* _ "," _ t: (args)* {return [a.flat(),t.flat()].flat()}  / 
arg 

arg = 	f: function {return f} / 
    w: word { 
     	const loc = location();
     	return {type: "word", value: w,   location: loc 
    } 
}

word = w:[^\(\),\[\]]+ {return w.join("").trim()} 
_ = [ \t\n\r]*

```
The grammar looks for 3 things: Words, functions, and lists. When defining a grammar, they're built from the bottom up. I started with defining what space is, then a word - and move up until I get to define what makes an expression at the top.  

A `word` is anything that isn't a `function` - function arguments, function names, numbers - it's all strings.  Lists are a series of expressions side by side, separated by brackets.  For Instance! If we took this mushcode snippet (warning, it's verbose! :D ):
```
[a([b(1,2)][c()])]
```
Once parsed by the Grammer returns:
```JavaScript
{
   "type": "function",
   "operator": {
      "type": "word",
      "value": "a"
   },
   "location": {
      "start": {
         "offset": 0,
         "line": 1,
         "column": 1
      },
      "end": {
         "offset": 18,
         "line": 1,
         "column": 19
      }
   },
   "args": [
      {
         "type": "list",
         "list": [
            {
               "type": "function",
               "operator": {
                  "type": "word",
                  "value": "b"
               },
               "location": {
                  "start": {
                     "offset": 3,
                     "line": 1,
                     "column": 4
                  },
                  "end": {
                     "offset": 11,
                     "line": 1,
                     "column": 12
                  }
               },
               "args": [
                  {
                     "type": "word",
                     "value": "1",
                     "location": {
                        "start": {
                           "offset": 6,
                           "line": 1,
                           "column": 7
                        },
                        "end": {
                           "offset": 7,
                           "line": 1,
                           "column": 8
                        }
                     }
                  },
                  {
                     "type": "word",
                     "value": "2",
                     "location": {
                        "start": {
                           "offset": 8,
                           "line": 1,
                           "column": 9
                        },
                        "end": {
                           "offset": 9,
                           "line": 1,
                           "column": 10
                        }
                     }
                  }
               ]
            },
            {
               "type": "function",
               "operator": {
                  "type": "word",
                  "value": "c"
               },
               "location": {
                  "start": {
                     "offset": 11,
                     "line": 1,
                     "column": 12
                  },
                  "end": {
                     "offset": 16,
                     "line": 1,
                     "column": 17
                  }
               },
               "args": [
                  null
               ]
            }
         ]
      }
   ]
}
```
I decided to keep the location information for a debugger I have planned in the future.  Once I have that AST I put it through the non-destructive in-game parser.  First, we'll save the grammar to the root of our project as `mushcode.pegjs`.  Then, we need to body `parser.ts` to handle the interpretation.

> Want to play with the grammar?  Head to [PegJS Online](https://pegjs.org/online), enter my grammar and start building expressions!  If you can make improvements? Please let me know!

## Updating `parser.ts`
**Before we begin!** We need to add a new folder to our project structure.  From your project root type:
```
mkdir src/functions
```
Then, we need to define a couple of new interfaces to shape our data:

```JavaScript
export type MuFunction = (
  enactor: DBObj,
  args: Array<Expression | string | number>,
  scope: Scope
) => Promise<any>;

export interface Expression {
  type: string;
  value: string;
  list?: Expression[];
  operator: {
    type: string;
    value: string;
  };
  location?: {
    start: {
      offset: number;
      line: number;
      column: number;
    };
    end: {
      offset: number;
      line: number;
      column: number;
    };
  };
  args: Array<string | Expression>;
}

export interface Scope {
  [key: string]: any;
}
```
And in the constructor:
```JavaScript
export class Parser {
  private stack: MiddlewareLayer[];
  private static instance: Parser;
  private peg: any; 
  private parser: peg.Parser;
  private fns: Map<string, MuFunction>;
  private constructor() {
    this.stack = [];
    this.peg = readFileSync(
      resolve(__dirname, "../../mushcode.pegjs"), {
        encoding: "utf8"
    });
    this.parser = peg.generate(this.peg);
    this.fns = new Map();
    loadDir("../functions/", (name: string) =>
      console.log(`Module loaded: ${name}`)
    );
  }
```
Pretty straight forward, we added `peg`, `parser`, and 'fns' to handle our softcode additions.  Next, we load the grammar file, generate a parser from it, and load all of the files located in `src/functions/`.

```JavaScript
/**
   * Parse a string for syntax
   * @param code
   */
  parse(code: string) {
    try {
      return this.parser.parse(code);
    } catch (error) {
      throw error;
    }
  }

  /**
   * Add a new softcode function to the system
   * @param name The name of the function
   * @param func The code to be called when the function
   * name is matched.
   */
  add(name: string, func: MuFunction) {
    this.fns.set(name.toLowerCase(), func);
  }
```
`parse` will generate our AST to work with.  Then we need to evaluate that tree:
```JavaScript
/**
   * Evaluate a mushcode expression AST.
   * @param en The enacting DBObj
   * @param expr The expression to be evaluated
   * @param scope Any variables, substitutions or special forms
   * that affect the lifetime of the expression.
   */
  async evaluate(en: DBObj, expr: Expression, scope: Scope) {
    // First we need to see what kind of expression we're working with.
    // If it's a word, then check to see if it has special value in
    // scope, or if it's just a word.
    if (expr.type === "word") {
      expr.value = expr.value || "";
      if (scope[expr.value]) {
        return scope[expr.value];
      } else {
        // Sometimes variables in scope can be imbedded
        // in a line of text that the parser evaluator 
        // can't see - so we'll do a RegExp replace as well.
        let output = expr.value;
        for (const key in scope) {
          output = output.replace(
            new RegExp(key, "gi"), scope[key]
          );
        }
        return output;
      }
      // If the expression is a function...
    } else if (expr.type === "function") {
      const operator = expr.operator;

      // Make sure it's operator exists in the Map...
      if (operator.type === "word" && this.fns.has(operator.value)) {
        const func = this.fns.get(operator.value);
        if (func) {
          // Execute it and return the results.
          return await func(en, expr.args, scope);
        }
      }

      // If it's a list (operations seperated by square brackets)
      // Process each item in the list.
    } else if (expr.type === "list") {
      let output;
      for (let i = 0; i < expr.list!.length; i++) {
        output += await this.evaluate(en, expr.list![i], scope);
      }
      return output;
      // Else throw an error, unknown operation!
    } else {
      throw new Error("Unknown Expression.");
    }
  }
```
Expressions can come in two flavors: Just an expression, or an expression surrounded by brackets, embedded within a string of text.  The second condition is a bit more verbose. :)
```JavaScript
/**
   * Run the parser on the input string.
   * @param en the enacting DBObj
   * @param string The string to be run through the parser.
   * @param scope Any variables, substitutions or special forms
   * that affect the lifetime of the expression.
   */
  async run(en: DBObj, string: string, scope: Scope) {
    try {
      return await this.evaluate(en, this.parse(string), scope);
    } catch (error) {
      return await this.string(en, string, scope);
    }
  }
```
And then there's `string()` It basically scrubs through the string character by character looking for parentheses and square brackets.
```JavaScript
  async string(en: DBObj, text: string, scope: Scope) {
    let parens = -1;
    let brackets = -1;
    let match = false;
    let workStr = "";
    let output = "";
    let start = -1;
    let end = -1;

    // Loop through the text looking for brackets.
    for (let i = 0; i < text.length; i++) {
      if (text[i] === "[") {
        brackets = brackets > 0 ? brackets + 1 : 1;
        start = start > 0 ? start : i;
        match = true;
      } else if (text[i] === "]") {
        brackets = brackets - 1;
      } else if (text[i] === "(") {
        parens = parens > 0 ? parens + 1 : 1;
      } else if (text[i] === ")") {
        parens = parens - 1;
      }

      // Check to see if brackets are evenly matched.
      // If so process that portion of the string and
      // replace it.
      if (match && brackets !== 0 && parens !== 0) {
        workStr += text[i];
      } else if (match && brackets === 0 && parens === 0) {
        // If the brackets are zeroed out, replace the portion of
        // the string with evaluated code.
        workStr += text[i];
        end = i;

        // If end is actually set (We made it past the first
        //character), then try to parse `workStr`.  If it 
        // won't parse (not an expression)
        // then run it through string again just to make sure.  
        // If /that/ fails? error.
        if (end) {
          let results = await this.run(en, workStr, scope)
            .catch(async () => {
              output += await this.string(en, workStr, scope)
               .catch(console.log);
            });
          // Add the results to the rest of the processed string.
          output += results;
        }

        // Reset the count variables.
        parens = -1;
        brackets = -1;
        match = false;
        start = -1;
        end = -1;
      } else {
        // HACK! If stray paren or bracket slips through, 
        // add it to `workStr`
        // else add it right to the output.  There's no code there.
        if (text[i].match(/[\[\]\(\)]/)) {
          workStr += text[i];
        } else {
          output += text[i];
        }
      }
    }
    // Return the evaluated text
    return output ? output : workStr;
  }
}

```
Next, we'll define a command that can handle expressions, and a function to example with! We'll use a classic:  `src/commands/think.ts`
```JavaScript
import cmds from "../api/commands";
import mu from "../api/mu";
import parser from "../api/parser";

export default () => {
  cmds.add({
    name: "think",
    flags: "connected",
    pattern: /think\s+?(.*)/i,
    exec: async (id: string, args: string[]) => {
      const en = mu.connMap.get(id);
      return await parser.run(en!, args[1], {});
    }
  });
};
```
Then we need to add our function to `src/functions/math.ts`:
```JavaScript
import parser, { Expression, Scope } from "../api/parser";
import { DBObj } from "../api/database";

export default () => {
  // MATHS!

  /**
   * Add a list of numbers together!
   */
  parser.add("add", async (en: DBObj, args: any[], scope: Scope) => {
    let total = 0;
    for (const arg of args) {
      // We have to evaluate any argument we want to work
      // with, because it's still in expression AST form.  
      // It could be anything at this point. this will recursively
      // trigger each expression in the tree.
      total += parseInt(await parser.evaluate(en, arg, scope), 10);
    }
    return total.toString();
  });
};

```
And now, let's see it work all together.  It's **animated gif** time!

![Mushcode!!](https://dev-to-uploads.s3.amazonaws.com/i/bpdy9chn7rs9kbrt1v40.gif)

I think that's where I'll wrap for this installment, woot!  We only have a few base features left!  Next time we'll cover grid commands (building/editing/destroying) so we can instantiate objects from within the mush!

Thanks for stopping in and surviving the read! Feel free to **Follow** me for updates, and or leave a comment!