Hacker News new | ask | show | jobs
by thesz 3764 days ago
Parser combinators for lazy streams can be written as recursive descent and perform as, more or less, generalized LR parsing (exploring all tree branches "simultaneously").

http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf

What is more, these combinators can express context-sensitive grammars: https://www.cs.york.ac.uk/plasma/publications/pdf/partialpar... (page 5).

And, by tweaking combinators, you can arrive to the wonders of stream processing parsing without (mostly) space leaks: http://www.cse.chalmers.se/edu/year/2015/course/afp/Papers/p...

It is easy to add syntax error position reporting, also it is easy to add syntax error corrections. All this can be done in under a day.

For me it offers good things from both worlds - declarative specification of parser generators and easy modifications from "parse damn thing by hand".

I actually encountered one case where that approach shines incommensurably: supporting old languages like VHDL. VHDL fits every parser formalism almost without seams but still has one place where you cannot do things either efficiently or elegantly: character literals and attributes. 'a' is a character literal, a'a is an invocation of attribute a on the object a. The ambiguity is in the lexing level, needing feedback from parsing level. Usual parsing tools cannot do that good enough, with parsing combinators it is trivial.