Meh .. I wrote a full LR(1) parser generator for fun about 40 years ago (c.1982), back when it was considered impossibly impractical (the "dragon book" said so!

Meh .. I wrote a full LR(1) parser generator for fun about 40 years ago (c.1982), back when it was considered impossibly impractical (the "dragon book" said so!). Generating an LR(1) parser itself is simple enough using Knuth's algorithm - you're just building a large state machine and having to maintain sets of look-head tokens for each partially-parsed production rule in the states, which is why the resulting state machine becomes impractically large (at least for computers at that time). What made this possible back at that time was a paper by Professor Pager from the university of Hawaii that described how you could merge states, under certain compatibility conditions, during the cannonical Knuth parser (state machine) generation algorithm, which kept the size of the state machine under control. The parsers built by parser generators like mine, YACC, OP's Langcc, etc, are referred to as "table driven parsers" (to differentiate them from recursive descent parsers), but back in 1982 representing the state machine as an actual table wasn't very practical (too big) so rather than having a large sparse 2-D array indexed by state and token you'd normally represent each state as a list of actions instead. However, I found I could represent the tables an sparse 2-D array, but then compress the array to make it on manageable size. This was much preferable to using lists since access was much faster - just 3 array accesses to translate raw state, token indeces into compressed array indeces, then the actual lookup. To compress the sparse array I converted it into a graph coloring problem. I mapped the sparse array to a graph where each row of the array would map to a node in the graph, and any two nodes would be connected only if the corresponding sparse rows had a conflicting entry in any column. I then used a simple graph coloring heuristic to color the graph (goal - color graph with minimum number of colors, given constraint that connected nodes can't have the same color), then converted back to a compressed array by merging rows whose corresponding graph node's had the same color (hence no conflicts). I then repeated same procedure for the columns. The resulting parsers, when coupled with an optimized hand written tokenizer, was stunningly fast, even on the dog slow computers of the time, but sadly I never did anything with it - was just a fun side project done for my own education/amusement. The good old days. Get off my lawn.