Grammar ambiguity solving with semantic LookAhead

[Redondant]

Hi,

I'm having some tricky problem with part of a grammar.
It concerns a metadata production, which can appear almost everywhere in the grammar, hence being checked by several syntactic lookaheads.
Here is how it looks like :

void Meta () :
{ /* omitted */ }
{
  < BEGINMETA >
  (IRIConstant())?
  (Term() "[" /* omitted */ "]")?
  < ENDMETA >
}

void Term() :
{ /* omitted */ }
{
  (Meta())?
  (
    Const()
  |  ... // omitted
  )
}

void Const() :
{ /* omitted */ }
{
    < STRING_VALUE > "^^" < ANY_DATATYPE >
  | < QNAME >
  | ... // omitted
}

void IRIConstant() :
{ /* omitted */ }
{
    < STRING_VALUE > "^^" < SPECIFIC_DATATYPE >
  | < QNAME >
  | ... // omitted
}

The problem is into the Meta() production, when the parser finds something like a QNAME token, it cannot decide whether it comes from the optional IRIConstant or the Term() -> Const() from the second optional block.
Basically I added a syntactic lookahead which solves the problem at parse-time, however when the Meta() production is analyzed by lookaheads, the nested LA is ignored, so the IRIConst() always returns "lookahead succeed", even while the validated token was in fact a Term() -> Const() from the second optional block of Meta(). I tried to use a semantic lookahead, but I can't get it working, moreover this really looks awkward.
I'm not a language theory expert thus I was unable to solve the problem at a higher level. Could anyone point me to the right direction ?
Regards,

CF

[Mazas Marc]

Hi

It seems to me that even for a human there is nothing in the grammar extract you've shown that can tell whether the QNAME token should come from the IRIConstant or the Const production.

So you need to explain this rule (and then you'll probably have to modify your productions) or give examples.

 

Marc Mazas

 

---

De : Redondant [mailto:redondant@...]
Envoyé : vendredi 21 août 2009 16:41
À : users@...
Objet : [JavaCC] Grammar ambiguity solving with semantic LookAhead

Hi,

I'm having some tricky problem with part of a grammar.
It concerns a metadata production, which can appear almost everywhere in the grammar, hence being checked by several syntactic lookaheads.
Here is how it looks like :

void Meta () :
{ /* omitted */ }
{
  < BEGINMETA >
  (IRIConstant())?
  (Term() "[" /* omitted */ "]")?
  < ENDMETA >
}

void Term() :
{ /* omitted */ }
{
  (Meta())?
  (
    Const()
  |  ... // omitted
  )
}

void Const() :
{ /* omitted */ }
{
    < STRING_VALUE > "^^" < ANY_DATATYPE >
  | < QNAME >
  | ... // omitted
}

void IRIConstant() :
{ /* omitted */ }
{
    < STRING_VALUE > "^^" < SPECIFIC_DATATYPE >
  | < QNAME >
  | ... // omitted
}

The problem is into the Meta() production, when the parser finds something like a QNAME token, it cannot decide whether it comes from the optional IRIConstant or the Term() -> Const() from the second optional block.
Basically I added a syntactic lookahead which solves the problem at parse-time, however when the Meta() production is analyzed by lookaheads, the nested LA is ignored, so the IRIConst() always returns "lookahead succeed", even while the validated token was in fact a Term() -> Const() from the second optional block of Meta(). I tried to use a semantic lookahead, but I can't get it working, moreover this really looks awkward.
I'm not a language theory expert thus I was unable to solve the problem at a higher level. Could anyone point me to the right direction ?
Regards,

CF

[Redondant]

Finally I was able to bypass the problem by expressing the grammar in a closer form to BNF than EBNF (i.e. expanding the (...)? productions with concrete choice points), and keeping some syntactic LAs.

Thanks anyway for your help !

Regards

CF

Marc Mazas wrote : 

Hi It seems to me that even for a human there is nothing in the grammar extract you've shown that can tell whether the QNAME token should come from the IRIConstant or the Const production. So you need to explain this rule (and then you'll probably have to modify your productions) or give examples. 

Marc Mazas

Hi,

I'm having some tricky problem with part of a grammar.

It concerns a metadata production, which can appear almost everywhere in the grammar, hence being checked by several syntactic lookaheads.

Here is how it looks like :

void Meta () :

{ /* omitted */ }

{

  < BEGINMETA >

  (IRIConstant())?

  (Term() "[" /* omitted */ "]")?

  < ENDMETA >

}

void Term() :

{ /* omitted */ }

{

  (Meta())?

  (

    Const()

    | ... // omitted

  )

}

void Const() :

{ /* omitted */ }

{

    < STRING_VALUE > "^^" < ANY_DATATYPE >

  | < QNAME >

  | ... // omitted

}

void IRIConstant() :

{ /* omitted */ }

{

    < STRING_VALUE > "^^" < SPECIFIC_DATATYPE >

  | < QNAME >

  | ... // omitted

}

The problem is into the Meta() production, when the parser finds something like a QNAME token, it cannot decide whether it comes from the optional IRIConstant or the Term() -> Const() from the second optional block.

Basically I added a syntactic lookahead which solves the problem at parse-time, however when the Meta() production is analyzed by lookaheads, the nested LA is ignored, so the IRIConst() always returns "lookahead succeed", even while the validated token was in fact a Term() -> Const() from the second optional block of Meta(). I tried to use a semantic lookahead, but I can't get it working, moreover this really looks awkward.

I'm not a language theory expert thus I was unable to solve the problem at a higher level. Could anyone point me to the right direction ?

Regards,

CF