Derivatives of Context-Free Grammars explained

A tutorial on adding Memoization, Smart Constructors, Simplification Rules and Extra Operators to the Derivatives for Regular Expression algorithm

10 min readOct 5, 2022

In the previous post, we explained what a derivative of a regular expression is, using Pac-Man.

In this post, we are going to use Ragas from Indian classic music as an example, to explain how to extend derivatives:

with new operators,
with simplification rules, smart constructors and memoization as an optimisation strategy and also
to Context-Free Grammars.

We will call them Ragalur expressions or Ragax for short. In the end, I will show you have to use these Ragax to generate music.

If you prefer, you can watch the following video instead of reading the post as it covers the same material:

What is a Raga?

A raga is a melodic framework for improvisation in Indian classical music. Here is an example of a Raga being played:

Skip to 2:16

Notice how the player slides their hand up and down the strings. There are very strict rules that decide what notes they are allowed to play next. Ragas are basically the Indian version of western scales.

They are stricter than western scales. The possible next note is not simply chosen from a set, but rather depends on the current note.
Also, notes are labelled a bit differently. They are labelled relative to the start note.

Here you can see how they are labelled, if you start at c:

There is a lot of other very interesting things to cover about Ragas, but I will skip over microtones and all the other theory since we are only interested in the stricter rules for this post.

Why we need simplification rules

As an example to compare a raga with later, let’s look at how we would describe a western scale using a regex. In this case the C Major Pentatonic scale: c(c|d|e|g|a)*. We can check if it matches the sequence of notes ceg by using the derivative algorithm, discussed in the previous post.

First, we take the derivative of the whole expression with respect to c. If we strictly follow the rules, we see that c matches the first c, so it becomes the empty string. Now we get the empty string concatenated with (c|d|e|g|a)*.

Now we take the derivative of this expression with respect to e and we get … Wat!

Yes, this is what the concat rule expands to. Feel free to go and double-check my work, but I don’t want to bore you with the details. The important thing I want to demonstrate is that everything in the previous post went a bit too smoothly because I was cheating and applying simplification rules on the fly. This is what happens when I don’t do that. Things quickly get out of hand.

Simplification Rules

Luckily we have lots of simplification rules that can help.

When we concatenate an empty string with another expression, we can throw the empty string away: εr ≈ rε ≈ r
When we or with the empty set, we can throw the empty set away: r|∅ ≈ ∅|r ≈ r
When we or two expressions that are the same, then we can also throw one of them away: r|r ≈ r
We can also reorder expressions in an or to try and increase the likelihood of finding duplicates: s|r ≈ r|s
When we concatenate with the empty set, then the whole expression becomes the empty set: r∅ ≈ ∅r ≈ ∅
Zero or more zero or more times is just zero or more: (r*)* ≈ r*
Zero or more empty strings is just the empty string: ε* ≈ ε
Zero or more empty sets is just the empty string: ∅* ≈ ε

I am sure you can think of some more, but let’s go back to our example and see how we can apply some of these rules.

Applying Simplification Rules

Let’s now continue our example where we left off with our very large expression and apply some simplification rules:

We see that we are concatenating the empty set with another expression, which we can simplify to the empty set:

Now we can throw away the empty set on the left side of the or:

Next, we can throw away all the empty sets in the big or so that we are left with the empty string:

This is the same expression we got as the result of the derivative with respect to c. We have come full circle, but we can now also throw away this empty string since it is part of a concatenation and we get a fully simplified single star expression:

Now we can take the derivative with respect to our next input character g. After simplification, we also get the star expression:

This final expression matches the empty string, which means that the sequence ceg matches the C Major Pentatonic expression.

Smart Constructors

There are two ways we can apply the simplification rules. We can:

apply them recursively after each derivative step or
use smart constructors to apply them once as we construct expressions.

Smart constructors are different from stupid constructors that only initialise fields with the exact values that were passed, because they also apply some extra logic before initialising the fields. The logic we are going to have inside our smart constructors is the simplification rules.

This means that when you try to create an or between an empty set and another expression, we will simply return the other expression, instead of constructing an or expression. This way it is impossible to construct a regular expression that is not simplified, which also means that we don’t have to check that each expression is simplified after we have calculated the derivative, which saves a lot of double work.

Our smart constructor can also calculate a hash to make comparisons required during simplification faster. In general, this is the preferred way of implementing the algorithm, as it is much more efficient.

Here is an example of the smart constructor for the or expression:

Example of the Smart Constructor for the Or expression

Memoization

