Sign up ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

A central difficulty here is coping with ambiguous grammars in a user-friendly way. Restricting the grammar to be unambiguous is not an option: that's the way the language is — the idea is that writers prefer to omit parentheses when they are not necessary to avoid ambiguity. As long as an expression isn't ambiguous, I need to parse it, and if it isn't, I need to reject it.

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?

(In the project where I needed that (a while back), I used CYK, which wasn't too hard to implement and worked adequately for my input sizes but didn't produce very nice errors.)

share|cite|improve this question
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 just answered below. It is a bit awkward to answer to a modification of an old question that already has a well received answer. Obviously I am not supposed to answer in a similar way, but users will read both answers as if they were answering the same question. – babou Jan 2 at 14:24
Do you actually expect an error message for ambiguous input, if a user writes x+y+z. – babou Jan 2 at 14:25
@babou I didn't change the question, I only added clarifications requested in comments (now deleted). For the tiny grammar given here, I haven't specified associativity for +, so x+y+z is indeed ambiguous hence erroneous. – Gilles Jan 2 at 14:28
Well, it is your last sentence, just added, even if between parentheses. You seem to say: I finally did it with CYK, but it is no longer adequate for some reasons. And I wonder what the precise reasons may be ... You are, now, the person with the most experience with your kind of problem and the solution you use, so one would expect more information from you if further answers are to be given. – babou Jan 2 at 14:48

2 Answers 2

up vote 13 down vote accepted

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.

share|cite|improve this answer
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… 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 '14 at 14:21

There are many general context-free parser that can parse ambiguous sentences (according to an ambiguous grammar). They come under various names, notably dynamic-programming or chart parsers. The best known one, and next to simplest, is probably the CYK parser that you have been using. That generality is needed since you have to handle multiple parses and may not know till the end whether you are dealing with an ambiguity or not.

From what you say, I would think that CYK is not such a bad choice. You probably do not have much to gain by adding predictiveness (LL or LR), and it may actually have a cost by discriminating computations that should be merged rather than discriminated (especially in the LR case). They may also have a corresponding cost in the size of the parse forest that is produced (which may have a role in ambiguity errors). Actually, while I am not sure how to compare formally the adequacy of the more sophisticated algorithms, I do know that CYK does give good computation sharing.

Now, I do not believe there is much literature on general CF parsers for ambiguous grammars that should only accept unambiguous input. I do not recall seeing any, probably because even for technical documents, or even programming languages, syntactic ambiguity is acceptable as long as it can be resolved by other means (e.g. ambiguity in ADA expressions).

I am actually wondering why you want to change your algorithm, rather than stick to what you have. That might help me understand what kind of change could best help you. Is it a speed issue, is it the representation of parses, or is it the error detection and recovery?

The best way to represent multiple parses is with a shared forest, which is simply a context-free grammar that generates only your input, but with exactly all the same parse trees as the DSL grammar. That makes it very easy to understand and process. For more details, I suggest you look at this answer I gave on the linguistic site. I do understand that you are not interested in getting a parse forest, but a proper representation of parse forest can help you give better messages as to what the ambiguity problen is. It could also help you decide that the ambiguity does not matter in some cases (associativity) if you wantd to do that.

You mention the processing time constraints of your DSL grammar, but give no hint as to its size (which does not means that I could answer with figures it you did).

Some error processing can be integrated in these general CF algorithms in simple ways. But I would need to understand what kind of error processing you expect to be more affirmative. Would you have some examples.

I am a bit ill at ease to say more, because I do not understand what are really your motivations and constraints. On the basis of what you say, I would stick to CYK (and I do know the other algorithms and some of their properties).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.