www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - [sorry for this again] D grammar

reply "Ivan Senji" <ivan.senji public.srce.hr> writes:
I have writen D grammar and i wanted to test it but:
-my LR parser generator generates a table with over 17000
states, and it takes around 3hours to calculate the table, using (200MB
of memory) (Probably mostly so slow because of my implementation of set
using an array and unoptimized algorithms)

So is there any tool for testing a grammar that could make grammar
debugging easier and faster?
Aug 18 2004
next sibling parent reply Charlie <Charlie_member pathlink.com> writes:
Yacc grammar ?  Not sure, though eclipse has a plugin for antlr that makes
developing super cool.  

and it takes around 3hours to calculate the table, using (200MB
of memory)

Not sure what this means, I hope thats not a runtime calculation :). Do you have the grammar posted somewhere ? Charlie In article <cfvhdi$2d8o$1 digitaldaemon.com>, Ivan Senji says...
I have writen D grammar and i wanted to test it but:
-my LR parser generator generates a table with over 17000
states, and it takes around 3hours to calculate the table, using (200MB
of memory) (Probably mostly so slow because of my implementation of set
using an array and unoptimized algorithms)

So is there any tool for testing a grammar that could make grammar
debugging easier and faster?

Aug 18 2004
parent reply "Ivan Senji" <ivan.senji public.srce.hr> writes:
"Charlie" <Charlie_member pathlink.com> wrote in message
news:cg04m0$8m6$1 digitaldaemon.com...
 Yacc grammar ?  Not sure, though eclipse has a plugin for antlr that makes
 developing super cool.

and it takes around 3hours to calculate the table, using (200MB
of memory)

Not sure what this means, I hope thats not a runtime calculation :). Do

 have the grammar posted somewhere ?

Well, a table has to be calculated only once and can be used many times :) I'll post the grammar if i finish it, i have taken another aproach of writing it one little peace at a time. So now i have expressions, import, declarations, and while :) But i don't think it is possible to solve some ambiguities that i have found, like identifier: basicType or primaryExpression? Right now to solve this my grammars basicTypes begins with "type". So this may turn out to be a grammar for a hypothetical language and not for D. If my memory serves me well, you mentioned writing a grammar too, how is that going?
 Charlie

 In article <cfvhdi$2d8o$1 digitaldaemon.com>, Ivan Senji says...
I have writen D grammar and i wanted to test it but:
-my LR parser generator generates a table with over 17000
states, and it takes around 3hours to calculate the table, using (200MB
of memory) (Probably mostly so slow because of my implementation of set
using an array and unoptimized algorithms)

So is there any tool for testing a grammar that could make grammar
debugging easier and faster?


Aug 18 2004
parent Charlie <Charlie_member pathlink.com> writes:
I modified the java grammar that ships with antlr, it almost works but it had
some ambiguity problems with attribues, it can do 'public :', and 'public {
declDefs }' but not just 'public' :S.

Its at dsource.org under General ( sites down atm or id give link ), under D
Grammar.

Ive given it up though for the DMD front end , which is very nice.  We defintly
need a grammar though.

Charlie

In article <cg0bj9$sak$1 digitaldaemon.com>, Ivan Senji says...
"Charlie" <Charlie_member pathlink.com> wrote in message
news:cg04m0$8m6$1 digitaldaemon.com...
 Yacc grammar ?  Not sure, though eclipse has a plugin for antlr that makes
 developing super cool.

and it takes around 3hours to calculate the table, using (200MB
of memory)

Not sure what this means, I hope thats not a runtime calculation :). Do

 have the grammar posted somewhere ?

Well, a table has to be calculated only once and can be used many times :) I'll post the grammar if i finish it, i have taken another aproach of writing it one little peace at a time. So now i have expressions, import, declarations, and while :) But i don't think it is possible to solve some ambiguities that i have found, like identifier: basicType or primaryExpression? Right now to solve this my grammars basicTypes begins with "type". So this may turn out to be a grammar for a hypothetical language and not for D. If my memory serves me well, you mentioned writing a grammar too, how is that going?
 Charlie

 In article <cfvhdi$2d8o$1 digitaldaemon.com>, Ivan Senji says...
I have writen D grammar and i wanted to test it but:
-my LR parser generator generates a table with over 17000
states, and it takes around 3hours to calculate the table, using (200MB
of memory) (Probably mostly so slow because of my implementation of set
using an array and unoptimized algorithms)

So is there any tool for testing a grammar that could make grammar
debugging easier and faster?



Aug 18 2004
prev sibling next sibling parent reply "Sammy" <not there.com> writes:
Yvan,

Here is a Yacc grammar for the "C" Language.
When processed by Bison, its gives a parser
with 355 states. There are 217 rules in this grammar.

The parser is produced in less than 2 seconds.

I think a "D" lalr grammar should be  comparable in size
and time processing to the "C" one.

Try the "C" one. If you do not get better figures, then
there might be a bug in your parser generator.

If you need any of the other files produced by Bison,
like the ansic.tab.c or the ansic.output file, just ask.

You posted a grammar recently (May, 2 2004), dgram.gram.
Is this the grammar you are using ?

I will do some tests with it and report my findings (if any).

-- S

