What do you call a reverse parser? Speed-typing, the “peaceful and relaxing” sport that breaks keyboard when you cannot get in that damn flow is actually very fun. If you haven’t tried it, good for you but basically you go onto websites like monkeytype and it presents you with words and as you start typing it times you on your words per minute so you have to type as fast as you can minimizing errors. I wanted to make a similar website, but for coders, where instead of typing through these random snippets, you type through code. I even have a working prototype..Its a WIP. You open it up, choose any language and it presents you with a snippet to type and we time you on that…simple.

The Problem?

These snippets themselves. for monkeytype, its easy, you can just paste random english words with variations and you got a good singleplayer experience. But we cannot just throw in random tokens and call it a day. Sure the code does not have to compile but it also cannot be nonsensical. If the person chooses Golang, the snippet should resemble golang.

So what do we do? We really have two options.

• Make a database with snippets of each language and randomly pick one and send it there, can work but again its not elegant and would be taxing on the server if someone wants to just practice on the singleplayer which will be most of the real usecase for it.
• Generate code on the client’s device on the fly, and this had so many advantages. The real backend server won’t be bothered as much and its bandwidth wont be piled up with sending code everywhere. And the app would be very snappy.

And that is why, I made Resrap, the reverse parser.

But what is a Parser?

Traditional Parsers take the “grammar” of the programming language, which contains all the rules to write syntactically correct code and using it validates the given code for its structure and reports syntax errors. It is a step while interpreting or compiling languages. What Resrap does, it reverses the parser’s role. It takes the Grammar and itself generates a syntactically correct snippet from it.

It is a substep in interpreting or compiling the code. We start off with Scanning or Tokenizing. A token (Not in LLM terms ffs) is the smallest piece of a language like

a=b+c

Here a,=,b,+,c and ; all are tokens.

So we first define what all type of tokens there are in a language, and scan through its text to get a list of the tokens.

Parsing comes right next to that step. We take the tokens and generate a Abstract Syntax Tree from it of the code. Then if you are making an interpreter you simply start at the leaf nodes and start collapsing the AST to run the code, a classic Tree Walking Interpreter or You could be making a compiler which is way more complex or a Just in Time compiler which are just legendary. ANYWAYS back to parsing.

Grammar Lesson

There is this one major difference between English and Java, every statement of the latter is deterministic. That is it always means the same thing. It won’t change what it does with change in context. And this level of precision has pushed us to develop grammars for languages. I learnt about from this book “Crafting Interpreters” you can check them out https://craftinginterpreters.com/

Back to Grammar. So, one of the most successful grammars for defining programming languages has been BNF. It will become obvious with a simple example

<sentence> ::= <noun> <verb> <object>
<noun> ::= Sam | Ali | Rohan
<verb> ::= ate | fought | saw
<object> ::= the robot | the food

We are just breaking down the structure and specifying what is a valid order for them. In the example, a sentence is made of noun verb and object. The noun further can be defined as being proper or not and the definitions can go till you have reached the simplest forms. More info about at Computerphile. But obviously BNF is very verbose so modern iterations like EBNF came over it to make it more readable, introducing more operators.

+ -> One or More
program: function+ 
Means a program is made with one or more functions
* -> Zero or More
function: statements*
Means A function is made with zero or more statements
? -> One or None
function: statement* return?
A function is made of one of more statements and it may or may not have a return

Lets right a (minimal) C grammar with it It’ll all make sense.

