Loading ...
Sorry, an error occurred while loading the content.

Not More Infinite Recursion

Expand Messages
  • Jason
    Hello, First off, I lied; it is more infinite recursion. I ve made quite a bit of progress with the converion of my grammar from YACC to ANTLR. There are
    Message 1 of 2 , Feb 2, 2004
    • 0 Attachment
      Hello,

      First off, I lied; it is more infinite recursion.

      I've made quite a bit of progress with the converion
      of my grammar from YACC to ANTLR. There are still
      pieces of the grammar though in which rules
      'cyclically' reference other rules thereby generating
      infinite recursions. I'm having difficulty figuring
      out how to rewrite these sections to eliminate the
      left recursions. Here is a slightly pared down
      example:

      //BEGIN EXAMPLE
      dimentia:
      membrane B A
      |
      A C membrane D
      |
      gentle B A
      |
      A C gentle D
      ;

      gentle:
      G
      |
      dimentia B E C
      |
      membrane B F C
      |
      F C dimentia H
      |
      F C membrane H
      |
      membrane B E C
      |
      E C dimentia H
      |
      E C membrane H
      ;

      membrane:
      I
      |
      J
      |
      gentle B K
      |
      membrane L K
      ;
      //END EXAMPLE

      I've tried refactoring this every which way but I
      can't seem to arrive at a solution. For what it's
      worth BISON consumes it without issuing any
      shift/reduce warnings. I'm not looking so much for a
      solution to this particular grammar (though I wouldn't
      complain if someone provided one) as I am looking for
      a general strategy to solve this kind of problem. I
      apologize for rambling. Any pointers anyone could
      provide would be greatly apprciated.

      -jason

      __________________________________
      Do you Yahoo!?
      Yahoo! SiteBuilder - Free web site building tool. Try it!
      http://webhosting.yahoo.com/ps/sb/
    • Chris Poirier
      Hi all, ... I m very new to ANTRL myself (new, as in, a week), and I don t expect to be writing my first grammar until later this week. Prior to this, I ve
      Message 2 of 2 , Feb 2, 2004
      • 0 Attachment
        Hi all,

        Jason wrote:
        > First off, I lied; it is more infinite recursion.
        >
        > I've made quite a bit of progress with the converion
        > of my grammar from YACC to ANTLR. There are still
        > pieces of the grammar though in which rules
        > 'cyclically' reference other rules thereby generating
        > infinite recursions. I'm having difficulty figuring
        > out how to rewrite these sections to eliminate the
        > left recursions. Here is a slightly pared down
        > example:

        I'm very new to ANTRL myself (new, as in, a week), and I don't expect to
        be writing my first grammar until later this week. Prior to this, I've
        written only ad hoc parsers, usually of fairly simple languages.

        I've been looking at Jason's example for a while, and I'm not seeing
        infinite recursion (recursion, but not infinite), but I think that's
        because I'm always considering the right end. Is Jason's grammar
        problem one where LR(k) will work and LL(k) won't?

        Thanks,
        Chris.


        > //BEGIN EXAMPLE
        > dimentia:
        > membrane B A
        > |
        > A C membrane D
        > |
        > gentle B A
        > |
        > A C gentle D
        > ;
        >
        > gentle:
        > G
        > |
        > dimentia B E C
        > |
        > membrane B F C
        > |
        > F C dimentia H
        > |
        > F C membrane H
        > |
        > membrane B E C
        > |
        > E C dimentia H
        > |
        > E C membrane H
        > ;
        >
        > membrane:
        > I
        > |
        > J
        > |
        > gentle B K
        > |
        > membrane L K
        > ;
        > //END EXAMPLE
      Your message has been successfully submitted and would be delivered to recipients shortly.