www.digitalmars.com         C & C++   DMDScript  

D - D grammar?

reply "Ivan Senji" <ivan.senji public.srce.hr> writes:
Is it LL(1)? Can it be converted to LL(1)?
Thanks
Aug 05 2003
parent reply "Walter" <walter digitalmars.com> writes:
"Ivan Senji" <ivan.senji public.srce.hr> wrote in message
news:bgntfi$qhg$1 digitaldaemon.com...

 Is it LL(1)? Can it be converted to LL(1)?


No, it requires arbitrary lookahead.
Aug 05 2003
next sibling parent reply "Ivan Senji" <ivan.senji public.srce.hr> writes:
I know I'm asking stupid questions:
I like D very much and i would like to write a parser for it (for fun).
Does arbitrary lookahead mean LR(1) grammar/parser?
Im writing a program that creates a LR(1) parser table from the grammar
but i would like to know is LR(1) the right parser?

"Walter" <walter digitalmars.com> wrote in message
news:bgon6j$1kfd$2 digitaldaemon.com...

 "Ivan Senji" <ivan.senji public.srce.hr> wrote in message
 news:bgntfi$qhg$1 digitaldaemon.com...

 Is it LL(1)? Can it be converted to LL(1)?


 No, it requires arbitrary lookahead.
Aug 08 2003
next sibling parent reply "Walter" <walter digitalmars.com> writes:
"Ivan Senji" <ivan.senji public.srce.hr> wrote in message
news:bgvq53$28sd$1 digitaldaemon.com...

 I know I'm asking stupid questions:
 I like D very much and i would like to write a parser for it (for fun).
 Does arbitrary lookahead mean LR(1) grammar/parser?
 Im writing a program that creates a LR(1) parser table from the grammar
 but i would like to know is LR(1) the right parser?


I can never remember the difference between LL, LR, LALR, etc., probably
because I never use parser generators. But it is not (1) because it requires
arbitrary lookahead, mostly in trying to figure out if a sequence of tokens
is a type or an expression, declaration or statement.

The parser (parse.c) is set up to make lookahead easy.
Aug 08 2003
next sibling parent reply Bill Cox <bill viasic.com> writes:
Walter wrote:

 "Ivan Senji" <ivan.senji public.srce.hr> wrote in message
 news:bgvq53$28sd$1 digitaldaemon.com...
 

I know I'm asking stupid questions:
I like D very much and i would like to write a parser for it (for fun).
Does arbitrary lookahead mean LR(1) grammar/parser?
Im writing a program that creates a LR(1) parser table from the grammar
but i would like to know is LR(1) the right parser?


 
 
 I can never remember the difference between LL, LR, LALR, etc., probably
 because I never use parser generators. But it is not (1) because it requires
 arbitrary lookahead, mostly in trying to figure out if a sequence of tokens
 is a type or an expression, declaration or statement.
 
 The parser (parse.c) is set up to make lookahead easy.
 
 


Hi, Walter.

