# Parsing arbitrary context-free grammars, mostly short snippets

I want to parse user-defined domain specific languages. These languages are typically close to mathematical notations (I am not parsing a natural language). Users define their DSL in a BNF notation, like this:

expr ::= LiteralInteger
| ( expr )
| expr + expr
| expr * expr


Input like 1 + ( 2 * 3 ) must be accepted, while input like 1 + must be rejected as incorrect, and input like 1 + 2 * 3 must be rejected as ambiguous.

My parser must work on any context-free grammar, even ambiguous ones, and must accept all unambiguous input. I need the parse tree for all accepted input. For invalid or ambiguous input, I ideally want good error messages, but to start with I'll take what I can get.

I will typically invoke the parser on relatively short inputs, with the occasional longer input. So the asymptotically faster algorithm may not be the best choice. I would like to optimize for a distribution of around 80% inputs less than 20 symbols long, 19% between 20 and 50 symbols, and 1% rare longer inputs. Speed for invalid inputs is not a major concern. Furthermore, I expect a modification of the DSL around every 1000 to 100000 inputs; I can spend a couple of seconds preprocessing my grammar, not a couple of minutes.

What parsing algorithm(s) should I investigate, given my typical input sizes? Should error reporting be a factor in my selection, or should I concentrate on parsing unambiguous inputs and possibly run a completely separate, slower parser to provide error feedback?

-
It sure sounds like you are looking for a jack of all trades. –  Raphael Mar 12 '12 at 11:41
Especially good error reports seem hard to achieve. You might have more than one local change that leads to an accepted input in case of ambiguous grammars. –  Raphael Mar 12 '12 at 13:13
I don't think this is reasonable. Part ot the idea of the syntax is to give some overall structure. The reason simple techniques like recursive descent are so sucessful in practice is that such LL(1) grammars announce what is to come by just the first token, which seems to be how we are wired to understand language. More powerful techniques, like LR(1), are required mostly because of arithmetic expressions, and early research showed that the inmense majority of those are very short in any case. Please do not use operators without at least the customary precedences! [...; from deleted answer] –  vonbrand Jan 24 '13 at 1:22
You seem to be under the delusion that I am parsing a programming language. Think mathematical notations. –  Gilles Jan 24 '13 at 11:50
@Gilles, No delusion. What is valid for a programming language is true for mathematical notation written as text. Trust me, I've written a fair amount of mathematics in troff and now LaTeX, and fought with maxima for symbolic computation. Very few have been what you'd call complete programs, just fragments. –  vonbrand Jan 24 '13 at 12:38

Probably the ideal algorithm for your needs is Generalized LL parsing, or GLL. This is a very new algorithm (the paper was published in 2010). In a way, it is the Earley algorithm augmented with a graph structured stack (GSS), and using LL(1) lookahead.

The algorithm is quite similar to plain old LL(1), except that it doesn't reject grammars if they are not LL(1): it just tries out all possible LL(1) parses. It uses a directed graph for every point in the parse, which means that if a parse state is encountered that has been dealt with before, it simply merges these two vertices. This makes it suitable for even left-recursive grammars, unlike LL. For exact details on its inner workings, read the paper (it's quite a readable paper, though the label soup requires some perseverance).

The algorithm has a number of clear advantages relevant to your needs over the other general parsing algorithms (that I know of). Firstly, implementation is very easy: I think only Earley is easier to implement. Secondly, performance is quite good: in fact, it becomes just as fast as LL(1) on grammars that are LL(1). Thirdly, recovering the parse is quite easy, and checking whether there is more than one possible parse is as well.

The main advantage GLL has is that it is based on LL(1) and is therefore very easy to understand and debug, when implementing, when designing grammars as well as when parsing inputs. Furthermore, it also makes error handling easier: you know exactly where possible parses stranded and how they might have continued. You can easily give the possible parses at the point of the error and, say, the last 3 points where parses stranded. You might instead opt to try to recover from the error, and mark the production that the parse that got the furthest was working on as 'complete' for that parse, and see if parsing can continue after that (say someone forgot a parenthesis). You could even do that for, say, the 5 parses that got the furthest.

The only downside to the algorithm is that it's new, which means there are no well-established implementations readily available. This may not be a problem to you - I've implemented the algorithm myself, and it was quite easy to do.

-
Nice to learn something new. When I needed this (a few years ago, in a project that I'd like to revive some day), I used CYK, largely because it was the first algorithm I found. How does GLL handle ambiguous inputs? The article doesn't seem to discuss this, but I've only skimmed it. –  Gilles Mar 12 '12 at 17:51
@Gilles: it builds up a graph structured stack, and all the (potentially exponentially many) parses are compactly represented in this graph, similar to how GLR works. If I recall correctly, the paper mentioned in cstheory.stackexchange.com/questions/7374/… deals with this. –  Alex ten Brink Mar 12 '12 at 18:19
@Gilles This 2010 parser seems to have to be programmed by hand from the grammar, not too adequate if you have several languages, or if you often modify the language. Techniques for automatic generation from the grammar of a general parser following any chosen strategy (LL, LR or others) and producing a forest of all parses have been known for about 40 years. However there are hidden issues regarding complexity and organization of the graph representing parses. The number of parses may be worse than exponential: infinite. Error recovery can use more systematic, parser independent techniques. –  babou Feb 10 at 14:21