PARSER for RUBY

P

puellula

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
 
H

Hugh Sasse

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 :(
Click to expand...

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 : ;
Click to expand...
[...]

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
| ;
Click to expand...

might work better?
 
P

puellula

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
 
H

Hugh Sasse

---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

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.
Click to expand...

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.
Click to expand...

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
Click to expand...

Good luck,
Hugh
---559023410-585771160-1130502801=:19167--
---559023410-585771160-1130502801=:19167--
 
E

Eric Mahurin

--- [email protected] said:
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 :(
Click to expand...

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
 
P

puellula

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
 
P

puellula

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
 
H

Hugh Sasse

Hugh, thank you very much for your help but I have the same problem! :(
Click to expand...

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!
Click to expand...

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

thank you.
Thank you very much

bye,
Sara
Click to expand...
Hugh
 
E

Eric Mahurin

--- [email protected] said:
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
Click to expand...

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
 
P

puellula

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
 
Y

Yukihiro Matsumoto

Hi,

In message "Re: PARSER for RUBY"
on Fri, 28 Oct 2005 23:47:05 +0900, (e-mail address removed) 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.
 
P

puellula

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
 
P

puellula

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
 
P

puellula

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
 
R

Ryan Davis

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?
Click to expand...

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
 
P

puellula

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
 
H

Hugh Sasse

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 ;
Click to expand...
^^^^
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.
Click to expand...

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
Click to expand...
Thank you,
Hugh
 
E

Eric Mahurin

--- Ryan Davis said:
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
Click to expand...

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
 
P

puellula

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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

[ANN] antlr3 1.3.1 ( improved ANTLR v3 for Ruby ) 0
ANTLR Target for Ruby 28
With this artifact, everyone can easily invent new languages 5
RUBY GRAMMAR 27
Deriving from concrete types like std::list 11
Best lexer/parser for Ruby language itself 0
my ears are burning... ;) 12
ruby lexer/parser 2

Members online

No members online now.
Total: 57 (members: 0, guests: 57)
Robots: 96

Forum statistics

Threads
473,982
Messages
2,570,190
Members
46,736
Latest member
zacharyharris

Latest Threads

Top