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

RE: Disturbing behaviour with infinite recursion .

Expand Messages
  • mzukowski@xxx.xxx
    ... In the above comlete parser, as soon as root doesn t see a CC it will stop. ... In this you never match anything, you never consume input, you will loop
    Message 1 of 10 , Oct 20, 1999
    • 0 Attachment
      > -----Original Message-----
      > From: Michael T. Richter [mailto:mtr@...]
      > Sent: Wednesday, October 20, 1999 10:40 AM
      > To: antlr-interest@onelist.com
      > Subject: [antlr-interest] Disturbing behaviour with infinite
      > recursion.
      >
      >
      > From: "Michael T. Richter" <mtr@...>
      >
      > The following grammar compiles fine with ANTLR:
      >
      > class RootParser extends Parser;
      >
      > root
      > : ( a )+
      > ;
      >
      > a
      > : b
      > ;
      >
      > b
      > : CC a
      > ;

      In the above comlete parser, as soon as root doesn't see a CC it will stop.

      > The following grammar does not:
      >
      > root
      > : ( a )+
      > ;
      >
      > a
      > : b
      > ;
      >
      > b
      > : a
      > ;
      >
      > error in test.g: line(12), infinite recursion to rule a
      > from rule b
      > error in test.g: line(8), infinite recursion to rule a
      > from rule a
      > error in test.g: line(4), infinite recursion to rule a
      > from rule root

      In this you never match anything, you never consume input, you will loop
      infinitely!

      > To my undoubtedly naive eyes, both grammars recurse
      > infinitely. But it
      > gets weirder. My ASN.1 grammar has several infinite recursion errors
      > reported. (I also still have those %#@&* nondeterminisms,
      > but I'll leave
      > those be for now with only a comment that knowing what the
      > #@$%%@#$* FOLLOW
      > set for a given portion WAS would be a really nice bit of
      > information from
      > ANTLR....) The problem is that the offending rules look more like the
      > first grammar (the one that passed) than the second (the one
      > that failed).

      There is a -debug or somesuch option to antlr which will dump the generated
      code full of FOLLOW sets. Also try my patch I posted earlier, I used it to
      track down many nondeterminisms in my GCC grammar.

      > Are there any specific tips available on how to actually
      > track down what an
      > ANTLR error message means?

      Ask here, or look at the source and documentation. There's even a FAQ at
      antlr.org now.

      Monty
    • Michael T. Richter
      ... -debug invokes ParseView (which is fine by me). But it will only do so if you get a clean ANTLR run. The problem is that my (non-infinitely-recursive)
      Message 2 of 10 , Oct 20, 1999
      • 0 Attachment
        At 01:45 PM 10/20/99 , you wrote:
        >There is a -debug or somesuch option to antlr which will dump the generated
        >code full of FOLLOW sets. Also try my patch I posted earlier, I used it to
        >track down many nondeterminisms in my GCC grammar.

        -debug invokes ParseView (which is fine by me). But it will only do so if
        you get a clean ANTLR run. The problem is that my
        (non-infinitely-recursive) infinite recursions are causing ANTLR to dump
        with errors. Right now I'm ignoring the whole nondeterminisms until I can
        actually get a successful (if not accurate) run.

        >> Are there any specific tips available on how to actually
        >> track down what an
        >> ANTLR error message means?

        >Ask here, or look at the source and documentation. There's even a FAQ at
        >antlr.org now.

        I'm doing some digging there, but there doesn't seem to be a "here's how to
        track down your (inevitable) errors" article. I guess that's the curse of
        using a free tool, eh? You don't have a vendor to hunt down and whine at. :-)

        I'm getting the feeling, though, that the hand-rolled ASN.1 option is going
        to be struck down as impractical.

        --
        Michael T. Richter <mtr@...> http://www.igs.net/~mtr/
        PGP Key: http://www.igs.net/~mtr/pgp-key.html
        PGP Fingerprint: 40D1 33E0 F70B 6BB5 8353 4669 B4CC DD09 04ED 4FE8
      • schen@xxxxxxxxxx.xxxx
        Hi Michael, everyone, ... You must ruthlessly track down and eliminate all indeterminacy warnings and then things will work out. This is basically the only
        Message 3 of 10 , Oct 20, 1999
        • 0 Attachment
          Hi Michael, everyone,

          On Wed, 20 Oct 1999, Michael T. Richter wrote:

          > I'm doing some digging there, but there doesn't seem to be a "here's how
          > to track down your (inevitable) errors" article. I guess that's the
          > curse of using a free tool, eh? You don't have a vendor to hunt down
          > and whine at. :-)

          You must ruthlessly track down and eliminate all indeterminacy warnings
          and then things will work out. This is basically the only way I've found
          to do things. After that you can use -debug and track down the rules.

          You said you worked with PCCTS before, but here's a short summary to jog
          your memory again. Basically, this boils down to rewriting all left
          recursive rules. For example, consider a parser with multiply
          expressions, written in pseudo BNF:

          multExpr ::= unaryExpr
          | multExpr '*' unaryExpr

          In ANTLR, this won't work because of the left recursion. You have to
          express it as something like this:

          multExpr : unaryExpr ( TIMES unaryExpr )* ;

          But not only this, you have to watch out for follow sets (as discussed
          previously). For example, take another pseudo BNF:

          locationPath ::= relativeLocationPath
          | absoluteLocationPath

          relativeLocationPath ::= step
          | relativeLocationPath '/' step

          absoluteLocationPath ::= '/' relativeLocationPath?

          First I got rid of the left recursion in relativeLocationPath:

          relativeLocationPath: step ( SLASH step )* ;

          Then to get absoluteLocationPath and locationPath working, I had to rely
          on syntatic predicates. This tells antlr which rule to actually invoke by
          looking ahead:

          locationPath : ( SLASH )=> absoluteLocationPath
          | relativeLocationPath
          ;

          absoluteLocationPath: ( SLASH relativeLocationPath )=>
          SLASH relativeLocationPath
          | SLASH
          ;

          (There's probably better ways to do this if the other old antlr hands on
          this list can come up with something)

          > I'm getting the feeling, though, that the hand-rolled ASN.1 option is going
          > to be struck down as impractical.

          If you're dying for a Java ASN.1 parser, try:
          http://www.cryptix.org/products/asn1/index.html

          It is however in beta and might need patching to work for you. Sadly,
          they use a JavaCC grammar.

          . . . Sean.
        • mzukowski@xxx.xxx
          ... Ack, it s -diagnostic! Monty
          Message 4 of 10 , Oct 20, 1999
          • 0 Attachment
            > -----Original Message-----
            > From: Michael T. Richter [mailto:mtr@...]
            > Sent: Wednesday, October 20, 1999 11:11 AM
            > To: antlr-interest@onelist.com
            > Subject: RE: [antlr-interest] Disturbing behaviour with infinite
            > recursion .
            >
            >
            > From: "Michael T. Richter" <mtr@...>
            >
            > At 01:45 PM 10/20/99 , you wrote:
            > >There is a -debug or somesuch option to antlr which will
            > dump the generated
            > >code full of FOLLOW sets. Also try my patch I posted
            > earlier, I used it to
            > >track down many nondeterminisms in my GCC grammar.
            >
            > -debug invokes ParseView (which is fine by me). But it will
            > only do so if
            > you get a clean ANTLR run. The problem is that my
            > (non-infinitely-recursive) infinite recursions are causing
            > ANTLR to dump
            > with errors. Right now I'm ignoring the whole
            > nondeterminisms until I can
            > actually get a successful (if not accurate) run.

            Ack, it's -diagnostic!

            Monty
          • Michael T. Richter
            ... It s also not shown on the command summary when I invoke java antlr.Tool by itself.... :-( But it certainly gives me a wild amount of information.
            Message 5 of 10 , Oct 20, 1999
            • 0 Attachment
              At 02:37 PM 10/20/99 , you wrote:
              >Ack, it's -diagnostic!

              It's also not shown on the command summary when I invoke java antlr.Tool by
              itself.... :-(

              But it certainly gives me a wild amount of information. Hopefully I can
              sort it out before the universe ends. :-)

              --
              Michael T. Richter <mtr@...> http://www.igs.net/~mtr/
              PGP Key: http://www.igs.net/~mtr/pgp-key.html
              PGP Fingerprint: 40D1 33E0 F70B 6BB5 8353 4669 B4CC DD09 04ED 4FE8
            • Michael T. Richter
              ... I was doing this on the fly as I entered the ASN.1 grammar. But it is the follow sets which seem to be killing me right now. ... Predicates are my weakest
              Message 6 of 10 , Oct 20, 1999
              • 0 Attachment
                At 02:30 PM 10/20/99 , you wrote:
                >You said you worked with PCCTS before, but here's a short summary to jog
                >your memory again. Basically, this boils down to rewriting all left
                >recursive rules. For example, consider a parser with multiply
                >expressions, written in pseudo BNF:

                >multExpr ::= unaryExpr
                > | multExpr '*' unaryExpr

                >In ANTLR, this won't work because of the left recursion. You have to
                >express it as something like this:

                >multExpr : unaryExpr ( TIMES unaryExpr )* ;

                I was doing this on the fly as I entered the ASN.1 grammar. But it is the
                follow sets which seem to be killing me right now.

                >But not only this, you have to watch out for follow sets (as discussed
                >previously). For example, take another pseudo BNF:

                >locationPath ::= relativeLocationPath
                > | absoluteLocationPath

                >relativeLocationPath ::= step
                > | relativeLocationPath '/' step

                >absoluteLocationPath ::= '/' relativeLocationPath?

                >First I got rid of the left recursion in relativeLocationPath:

                >relativeLocationPath: step ( SLASH step )* ;

                >Then to get absoluteLocationPath and locationPath working, I had to rely
                >on syntatic predicates. This tells antlr which rule to actually invoke by
                >looking ahead:

                >locationPath : ( SLASH )=> absoluteLocationPath
                > | relativeLocationPath
                > ;

                >absoluteLocationPath: ( SLASH relativeLocationPath )=>
                > SLASH relativeLocationPath
                > | SLASH
                > ;

                Predicates are my weakest point in understanding the new stuff. The last
                ANTLR version I actually worked with was 1.06 which was before Ter
                introduced predicates. (I think the predicates were a 1.1 feature.) I
                understand at a theoretical level what they do, but at the practical level
                I'm still pretty much a clueless newbie with them.

                >If you're dying for a Java ASN.1 parser, try:
                >http://www.cryptix.org/products/asn1/index.html

                I'm not. That's the problem. I need a C++ one. Without the $100k per-set
                license fees that OSS and its ilk want to charge. And that's flexible
                enough for me to plug in any kind of back-end I want.

                --
                Michael T. Richter <mtr@...> http://www.igs.net/~mtr/
                PGP Key: http://www.igs.net/~mtr/pgp-key.html
                PGP Fingerprint: 40D1 33E0 F70B 6BB5 8353 4669 B4CC DD09 04ED 4FE8
              • schen@xxxxxxxxxx.xxxx
                Hi Michael, everyone, ... See if you can understand my example. You use syntatic predicates basically to disambiguate non-determinacies and help antlr
                Message 7 of 10 , Oct 20, 1999
                • 0 Attachment
                  Hi Michael, everyone,

                  On Wed, 20 Oct 1999, Michael T. Richter wrote:

                  > Predicates are my weakest point in understanding the new stuff. The last
                  > ANTLR version I actually worked with was 1.06 which was before Ter
                  > introduced predicates. (I think the predicates were a 1.1 feature.) I
                  > understand at a theoretical level what they do, but at the practical level
                  > I'm still pretty much a clueless newbie with them.

                  See if you can understand my example. You use syntatic predicates
                  basically to disambiguate non-determinacies and help antlr determine which
                  rule to actually use.

                  > >If you're dying for a Java ASN.1 parser, try:
                  > >http://www.cryptix.org/products/asn1/index.html
                  >
                  > I'm not. That's the problem. I need a C++ one. Without the $100k per-set
                  > license fees that OSS and its ilk want to charge. And that's flexible
                  > enough for me to plug in any kind of back-end I want.

                  Ok, try snacc instead, based on a yacc/lex parser:
                  http://www.fokus.gmd.de/ovma/freeware/snacc/entry.html

                  It however is ASN.1:1990 only. Don't tell me you need ASN.1:1994 =)

                  . . . Sean.
                • schen@xxxxxxxxxx.xxxx
                  Hi Michael, ... You might as well see if you can locate a couple rules that stand by themselves and post it for us to take a crack at. . . . Sean.
                  Message 8 of 10 , Oct 20, 1999
                  • 0 Attachment
                    Hi Michael,

                    On Wed, 20 Oct 1999, Michael T. Richter wrote:

                    > I was doing this on the fly as I entered the ASN.1 grammar. But it is the
                    > follow sets which seem to be killing me right now.

                    You might as well see if you can locate a couple rules that stand by
                    themselves and post it for us to take a crack at.

                    . . . Sean.
                  • Michael T. Richter
                    ... Snacc is what I m drying to displace. ... I d like to have ITU-T Rec. X.68(0-3) (1997 E). I don t want ANY or ANY OF. I don t want macros. These are
                    Message 9 of 10 , Oct 20, 1999
                    • 0 Attachment
                      At 03:15 PM 10/20/99 , you wrote:
                      >Ok, try snacc instead, based on a yacc/lex parser:
                      >http://www.fokus.gmd.de/ovma/freeware/snacc/entry.html

                      Snacc is what I'm drying to displace.

                      >It however is ASN.1:1990 only. Don't tell me you need ASN.1:1994 =)

                      I'd like to have ITU-T Rec. X.68(0-3) (1997 E). I don't want ANY or ANY
                      OF. I don't want macros. These are dinosaurs which should never have
                      lived and were correctly retroactively aborted.

                      --
                      Michael T. Richter <mtr@...> http://www.igs.net/~mtr/
                      PGP Key: http://www.igs.net/~mtr/pgp-key.html
                      PGP Fingerprint: 40D1 33E0 F70B 6BB5 8353 4669 B4CC DD09 04ED 4FE8
                    • Michael T. Richter
                      ... HAHAHAHAHAHAHAHAHAHAHAHHAHAHAHA!!!! ASN.1 rules which stand by themselves! What a wonderfully comedic concept! ... This grammar is a mess. It s pure BNF
                      Message 10 of 10 , Oct 20, 1999
                      • 0 Attachment
                        At 03:16 PM 10/20/99 , you wrote:
                        >> I was doing this on the fly as I entered the ASN.1 grammar. But it is the
                        >> follow sets which seem to be killing me right now.

                        > You might as well see if you can locate a couple rules that stand by
                        > themselves and post it for us to take a crack at.

                        HAHAHAHAHAHAHAHAHAHAHAHHAHAHAHA!!!!

                        ASN.1 rules which stand by themselves! What a wonderfully comedic concept!

                        :-)

                        This grammar is a mess. It's pure BNF written by people who never bothered
                        to machine-check the productions. Except for X.681-3, of course. Those
                        have some weirdo BNF extensions which almost, but not quite, make the
                        grammar readable.

                        --
                        Michael T. Richter <mtr@...> http://www.igs.net/~mtr/
                        PGP Key: http://www.igs.net/~mtr/pgp-key.html
                        PGP Fingerprint: 40D1 33E0 F70B 6BB5 8353 4669 B4CC DD09 04ED 4FE8
                      Your message has been successfully submitted and would be delivered to recipients shortly.