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

Predicates are too restricted

Expand Messages
  • Michael Schmitt
    Hello everybody, I have been playing aroung with ANTLR for several days now and even though I am quite satisfied with the tool in general, I think that the
    Message 1 of 5 , Oct 31, 1999
      Hello everybody,

      I have been playing aroung with ANTLR for several days now and even
      though I am quite satisfied with the tool in general, I think that the
      usage of syntactic and semantic predicates is too restricted.

      Consider the following grammar:

      a : b c ;
      b : d | e ;
      c : d | e ; // yet another rule using b and c
      d : f ID1 something ;
      e : f ID2 something ;
      f : ( T )*

      Obviously it is not possible to parse this grammar with a finite
      lookahead. Instead you have to introduce syntactic predicates that guide
      parsing. But where would you like to add these predicates? What I would
      like to do is:

      a : b c ;
      b : d | e ;
      c : d | e ; // yet another rule using b and c
      d : ( f ID1 ) => f ID1 something ;
      e : ( f ID1 ) => f ID2 something ;
      f : ( T )*

      But unfortunately, it is not possible to do so with ANTLR. Instead you
      have to add the predicates to the alternatives listed in rule "b" and
      "e":

      b : ( f ID1 ) => d | ( f ID2 ) => e ;
      c : ( f ID1 ) => d | ( f ID2 ) => e ;

      This approach has two big disadvantages: The right-side content of rules
      is distributed all over the grammar! I would not like to see any details
      about d and e within rule "b" and "c". Moreover, you need a lot of more
      syntactic predicates (twice as much in the example above)! I need to
      write a parser for a language whose standardized grammar includes a lot
      of rules of type "b" and "c". You can imagine the beauty of the grammar!

      Are there any reasons (except for implementation ones) why it is not
      possible to specify syntactic predicates in the way described above? If
      I remember correclty, Metamata Parse (formerly known as "JavaCC"
      formerly known as "Jack") supports such descriptions.

      Kind regards,

      Michael
    • parrt@xxxxx.xxxx
      ... Sure will. I didn t put it in initially mainly because people didn t seem to understand them in PCCTS ;) You smart guys will have to wait a bit ;) Ter
      Message 2 of 5 , Nov 1, 1999
        mzukowski@... writes:
        >From: mzukowski@...
        >
        >You've just described "hoisting" of predicates which is a feature of PCCTS
        >which has not made it to antlr 2.x yet, but enough people are beating up Ter
        >about it that it will happen someday...

        Sure will. I didn't put it in initially mainly because people didn't
        seem to understand them in PCCTS ;) You smart guys will have to wait
        a bit ;)

        Ter
      • mzukowski@xxx.xxx
        You ve just described hoisting of predicates which is a feature of PCCTS which has not made it to antlr 2.x yet, but enough people are beating up Ter about
        Message 3 of 5 , Nov 1, 1999
          You've just described "hoisting" of predicates which is a feature of PCCTS
          which has not made it to antlr 2.x yet, but enough people are beating up Ter
          about it that it will happen someday...

          Monty

          > -----Original Message-----
          > From: Michael Schmitt [mailto:schmitt@...-luebeck.de]
          > Sent: Sunday, October 31, 1999 8:11 AM
          > To: ANTLR
          > Subject: [antlr-interest] Predicates are too restricted
          >
          >
          > From: Michael Schmitt <schmitt@...-luebeck.de>
          >
          > Hello everybody,
          >
          > I have been playing aroung with ANTLR for several days now and even
          > though I am quite satisfied with the tool in general, I think that the
          > usage of syntactic and semantic predicates is too restricted.
          >
          > Consider the following grammar:
          >
          > a : b c ;
          > b : d | e ;
          > c : d | e ; // yet another rule using b and c
          > d : f ID1 something ;
          > e : f ID2 something ;
          > f : ( T )*
          >
          > Obviously it is not possible to parse this grammar with a finite
          > lookahead. Instead you have to introduce syntactic predicates
          > that guide
          > parsing. But where would you like to add these predicates?
          > What I would
          > like to do is:
          >
          > a : b c ;
          > b : d | e ;
          > c : d | e ; // yet another rule using b and c
          > d : ( f ID1 ) => f ID1 something ;
          > e : ( f ID1 ) => f ID2 something ;
          > f : ( T )*
          >
          > But unfortunately, it is not possible to do so with ANTLR. Instead you
          > have to add the predicates to the alternatives listed in rule "b" and
          > "e":
          >
          > b : ( f ID1 ) => d | ( f ID2 ) => e ;
          > c : ( f ID1 ) => d | ( f ID2 ) => e ;
          >
          > This approach has two big disadvantages: The right-side
          > content of rules
          > is distributed all over the grammar! I would not like to see
          > any details
          > about d and e within rule "b" and "c". Moreover, you need a
          > lot of more
          > syntactic predicates (twice as much in the example above)! I need to
          > write a parser for a language whose standardized grammar
          > includes a lot
          > of rules of type "b" and "c". You can imagine the beauty of
          > the grammar!
          >
          > Are there any reasons (except for implementation ones) why it is not
          > possible to specify syntactic predicates in the way described
          > above? If
          > I remember correclty, Metamata Parse (formerly known as "JavaCC"
          > formerly known as "Jack") supports such descriptions.
          >
          > Kind regards,
          >
          > Michael
          >
          > --------------------------- ONElist Sponsor
          > ----------------------------
          >
          > Thinking about putting your business on the Web?
          > MindSpring Biz has helped over 100,000 businesses get their .com.
          > Join MindSpring Biz and save $50!
          > <a href=" http://clickme.onelist.com/ad/mindspring3 ">Click Here</a>
          >
          > --------------------------------------------------------------
          > ----------
          >
        • parrt@xxxxx.xxxx
          ... Right on. Yeah, we need them back. As Tom Moog pointed out today that part of the problem (in understanding them) was that they...um...didn t quite work
          Message 4 of 5 , Nov 1, 1999
            Geoff Leyland writes:
            >From: Geoff Leyland <geoff.leyland@...>
            >
            >I hate to beat up the guy that wrote antlr, since he's obviously a lot
            >more useful than all of us that didn't, but I've run into predicate
            >hoisting problems fairly often (tho' I didn't know it had a name), or at
            >least had to spread my grammar around the file (which seems to be a
            >symptom?), so, sorry, Ter, consider yourself, just a little, beat up.

            Right on. Yeah, we need them back. As Tom Moog pointed out today
            that part of the problem (in understanding them) was that
            they...um...didn't quite work right all the time in PCCTS ;)

            Ter :)
          • Geoff Leyland
            I hate to beat up the guy that wrote antlr, since he s obviously a lot more useful than all of us that didn t, but I ve run into predicate hoisting problems
            Message 5 of 5 , Nov 1, 1999
              I hate to beat up the guy that wrote antlr, since he's obviously a lot
              more useful than all of us that didn't, but I've run into predicate
              hoisting problems fairly often (tho' I didn't know it had a name), or at
              least had to spread my grammar around the file (which seems to be a
              symptom?), so, sorry, Ter, consider yourself, just a little, beat up.

              Cheers, and as always, thanks,
              Geoff

              mzukowski@... wrote:
              >
              > From: mzukowski@...
              >
              > You've just described "hoisting" of predicates which is a feature of PCCTS
              > which has not made it to antlr 2.x yet, but enough people are beating up Ter
              > about it that it will happen someday...
              >
              > Monty

              --
              Geoff Leyland
              Laboratoire d'energetique industrielle
              LENI-DGM-EPFL, CH-1015 Lausanne, Switzerland
              Phone: +41 (21) 693 3505 Fax: +41 (21) 693 35 02
            Your message has been successfully submitted and would be delivered to recipients shortly.