Parsing regular expressions can be a real chicken-or-the-egg scenario, many algorithms for compiling regular expressions to NFA or DFA involves converting the expression to an AST. This is the job of a parser of course, which as you may know tend to in
When Donald Knuth published "On the translation of language from left to right" in 1965 he introduced the concept of LR parsers to the world. LR(k) parsers are a family of bottom-up parsers that perform a rightmost derivation in reverse. At th
One of the major selling points of LR parsing is the ability to write expression grammars with a higher degree of ambiguity than would otherwise be allowed. When designing an expression grammar there are ways to encode the operators precedence and asso
Over the past few post's I've introduced data structures for representing Context Free Grammars from BNF, algorithms for computing First sets of those CFGs, and algorithms for computing the follow sets to accompany them. With that, we have everything n
Having previously discussed the data structures needed for representing a context free grammar as well as a method for computing the 'First' set, in todays post I will cover constructing the 'Follow' set. The follow set, as it's name would imply, is th