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

RE: precedence and recursion

Expand Messages
  • mzukowski@xxx.xxx
    Look at the code that ANTLR generates and step through it as you are parsing. It s clear to me from this fragment that filter ends with zero or more LBRACKET
    Message 1 of 5 , Jul 19, 1999
      Look at the code that ANTLR generates and step through it as you are
      parsing. It's clear to me from this fragment that filter ends with zero or
      more LBRACKET query RBRACKET matches, followed by nothing else. I think you
      got your rules backwards, higher precedence rules come lower in the parse
      tree. Look at the calculator examples in the distribution.

      Really, the code will help you see how ()* is a loop and stuff. LL isn't as
      tricky as LR.

      Monty



      -----Original Message-----
      What I've come up with to handle this (with some help from Scott
      Stanchfield: thank you, Scott) is:

      query: filter | DASH ;

      tagQuery: TAG_NAME | LPAREN query RPAREN ;
      slashQuery: tagQuery ( SLASH query )* ;
      doubleSlashQuery: slashQuery ( DOUBLE_SLASH query )* ;
      filter: doubleSlashQuery ( LBRACKET query
      RBRACKET )* ;
    • Howard Katz
      Backwards you say? My goodness! :-) I have looked at the code and can see what it s doing very generally. I couldn t quite figure out tho how it got -that-
      Message 2 of 5 , Jul 19, 1999
        Backwards you say? My goodness! :-) I have looked at the code and can see what
        it's doing very generally. I couldn't quite figure out tho how it got -that-
        code from -my- rules. I'll go back and have a look at the calc example and see
        if that helps.

        Thanks,

        Howard

        mzukowski@... wrote:

        > From: mzukowski@...
        >
        > Look at the code that ANTLR generates and step through it as you are
        > parsing. It's clear to me from this fragment that filter ends with zero or
        > more LBRACKET query RBRACKET matches, followed by nothing else. I think you
        > got your rules backwards, higher precedence rules come lower in the parse
        > tree. Look at the calculator examples in the distribution.
        >
        > Really, the code will help you see how ()* is a loop and stuff. LL isn't as
        > tricky as LR.
        >
        > Monty
        >
        > -----Original Message-----
        > What I've come up with to handle this (with some help from Scott
        > Stanchfield: thank you, Scott) is:
        >
        > query: filter | DASH ;
        >
        > tagQuery: TAG_NAME | LPAREN query RPAREN ;
        > slashQuery: tagQuery ( SLASH query )* ;
        > doubleSlashQuery: slashQuery ( DOUBLE_SLASH query )* ;
        > filter: doubleSlashQuery ( LBRACKET query
        > RBRACKET )* ;
        >
        > --------------------------- ONElist Sponsor ----------------------------
        >
        > Get $20 off all MotherNature brand products!
        > <a href=" http://clickme.onelist.com/ad/mothernature1 ">Click Here</a>
        >
        > ------------------------------------------------------------------------
      • Lubos Vrba
        Hello, I take your grammar: query = tagQuery ... tagQuery = TAG_NAME ... Of course this is not LL(k) grammar. You must replace left recursion,
        Message 3 of 5 , Jul 19, 1999
          Hello, I take your grammar:

          query = tagQuery
          | DASH

          tagQuery = TAG_NAME
          | LPAREN query RPAREN
          | tagQuery SLASH query
          | tagQuery DOUBLE_SLASH query
          | tagQuery LBRACKET query RBRACKET

          Of course this is not LL(k) grammar. You must replace left recursion, this
          is the way:
          query = tagQuery
          | DASH

          tagQuery = TAG_NAME tagQuery1
          | LPARENT query RPARENT tagQuery1

          tagQuery1 = SLASH query tagQuery1
          | DOUBLE_SLASH query tagQuery1
          | LBRACKET query RBRACKET tagQuery1
          |

          I don't know if this is LL(1) grammar becouse I don't know FOLLOW(tagQuery1)

          (which must be different SLASH, DOUBLE_SLASH, LBRACKET) and FOLLOW(query)
          (which must different DASH, TAG_NAME, LPARENT)
          FOLLOW(xx) is the set of Lexical symbols that can be find in your grammar
          after the parsing token xx.

          Lubos Vrba
          Czech Republic

          Howard Katz wrote:

          > From: Howard Katz <howardk@...>
          >
          > Hi,
          >
          > I'm trying to implement a parser for Xtract, an XQL-like query language,
          > but I'm having a difficulty or two I hope someone can shed some light
          > on. I'm new to antlr and formal parsing in general, so here's what I've
          > come up with so far. Please bear with.
          >
          > A simplified form of the Xtract grammar is:
          >
          > query = tagQuery
          > | DASH
          >
          > tagQuery = TAG_NAME
          > | LPAREN query RPAREN
          > | tagQuery SLASH query
          > | tagQuery DOUBLE_SLASH query
          > | tagQuery LBRACKET query RBRACKET
          >
          > The order of the terms in the tagQuery production reflects their
          > precedence: TAG_NAME higher than (LPAREN query RPAREN) higher than
          > (tagQuery SLASH query) etc. Note the left recursion on tagQuery in the
          > last three terms.
          >
          > What I've come up with to handle this (with some help from Scott
          > Stanchfield: thank you, Scott) is:
          >
          > query: filter | DASH ;
          >
          > tagQuery: TAG_NAME | LPAREN query RPAREN ;
          > slashQuery: tagQuery ( SLASH query )* ;
          > doubleSlashQuery: slashQuery ( DOUBLE_SLASH query )* ;
          > filter: doubleSlashQuery ( LBRACKET query
          > RBRACKET )* ;
          >
          > This --almost-- works. The problem is that queries involving the filter
          > production don't resolve properly. To wit, queries of the form
          > "tag1[tag2]/tag3/tag4" terminate prematurely and never get beyond the
          > first closing RBRACKET. In other words, internally I'll get "tag1[tag2]"
          > reported, but that's it.
          >
          > Can anyone see what I'm doing wrong? I presume I'm stating the rules
          > incorrectly for the grammar I'm showing, but I can't see why or how to
          > correct it.
          >
          > Thanks,
          >
          > Howard
          >
          > --------------------------- ONElist Sponsor ----------------------------
          >
          > The planet's eCenter for health & well-being. PlanetRX.
          > <a href=" http://clickme.onelist.com/ad/planetrx1 ">Click Here</a>
          >
          > ------------------------------------------------------------------------
        • Lubos Vrba
          There was a small mistake, now it s all OK:
          Message 4 of 5 , Jul 19, 1999
            There was a small mistake, now it's all OK:

            Lubos Vrba wrote:

            > From: Lubos Vrba <lubos.vrba@...>
            >
            > Hello, I take your grammar:
            >
            > query = tagQuery
            > | DASH
            >
            > tagQuery = TAG_NAME
            > | LPAREN query RPAREN
            > | tagQuery SLASH query
            > | tagQuery DOUBLE_SLASH query
            > | tagQuery LBRACKET query RBRACKET
            >
            > Of course this is not LL(k) grammar. You must replace left recursion, this
            > is the way:
            > query = tagQuery
            > | DASH
            >
            > tagQuery = TAG_NAME tagQuery1
            > | LPARENT query RPARENT tagQuery1
            >
            > tagQuery1 = SLASH query tagQuery1
            > | DOUBLE_SLASH query tagQuery1
            > | LBRACKET query RBRACKET tagQuery1
            > |
            >
            > I don't know if this is LL(1) grammar becouse I don't know FOLLOW(tagQuery1)
            > (which must be different SLASH, DOUBLE_SLASH, LBRACKET) and
            > FOLLOW(xx) is the set of Lexical symbols that can be find in your grammar
            > after the parsing token xx.
            >
            > Lubos Vrba
            > Czech Republic
            >
            > Howard Katz wrote:
            >
            > > From: Howard Katz <howardk@...>
            > >
            > > Hi,
            > >
            > > I'm trying to implement a parser for Xtract, an XQL-like query language,
            > > but I'm having a difficulty or two I hope someone can shed some light
            > > on. I'm new to antlr and formal parsing in general, so here's what I've
            > > come up with so far. Please bear with.
            > >
            > > A simplified form of the Xtract grammar is:
            > >
            > > query = tagQuery
            > > | DASH
            > >
            > > tagQuery = TAG_NAME
            > > | LPAREN query RPAREN
            > > | tagQuery SLASH query
            > > | tagQuery DOUBLE_SLASH query
            > > | tagQuery LBRACKET query RBRACKET
            > >
            > > The order of the terms in the tagQuery production reflects their
            > > precedence: TAG_NAME higher than (LPAREN query RPAREN) higher than
            > > (tagQuery SLASH query) etc. Note the left recursion on tagQuery in the
            > > last three terms.
            > >
            > > What I've come up with to handle this (with some help from Scott
            > > Stanchfield: thank you, Scott) is:
            > >
            > > query: filter | DASH ;
            > >
            > > tagQuery: TAG_NAME | LPAREN query RPAREN ;
            > > slashQuery: tagQuery ( SLASH query )* ;
            > > doubleSlashQuery: slashQuery ( DOUBLE_SLASH query )* ;
            > > filter: doubleSlashQuery ( LBRACKET query
            > > RBRACKET )* ;
            > >
            > > This --almost-- works. The problem is that queries involving the filter
            > > production don't resolve properly. To wit, queries of the form
            > > "tag1[tag2]/tag3/tag4" terminate prematurely and never get beyond the
            > > first closing RBRACKET. In other words, internally I'll get "tag1[tag2]"
            > > reported, but that's it.
            > >
            > > Can anyone see what I'm doing wrong? I presume I'm stating the rules
            > > incorrectly for the grammar I'm showing, but I can't see why or how to
            > > correct it.
            > >
            > > Thanks,
            > >
            > > Howard
            > >
            > > --------------------------- ONElist Sponsor ----------------------------
            > >
            > > The planet's eCenter for health & well-being. PlanetRX.
            > > <a href=" http://clickme.onelist.com/ad/planetrx1 ">Click Here</a>
            > >
            > > ------------------------------------------------------------------------
            >
            > --------------------------- ONElist Sponsor ----------------------------
            >
            > The planet's eCenter for health & well-being. PlanetRX.
            > <a href=" http://clickme.onelist.com/ad/planetrx1 ">Click Here</a>
            >
            > ------------------------------------------------------------------------
          Your message has been successfully submitted and would be delivered to recipients shortly.