LP Parser

Writing the parser

A parser in Esolang Park is responsible for taking the raw source code in textual form and converting it into a compact format that can be executed by the language engine. This intermediate format is generally called an abstract syntax tree or an AST. Note that it doesn't need to be a tree - the exact structure depends on how you wish to implement the language provider. A parser also validates the syntax of the source code and points out any mistakes to the user.

Depending on the complexity of the syntax of your esolang, the parser may be as small as a simple function or may use a lexing stage and grammar definition. Each of the cases are covered below but before that, we need to cover some basics that apply to all cases. The last section of this page covers how to test and try out your parser on the Esolang Park IDE.

The common basics

An Esolang Park language provider is not the same as other interpreters. Interpreters like the ones used in TryItOnline can do with just processing and executing the source code all in one go and spitting out error messages - Esolang Park parsers and interpreters are more sophisticated. To provide features like breakpoint support, you'll need to keep track of the location of each operation and be able to execute the program one step at a time. You'll have to keep this requirement in mind while you're implementing the parser and engine. The examples below illustrate this to some extent.

Also, take a look at the DocumentRange type and ParseError error class in the Utilities page. The DocumentRange type represents the location of some text in the source code, and is super-important while implementing the parser. The ParseError error class is used to point out syntax errors which are then marked in the editor or shown in the output pane.

Working on the parser or engine requires you to have both yarn dev and yarn dev:worker running at the same time. You can use multiple terminal windows or terminal multiplexing to do this. Also, you'll have to refresh the page everytime you make a change.

For simple languages

Similar to the syntax highlighting example, parsers for syntactically trivial languages can be implemented quite easily. The Deadfish parser simply pushes each idso character (along with its location) into an array - this array becomes the AST for the Deadfish engine. Here's the Deadfish parser in its entirety:

parseCode(code: string) {
  const ast: DFAstStep[] = [];

  // For each line...
  code.split("\n").forEach((line, lIdx) => {
    // For each character of this line...
    line.split("").forEach((char, cIdx) => {
      // If it is an `idso` character...
      if (OP_CHARS.includes(char as DF_OP)) {
        // Add the op and its location to the AST
        ast.push({
          instr: char as DF_OP,
          location: { line: lIdx, char: cIdx },
        });
      }
    });
  });

  return ast;
}

The Brainfuck parser works similar to Deadfish, but is slightly more complex due to loops. In addition to the above, the Brainfuck parser does the following:

• While parsing, it maintains a stack containing the AST index of currently active loops.
• Using this stack, jump addresses are added to loop-opening and loop-closing ops for directly jumping to the start or end of the loop while executing code.
• This stack is also used to validate that all loop characters ([]) are matched properly.