I believe LR(1) is what YACC does (maybe it's LL(1)).

YACC has some abilities to look ahead.  It pushes "unreduced" tokens on 
the token stack, and waits for a rule to be able to reduce them.  I 
doubt D's type declarations are a problem.  Generally, grammers become 
non-YACC friendly when parsing depends on context information.  For 
example, foo(bar) in an expression can be a function call, or a cast 
expression in C++.  You can't build a reasonable data structure for it 
when you read it, and instead have to come back later and patch it.

 From what I've seen of D, the grammer looks YACC friendly.  I could be 
talked into verifying this, if you could create a text file of BNF rules 
for D.

Bill
Aug 08 2003
parent reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
YACC (and Bison) is LALR(1).  LALR(1) cannot parse C, D, or other 
similar languages without some nasty hacks.

LALR(1) is LookAhead Left Right (1 symbol of lookahead).  It means that 
it reads the tokens starting at the left, but interprets them starting 
from the right.  Basically, it means that it can only evaluate the 
topmost token(s) on the stack.  The 1 symbol of lookahead means that you 
can read one additional symbol before deciding how to evaluate the 
topmost tokens.

As Burton said, the classic problem that YACC has is parsing the 
difference between expressions and type declarations.  A grammar to 
parse a statment might include the following rules:

statement:
	  declaration ';'
	| expression ';'
;

declaration:
	  type IDENT
;

type:
	  IDENT
	| type '*'
;

expression:
	  IDENT
	| expression '*' expression
;

Now, as an LALR(1) parser, how do you parse this series of tokens:

IDENT '*' IDENT ';'

This could be either a declaration of a pointer, or an expression where 
two variables are multiplied together.

An LALR(1) parser MUST be able to parse the top tokens on the stack with 
only 1 symbol of lookahead.  The grammar requires that the parser make a 
reduction of the first IDENT token, either IDENT->type or 
IDENT->expression.  However, the parser cannot tell from the single 
token of lookahead which is valid - either could work!

Thus, the grammar given above CANNOT be parsed by an LALR(1) parser.

You can try to hack around things, if you want:

statement:
	  IDENT stars IDENT ';'
;

stars:
	  '*'
	| stars '*'
;

This grammar is parsable by an LALR(1) parser.  But it isn't really 
readable!

Right when D first came out, I decided to write a parser for it.  I 
started with bison (GNU's yacc alternative).  I never had any success 
parsing D because of problems like this.  The grammar eventually gets 
too ugly to maintain, and even with all the ugliness, my grammar still 
had ambiguities.  In my mind, it's an open question whether it is even 
possible to devicse an LALR(1) grammar that parses C or D.

So I wrote my own parser generator :)



Bill Cox wrote:

 Walter wrote:
 

 "Ivan Senji" <ivan.senji public.srce.hr> wrote in message
 news:bgvq53$28sd$1 digitaldaemon.com...


 I know I'm asking stupid questions:
 I like D very much and i would like to write a parser for it (for fun).
 Does arbitrary lookahead mean LR(1) grammar/parser?
 Im writing a program that creates a LR(1) parser table from the grammar
 but i would like to know is LR(1) the right parser?




 I can never remember the difference between LL, LR, LALR, etc., probably
 because I never use parser generators. But it is not (1) because it 
 requires
 arbitrary lookahead, mostly in trying to figure out if a sequence of 
 tokens
 is a type or an expression, declaration or statement.

 The parser (parse.c) is set up to make lookahead easy.


 
 Hi, Walter.
 
 I believe LR(1) is what YACC does (maybe it's LL(1)).
 
 YACC has some abilities to look ahead.  It pushes "unreduced" tokens on 
 the token stack, and waits for a rule to be able to reduce them.  I 
 doubt D's type declarations are a problem.  Generally, grammers become 
 non-YACC friendly when parsing depends on context information.  For 
 example, foo(bar) in an expression can be a function call, or a cast 
 expression in C++.  You can't build a reasonable data structure for it 
 when you read it, and instead have to come back later and patch it.
 
  From what I've seen of D, the grammer looks YACC friendly.  I could be 
 talked into verifying this, if you could create a text file of BNF rules 
 for D.
 
 Bill
Aug 08 2003
next sibling parent "Walter" <walter digitalmars.com> writes:
"Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:bh15g0$gq9$1 digitaldaemon.com...

 So I wrote my own parser generator :)


You're obviously a kindred spirit!
Aug 08 2003
prev sibling parent reply Bill Cox <bill viasic.com> writes:
Russ Lewis wrote:

 YACC (and Bison) is LALR(1).  LALR(1) cannot parse C, D, or other 
 similar languages without some nasty hacks.
 
 LALR(1) is LookAhead Left Right (1 symbol of lookahead).  It means that 
 it reads the tokens starting at the left, but interprets them starting 
 from the right.  Basically, it means that it can only evaluate the 
 topmost token(s) on the stack.  The 1 symbol of lookahead means that you 
 can read one additional symbol before deciding how to evaluate the 
 topmost tokens.
 
 As Burton said, the classic problem that YACC has is parsing the 
 difference between expressions and type declarations.  A grammar to 
 parse a statment might include the following rules:
 
 statement:
       declaration ';'
     | expression ';'
 ;
 
 declaration:
       type IDENT
 ;
 
 type:
       IDENT
     | type '*'
 ;
 
 expression:
       IDENT
     | expression '*' expression
 ;
 
 Now, as an LALR(1) parser, how do you parse this series of tokens:
 
 IDENT '*' IDENT ';'
 
 This could be either a declaration of a pointer, or an expression where 
 two variables are multiplied together.
 
 An LALR(1) parser MUST be able to parse the top tokens on the stack with 
 only 1 symbol of lookahead.  The grammar requires that the parser make a 
 reduction of the first IDENT token, either IDENT->type or 
 IDENT->expression.  However, the parser cannot tell from the single 
 token of lookahead which is valid - either could work!
 
 Thus, the grammar given above CANNOT be parsed by an LALR(1) parser.
 
 You can try to hack around things, if you want:
 
 statement:
       IDENT stars IDENT ';'
 ;
 
 stars:
       '*'
     | stars '*'
 ;
 
 This grammar is parsable by an LALR(1) parser.  But it isn't really 
 readable!
 
 Right when D first came out, I decided to write a parser for it.  I 
 started with bison (GNU's yacc alternative).  I never had any success 
 parsing D because of problems like this.  The grammar eventually gets 
 too ugly to maintain, and even with all the ugliness, my grammar still 
 had ambiguities.  In my mind, it's an open question whether it is even 
 possible to devicse an LALR(1) grammar that parses C or D.
 
 So I wrote my own parser generator :)
 
 
 
 Bill Cox wrote:
 

 Walter wrote:


 "Ivan Senji" <ivan.senji public.srce.hr> wrote in message
 news:bgvq53$28sd$1 digitaldaemon.com...


 I know I'm asking stupid questions:
 I like D very much and i would like to write a parser for it (for fun).
 Does arbitrary lookahead mean LR(1) grammar/parser?
 Im writing a program that creates a LR(1) parser table from the grammar
 but i would like to know is LR(1) the right parser?





 I can never remember the difference between LL, LR, LALR, etc., probably
 because I never use parser generators. But it is not (1) because it 
 requires
 arbitrary lookahead, mostly in trying to figure out if a sequence of 
 tokens
 is a type or an expression, declaration or statement.

 The parser (parse.c) is set up to make lookahead easy.


 Hi, Walter.

 I believe LR(1) is what YACC does (maybe it's LL(1)).

 YACC has some abilities to look ahead.  It pushes "unreduced" tokens 
 on the token stack, and waits for a rule to be able to reduce them.  I 
 doubt D's type declarations are a problem.  Generally, grammers become 
 non-YACC friendly when parsing depends on context information.  For 
 example, foo(bar) in an expression can be a function call, or a cast 
 expression in C++.  You can't build a reasonable data structure for it 
 when you read it, and instead have to come back later and patch it.

  From what I've seen of D, the grammer looks YACC friendly.  I could 
 be talked into verifying this, if you could create a text file of BNF 
 rules for D.

 Bill


 



Hi, Russ.

Can the latest bison parse your D grammer?  I think an official machine 
readable grammer is a good thing, even if no one uses it to create an 
actual parser.  If you have a D grammer, could you post it?

Also, if I remember, you couldn't share your new parser generator due to 
issues at work.  Is that right?

Bill
Aug 11 2003
parent Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Bill Cox wrote:

 Can the latest bison parse your D grammer?  I think an official machine 
 readable grammer is a good thing, even if no one uses it to create an 
 actual parser.  If you have a D grammer, could you post it?
 
 Also, if I remember, you couldn't share your new parser generator due to 
 issues at work.  Is that right?
 
 Bill


I haven't tried it since they put the GLR code in.  It's a good idea, 
but I'd probably have to rebuild it from scratch.  I don't (anymore) 
have a "clean" bison grammar.  I hacked up the first one to try to make 
it work (and failed), and the new, up-to-date grammar uses the syntax 
from my new parser.

Sometime in the future I can try to port it back to Bison.  Ick. 
Anybody ever tried to write a parser for the for statement in Bison? 
There are 8 different possible alternatives you have to express.

I like my parser because I could parse a for with a single expression. 
But yeah, the company's still not allowing me release it.
Aug 11 2003
prev sibling next sibling parent reply "Mike Wynn" <mike.wynn l8night.co.uk> writes:
"Walter" <walter digitalmars.com> wrote in message
news:bh0tjn$9cu$1 digitaldaemon.com...

 "Ivan Senji" <ivan.senji public.srce.hr> wrote in message
 news:bgvq53$28sd$1 digitaldaemon.com...

 I know I'm asking stupid questions:
 I like D very much and i would like to write a parser for it (for fun).
 Does arbitrary lookahead mean LR(1) grammar/parser?
 Im writing a program that creates a LR(1) parser table from the grammar
 but i would like to know is LR(1) the right parser?


 I can never remember the difference between LL, LR, LALR, etc., probably
 because I never use parser generators. But it is not (1) because it


requires

 arbitrary lookahead, mostly in trying to figure out if a sequence of


tokens

 is a type or an expression, declaration or statement.


LL(n) is a top down parser i.e. recursive decent or predictive rd.
LR is a bottom up parser (shift reduce)
LALR is a lookahead LR

LL parsers have problems with e ::= e + t; so you have to rewrite your
grammers to avoid left recursion

as far as I know (my dragon book claims anyway) yacc is an LALR parser
JavaCC was LL(n) and Antlr is either LL(n) or LALR

unlike C or C++ you do not know if an id is an id or a type so you have to
go quite a way until you know if you have a variable declare or an assign

simple examples to try out
id[id] a;  // declare
id[id] = s; // assign
this could of course be
id.id[id.id[id.id[id]][id]] etc
and func pointers I think cause similar issues
id(*id)(id, id )   // type or function call that returns func ptr that is
called ? given that

worse is c cast ..  (id)(id)  // func call or cast ? but I think they should
be outlawed

I think you'll just have to try it out, a D parser generator would be a good
tool anyway and I'm sure there are tweeks that can be put in to resolve some
issues and if you build a tree then work out what it is I think LALR should
handle it initially.
it would be a good excersise, especially with all the random good ideas ppl
have, would allow someone to try out a given syntax and see if it would
actually work or not.
Aug 08 2003
parent reply "Walter" <walter digitalmars.com> writes:
"Mike Wynn" <mike.wynn l8night.co.uk> wrote in message
news:bh13pd$f5f$1 digitaldaemon.com...

 I think you'll just have to try it out, a D parser generator would be a


good

 tool anyway and I'm sure there are tweeks that can be put in to resolve


some

 issues and if you build a tree then work out what it is I think LALR


should

 handle it initially.
 it would be a good excersise, especially with all the random good ideas


ppl

 have, would allow someone to try out a given syntax and see if it would
 actually work or not.


In my experience, I've been able to crank out a hand-built parser than
someone using Bison could do. So I never saw the point to using those tools
<g>.

The biggest improvement the D grammar has over C/C++ is that it does not
require semantic information in order to lex or to parse. This makes it a
*lot* easier to build syntax sensitive editors and other types of code
analysis tools.
Aug 08 2003
next sibling parent "Mike Wynn" <mike.wynn l8night.co.uk> writes:
"Walter" <walter digitalmars.com> wrote in message
news:bh1kt5$uua$2 digitaldaemon.com...

 "Mike Wynn" <mike.wynn l8night.co.uk> wrote in message
 news:bh13pd$f5f$1 digitaldaemon.com...

 I think you'll just have to try it out, a D parser generator would be a


 good

 tool anyway and I'm sure there are tweeks that can be put in to resolve


 some

 issues and if you build a tree then work out what it is I think LALR


 should

 handle it initially.
 it would be a good excersise, especially with all the random good ideas


 ppl

 have, would allow someone to try out a given syntax and see if it would
 actually work or not.


 In my experience, I've been able to crank out a hand-built parser than
 someone using Bison could do. So I never saw the point to using those


tools

 <g>.


the reason for (as I see it) using Bison, Antlr etc is that you can "prove"
your grammer does not have obscure conflicts.
I agree that a hand crafted parser can be easier, just little things like C
comments are easy to deal with in a hand written parser (once you've read
'/*' ignore everything until you get '*/') but a pain to write in antlr for
example
ML_COMMENT
 : "/*"
  ( { LA(2)!='/' }? '*'
  | '\n' { newline(); }
  | ~('*'|'\n')
  )*
  "*/"
   { $setType(Token.SKIP); }
 ;

but I don't see that that alone makes parser/lexer/treewalker generating
tools redundant they do offer a level of maintainability that a hand written
parser can lack.
it not always a case of who can write the parser first, but also who's is
the most robust and can detect that the original grammer had flaws.
and who could add new features without breaking to much ?
hand written parsers do allow blending of LL and LR techniques but I'm not
100% convinced that that is altogether a good idea, quite a lot of LR
grammers can be converted to LL(n) grammer and if you have a grammer that
can not be written as LR(n) or LL(n) is it a "good" grammer ?



 The biggest improvement the D grammar has over C/C++ is that it does not
 require semantic information in order to lex or to parse. This makes it a
 *lot* easier to build syntax sensitive editors and other types of code
 analysis tools.


that would imply that the grammer should be easy to write.
but you do have to perform 2 passes over the parsed tree due to this lack of
semantic info
in C (or C++) at the time when you parse a type identifier you know what it
is, in D you do not.
Aug 09 2003
prev sibling parent reply Helium <Helium_member pathlink.com> writes:
The biggest improvement the D grammar has over C/C++ is that it does not
require semantic information in order to lex or to parse. This makes it a
*lot* easier to build syntax sensitive editors and other types of code
analysis tools.


But are there any tools like this? e.g. a refactoring tool? I haven't seen one.
Aug 10 2003
parent "Walter" <walter digitalmars.com> writes:
"Helium" <Helium_member pathlink.com> wrote in message
news:bh5489$15nn$1 digitaldaemon.com...

The biggest improvement the D grammar has over C/C++ is that it does not
require semantic information in order to lex or to parse. This makes it a
*lot* easier to build syntax sensitive editors and other types of code
analysis tools.


 But are there any tools like this? e.g. a refactoring tool? I haven't seen


one.

No, not yet. But there will be.
Aug 11 2003
prev sibling parent "Fabian Giesen" <rygNO SPAMgmx.net> writes:
 I can never remember the difference between LL, LR, LALR, etc.,
 probably because I never use parser generators. But it is not (1)
 because it requires arbitrary lookahead, mostly in trying to figure
 out if a sequence of tokens is a type or an expression, declaration
 or statement.


Any LR(k) grammar can be converted to a LR(1) grammar that parses the
exact same language, at the expense of the need for more states (and a
more complicated source grammar). That's why most LR parser generators
don't bother providing more than one token of lookahead.

-fg
Aug 09 2003
prev sibling parent reply "Peter Hercek" <vvp no.post.spam.sk> writes:
Hi Ivan,

It would be great if you (or anybody) would create D grammar in BNF
 or EBNF. I tried it myself a few month ago from the web documentation,
 but the grammar (on the web) had tons of trivial errors and was not
 complete. I tried to get it from sources, but found out that the parser
 is hand writen. Uff, I have given up. I did not feel like courageous
 enough to reverse engineer the souce code to create BNF grammar :o(
 Shame on me, but to reverse engineer the souce code was too much.

I attached the BNF grammar, I was able to extract from the web. Anyway,
 it is few months old. If you (or anybody) can update the file, I would
 like to play with is and generate a *nice* html grammar for D. (I should
 be able to generate antlr grammar description from it too, but I do not
 have this implemented.) I created some XML schema for grammar description
 and XSLT template to generate the html file; it was my fun project to
 learn what it is XSLT. To have idea how the hyperlinked grammar would

 engineering there :o) )

http://peter.hercek.sk/c-sharp-grammar.html

It contains both forward and backward links (ie "show me all the rules,
 which do use this symbol" can be achieved by clicking on the rule head).
 Tested only for IE.

So, if somebody wants to move D grammar on, please respond to this
 message (to group of course). But it requires a lot of source code
 studying unfortunately! I would tell that D grammar is protected through
 obcurity :o). Seriously now, I may be helpfull with some tools to look
 up trivial problems etc.

Peter.


"Ivan Senji" <ivan.senji public.srce.hr> wrote in message
news:bgvq53$28sd$1 digitaldaemon.com...

 I know I'm asking stupid questions:
 I like D very much and i would like to write a parser for it (for fun).
 Does arbitrary lookahead mean LR(1) grammar/parser?
 Im writing a program that creates a LR(1) parser table from the grammar
 but i would like to know is LR(1) the right parser?

 "Walter" <walter digitalmars.com> wrote in message
 news:bgon6j$1kfd$2 digitaldaemon.com...

 "Ivan Senji" <ivan.senji public.srce.hr> wrote in message
 news:bgntfi$qhg$1 digitaldaemon.com...

 Is it LL(1)? Can it be converted to LL(1)?


 No, it requires arbitrary lookahead.





begin 666 d-grammar.txt


M(#H




M8"HO8 T*('P (& O+V  0VAA<F%C=&5R<R!%;F1/9DQI;F4-"B!\("! +RM 






M=6]T9613=')I;F<-"B!\($1O=6)L95%U;W1E9%-T<FEN9PT*('P 17-C87!E


M< T*(#H











M"B Z($1E8VEM86P-"B!\($)I;F%R>0T*('P 3V-T86P-"B!\($AE>&%D96-I

M8 T*('P (&!,8 T*('P (&!U8 T*('P (&!58 T*('P (&!L=6 -"B!\("! 







M"D9L;V%T3&ET97)A; T*(#H 1FQO870-"B!\($9L;V%T($9L;V%T4W5F9FEX




M?"! 26 -" T*2V5Y=V]R9 T*(#H 8&%B<W1R86-T8 T*('P 8&%L:6%S8 T*




M=& -"B!\(&!C;VYT:6YU96 -"B!\(&!D96)U9V -"B!\(&!D969A=6QT8 T*
M('P 8&1E;&5G871E8 T*('P 8&1E;&5T96 -"B!\(&!D97!R96-A=&5D8 T*

M?"! 97AP;W)T8 T*('P 8&5X=&5N9&5D8 T*('P 8&5X=&5R;F -"B!\(&!F
M86QS96 -"B!\(&!F:6YA;& -"B!\(&!F:6YA;&QY8 T*('P 8&9L;V%T8 T*
M('P 8&9O<F -"B!\(&!S=7!E<F -"B!\(&!N=6QL8 T*('P 8&YE=V -"B!\







M"B!\(&!T>7!E9&5F8 T*('P 8'5B>71E8 T*('P 8'5C96YT8 T*('P 8'5I



M9FEE< T*('P 4W1R:6YG3&ET97)A; T*('P 26YT96=E<DQI=&5R86P-"B!\




M8 T*('P 8#P]8 T*('P 8#P\8 T*('P 8#P\/6 -"B!\(& \/F -"B!\(& \











M1&5F<PT*('P 1&5C;$1E9G,-" T*1&5C;$1E9G,-"B Z($1E8VQ$968-"B!\
M($1E8VQ$968 1&5C;$1E9G,-" T*1&5C;$1E9 T*(#H 071T<FEB=71E4W!E


M=&EO; T*('P 06=G<F5G871E1&5C;&%R871I;VX-"B!\($1E8VQA<F%T:6]N


M8T1E<W1R=6-T;W(-"B!\($1E8G5G4W!E8VEF:6-A=&EO; T*('P 5F5R<VEO

M(#H 8&UO9'5L96  36]D=6QE3F%M92! .V -" T*36]D=6QE3F%M90T*(#H 

M;7!O<G1$96-L87)A=&EO; T*(#H 8&EM<&]R=&  36]D=6QE3F%M94QI<W0 
M8#M





M($)A<VEC5'EP93( 1&5C;&%R871O<G, 8#M
M:6-4>7!E,B!&=6YC=&EO;D1E8VQA<F%T;W(-" T*1&5C;&%R871O<G,-"B Z

M"D)A<VEC5'EP90T*(#H




M<F -"B!\(&!W8VAA<F -" T*8& P4')O<&5R=&EE<V -" T*26YT96=R86Q0
M<F]P97)T>0T*(#H
M?"! +FUI;F -"B!\(& N<VEG;F -" T*1FQO871I;F=0;VEN=%!R;W!E<G1Y


M:71E8 T*('P 8"YI<VYO<FUA;& -"B!\(& N9&EG:71S8 T*('P 8"YE<'-I
M;&]N8 T*('P 8"YM86YT:7-S86 -"B!\(& N;6%X17AP8 T*('P 8"YM87A 


M8G5T95-P96-I9FEE< T*(#H 071T<FEB=71E(& Z8 T*('P 071T<FEB=71E

M='1R:6)U=&5%;'-E(& Z8 T*('P 071T<FEB=71E16QS92!$96-L1&5F0FQO
M8VL-"B!\($%T=')I8G5T945L<V4 1&5C;$1E9D)L;V-K(&!E;'-E8"!$96-L





M16QS90T*(#H 1&5B=6=!='1R:6)U=&4-"B!\(%9E<G-I;VY!='1R:6)U=&4-





M8"! *&  26YT96=E<B! *6 -" T*1&5B=6=!='1R:6)U=&4-"B Z(&!D96)U


M<VEO; T*(#H 07-S:6=N17AP<F5S<VEO; T*('P 07-S:6=N17AP<F5S<VEO

M:71I;VYA;$5X<')E<W-I;VX-"B!\($-O;F1I=&EO;F%L17AP<F5S<VEO;B! 
M/6  07-S:6=N17AP<F5S<VEO; T*('P 0V]N9&ET:6]N86Q%>'!R97-S:6]N
M(& K/6  07-S:6=N17AP<F5S<VEO; T*('P 0V]N9&ET:6]N86Q%>'!R97-S
M:6]N(& M/6  07-S:6=N17AP<F5S<VEO; T*('P 0V]N9&ET:6]N86Q%>'!R
M97-S:6]N(& J/6  07-S:6=N17AP<F5S<VEO; T*('P 0V]N9&ET:6]N86Q%
M>'!R97-S:6]N(& O/6  07-S:6=N17AP<F5S<VEO; T*('P 0V]N9&ET:6]N
M86Q%>'!R97-S:6]N(& E/6  07-S:6=N17AP<F5S<VEO; T*('P 0V]N9&ET
M:6]N86Q%>'!R97-S:6]N(& F/6  07-S:6=N17AP<F5S<VEO; T*('P 0V]N
M9&ET:6]N86Q%>'!R97-S:6]N(&!\/6  07-S:6=N17AP<F5S<VEO; T*('P 
M0V]N9&ET:6]N86Q%>'!R97-S:6]N(&!>/6  07-S:6=N17AP<F5S<VEO; T*
M('P 0V]N9&ET:6]N86Q%>'!R97-S:6]N(&!^/6  07-S:6=N17AP<F5S<VEO
M; T*('P 0V]N9&ET:6]N86Q%>'!R97-S:6]N(& \/#U ($%S<VEG;D5X<')E
M<W-I;VX-"B!\($-O;F1I=&EO;F%L17AP<F5S<VEO;B! /CX]8"!!<W-I9VY%



M;VX 8#I
M; T*(#H 06YD06YD17AP<F5S<VEO; T*('P 06YD06YD17AP<F5S<VEO;B! 
M?'Q ($%N9$%N9$5X<')E<W-I;VX-" T*06YD06YD17AP<F5S<VEO; T*(#H 



M"B Z($%N9$5X<')E<W-I;VX-"B!\($%N9$5X<')E<W-I;VX 8%Y ($%N9$5X
M<')E<W-I;VX-" T*06YD17AP<F5S<VEO; T*(#H 17%U86Q%>'!R97-S:6]N

M<75A;$5X<')E<W-I;VX-"B Z(%)E;$5X<')E<W-I;VX-"B!\(%)E;$5X<')E
M<W-I;VX 8#T
M/6  4F5L17AP<F5S<VEO; T*('P 4F5L17AP<F5S<VEO;B! /3T]8"!296Q%

M;VX-" T*4F5L17AP<F5S<VEO; T*(#H
M:&EF=$5X<')E<W-I;VX 8#Q (%-H:69T17AP<F5S<VEO; T*('P 4VAI9G1%

M<W-I;VX 8#Y (%-H:69T17AP<F5S<VEO; T*('P 4VAI9G1%>'!R97-S:6]N

M/CU (%-H:69T17AP<F5S<VEO; T*('P 4VAI9G1%>'!R97-S:6]N(& A/#Y 
M(%-H:69T17AP<F5S<VEO; T*('P 4VAI9G1%>'!R97-S:6]N(& \/F  4VAI


M<W-I;VX-"B!\(%-H:69T17AP<F5S<VEO;B! (3X]8"!3:&EF=$5X<')E<W-I
M;VX-"B!\(%-H:69T17AP<F5S<VEO;B! (3Q (%-H:69T17AP<F5S<VEO; T*
M('P 4VAI9G1%>'!R97-S:6]N(& A/#U (%-H:69T17AP<F5S<VEO; T*('P 

M17AP<F5S<VEO; T*(#H 061D17AP<F5S<VEO; T*('P 061D17AP<F5S<VEO
M;B! /#Q ($%D9$5X<')E<W-I;VX-"B!\($%D9$5X<')E<W-I;VX 8#X^8"!!

M<W-I;VX-" T*061D17AP<F5S<VEO; T*(#H 375L17AP<F5S<VEO; T*('P 
M375L17AP<F5S<VEO;B! *V  375L17AP<F5S<VEO; T*('P 375L17AP<F5S
M<VEO;B! +6  375L17AP<F5S<VEO; T*('P 375L17AP<F5S<VEO;B! ?F  

M<W-I;VX-"B!\(%5N87)Y17AP<F5S<VEO;B! *F  56YA<GE%>'!R97-S:6]N

M56YA<GE%>'!R97-S:6]N(& E8"!5;F%R>45X<')E<W-I;VX-" T*56YA<GE%

M17AP<F5S<VEO; T*('P 8"LK8"!5;F%R>45X<')E<W-I;VX-"B!\(& M+6  




M;VX-"B!\(& H8"!4>7!E(& I8"!5;F%R>45X<')E<W-I;VX-"B!\(& H8"!4

M(#H 4')I;6%R>45X<')E<W-I;VX-"B!\(%!O<W1F:7A%>'!R97-S:6]N(& N


M*&  07)G=6UE;G1,:7-T(& I8 T*('P 4&]S=&9I>$5X<')E<W-I;VX 8%M 



M:6YG3&ET97)A; T*('P 07-S97)T17AP<F5S<VEO; T*('P 5'EP92! +F  


M<F5S<VEO; T*('P 07-S:6=N17AP<F5S<VEO;B! +&  07)G=6UE;G1,:7-T

M6V  07-S:6=N17AP<F5S<VEO;B! 76  1&5C;&%R871O< T*('P 8&YE=V  

M8"!"87-I8U1Y<&4 4W1A<G,-"B!\(&!N97= (& H8"!!<F=U;65N=$QI<W0 
M8"E ($)A<VEC5'EP92!3=&%R<R! 6V  07-S:6=N17AP<F5S<VEO;B! 76  
M1&5C;&%R871O< T*('P 8&YE=V  8"A ($%R9W5M96YT3&ES="! *6  0F%S

M*&  07)G=6UE;G1,:7-T(& I8"!"87-I8U1Y<&4 4W1A<G,-" T*4W1A<G,-


M0FQO8VM3=&%T96UE;G0-"B!\($5X<')E<W-I;VY3=&%T96UE;G0-"B!\($1E

M=&%T96UE;G0-"B!\(%9E<G-I;VY3=&%T96UE;G0-"B!\(%=H:6QE4W1A=&5M

M(%-W:71C:%-T871E;65N= T*('P 0V%S95-T871E;65N= T*('P 1&5F875L
M=%-T871E;65N= T*('P 0V]N=&EN=653=&%T96UE;G0-"B!\($)R96%K4W1A



M96UE;G0-" T*3&%B96QL9613=&%T96UE;G0-"B Z($ED96YT:69I97( 8#I 


M871E;65N= T*('P 4W1A=&5M96YT(%-T871E;65N=$QI<W0-" T*17AP<F5S
M<VEO;E-T871E;65N= T*(#H 17AP<F5S<VEO;B! .V -" T*1&5C;&%R871I
M;VY3=&%T96UE;G0-"B Z(%1Y<&4 261E;G1I9FEE<DQI<W0 8#M



M;65N= T*(#H 8&EF("A ($5X<')E<W-I;VX 8"E (%-T871E;65N= T*('P 
M8&EF("A ($5X<')E<W-I;VX 8"E (%-T871E;65N="! 96QS96  4W1A=&5M

M:6]N(& I8"!3=&%T96UE;G0-" T*1&]3=&%T96UE;G0-"B Z(&!D;V  4W1A
M=&5M96YT(&  =VAI;&4 *&  17AP<F5S<VEO;B! *6 -" T*1F]R4W1A=&5M


M17AP<F5S<VEO; T*('P 1&5C;&%R871I;VX-" T*5&5S= T*(#H 96UP='D-







M"B!\(&!B<F5A:V  261E;G1I9FEE<B! .V -" T*4F5T=7)N4W1A=&5M96YT




M8VAR;VYI>F5D8"!3=&%T96UE;G0-"B!\(&!S>6YC:')O;FEZ960 *&  17AP

M>6  0FQO8VM3=&%T96UE;G0 0V%T8VAE<PT*('P 8'1R>6  0FQO8VM3=&%T
M96UE;G0 0V%T8VAE<R! 9FEN86QL>6  0FQO8VM3=&%T96UE;G0-"B!\(&!T
M<GE ($)L;V-K4W1A=&5M96YT(&!F:6YA;&QY8"!";&]C:U-T871E;65N= T*






M<W1R=6-T:6]N3&ES= T*(#H 07-M26YS=')U8W1I;VX 8#M


M.B!486< 8'M ($1E8VQ$969S(&!]8 T*('P 5&%G($ED96YT:69I97( 8'M 
M($1E8VQ$969S(&!]8 T*('P 5&%G($ED96YT:69I97( 8#M
M(#H

M96YU;6  8'M ($5N=6U-96UB97)S(&!]8 T*('P 8&5N=6U (&ED96YT:69I
M97( 8#M
M365M8F5R(& L8 T*('P 16YU;4UE;6)E<B! +&  16YU;4UE;6)E<G,-" T*
M16YU;4UE;6)E< T*(#H 261E;G1I9FEE< T*('P 261E;G1I9FEE<B! /6  



M($ED96YT:69I97(-" T*26YT97)F86-E0VQA<W,-"B Z($ED96YT:69I97(-



M8"!)9&5N=&EF:65R(& Z8"!3=7!E<DEN=&5R9F%C97, 26YT97)F86-E0F]D



M=&5$96-L87)A=&EO; T*(#H 8'1E;7!L871E8"!496UP;&%T94ED96YT:69I
M97( 8"A (%1E;7!L871E4&%R86UE=&5R3&ES="! *6  8'M ($1E8VQ$969S


M('P 5&5M<&QA=&5087)A;65T97( 8"Q (%1E;7!L871E4&%R86UE=&5R3&ES

M5F%L=65087)A;65T97(-" T*5'EP95!A<F%M971E< T*(#H 261E;G1I9FEE

M(#H 1&5C;&%R871I;VX-"B!\($1E8VQA<F%T:6]N(& Z8"!!<W-I9VY%>'!R

M<&QA=&5)9&5N=&EF97( 8"A (%1E;7!L871E07)G=6UE;G1,:7-T(& I8 T*


M($ED96YT:69I97(-" T*5&5M<&QA=&5!<F=U;65N=$QI<W0-"B Z(%1E;7!L
M871E07)G=6UE;G0-"B!\(%1E;7!L871E07)G=6UE;G0 8"Q (%1E;7!L871E

3($%S<VEG;D5X<')E<W-I;VX-" ``
`
end
Aug 10 2003
next sibling parent reply "Walter" <walter digitalmars.com> writes:
If you're interested in critiquing the grammar in the D documentation, I can
work on improving it.
Aug 11 2003
parent reply "Peter Hercek" <vvp no.post.spam.sk> writes:
I would like to do so, but not from the current state of the web site.
 I think the grammar must be hard to maintain ... it is distribueted to
 a lot of pages. Do you generate them somehow? How you keep it
 up to date?
I prefer to critique one file with the grammar, preferably in the format
 attached in my previous message. The file can have sections,

 already has eg ``0Lexical` (the number zero is the nest level). We can
 include some remarks etc. For me this was a way to check posibilities
 of XSLT. I can generate more files (may be a file for each section) to
 include it into different pages. But then cross-links between different
 pages would not work, or we need some good naming convention
 derived from section names or something similar.
It is a pain to extract grammar from the webpages and transform it
 into something usable for automatic processing. I'm lazy to do it
 manually and it is error prone too.
Check also my response to Bil Cox. If he finaly decides to analyze your
 code, you can get a good grammar for free :) Then we can cut off
 sections for you to replace in your pages?
I believe we can figure it out somehow together.

"Walter" <walter digitalmars.com> wrote in message
news:bha72n$b1f$1 digitaldaemon.com...

 If you're interested in critiquing the grammar in the D documentation, I can
 work on improving it.
Aug 12 2003
parent "Walter" <walter digitalmars.com> writes:
All the web pages are html pages written by hand.

"Peter Hercek" <vvp no.post.spam.sk> wrote in message
news:bhce0l$2g97$1 digitaldaemon.com...

 I would like to do so, but not from the current state of the web site.
  I think the grammar must be hard to maintain ... it is distribueted to
  a lot of pages. Do you generate them somehow? How you keep it
  up to date?
 I prefer to critique one file with the grammar, preferably in the format
  attached in my previous message. The file can have sections,

  already has eg ``0Lexical` (the number zero is the nest level). We can
  include some remarks etc. For me this was a way to check posibilities
  of XSLT. I can generate more files (may be a file for each section) to
  include it into different pages. But then cross-links between different
  pages would not work, or we need some good naming convention
  derived from section names or something similar.
 It is a pain to extract grammar from the webpages and transform it
  into something usable for automatic processing. I'm lazy to do it
  manually and it is error prone too.
 Check also my response to Bil Cox. If he finaly decides to analyze your
  code, you can get a good grammar for free :) Then we can cut off
  sections for you to replace in your pages?
 I believe we can figure it out somehow together.

 "Walter" <walter digitalmars.com> wrote in message


news:bha72n$b1f$1 digitaldaemon.com...

 If you're interested in critiquing the grammar in the D documentation, I




can

 work on improving it.
Aug 15 2003
prev sibling parent reply Bill Cox <bill viasic.com> writes:
Peter Hercek wrote:

 So, if somebody wants to move D grammar on, please respond to this
  message (to group of course). But it requires a lot of source code
  studying unfortunately! I would tell that D grammar is protected through
  obcurity :o). Seriously now, I may be helpfull with some tools to look
  up trivial problems etc.


I'm willing to take it on.  I've had a fair amount of experience with 
paser generators.  With bison's latest upgrades, and some work, I bet I 
get it to work.

Bill
Aug 12 2003
parent reply "Peter Hercek" <vvp no.post.spam.sk> writes:
Cool, I did it this way last time.
Pulled out the grammar from web pages and created the text file
 (this was pain, because I was not able to automate this completely!)
Generated an XML description of the grammar from the text file
 using antlr.
The XML file was transormed to HTML using XSLT.

If you would create directly a bison grammar description (this may
 be easier finaly), I should be able to process the bison file (I hope its
 grammar is not too complicated without C code) and get the final
 HTML. Till now I only thought to genereate antlr grammar description
 to check the grammar for more complicated errors. Simple errors (like
 multiple definitions for a symbol, no definition for a symbol) can be
 detected during translation to HTML. I can get you these errors for
 the file I attached previously, if you think this can help you.

I guess bison/LARL(1) and antlr/LL(k) are not the same, but who cares
 provideded that at least one of them is available.


"Bill Cox" <bill viasic.com> wrote in message
news:bhas3p$vtm$1 digitaldaemon.com...

 Peter Hercek wrote:

 So, if somebody wants to move D grammar on, please respond to this
  message (to group of course). But it requires a lot of source code
  studying unfortunately! I would tell that D grammar is protected through
  obcurity :o). Seriously now, I may be helpfull with some tools to look
  up trivial problems etc.


 I'm willing to take it on.  I've had a fair amount of experience with
 paser generators.  With bison's latest upgrades, and some work, I bet I
 get it to work.

 Bill
Aug 12 2003
parent reply Bill Cox <bill viasic.com> writes:
Hi, Peter.

I'll give it a try.  I'll start with your grammar file.

Bill

Peter Hercek wrote:

 Cool, I did it this way last time.
 Pulled out the grammar from web pages and created the text file
  (this was pain, because I was not able to automate this completely!)
 Generated an XML description of the grammar from the text file
  using antlr.
 The XML file was transormed to HTML using XSLT.
 
 If you would create directly a bison grammar description (this may
  be easier finaly), I should be able to process the bison file (I hope its
  grammar is not too complicated without C code) and get the final
  HTML. Till now I only thought to genereate antlr grammar description
  to check the grammar for more complicated errors. Simple errors (like
  multiple definitions for a symbol, no definition for a symbol) can be
  detected during translation to HTML. I can get you these errors for
  the file I attached previously, if you think this can help you.
 
 I guess bison/LARL(1) and antlr/LL(k) are not the same, but who cares
  provideded that at least one of them is available.
 
 
 "Bill Cox" <bill viasic.com> wrote in message
news:bhas3p$vtm$1 digitaldaemon.com...
 

Peter Hercek wrote:


So, if somebody wants to move D grammar on, please respond to this
 message (to group of course). But it requires a lot of source code
 studying unfortunately! I would tell that D grammar is protected through
 obcurity :o). Seriously now, I may be helpfull with some tools to look
 up trivial problems etc.


I'm willing to take it on.  I've had a fair amount of experience with
paser generators.  With bison's latest upgrades, and some work, I bet I
get it to work.

Bill
Aug 13 2003
parent Bill Cox <Bill_member pathlink.com> writes:
In article <bhdv9c$vum$1 digitaldaemon.com>, Bill Cox says...

Hi, Peter.

I'll give it a try.  I'll start with your grammar file.

Bill


Hi.

I've gotten started.  The grammar needs a lot of work.  Here's my changed
version.

There are several undefined rules.  I can make them up, but I could use some
help from Walter on a couple...

I need some help with these
---------------------------------
Invariant - from module.html
Type - used all over
BasicType2 - from declaration.html
FunctionDeclarator - from declaration.html

I think I can figure these out...
---------------------------------
Constructor
Destructor
StaticConstructor
StaticDestructor
Unittest

I haven't looked at these yet, but they aren't defined in the grammar file...
---------------------------------
Declarator
VersionAttribute
NumericLiteral
LabeledStatement
DoWhileStatement
AssignmentExpression
Parameter
AsmInstruction
Aug 14 2003
prev sibling parent reply Bill Cox <bill viasic.com> writes:
Walter wrote:

 "Ivan Senji" <ivan.senji public.srce.hr> wrote in message
 news:bgntfi$qhg$1 digitaldaemon.com...
 

Is it LL(1)? Can it be converted to LL(1)?


 
 
 No, it requires arbitrary lookahead.
 
 


Hi, Walter.

What parts require arbitrary lookahead?  Being able to YACC D seems a 
worthy goal.

Bill
Aug 08 2003
next sibling parent Burton Radons <loth users.sourceforge.net> writes:
Bill Cox wrote:

 Walter wrote:
 

 "Ivan Senji" <ivan.senji public.srce.hr> wrote in message
 news:bgntfi$qhg$1 digitaldaemon.com...


 Is it LL(1)? Can it be converted to LL(1)?




 No, it requires arbitrary lookahead.


 
 Hi, Walter.
 
 What parts require arbitrary lookahead?  Being able to YACC D seems a 
 worthy goal.


Distinguishing locals declarations and C-style casts from expressions.
Aug 08 2003
prev sibling parent reply Ilya Minkov <midiclub 8ung.at> writes:
Bill Cox wrote:

 Being able to YACC D seems a worthy goal.


What for? YACC is past and even "considered harmful"! New Bison supports 
GLR. There are tons of other GLR and LL(inf) parser generators out there.

-i.
Aug 08 2003
next sibling parent Bill Cox <bill viasic.com> writes:
Ilya Minkov wrote:

 Bill Cox wrote:
 

 Being able to YACC D seems a worthy goal.


 
 
 What for? YACC is past and even "considered harmful"! New Bison supports 
 GLR. There are tons of other GLR and LL(inf) parser generators out there.
 
 -i.
 


Hi, Ilya.

Support for GLR in Bison is quite new.  It wasn't in the general release 
last year.  Also, there's a performance penalty to use GLR.

I strongly encourage anyone making a new language format to create a 
machine verified version, whether it uses GLR or LR(1).

Until the rules have be verified by a parser generator, you can bet the 
rules are wrong.

Bill
Aug 08 2003
prev sibling parent "Mike Wynn" <mike.wynn l8night.co.uk> writes:
"Ilya Minkov" <midiclub 8ung.at> wrote in message
news:bh0jct$30ml$1 digitaldaemon.com...

 Bill Cox wrote:

 Being able to YACC D seems a worthy goal.


 What for? YACC is past and even "considered harmful"! New Bison supports
 GLR. There are tons of other GLR and LL(inf) parser generators out there.


there may be, but none will create D code .... Antlr does C++ and Java and I
believe it can rebuild itself (am looking for somewhere to get it
www.antlr.org seems to be missing! so might be able to squeeze a D version
out of it.
I don't fancy trying to port Bison to D.
Antlr also allows tree walkers to be defined which is very useful (LALR and
LL(n) only I believe)
Aug 08 2003