program :  function+;
function:functionheader'{''\n'functioncontent'}';
functionheader:datatype ' ' identifier '(' ')' ;
functioncontent:block+;
block:(statement+) | ifblock | whileblock ;
ifblock: 'if(' conditionalexpression '){\n' statement+ '}\n';
whileblock :'while(' conditionalexpression '){\n' statement+ '}\n';
conditionalexpression: conditionalexpone (conditionaljoin conditionalexpone)*;
conditionalexpone: (identifier conditionaloperation operand);
conditionaloperation: ' < ' | ' > ';
conditionaljoin: ' && ' | ' || ';
statement:assignment;
assignment: datatype ' ' identifier ' = ' expression ';\n';
expression: operand (operator (operand | '(' expression ')'))*;
operand: identifier | integer | float;
operator : ' + ' | ' - ' | ' * ' | ' / ';
datatype: 'int'|'float'|'double';
identifier: (A|a|B|b)+;
integer:(0|1|2|3|4|5)+;
whitespace: ' ';

Great now that we are on the same page, lets think

How do we generate from this grammar?

My first guess? Make it a graph I mean it literally looks like it is waiting to be converted to a graph! and that is exactly what I did in my first trial. Converting it to a simple graph and just walking it randomly. Just Connect what it needs to go next to and…

Then I was shot 50 times cuz that needed a lot of “state management” and was not a good idea. The problem was that if I am randomly walking, I would have to keep managing where I came from, and where to go from there. For example if I am in “Statement” node, I have no idea where on earth did I come from and what all came before. This would just get worse when we have to generate nested blocks and stuff so we totally could not do that.

To add to our troubles, the special operators like + would over-complicate it tenfold.

Plus we also had to code a recursion free solution since I wanted a more performant solution and easier on the RAM.

Wrapping every Node

If you look closely at the grammar, it has the special characters +,.* etc and then apart from that there are two main nodes,

functionheader:datatype ' ' identifier '(' ')' ;

