CODEWITHSUNDEEP
parsingantlrgenerator
Coen
Coen

Reputation: 106

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 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

Upvotes: 3

Views: 199

Answers (2)

Nicholas Carey
Nicholas Carey

Reputation: 74355

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: enter image description here

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'
         ;

enter image description here

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

Upvotes: 2

Christopher Creutzig
Christopher Creutzig

Reputation: 8774

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.

Upvotes: 5

Related Questions