Recognizing the Unrecognizable

It's obvious right? It's, it's umm, hmm, take the (( and put down the * and then.
Okay, this actually makes no sense. "Arr", you say to yourself, "I know why their smirking, because while I can recognise all the valid tokens in the language, I still cannot recognise all the valid programs that can be written." You are all over it!

Hello Context Free Grammars (CFG), the older more powerful sibling to the much loved Regular Expressions. The reality is, there is about a 3% chance that CFGs could be explained in this one paragraph. So, instead below are a list of great resources that in total cover them in detail:

• Neso Academy [CFG Overview: 7:51m]
• The Coding Train [Into to Session 7: 14:29m]
• Ravindrababu Ravula [Intro to Lexical Analyser & Grammars: 19:50m]
• Stanford Online [Compiler Course Unit 3]
• Matt Might Article [The language of languages]

Assuming you stayed up all night learning all about CFGs, your manager is now asking why you haven't started running calculations yet on the new PDP-11s that you were so excited about? You can't tell them the truth, and so you let them that you are first double checking someone else's work. That should be enough to get them off your back for now! Okay, where were we again? That's right, CFGs. Working with nothing but intution you write up your first attempt at the grammar.

Notice how we get different parse trees! In other words, the grammar is ambiguous. That doesn't sound too good. But, wait a second minute, both parse trees when evaluated equaled 6 (thank you kindly associativity). So, look how about this, can we just promise never to use the rightmost derivation and instead always use the leftmost which gives us (1 + 2) + 3? Almost.

I know what you are thinking, "maybe I should just learn to be effective with postfix notation and abanden this whole idea of building acalculator language". Hang in there, you'll be getting your hands dirty in no time. Actually, speaking of getting our hands dirty, how are we going to actually implement the grammar? Like, it's great and all having a nice notation to work with, but we need to realise the grammar using a parsing algorithm. LL(1) parsing is one such algorithm. In a mouthfull, an LL(1) parser is a top down parser that reads the input left-to-right, using leftmost derivations to apply production rules, with at most 1 token of lookahead (don't worry if not a single word of that sentence made sense).

Knowing little about LL(1) parsers, you decide to consult your coworker again. They advise you that using LL(1) parser is a great choice, phew! But, before you can run back to your desk they qualify their statement by saying it's a great choice as long as the grammar does not have any left recursion. Left recursion? That doesn't ring a bell. You look at your grammar, trying to find signs of something that may be left recursion. Ah ha! You think you've found the culprit.

The answer probably goes along the line of, well I could see that the string contained three instances of the token + and so once I had three instances I knew to stop producing more and apply E -> INTLITERAL to each E. Without even realising, you've used a LL(k) parsing algo with k tokens of lookahead, where k is the number of tokens in the string. In other words, the parser could look at the whole string! Unfortunately, our parser doesn't have this sweet luxury but instead has to live it's life constrained to only 1 token of lookahead. It's important to note there are two well known ways to implement LL(k) parsers. The first is a recursive descent parser, and the second is a table driven parser.

The problem with left recursion is that for a recursive descent parser it will recurse forever, never terminating, while for a table driven parser we will end up with multiiple entries for a given cell and not know which one to apply. How do we get ourselves out of this bleek situation? Left recursion elimination. As if it was going to be called anything else haha. You decide in your next lunch break that you will read up on it!

After what I can only describe as a successful lunch break, you return to your desk with a revised (and hopefully final) version of the grammar.

Turns out there is a special type of top down parsers that we want to use to maximise the effeciency of the parsing algorithm. Remember, we need to run this on a PDP-11! It is called a predictaive top down parser, which just means that it doesn't require backtracking. The key thing to realise is that without a predictive parser, we essentially need to try all productions, and then choose the one that gives us the longest match (if any). If we can compute the first, follow and select sets for the grammar then we will have everything needed to implement the parser! Ravindrababu Ravula does a fantastic job walking us through that process over here on their youtube channel.

After being enlightened on how to compute the sets, you sit down and decide to have a crack at the final edition of the grammar. You can feel the implementation of the parser only minutes away. I should add, select sets are simply a convenience set thats wraps around first and follow sets to make building the parsing table or recursive decent parser more straightforward. You'll see the definition in the stub file for the Parser! One long coffee later, and there they are below in all their glory!

First(eps) = { eps }
First(+)   = { + }
First(-)   = { - }
First(/)   = { / }
First(*)   = { * }
First("(") = { ( }
First(")") = { ) }
First(INTLITERAL) = { INTLITERAL }
						

First(E)  = First(T)
          = { (, INTLITERAL }

First(E') = First(+) U First(-) U First(eps)
          = { +, -, eps }

First(T)  = First(F)
          = { (, INTLITERAL }

First(T') = First(*) U First(/) U First(eps)
          = { *, /, eps }

First(F)  = First("(") U First(INTLITERAL)
          = { (, INTLITERAL }
						

Follow(E)  = { $ } U First(")")
		
Follow(E') = Follow(E)
           = { $, ) }

Follow(T)  = First(E') U Follow(E') U Follow(E)
           = First(E') U Follow(E') // by Follow(E') = Follow(E)
           = { +, -, eps, $, ) }
		
Follow(T') = Follow(T)
           = { +, -, eps, $, ) }
			
Follow(F)  = First(T') U Follow(T') U Follow(T)
           = First(T') U Follow(T') // by Follow(T') = Follow(T)
           = { *, /, eps, +, -, $, ) }
						

Select(E -> TE')   = First(TE') = First(T)
                   = { (, INTLITERAL }

Select(E' -> +TE') = First(+TE') = First(+)
                   = { + }
Select(E' -> -TE') = First(-TE) = First(-)
                   = { - }
Select(E' -> eps)  = First(eps) - {eps} U Follow(E')
                   = { $, ) } 

Select(T -> FT')   = First(FT') = First(F)
                   = { (, INTLITERAL }

Select(T' -> *FT') = First(*FT') = First(*)
                   = { * }
Select(T' -> /FT') = First(/FT') = First(/)
                   = { / }
Select(T' -> eps)  = First(eps) - {eps} U Follow(T')
                   = { +, -, $, ) }

Select(F -> (E))   = First((E)) = First("(")
                   = { ( }
Select(F -> INTLITERAL)
                   = First(INTLITERAL)
                   = { INTLITERAL }
						

To complete this stage, you need to implement a [predictive] recursive descent LL(1) parser. A template scanner has been defined in compiler/Parser/Parser.js. To test your implementation as you go along, run: $ yarn run test:Recognizer Don't forget to checkout the handy tool a little further down to help visualise what the parse tree looks like for a given program. When a production is applied, for example E => TE' that corresponds to a node called E that has two children T and E' (as is the case with the root node below). An interesting side note, if you change the stream of characters to be just the program 1, it requires 9 nodes in total in the tree!