Here, identifier will invoke the identifier: … statement And ‘{‘ will print something

We take them and wrap them up, with two empty nodes in out graph Lets ignore everything else right now and look into this structure. It makes applying the operators to the graphs super easy just see.

State of The Operators

How a whole statement would play out

Now, we can simply iterate through this mini graph randomly we have made for each statement and it would print things out perfectly

Now we make these mini graphs for each statement. A different one for each and can save them in a map just like:

All we need to do is figure out a way if a node references statement1 how do jump and track out last position and make it work.

The Stack

So now we have a map of graphs we need to iterate through it. For single statement it works, generating that specific sequence perfectly, however we still need a state management for cases like such:

The graph starts at A, then it needs to go to abra, and safely return back to A again. For this, we just use the trusty stack. A simple integer stack whenever you need to jump to a different statement, you will save the id of that node’s inter in the stack. Then the flow can switch to the other graph. And it can happen any number of times, since each jump is only filling a single integer in the stack, we can have practically endlessly deep references. Then when you hit the end node of any statement, you check the stack for what is the top value. You then shift back the control to the top value from the stack and pop that. Simple and elegant

Placing the Seed

This structure can generate code randomly at this point. But lets remember the original problem. It will work just fine with the OSDType interface you provide the grammar and get back a random script that too very fast. But what if you want to play multiplayer. Two players are to be given the same snippet to see who writes that the fastest. How do we build that!?

This is where Pseudo Random Numbers (PRN) help us. We set up a “Seed” initially which is something you would be familiar if you have played minecraft before.

When you first load a Minecraft world, it generates everything you see the biomes, the villages the mountains everything right there. It appears random but is not. All the random numbers needed in its generation are sourced from a single number, the seed. If like a huge integer code in minecraft. If you want the same world loaded into you as a friend or as a youtuber, you would get their world’s seed and enter that. While generating, now all the random numbers used in generation of the world will be same for everyone using the seed.

See: https://minecraft.wiki/w/World_generation

123 -> 432 -> 5435 -> 4123 -> 901 We start from a seed, here its 123 and genrate anay number of random numbers from it

Hence its called Pseudo Random Number Generation. These values are seemingly random, but they are sourced from a single Seed.

Similarly, when I say I am walking the graph inside Resrap, I am not randomly going. I am using PRNG to get values where to go. If the user sets no seed, it picks a random seed, if we get a seed while generation, then the snippet generated will always be identical.

Now think about it, in a multiplayer typing contest where there are a thousand players playing simultaneously say, the server only needs to forward on 64 bit integer to every player and it would automatically be converted to full on snippets on everyone’’s devices. No load on the server at all, and an amazing snappy experience for all the users.

Inventing New Operators

EBNF is amazing but the specific needs of a language generation needs some more operators in order to generate realistic snippets.

Making it truly infinite

We cannot specify how many tokens it will generate. Sure we can specify a max cap to generate after which we can stop the program, but its not guaranteed to reach that specific number, it can go through the graph and reach the end and check the stack and there would be nowhere to go. The program will just stop then. If you want a million tokens you literally cannot.

Hence introducing the infinity operator tadaa: program : functions^ This specifies that program is made of infinite functions. Hence, whenever we reach the end of a statement, and the stack is empty, then we jump to the function node. So now we can generate absurdly long pieces of code, in benchmarks I have gone well over 50 million tokens in a single run.

The Regex-er

We need random numbers and strings to be generated, and to make that less tiresome, I added a “syntax sugar”. Here you can define a simple regex of the code you want to generate and it will generate those. More work needs to be done to make it more adaptable, but it can generate simple identifiers like variable names and all.

identifier: [a-z];
integer:[0-9];

To make them sound less random, we also have a bias function placed which gives a bias to all the numbers like e get highest then other common characters. This allows us to make normal sounding random words. Would probably add support for random real words if that does not cost us too much performance.

Cumulative Frequency Distribution something something

The final one, and this is for the aesthetics of the code itself. In my code, I would prefer there be more normal block statements than if or while blocks in general . Or maybe there be a longer number of statements in a block before it exits.

For this we introduce the probability operator:

block:(statement+)<0.8> | ifblock<0.1> | whileblock<0.1> ;

Underneath, after we have generated the graph, we call a Normalize function, which normalizes all the probabilities to 1. Where there are no probabilities, we add them to ensure a common structure throughout. So each edge has a probability. Now for a node A which has 3 next options to go to. we make a Cumulative Frequency Distribution, which is just an array where we add keep adding the last sum of frequencies. It should make the last value 1.

With this, all we need to do while iterating is generate a random number with prng and normalize it such that it lies below 0 and 1 (evenly). Now all we have to do is iterate through this array and find the first number that is larger than out generated number.

If we get 0.8 for example, then we pick C because its CF index reads 0.9.

We can optimize it even further but altering the position of the elements such that the one with the probabilities are in descending order such that we will usually find the solution in the earlier tries. Something like:

So now 70 percent of the times we will get the value on the very first value of the structure. And that is how we over engineer Random Code Generation

— > Now we can generate infinitely nonsensical code very efficiently

Multi threading Without Safety

If you have one data structure, and many threads accessing it, you need to introduce locks to avoid two threads accessing at once which may lead to race conditions. There is a classic “Readers Writers Problem” in CS which is that what to do when many threads which only read and other threads which also write are accessing the same data structure.

A common solution to this is when the data structure needs to be written to, it blocks everything, every other reader, writer etc. Others have to wait till they acquire the lock before proceeding. However, if a reader gets the lock, every other reader is allowed to access the data structure, and all writers are blocked. This way we can get a good throughput and not lock everyone all the time. Readers can have this selective read only lock.

In our codebase however, there are two distinct phases, One when the graph is being built, and the other when we iterate through it. This means we can have a writer stage in single threaded mode, and then we can literally freeze the ds from any further changes so multiple threads can in parallel access it increasing the throughput substantially. Thanks to this, we can convert the code to walk the graph in parallel once the graph is generated. So we do not need to implement locks and it can safely do that without them.

Contributing

I have made this an actual Golang (and rust) library with docs published. You can find more about this project at https://resrap.osdc.dev/, it comes with documentation and a in browser tester running on a WASM engine.