Another thing we can do to optimise is to use memoization. Memoization is a fancy word for just a way of remembering the result of a function, so you don’t have to go and recalculate the same result, given you have seen the same inputs before. This only applies to pure functions that always return the same results given the same inputs, which is perfect for our use case. We can start saving the results of the derivative function in a little table:

For example, given the expression: c(c|d|e|g|a)*, we go to (c|d|e|g|a)*, given the derivative is taken with respect to c, as you can see in row 2 column 2. If we run through our two other derivatives we get a total of 3 cells filled in. The rest of the table will be filled in as we calculate more derivatives. We can also use this table to look up results that have been calculated before as we calculate new derivates.

Deterministic Finite Automata

If we do fill in the table completely, we get what is called a transition table for a Deterministic Finite Automaton or DFA. Here you can see the resulting automaton or state machine:

Each state is represented by a regular expression. The nullable function represents the accepting function of the DFA. I just think this is so cool that we get this for free. We can lazily build the transition table, using our memoization strategy. This means our simplification rules are now technically being used for minimisation of the state space.

Raag Bhupali

Now back to Ragas. Here is a type of Pentatonic scale called Raag Bhupali.

Given the current note, you must choose the next ascending or descending note. For example, given G (e) you can choose P (g) if you want to ascend or R (d) if you want to descend.

This is much stricter than a western scale, where you can choose any note in the set at any time. The problem is describing these Raga sequences requires a new operator. This means we need to extend our algorithm to handle more operators.

Recursive Regular Expressions

Describing Raag Bhupali requires recursive Regular Expressions or Context-Free Grammars. This means we need to add references or links to our regular expressions. Here is a Context-Free Grammar that describes Raag Bhupali:

Our first note S is followed by its ascending or descending note and the whole expression is repeated zero or more times. The ascending note R is ascended by G or descended back to S, which is represented by the empty string, because when the expression R ends, the bigger S expression starts again at S.

The same goes for the rest:

G is followed by P or R.
P is followed by D or G and
D is followed by P or a termination since it can be followed by S.

Getting this linking feature requires us to extend our derivative algorithm to include a new operator for references.

Extending Logical Operators

Extending derivatives is easy, we simply need to implement the nullable and derivative functions for each new operator. For example, here is what it would look like for the and operator:

The logical operators can just push the problem down. This is why it is also very easy to implement the not operator:

They both just push the problem down.

Interleave Operator

Okay, that was too easy. Let’s try to invent an operator called interleave or shuffle. We want to interleave the two expressions S concatenated with R and D concatenated with G. This would result in all the following note sequences being accepted:

All strings accepted by SR interleaved with DG

S is always before R and D is always followed by G, but otherwise, the 4 notes can be in any order.

We can easily extend our regular expression matcher to handle this new operator by simply implementing both the derive and nullable functions for the interleave operator.

The derivative function requires us to return the expression that is left to match after matching a single character of an interleave expression. We are either going to take the character from the first expression or the second expression. We can take the derivative of the first expression r and interleave it with the second expression or we can take the derivative of the second expression s interleaved with the first expression:

Easier than expected and it works.

Finally, an interleaved expression matches the empty string only if both child expressions match the empty string. And that is it, we have implemented a very complicated operator, very simply.

Recursion

Let’s get back to implementing the recursion we needed. The operator we need to implement is a reference. This reference will go and look up an expression in a table, given the reference name. If we have this, then expressions can reference each other to create recursive regular expressions or Context-Free Grammars. To take the derivative we simply have to go and lookup and the expression and then take the derivative of the looked-up expression. The nullable function needs to do exactly the same:

This seems very simple and it works for our case and most cases.

Left Recursion

The case it does not work for is left recursion. Let’s look at our starting rule for our Raga again.

This rule has no left recursion and it will work without any problems, given our current implementation, but we could have just as easily rewritten it in a left recursive style:

These two rules will match the same Ragas, but the second one uses recursion instead of the star operator. It uses the recursion on the left side of the rule. This means when we calculate the derivative or nullability we will immediately be forced to look up the rule again, which would just result in us having to look up the rule again. Over and over, resulting in an infinite loop. Luckily a way has been figured out around this problem. It uses laziness, memoization and a least fixed point to get around this to stop the infinite loop. I have attached a reference, where you can read up on it a bit more.

I encourage you to go and check out the resources if you are interested to learn more about Ragas or how to solve the left recursion problem for Context-Free Grammars. In this video, I will show you how to generate musical Ragas using the algorithm you just learned about in a Digital Audio Workstation called Ableton Live with Max/MSP and Javascript.

Here is the resulting generated music:

Thank you

Ryan Lemmer and Antoine van Gelder for the idea to combine ragas and derivative for regular expressions