is there a parser generator capable of generating a parser that can parse this: S → 'x' S 'x' | 'x'

For a while now I am intrigued by开发者_C百科 the fact that ANTLR isn't capable of parsing the following context free grammar rule: S → 'x' S 'x' | 'x'.

It didn't seem that complex to me.

For all I know, ANTLR is the most powerful LL parser available. Are there any other kind of parser generators (LR or other) that are capable of generating a parser for this?

gr,

Coen

I don't think your grammar is LL(n) or LALR(n) or LR(n) for any n. Proof: Fix any n. Your input stream starts with n x characters, followed by another one. At this point, without any further look-ahead, do you need to go up or down?

Since the standard parser generators only work on languages in one of those classes (and many only for small values of n), it is not surprising that you don't find one that handles your input. You might want to reconsider if your grammar really needs to look the way it does; for the reduced example you gave, you could just as well have S → 'x' 'x' S | 'x', for example.

In Antlr, you need to add a syntactic predicate to resolve the ambiguity, like this:

grammar fred;

sentence : ( 'x' 'x' 'x' ) => 'x' sentence 'x'
         |                    'x'
         ;

This shouldn't, I think, require more than 1 additional token of lookahead. The semantic predicate says "if you see an 'x' followed by another 'x', try the first alternative.

Antlr 3.3/Antlrworks 1.4.2 is happy with it:

Another option is to refactor your grammar to eliminate the alternative that introduces the ambiguity:

grammar fred;

start    : sentence
         ;

sentence : 'x'  'x'('x' 'x')*  'x'
         |      'x'
         ;

This, I believe, will give you the same parse tree (or close) as your original grammar.