GLR is here

Two wrong approaches with optimization later and GLR parser is ready for download.

In my case the last missing step was upgrading LALR parser to MLR — I was following great explanation given by David R. Tribble (of course all errors in implementations are mine). One thing that caused my confusion was the term “lookahead” — it seems a lot of people using it for two different things, and so I introduced “after lookahead” and “next lookahead” terms to clarify which is which. The first one is used when building a parser to denote terminals which can show up after entire production is consumed (so it is irrelevant how much of the production is processed). The “next lookahead” is used when parsing — it denotes terminals which can show next in input stream (for reduce states of productions those two sets are identical).

Besides that implementing MLR parser was easier than LALR one — you don’t have to compute follow sets, there is less work with NFA and DFA.

As for optimization I went with pre-computing first sets for entire chunks of the symbols present in productions and with stamping NFA states whenever their after-lookaheads get updated. It allowed me to get to the point where lexer is again the bottleneck of entire processing.

I don’t know how about you, but I think I deserved Grand Imperial Porter. I will get another one after implementing multi-regex.

Advertisement

A reminder from the closed source world

Now and then I get stern reminder to stick with open source when it comes to base system. I have to replicate the system, it refuses to do so, I have to install the updates, it cannot find root partition, and so on. 16 years ago I switched from Microsoft Windows to SUSE Linux and I found it is plagued with bugs as well. The difference is with Linux I can boot the computer from the pendrive, I can run console, I can actually diagnose the problem — same story with programs. And when I need something badly I can modify the source code, compile it and voilà I have my custom tool.

Around week ago I finished GLR parser as part of NLT suite. The only annoyance is it is too slow to publish it, so I need to profile it. And then Visual Studio profiler stopped working, I switched to PerfView and instead usual 3% of broken stacks I got something more like 80%. Just my luck — go figure the bottleneck now.

And still, I am grateful for this refreshing experience, it is good to know what closed source programs stands for — reinstall everything or buy newer versions and pray the problem will go away. Right…

Don’t mix deferred execution with optional outcome

I prefer using yield when returning IEnumerable because code looks really clean — storing the output manually loses this nice look, not mentioning extra wrapper method.

But the look can be misleading when the language design leaves a hole — and I fell into this trap. I used yield in method that returns not some crucial data, but simply a report about what was not computed. You can read it, display it, or ignore it, your call. The problem is yield unlike cached result, uses deferred execution. And deferment is based on usage of… the outcome. So if you ignore it (and C# compiler does not make a peep about it), it will be not executed at all.

The lesson for C# devs is this — if it is OK to ignore the outcome of the method (as in my case, just a summary of computation), do not use yield. Go with storing the output inside the method.