127 karma · joined May 20, 2014
Full context-free grammar are supported by "generalised parsing". The older stuff is GLR by Tomita, Early parsing, the CYK algorithm. The newer stuff based on Tomita is the particular rabbit hole I stuck with for a while. I read about SGLR which eliminates lexers, GLL which is GLR but based on the LL algorithm. The people who do GLL research also did improvements on SGLR with improved speed on right-nulled grammars. Then there is the SGLR improvements with disambiguation filters, automatic derivation of error recovery with island grammars, etc. The disambiguation filters include a kind of negation, making the current implementation of SGLR for SDF capable to parsing Boolean Grammars, which are a superset of context-free grammars.
Anyway, there's more than context-free grammars. Definitely look into data-dependant grammars! It's able to define a lot of interesting things, like network protocol formats where you parse the length of the payload, then based on that length you know how much to interpret as the payload before you read the footer of the message. And you write all of that in a more declarative way and get a nice parser generated from it.
There is so much more, but I think I should to stop now :)
[1] https://github.com/evancz/elm-architecture-tutorial/ [2] http://elm-lang.org/
Another space you can look for interesting things (not necessarily optimising compilation) is the compilation of functional programming languages. They usually take a slightly different approach compared to imperative languages, though there's clearly a lot of overlap. I really enjoy reading in an old book called The Implementation of Functional Programming Languages from 1987, which is available online: http://research.microsoft.com/en-us/um/people/simonpj/papers...
[0]: https://groups.google.com/d/topic/elm-discuss/NJCZFIYxshE/di...
[1]: https://groups.google.com/d/topic/elm-discuss/ZJ6lkfPimW8/di...
I think eventually there might be a performance problem with scaling, and yes each components seems to have a bit of boilerplate. But overall the pattern is very reusable and predictable, so if it really becomes the standard (instead of the experiment that it is now!) there could be compiler support for less boilerplate/ better performance.
For now I haven't seen enough people with actual experience using this architecture to really buy any complaints. I've seen more unintuitive things come around in Elm that seem weird (perhaps even wrong) at first, but by really trying it out, I've found that more of those things work really well!