# 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 at 1:22 You seem to be under the delusion that I am parsing a programming language. Think mathematical notations. – Gilles♦ Jan 24 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 at 12:38
show 2 more comments