"Ivan Senji" <ivan.senji public.srce.hr> wrote in message
news:cfvhdi$2d8o$1 digitaldaemon.com...
 I have writen D grammar and i wanted to test it but:
 -my LR parser generator generates a table with over 17000
 states, and it takes around 3hours to calculate the table, using (200MB
 of memory) (Probably mostly so slow because of my implementation of set
 using an array and unoptimized algorithms)

 So is there any tool for testing a grammar that could make grammar
 debugging easier and faster?

--- Outgoing mail is certified Virus Free. Checked by AVG anti-virus system (http://www.grisoft.com). Version: 6.0.740 / Virus Database: 494 - Release Date: 04-08-16
Aug 18 2004
parent "Ivan Senji" <ivan.senji public.srce.hr> writes:
"Sammy" <not there.com> wrote in message
news:cg17n8$2ohr$1 digitaldaemon.com...
 Yvan,

 Here is a Yacc grammar for the "C" Language.
 When processed by Bison, its gives a parser
 with 355 states. There are 217 rules in this grammar.

My lr(1) parser generates 1503 states and i think this is a normal difference between lalr and lr(1)
 The parser is produced in less than 2 seconds.

Mine takes a little less than 2min, i think i should consider making a switch wich parser to create lalr or lr(1), it shouldn't be too difficult.
 I think a "D" lalr grammar should be  comparable in size
 and time processing to the "C" one.

 Try the "C" one. If you do not get better figures, then
 there might be a bug in your parser generator.

I wouldn't like this, because from experience these bugs are very hard to find.
 If you need any of the other files produced by Bison,
 like the ansic.tab.c or the ansic.output file, just ask.

 You posted a grammar recently (May, 2 2004), dgram.gram.
 Is this the grammar you are using ?

No. That is an old attempt (and not a very good one) I think i know now why in my first attempt i got 17000 states: i was writing a grammar by figuring out what "parse.c" does. As this is basicaly a recursive descent parser + some magic the grammar i got was more complicated that it should have been because it was more like a ll(1) than lr(1) grammar. Implementing just two changes in two rules (ideas from c gram), decreased the number of states by ~100. PS. I should be studying these days so it will take a couple more days before i get an even partially usefull grammar to post.
Aug 19 2004
prev sibling parent reply "Sammy" <not there.com> writes:
 -my LR parser generator generates a table with over 17000

In my preceding post i forgot to ask: What parser generator are you using, your own or another parser available on the Net ? --
Aug 18 2004
parent reply "Ivan Senji" <ivan.senji public.srce.hr> writes:
"Sammy" <not there.com> wrote in message
news:cg1ipc$mec$1 digitaldaemon.com...
 -my LR parser generator generates a table with over 17000

In my preceding post i forgot to ask: What parser generator are you using, your own or another parser available on the Net ?

My own :) (that is why it is so slow :)
Aug 19 2004
parent reply "Sammy" <not there.com> writes:
 My own :) (that is why it is so slow :)

it is written in C. C++, ??? Will you opensource it ?
Aug 19 2004
parent reply "Ivan Senji" <ivan.senji public.srce.hr> writes:
"Sammy" <not there.com> wrote in message
news:cg22uf$1sg5$1 digitaldaemon.com...
 My own :) (that is why it is so slow :)

it is written in C. C++, ???

What kind of a question is this? D ofcourse! :)
 Will you opensource it ?

Maybe, if i get to parse D with it and conclude it is working, then i would only have to translate it to English and make it public. Actually the grammar is going really well, except for one (not that tiny) simplification.
Aug 19 2004
parent reply Charlie <Charlie_member pathlink.com> writes:
Actually the grammar is going really well, except for
one (not that tiny) simplification.

Whats the simplification ? Charlie In article <cg26hg$1tp5$1 digitaldaemon.com>, Ivan Senji says...
"Sammy" <not there.com> wrote in message
news:cg22uf$1sg5$1 digitaldaemon.com...
 My own :) (that is why it is so slow :)

it is written in C. C++, ???

What kind of a question is this? D ofcourse! :)
 Will you opensource it ?

Maybe, if i get to parse D with it and conclude it is working, then i would only have to translate it to English and make it public. Actually the grammar is going really well, except for one (not that tiny) simplification.

Aug 19 2004
parent "Ivan Senji" <ivan.senji public.srce.hr> writes:
"Charlie" <Charlie_member pathlink.com> wrote in message
news:cg3f41$2lir$1 digitaldaemon.com...
Actually the grammar is going really well, except for
one (not that tiny) simplification.

Whats the simplification ?

As i can't tell the difference between basicType and primaryExpression (identifier can be both..) i made a change that basicType begins with "type" so instead of int x; -> type int x; int func(char[] y); -> type int func(type char[] y); Maybe when i finish the grammar someone will come up with a way of combining the rules for basicType and primaryExpression to eliminate the problem.
 Charlie

 In article <cg26hg$1tp5$1 digitaldaemon.com>, Ivan Senji says...
"Sammy" <not there.com> wrote in message
news:cg22uf$1sg5$1 digitaldaemon.com...
 My own :) (that is why it is so slow :)

it is written in C. C++, ???

What kind of a question is this? D ofcourse! :)
 Will you opensource it ?

Maybe, if i get to parse D with it and conclude it is working, then i would only have to translate it to English and make it public. Actually the grammar is going really well, except for one (not that tiny) simplification.


Aug 20 2004