Superpower: The parser combinator library [Part 1] 💻🤓

Superpower

SUPERPOWER

The parser combinator library – Part 1

You depend on parsers

Everything you do as a developer relies heavily on parsers. Programming languages, data, scripting engines, tools… almost everything in development uses languages to be described. For example, our code needs to be translated to real code that our machines can understand. What happens under the hood is not magic, but it looks so 😊 We are constantly using compilers and interpreters. Both need parsers.Parsers are deeply attached in almost every development tool we use!

But what does a parser do?

They translate. Or more specifically, they transform one representation “A” into another “B”.

Let’s consider a sentence to illustrate:

“A house contains a garage which contains a car”

This sentence has sense in English, and we can understand it as is, but it has an important downside: natural languages like English are too complex to be used by computers. To overcome this problem we use formal languages, defined by a set of strict rules that are easier to handle.

For instance, the sentence above can be represented like

 

<House>
            <Garage>
                        <Car />
            </Garage>
</House>

 

Or can be modeled using C# with something like

new House { Parts = new List<Part> { new Garage { Items = new List<Item> { new Car() } } } }

 

We translated the sentence into other languages that are:

  1. Concise
  2. Have a very strict way to express

With this conversion, we’re sacrificing flexibility to gain simplicity. And simplicity is always a good thing in software development!

Going to the details: we had a sentence in English, and we converted it into 2 different representations.  Our brain acted as a parser (a translator). We’re doing this kind of translation every time: From sounds (voice) to words, from words to concepts, from concepts to actions, feelings, memories… Too deep to be an article about development, isn’t it? 😊

We use different languages to represent the reality, our domain, our business logic, data… there are thousands of languages! Each one is thought to be useful in each context.

Parsers help us interpret them and convert them to abstractions that are useful and usable in our applications.

Why would I need a parser?

Because different domains and different problems usually require different languages to be expressed, that ultimately need to be translated to be useful.

For example, they’re very useful when using Domain Specific Languages (DSLs). DSLs are languages tailored so they describe things in terms of our domain.

Let’s create a language

Imagine that our domain is related to the robot industry and we want to have a high-level language to tell a robot what to do.

We could define a language to represent the actions of a robot.

 

Move[F:20], Jump, Turn[45], Move[B:30], Spin[3]

 

This invented language is super easy to understand for us, but it isn’t anything than a bunch of letters, numbers and symbols in a special order that makes sense for us.

Our language can be formalized with a proper grammar definition to define what is well-formed and what isn’t. To do it, we can use BNF (Backus-Naur Form), that is a notation to define grammars.

So, we define a grammar for the language.

Grammars

Our languages are defined by grammar, that are basically a set of rules. They are a basic requirement when you want to build a parser.

We can generate parsers from grammars

Good news. There are automatic tools that will convert a grammar definition into a parser for that grammar. Oh yeah!!

We won’t use them!

This time we’re not using external tools, but plain C# with the help of Superpower, the easy yet powerful way to create parsers in .NET.

Why?

The greatest benefits are

  1. Parsers generated with Superpower can be part of your codebase
  2. They are inherently cross-platform (they target a very low .NET Standard version)

But that will be in Part 2 of this article.

Stay tuned!

In the meanwhile, you can take a look at the following links to be prepared for the next part 🙂

 

Written by: Jose Manuel Nieto, part of Idiwork’s team.

Stay up to date!



Leave a comment