Take a look at the Brainfuck parser (it's just 40 lines) to see the details of how jump addresses are used for looping.

While in some ways similar, Befunge-93 has an additional layer of complexity due to its self-modifying and two-dimensional nature, which is why it is covered in a separate section. If your esolang is self-modifying, refer to that section.

Simple hand-built parsers

The next category of esolangs we consider is of those which are more complicated than character-wise operations, but not too complex - there is no nested expressions and no recursive definitions. Chef is a great example for this category.

The Chef parser in Esolang Park makes extensive use of regular expressions. The method section of every Chef recipe is first split into individual instructions. Each instruction is then matched against regular expressions for different instruction types, and pushed into the AST for that recipe. A loop stack is maintained in this process and jump addresses are added in loop instructions.

This kind of simple hand-built parsers have the advantage of fairly quick implementation and a very small bundle size. There are drawbacks though - for instance, it is very difficult to provide helpful error messages for statements that don't match any known pattern. Play around with Chef programs on Esolang Park to get a feel.

The alternative to such hand-built parsers is using third-party libraries to implement a full-blown parser. This adds to the bundle size but allows you to create the parser by usually just writing the grammar rules for your esolang. It also allows better error messages like Expected "the" but found "them". The next section covers this.

Grammar-based parsers

Almost all mainstream parsers are implemented by laying down the grammar rules of the language's syntax. If you know a bit about context-free grammars, this should be easy to understand. If you're new, this allows you to create parsers by defining rules like follows:

// An example for sample syntax of stack operations
VariableName ::= /[a-zA-Z]+/
Expression ::= /[0-9]+/ | VariableName
StackPopStatement ::= "Pop" VariableName
StackPushStatement ::= "Push" Expression "onto" VariableName

The parser library does the rest by applying your rules onto the source code. Most parser libraries also provide the location of each token along with user-friendly error messages.

There are several different kinds of parsing libraries available and I cannot cover them here - this fantastic must-read article covers many of them along with a great intro to parsers too. Go through the article and consider the options. Keep bundle size in mind, though - don't bring in a megabyte beast.

The Shakespeare parser in Esolang Park uses Chevrotain, a TypeScript-friendly parsing DSL. With a little bit of redundancy and a little bit of TypeScript-hackery, Chevrotain allows implementing an almost perfectly type-safe parser. It also boasts of fantastic performance and other useful capabilities - some which Esolang Park currently can't even make full use of, like multiple syntax error reporting and auto-complete helper functionality. Do have a look at the Shakespeare parser to get an idea of what a Chevrotain parser looks like.

Self-modifying esolangs

Self-modifying esolangs are esolangs which allow the program to access and edit its own source code at runtime - or in more evil cases, the language runtime itself modifies the source code at runtime. The important matter is that code changes at runtime. Befunge-93 is an example of such a language.

Since Esolang Park allows displaying runtime changes in source code to the user, a major difference in the parser implementation for self-modifying esolangs is that directly or indirectly, you need to maintain the source code in textual form. Then when there is a change in the source code, the engine sends the modified version of source code back to the IDE.

In such languages, the work of the parser somewhat overlaps with and merges into the engine itself. Most of what's said above goes out the window, so feel free to implement it whichever way you want. As long as it works well and is maintainable, it's fine. Read the Befunge-93 language engine to see an example of how it's done.

Handling syntax errors

Your parser also needs to handle source code that is syntactically incorrect. This is fairly simple - while parsing the source code, if you encounter syntactically incorrect code, just throw a ParseError with an appropriate error message and the location of the incorrect code. Esolang Park does the rest and the relevant source code is red-marked in the editor for the user to check. See the Utilities page and the source code for more information on ParseError.

In its current form, Esolang Park only supports displaying a single syntax error to the user, which is why this error-throwing method works. Support for multiple syntax error may arrive later, which will use a different way of error-reporting. This method will still work, though.

Note that for live syntax checking in the editor, Esolang Park calls your parser (via the engine) whenever the user makes changes to the source code. This means that your parser should ideally be a pure function, meaning it should not affect anything outside of itself. For instance, instead of setting the AST field inside the parse function, the function should return the AST as a value instead. This will be clearer in the next section.

Designing and building the AST

As mentioned, the AST is the source code expressed in compact format - as simple as an array of operations in Brainfuck, or more complicated like Chef or Shakespeare. The one super-important requirement to consider while designing the AST is that it must be executable step-by-step, keeping track of the location of each step. Information that is not useful in execution should not be included in the AST at all. In essence, the AST should be designed as the simplest possible structure that contains all the information required for step-by-step execution.

For instance, clubbing the statements inside a while-loop is usually a no-no and is going to pain you while implementing the engine, because it will become difficult to keep track of where the execution is ("execution is inside the second while-loop in the else-branch of the top-level while-loop - what's the next instruction to execute now?"). It's not impossible, but jump addresses do the job much more easily in most cases.

If the design of the AST is not immediately clear, try creating a basic version of the AST and implement the engine with that. Insights from trying the engine implementation will guide you to make the right changes in the AST.

Trying out your parser

Once you have a prototype version of your parser ready, you can plug it into the engine and test it on the IDE. Assuming your stub files are intact and you have a function parseCode that takes in the source code as input, open runtime.ts and make the following changes:

export default class XYZLanguageEngine implements LanguageEngine<RS> {
  // ... other methods ...

  validateCode(code: string) {
    parseCode(code);
  }

  prepare(code: string, input: string) {
    parseCode(code);
  }

  // ... other methods ...
}

Once done, refresh the page to see your parser in action. If your parser is working correctly, syntax errors will be red-marked in the editor. Now you can use the IDE to fix, iterate upon and improve your parser.

If refreshing the page doesn't work, make sure you have both yarn dev and yarn dev:worker running at the same time.

Once you're satisfied with your parser and are ready to execute on the AST output, move to the Language Engine page using the sidebar.