PARSER for RUBY

Discussion in 'Ruby' started by puellula@gmail.com, Oct 28, 2005.

  1. Guest

    Hi,
    can you help me?
    I have to write a parser for Ruby. I had think to use the parser
    generator ANTLR.
    I have find Ruby Grammar, but I have problem with ANTLR for "infinite
    recursion". I have cancel left recursion but I have the same problem :(

    Please, can you help me?
    Now I'm trying with a simple grammar to find where is the problem. The
    simple grammar is:


    // PARSER
    class RubyParser extends Parser;
    options { buildAST=true; }


    program : compstmt;
    compstmt : stmt;
    stmt : stmt1 expr
    | ;
    stmt1 : stmt IF
    | stmt WHILE
    | stmt UNLESS
    | stmt UNTIL
    | ;
    expr : ;


    // LEXER
    class RubyLexer extends Lexer;
    IF : "if";
    WHILE : "while";
    UNLESS : "unless";
    UNTIL : "until";


    I have write this on a file provaLexerParser.g
    On the command line I have write:


    antlr provaLexerParser.g


    and the result is:


    java -classpath "C:\antlr\275\lib\antlr.jar;" antlr.Tool
    provaLexerParser.g
    ANTLR Parser Generator Version 2.7.5 (20050128) 1989-2005 jGuru.com

    provaLexerParser.g:7:19: infinite recursion to rule stmt1 from rule
    stmt
    provaLexerParser.g:9:19: infinite recursion to rule stmt1 from rule
    stmt1
    provaLexerParser.g:10:19: infinite recursion to rule stmt1 from rule
    stmt1
    provaLexerParser.g:11:19: infinite recursion to rule stmt1 from rule
    stmt1
    provaLexerParser.g:12:19: infinite recursion to rule stmt1 from rule
    stmt1
    provaLexerParser.g:7:19: infinite recursion to rule stmt1 from rule
    stmt
    provaLexerParser.g:7: warning:nondeterminism between alts 1 and 2 of
    block upon
    provaLexerParser.g:7: k==1:EOF,IF,WHILE,UNLESS,UNTIL
    Exiting due to errors.


    Plase, I need help.


    Thank you for all!


    bye,
    puellula
     
    , Oct 28, 2005
    #1
    1. Advertising

  2. Hugh Sasse Guest

    On Fri, 28 Oct 2005, wrote:

    > Hi,
    > can you help me?
    > I have to write a parser for Ruby. I had think to use the parser
    > generator ANTLR.
    > I have find Ruby Grammar, but I have problem with ANTLR for "infinite
    > recursion". I have cancel left recursion but I have the same problem :(


    You've not removed all left recursion.
    [...]
    > simple grammar is:
    >
    >
    > // PARSER
    > class RubyParser extends Parser;
    > options { buildAST=true; }
    >
    >
    > program : compstmt;
    > compstmt : stmt;
    > stmt : stmt1 expr
    > | ;
    > stmt1 : stmt IF

    [...]
    > | ;
    > expr : ;

    [...]

    Just take the if example:

    stmt = stmt1 expr
    = stmt IF expr
    = stmt1 IF expr
    = stmt IF IF expr
    = stmt1 IF IF IF expr

    I don't know antlr well, but maybe
    > stmt : stmt IF expr
    > | stmt WHILE expr
    > | stmt UNLESS expr
    > | ;


    might work better?
     
    Hugh Sasse, Oct 28, 2005
    #2
    1. Advertising

  3. Guest

    Hi Hugh Sasse and thank you for you message :)
    Well... I had write on my file .g this, how you told to me:

    // PARSER
    class RubyParser extends Parser;
    options { buildAST=true; }

    program : compstmt;
    compstmt : stmt;

    stmt : stmt IF expr
    | stmt WHILE expr
    | stmt UNLESS expr
    | ;

    expr : ;

    // LEXER
    class RubyLexer extends Lexer;
    IF : "if";
    WHILE : "while";
    UNLESS : "unless";
    UNTIL : "until";


    but there is left recursione now! What do you think about? You can see
    that there is left recursion!

    The output is:

    C:\Personal\Università\Materiale Esami\Teconologie dei Linguaggi di
    Programmazio
    ne + Lab>antlr provaLexerParser.g
    java -classpath "C:\antlr\275\lib\antlr.jar;" antlr.Tool
    provaLexerParser.g
    ANTLR Parser Generator Version 2.7.5 (20050128) 1989-2005 jGuru.com
    provaLexerParser.g:8:17: infinite recursion to rule stmt from rule stmt
    provaLexerParser.g:9:17: infinite recursion to rule stmt from rule stmt
    provaLexerParser.g:10:17: infinite recursion to rule stmt from rule
    stmt
    provaLexerParser.g:8:17: infinite recursion to rule stmt from rule stmt
    provaLexerParser.g:9:17: infinite recursion to rule stmt from rule stmt
    provaLexerParser.g:10:17: infinite recursion to rule stmt from rule
    stmt
    provaLexerParser.g:8: warning:nondeterminism between alts 1 and 4 of
    block upon
    provaLexerParser.g:8: k==1:IF
    provaLexerParser.g:8: warning:nondeterminism between alts 2 and 4 of
    block upon
    provaLexerParser.g:8: k==1:WHILE
    provaLexerParser.g:8: warning:nondeterminism between alts 3 and 4 of
    block upon
    provaLexerParser.g:8: k==1:UNLESS
    Exiting due to errors.


    I think the problem finish when I know how I can write on ANTLR the
    empty string. I try to rappresent this with " ", when I write "| ;". I
    hope you undestand what I would tell to you.

    Thank you so much for your message
    bye,
    puellula
     
    , Oct 28, 2005
    #3
  4. Hugh Sasse Guest

    ---559023410-585771160-1130502801=:19167
    Content-Type: MULTIPART/MIXED; BOUNDARY="-559023410-585771160-1130502801=:19167"

    This message is in MIME format. The first part should be readable text,
    while the remaining parts are likely unreadable without MIME-aware tools.

    ---559023410-585771160-1130502801=:19167
    Content-Type: TEXT/PLAIN; charset=X-UNKNOWN
    Content-Transfer-Encoding: QUOTED-PRINTABLE

    On Fri, 28 Oct 2005, wrote:

    > Hi Hugh Sasse and thank you for you message :)
    > Well... I had write on my file .g this, how you told to me:
    >=20
    > // PARSER
    > class RubyParser extends Parser;
    > options { buildAST=3Dtrue; }
    >=20
    > program=09=09: compstmt;
    > compstmt=09: stmt;
    >=20
    > stmt : stmt IF expr
    > | stmt WHILE expr
    > | stmt UNLESS expr
    > | ;
    >=20
    > expr=09: ;
    >=20
    > // LEXER
    > class RubyLexer extends Lexer;
    > IF : "if";
    > WHILE : "while";
    > UNLESS : "unless";
    > UNTIL : "until";
    >=20
    >=20
    > but there is left recursione now! What do you think about? You can see
    > that there is left recursion!
    >=20
    > The output is:
    >=20
    > C:\Personal\Universit=E0\Materiale Esami\Teconologie dei Linguaggi di
    > Programmazio
    > ne + Lab>antlr provaLexerParser.g
    > java -classpath "C:\antlr\275\lib\antlr.jar;" antlr.Tool
    > provaLexerParser.g
    > ANTLR Parser Generator Version 2.7.5 (20050128) 1989-2005 jGuru.com
    > provaLexerParser.g:8:17: infinite recursion to rule stmt from rule stmt
    > provaLexerParser.g:9:17: infinite recursion to rule stmt from rule stmt
    > provaLexerParser.g:10:17: infinite recursion to rule stmt from rule
    > stmt

    [...]
    > provaLexerParser.g:8: warning:nondeterminism between alts 1 and 4 of
    > block upon
    > provaLexerParser.g:8: k=3D=3D1:IF
    > provaLexerParser.g:8: warning:nondeterminism between alts 2 and 4 of
    > block upon
    > provaLexerParser.g:8: k=3D=3D1:WHILE
    > provaLexerParser.g:8: warning:nondeterminism between alts 3 and 4 of
    > block upon
    > provaLexerParser.g:8: k=3D=3D1:UNLESS
    > Exiting due to errors.


    Right. I'm not sure what to do about this. You can have=20

    do_this if condition1 unless condition2=20

    in ruby. What about:

    program=09=09: compstmt;
    compstmt=09: stmt;
    =20
    stmt : conditionalbody IF expr
    | conditionalbody WHILE expr
    | conditionalbody UNLESS expr
    | conditionalbody // a way out=20
    | ;
    =20
    conditionalbody : stmt
    | simplestatement;
    ;

    //simplestatement is a way out of the stmt definition loop
    simplestatement : returnstatement
    ; // other statemtents go here

    returnstatement : RETURN expr
    ;

    expr=09: ;

    =20
    // LEXER
    class RubyLexer extends Lexer;
    IF : "if";
    WHILE : "while";
    UNLESS : "unless";
    UNTIL : "until";
    RETURN : "return";
    =20
    >=20
    > I think the problem finish when I know how I can write on ANTLR the
    > empty string. I try to rappresent this with " ", when I write "| ;". I
    > hope you undestand what I would tell to you.


    Well, I'm not familiar with ANTLR. Actually, I read about PCCTS but
    not ANTLR. I find this stuff pretty difficult to debug.
    >=20
    > Thank you so much for your message
    > bye,
    > puellula


    Good luck,
    Hugh
    ---559023410-585771160-1130502801=:19167--
    ---559023410-585771160-1130502801=:19167--
     
    Hugh Sasse, Oct 28, 2005
    #4
  5. Eric Mahurin Guest

    --- wrote:

    > Hi,
    > can you help me?
    > I have to write a parser for Ruby. I had think to use the
    > parser
    > generator ANTLR.
    > I have find Ruby Grammar, but I have problem with ANTLR for
    > "infinite
    > recursion". I have cancel left recursion but I have the same
    > problem :(


    Hey, we are doing the same thing! I'm using my grammar project
    to implement a ruby lexer/parser:

    http://rubyforge.org/projects/grammar/

    I'm starting with what's in parse.y (from the 1.8 ruby source).
    This is for yacc (an LALR parser). My parser is also an LL
    parser like ANTLR so I have to do the same LR -> LL conversion.
    I used ANTLR about a year ago and as a matter of fact one of
    my contributions is in the ANTLR distribution - C preprocessor
    lexer. Almost any feature you find in ANTLR will be in
    Grammar.

    Anybody know of something that can convert from LR to LL
    grammar? Hasn't anybody made something like that for ANTLR?

    Right now, my focus is only the ruby lexer and managing the
    lexer states (some of it is determined by the parser). I think
    making the lexer (hand coded C in parse.y) is much harder than
    converting from LR to LL (a fairly mechanical process) for the
    parser.


    __________________________________________________
    Do You Yahoo!?
    Tired of spam? Yahoo! Mail has the best spam protection around=20
    http://mail.yahoo.com=20
     
    Eric Mahurin, Oct 28, 2005
    #5
  6. Guest

    Hugh, thank you very much for your help but I have the same problem! :(
    For me it has been very important your help.
    Thank you so much!

    If I will resolve this problem I will tell you how, ok? :)

    Thank you very much

    bye,
    Sara
     
    , Oct 28, 2005
    #6
  7. Guest

    Eric, thank you for your message!
    I had see the link you sent to me, but I have to write a parser in Java
    for Ruby, I haven't write a parser in Ruby.
    I had think to use ANTLR like parser generator. What do you think
    about?
    I have problem with "infinite recursion" but I don't know what I write
    not correct when I cancel left recursion. I think the problem is how I
    have to write empty string in ANTLR.
    Plase, if you can help me you are welcome! :)
    Thank you very much.

    bye,
    puellula
     
    , Oct 28, 2005
    #7
  8. Hugh Sasse Guest

    On Fri, 28 Oct 2005, wrote:

    > Hugh, thank you very much for your help but I have the same problem! :(


    Then I'm stuck. This is what I find: they are difficult to
    debug.

    Hopefully someone who lives and breathes this stuff can help out,
    but is there an ANTLR mailing list? Google says:

    http://www.antlr.org:8080/mailman/listinfo

    but I can't reach it.

    > For me it has been very important your help.
    > Thank you so much!


    I can't take credit for getting you no further forward!
    >
    > If I will resolve this problem I will tell you how, ok? :)


    thank you.
    >
    > Thank you very much
    >
    > bye,
    > Sara

    Hugh
     
    Hugh Sasse, Oct 28, 2005
    #8
  9. Guest

    Hugh, thank you for your interest!

    bye,
    puellula
     
    , Oct 28, 2005
    #9
  10. Eric Mahurin Guest

    --- wrote:

    > Eric, thank you for your message!
    > I had see the link you sent to me, but I have to write a
    > parser in Java
    > for Ruby, I haven't write a parser in Ruby.
    > I had think to use ANTLR like parser generator. What do you
    > think
    > about?
    > I have problem with "infinite recursion" but I don't know
    > what I write
    > not correct when I cancel left recursion. I think the problem
    > is how I
    > have to write empty string in ANTLR.
    > Plase, if you can help me you are welcome! :)
    > Thank you very much.=20


    I suggest you google something like this:

    convert LR LL parser

    I found some interesting things from Terrance Parr (author of
    ANTLR), zenspider (Ryan Davis - hard-core ruby hacker), and a
    few others.

    If all you need is java code that parses ruby, you could also
    download the jruby source.

    Why are you wanting to write a ruby parser in ANTLR? Be warned
    that ruby is a very hard language to parse because of all of
    the lexer states (heredocs are probably the hardest).



    =09
    =09
    __________________________________=20
    Yahoo! Mail - PC Magazine Editors' Choice 2005=20
    http://mail.yahoo.com
     
    Eric Mahurin, Oct 28, 2005
    #10
  11. Guest

    Dear Eric,
    you had tell Saint Words, but I have to do this parser for Ruby for an
    exam at Univerisity, therefore...

    Thank you for your interest. Now I have download jRuby and now I see
    this.

    Thank you for your help!

    bye,
    puellula
     
    , Oct 28, 2005
    #11
  12. Hi,

    In message "Re: PARSER for RUBY"
    on Fri, 28 Oct 2005 23:47:05 +0900, writes:

    |you had tell Saint Words, but I have to do this parser for Ruby for an
    |exam at Univerisity, therefore...

    Toughest examination I have ever heard. Indeed.

    matz.
     
    Yukihiro Matsumoto, Oct 28, 2005
    #12
  13. Guest

    Hi Yurihiro,
    but I have to implement a Ruby Editor with the parser inside. This is
    the complete exam!
    Poor me! ;)
    Now I think for the parser...

    bye bye
    puellula
     
    , Oct 29, 2005
    #13
  14. Guest

    Mr. Matsumoto,
    can you help me? I need a Ruby Grammar without Left Recursion. I have
    find Ruby Grammar, but when I try to cancel left recursion, antlr don't
    like this. ANTLR is a good parser generator or is better another parser
    generator?
    If you can help me I'm very happy. It' very important this for me.
    I want to do this exam soon as possible.

    Thank you for your interest!

    bye
    puellula
     
    , Oct 29, 2005
    #14
  15. Guest

    OK :)
    Now it's all ok, I had understand where is the problem. I had to write
    like this:

    program : compstmt;
    compstmt : stmt;
    stmt : LPAREN stmt1;
    stmt1 : smtp ;

    where LPAREN is "(".
    Now, I have to write the ruby grammar because I need a grammar with
    this feature.
    Thanks to all.
    If we can help me I'm very happy :)
    Thank you for yours interest.

    bye bye
    puellula
     
    , Oct 30, 2005
    #15
  16. Ryan Davis Guest

    On Oct 29, 2005, at 12:47 AM, wrote:

    > Mr. Matsumoto,
    > can you help me? I need a Ruby Grammar without Left Recursion. I have
    > find Ruby Grammar, but when I try to cancel left recursion, antlr
    > don't
    > like this. ANTLR is a good parser generator or is better another
    > parser
    > generator?


    Below are the notes I wrote up while doing an LR to LL flip on an
    ST80 grammar. ST80 is much cleaner than ruby in terms of how many
    grammar rules there are in the language so it was easier to get my
    head around when I was doing the work. I tried to do an LR to LL flip
    on ruby a couple years back and I failed at it. Your professor is a
    sadist as far as I'm concerned. I hope these notes help:

    http://www.zenspider.com/Languages/PCCTS/LR2LL.html

    --
    - Seattle.rb - http://www.zenspider.com/
    seattle.rb
    http://blog.zenspider.com/ - http://rubyforge.org/projects/ruby2c
     
    Ryan Davis, Oct 30, 2005
    #16
  17. Guest

    Hi Ryan,
    thank you for your help. I had read the document you sent to me. Oh,
    yes, it's very interesting and I think this can help me.
    Now I'm trying with a simple grammar, for simple programs. I hope will
    be ok my parser for this simple program, for the moment. After I will
    think for complete program. :|
    I hope will be all good! :)
    I hope to finish this exam as soon as possible.

    thank you for your interest,
    puellula
     
    , Oct 30, 2005
    #17
  18. Hugh Sasse Guest

    On Sun, 30 Oct 2005, wrote:

    > OK :)
    > Now it's all ok, I had understand where is the problem. I had to write
    > like this:
    >
    > program : compstmt;
    > compstmt : stmt;
    > stmt : LPAREN stmt1;
    > stmt1 : smtp ;

    ^^^^
    That 'smtp' doesn't look right to me.... What is it?
    >
    > where LPAREN is "(".
    > Now, I have to write the ruby grammar because I need a grammar with
    > this feature.
    > Thanks to all.
    > If we can help me I'm very happy :)
    > Thank you for yours interest.


    I hope you are successful. If you can share the results they may be
    of use to us. We have had some difficulties over new ruby syntax
    imposed by YACC/LEX, so opening up other possibilities would seem to
    be useful.
    >
    > bye bye
    > puellula
    >

    Thank you,
    Hugh
     
    Hugh Sasse, Oct 30, 2005
    #18
  19. Eric Mahurin Guest

    --- Ryan Davis <> wrote:
    > Below are the notes I wrote up while doing an LR to LL flip
    > on an =20
    > ST80 grammar. ST80 is much cleaner than ruby in terms of how
    > many =20
    > grammar rules there are in the language so it was easier to
    > get my =20
    > head around when I was doing the work. I tried to do an LR to
    > LL flip =20
    > on ruby a couple years back and I failed at it. Your
    > professor is a =20
    > sadist as far as I'm concerned. I hope these notes help:
    >=20
    > http://www.zenspider.com/Languages/PCCTS/LR2LL.html


    Ryan,

    I found many links on techniques for left-recursion elimination
    (including yours above). I think the most interesting one was
    this paper by Wolfgang Lohmann:

    http://www.informatik.uni-rostock.de/~wlohmann/Publications/LDTA04/lohman=
    n_ldta04_preliminary.pdf

    It does sound like there is software out there for doing LR to
    LL transformations from the paper. Unfortunately, I couldn't
    find anything that I could download.

    Do you know of any tools out there for doing left-recursion
    elimination and possibly left-factoring?

    Eric



    =09
    =09
    __________________________________=20
    Yahoo! Mail - PC Magazine Editors' Choice 2005=20
    http://mail.yahoo.com
     
    Eric Mahurin, Oct 30, 2005
    #19
  20. Guest

    Hugh,
    in this time I haven't Left Recursion Problem :)

    Oh, yes, if I finish this exam I will share this, don't worry! :)
    For the moment I have problems with Lexer and now I'm reading many
    documents about. I hope will be all good!

    Thank you for the interest!

    bye,
    puellula
     
    , Oct 30, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Bernd Oninger
    Replies:
    0
    Views:
    789
    Bernd Oninger
    Jun 9, 2004
  2. ZOCOR

    XML Parser VS HTML Parser

    ZOCOR, Oct 3, 2004, in forum: Java
    Replies:
    11
    Views:
    845
    Paul King
    Oct 5, 2004
  3. Bernd Oninger
    Replies:
    0
    Views:
    842
    Bernd Oninger
    Jun 9, 2004
  4. Joel Hedlund
    Replies:
    2
    Views:
    554
    Joel Hedlund
    Nov 11, 2006
  5. Joel Hedlund
    Replies:
    0
    Views:
    326
    Joel Hedlund
    Nov 11, 2006
Loading...

Share This Page