How I built a simple compiler — Markdown to HTML
Tags: csharp, dotnet, compiler, computerscience
Published: 2019-11-22 12:12:41

A colleague of mine, who happens to be my ̶ b̶o̶s̶s̶  leader wrote a really cool compiler. It’s not a cool CRUD app or complicated animation.

IT’S A COMPILER. Used in the production environment. And it’s not backed up by a community or a big company.

![MINDBLOW](https://media.giphy.com/media/Um3ljJl8jrnHy/giphy.gif)

I think that’s pretty cool…I would like to code cool stuff...So I decided I’m going to write a compiler!

*So I did*…because I could do following

- Learn more about the magic of compilers
- Learn something else than a new JavaScript framework
- Achieve one of my goals.
- Code something different.
- Understand the codebase more in-depth

## How?

Foundation of my compiler is built on top of [Irony](https://github.com/IronyProject/Irony). It’s a .NET Language Implementation Kit. Unfortunately, there’s not a lot of info or tutorials online. Even with the little amount of online documentation, I was able to define language grammar, so I can parse the input.

I’m using Irony’s NonTerminal and Terminal classes to define my markdown.

{% gist https://gist.github.com/jozefchmelar/ee42ea031d9b04edeb039ecee200d997 %}

## Grammar
Now it’s time to define Grammar rules. Grammar is defined using [Backus-Naur form](https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form). Irony overloads C# operators and makes it really easy to define grammar.

{% gist https://gist.github.com/jozefchmelar/8c638b52517363e6093f35ab3d5eca46 %}

It’s so easy to read. Let’s dive in.

Bold text has to start with a _star *_ followed by a _Text_ ending with a _star *_. _Text_ can be _StyledText_ or _PlainText_. But _StyledText_ can _Bold, Italics_ or U͟n͟d͟e͟r͟s͟c͟o͟r͟e͟. Do you see the little hack? Now _Bold_ text can also be underscore and italics! Same thing with Header. Underscore header? No problem, since it fits our grammar rules.
![It's not THAT complicated](https://miro.medium.com/max/1280/0*aYgkI4mqH6eoqreU.jpg)
<figcaption >It's not THAT complicated</figcaption >

If you notice the definition of NonTerminals and Terminals you will see the second parameter is a type of Ast node. This way I could map my parse tree to AST. It was really a pain to achieve this. I searched StackOverflow, second page of google results…no luck. My solution might not be the best in the world but it works. It’s a function which creates an instance of the type you provide it with.

{% gist https://gist.github.com/jozefchmelar/f0c184066ab4824bb6b821a8e974c6cd %}

It’s much easier to work with AST than parse tree :) That’s why you do it.
![Parse vs AST tree](https://miro.medium.com/max/936/1*hgUs6W3ldETMAP5J9JLe1Q.png)
<figcaption >Parse vs AST tree</figcaption >

## From Abstract Syntax Tree to HTML

Grammar is defined, AST looks good. Now I had to do a thing which I’ve been successfully avoiding for like 5 years. **I had to learn the [visitor pattern](https://en.wikipedia.org/wiki/Visitor_pattern)**. It makes much more sense now, than in a university few years ago.

![Accurate description of visitor pattern](https://media.giphy.com/media/11gC4odpiRKuha/giphy.gif)
<figcaption >Accurate description of visitor pattern</figcaption >

This is how Irony accepts Visitor when traversing the tree.

{% gist https://gist.github.com/jozefchmelar/04f6ec35e9ed2e6aed675f2c99aab9cf %}

And this is how I wrote my HTML visitor. Before you visit a node write you tag, after that he will visit every child.

{% gist https://gist.github.com/jozefchmelar/a9f907207ed43043d478ce7dccba6e66 %}

When you encounter PlainTextAst, output the text we parsed

{% gist https://gist.github.com/jozefchmelar/2e3b70a0e84d1fa4fc938556a7743491 %}

And now just visit the root

{% gist https://gist.github.com/jozefchmelar/59677f63ae6cec240fbd9c95bac243ab %}

## Voilà!

From this
```
#"H1 Heading"
#_"H1 undescore heading"_
##"H2 Heading"
*"This is bold text"* "and this is regular text"
"Following three items should be in a list, this is plaintext"
- "Plaintext list item"
- *"Bold List item"*
- _*"Underscore bold list item"*_
- _"Underscore  list item"_
#"This is heading again"
```
To this
```
<div>
  <h1>H1 Heading</h1>
  <h1>
    <u>H1 undescore heading</u>
  </h1>
  <h2>H2 Heading</h2>
  <b>This is bold text</b>
  <p>and this is regular text</p>
  <p>Following three items should be in a list, this is plaintext</p>
  <ul>
    <li>Plaintext list item</li>
    <li>
      <b>Bold List item</b>
    </li>
    <li>
      <u>
        <b>Underscore bold list item</b>
      </u>
    </li>
    <li>
      <u>Underscore  list item</u>
    </li>
  </ul>
  <h1>This is heading again</h1>
</div>
```
## It works!
![Great success](https://media.giphy.com/media/a0h7sAqON67nO/giphy.gif)

# Conclusion

I wanted to write a compiler from my markdown to HTML. I picked up great available tools to achieve it and **did it**. You don’t have to start in assembly to write your own parser, compiler, language, operating system…

Try it. Do it. Solve it.

{% github https://github.com/jozefchmelar/MarkdownCompiler no-readme %}




[![I'm just really curious if there are ppl like this](https://miro.medium.com/max/213/1*9vg3-OY14aZN1UpKwIxxZg.png)](https://www.buymeacoffee.com/jozefchmelar)