www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - problem with declaration grammar?

reply jerry quinn <jlquinn optonline.net> writes:
Hi there,

I'm not sure if I'm missing something, but I'm having trouble seeing that a
simple declaration will parse correctly with the D grammar.

If we take a declaration statment like:

int x = 3;

we have (my best guess):

DeclarationStatement -> Declaration
Declaration -> Decl
Decl -> BasicType Declarators ;
BasicType -> int
Declarators -> DeclaratorInitializer
DeclaratorInitializer -> Declarator = Initializer
Declarator -> BasicType2 Identifier
BasicType2 -> ????

I'm thinking that BasicType2 is optional here, rather than required as the
grammar shows.  Is that correct?

Thanks
Jerry
Feb 18 2009
next sibling parent reply Christopher Wright <dhasenan gmail.com> writes:
jerry quinn wrote:
 Hi there,
 
 I'm not sure if I'm missing something, but I'm having trouble seeing that a
simple declaration will parse correctly with the D grammar.
 
 If we take a declaration statment like:
 
 int x = 3;
 
 we have (my best guess):
 
 DeclarationStatement -> Declaration
 Declaration -> Decl
 Decl -> BasicType Declarators ;
 BasicType -> int
 Declarators -> DeclaratorInitializer
 DeclaratorInitializer -> Declarator = Initializer
 Declarator -> BasicType2 Identifier
 BasicType2 -> ????
 
 I'm thinking that BasicType2 is optional here, rather than required as the
grammar shows.  Is that correct?
 
 Thanks
 Jerry
. Declaration -> Decl . Decl -> BasicType Declarators . BasicType -> "int" . Declarators -> DeclaratorInitializer . DeclaratorInitializer -> Declarator "=" Initializer We agree up to here. . Declarator -> Identifier Here, you don't need BasicType2, and if you use it, you recurse, so using the rule Declarator -> BasicType2 Declarator here is useless. . Identifier -> "x" . Initializer -> ... -> "3"
Feb 18 2009
parent reply jerry quinn <jlquinn optonline.net> writes:
Christopher Wright Wrote:

 jerry quinn wrote:
 Hi there,
 
 I'm not sure if I'm missing something, but I'm having trouble seeing that a
simple declaration will parse correctly with the D grammar.
 
 If we take a declaration statment like:
 
 int x = 3;
 
 we have (my best guess):
 
 DeclarationStatement -> Declaration
 Declaration -> Decl
 Decl -> BasicType Declarators ;
 BasicType -> int
 Declarators -> DeclaratorInitializer
 DeclaratorInitializer -> Declarator = Initializer
 Declarator -> BasicType2 Identifier
 BasicType2 -> ????
 
 I'm thinking that BasicType2 is optional here, rather than required as the
grammar shows.  Is that correct?
 
 Thanks
 Jerry
. Declaration -> Decl . Decl -> BasicType Declarators . BasicType -> "int" . Declarators -> DeclaratorInitializer . DeclaratorInitializer -> Declarator "=" Initializer We agree up to here. . Declarator -> Identifier Here, you don't need BasicType2, and if you use it, you recurse, so using the rule Declarator -> BasicType2 Declarator here is useless.
What you describe sounds like what I'd expect. Maybe I'm missing something. The grammar shown in http://www.digitalmars.com/d/2.0/declaration.html has the following rules: BasicType2: * [ ] [ Expression ] [ Expression .. Expression ] [ Type ] delegate Parameters FunctionAttributesopt function Parameters FunctionAttributesopt Declarator: BasicType2 Declarator DeclaratorSuffixesopt BasicType2 Identifier DeclaratorSuffixesopt With this definition, I don't see how you can get Declarator->Identifier. Jerry
Feb 18 2009
next sibling parent Christopher Wright <dhasenan gmail.com> writes:
jerry quinn wrote:
 Christopher Wright Wrote:
 
 jerry quinn wrote:
 Hi there,

 I'm not sure if I'm missing something, but I'm having trouble seeing that a
simple declaration will parse correctly with the D grammar.

 If we take a declaration statment like:

 int x = 3;

 we have (my best guess):

 DeclarationStatement -> Declaration
 Declaration -> Decl
 Decl -> BasicType Declarators ;
 BasicType -> int
 Declarators -> DeclaratorInitializer
 DeclaratorInitializer -> Declarator = Initializer
 Declarator -> BasicType2 Identifier
 BasicType2 -> ????

 I'm thinking that BasicType2 is optional here, rather than required as the
grammar shows.  Is that correct?

 Thanks
 Jerry
. Declaration -> Decl . Decl -> BasicType Declarators . BasicType -> "int" . Declarators -> DeclaratorInitializer . DeclaratorInitializer -> Declarator "=" Initializer We agree up to here. . Declarator -> Identifier Here, you don't need BasicType2, and if you use it, you recurse, so using the rule Declarator -> BasicType2 Declarator here is useless.
What you describe sounds like what I'd expect.
It's from the 1.0 grammar.
 Maybe I'm missing something.  The grammar shown in
http://www.digitalmars.com/d/2.0/declaration.html has the following rules:
That looks to be in error.
Feb 19 2009
prev sibling next sibling parent Sergey Gromov <snake.scaly gmail.com> writes:
Thu, 19 Feb 2009 01:30:36 -0500, jerry quinn wrote:

 Christopher Wright Wrote:
 
 jerry quinn wrote:
 Hi there,
 
 I'm not sure if I'm missing something, but I'm having trouble seeing that a
simple declaration will parse correctly with the D grammar.
 
 If we take a declaration statment like:
 
 int x = 3;
 
 we have (my best guess):
 
 DeclarationStatement -> Declaration
 Declaration -> Decl
 Decl -> BasicType Declarators ;
 BasicType -> int
 Declarators -> DeclaratorInitializer
 DeclaratorInitializer -> Declarator = Initializer
 Declarator -> BasicType2 Identifier
 BasicType2 -> ????
 
 I'm thinking that BasicType2 is optional here, rather than required as the
grammar shows.  Is that correct?
 
 Thanks
 Jerry
. Declaration -> Decl . Decl -> BasicType Declarators . BasicType -> "int" . Declarators -> DeclaratorInitializer . DeclaratorInitializer -> Declarator "=" Initializer We agree up to here. . Declarator -> Identifier Here, you don't need BasicType2, and if you use it, you recurse, so using the rule Declarator -> BasicType2 Declarator here is useless.
What you describe sounds like what I'd expect. Maybe I'm missing something. The grammar shown in http://www.digitalmars.com/d/2.0/declaration.html has the following rules: BasicType2: * [ ] [ Expression ] [ Expression .. Expression ] [ Type ] delegate Parameters FunctionAttributesopt function Parameters FunctionAttributesopt Declarator: BasicType2 Declarator DeclaratorSuffixesopt BasicType2 Identifier DeclaratorSuffixesopt With this definition, I don't see how you can get Declarator->Identifier. Jerry
The grammar works the other way around: int x = 3 ; int -> BasicType(int) // this is either Decl or Type, need more tokens, expect Declarators, // Declarator, or Declarator2 ----- x -> Identifier(x) // either DeclaratorInitializer (Declarators), Declarator, // IdentifierList (not expecting), StructMemberInitializer (not // expecting), or PrimaryExpression (not expecting) // therefore expecting '=' or DeclaratorSuffixes ----- = -> = // token // Identifier(x) = -> definitely DeclaratorInitializer, expecting // Initializer, that is , either void, AssignExpression, // ArrayInitializer, or StructInitializer ----- 3 -> IntegerLiteral(3) -> PrimaryExpression(3) // may be some sort of other expression, need more tokens ----- ; -> ; // token // not a part of an expression ----- PrimaryExpression(3) -> AssignExpression(3) Identifier(x) = AssignExpression(3) -> DeclaratorInitializer(x=3) // DeclaratorInitializer(x=3) is Declarators, expect ',' but actually // have ';' next, so DeclaratorInitializer(x=3) -> Declarators(x=3) ----- BasicType(int) DeclaratorInitializer(x=3) ; -> Decl(int x=3;) Finita la comedia.
Feb 19 2009
prev sibling parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
jerry quinn wrote:
 Christopher Wright Wrote:
 
 jerry quinn wrote:
 Hi there,

 I'm not sure if I'm missing something, but I'm having trouble seeing that a
simple declaration will parse correctly with the D grammar.

 If we take a declaration statment like:

 int x = 3;

 we have (my best guess):

 DeclarationStatement -> Declaration
 Declaration -> Decl
 Decl -> BasicType Declarators ;
 BasicType -> int
 Declarators -> DeclaratorInitializer
 DeclaratorInitializer -> Declarator = Initializer
 Declarator -> BasicType2 Identifier
 BasicType2 -> ????

 I'm thinking that BasicType2 is optional here, rather than required as the
grammar shows.  Is that correct?

 Thanks
 Jerry
. Declaration -> Decl . Decl -> BasicType Declarators . BasicType -> "int" . Declarators -> DeclaratorInitializer . DeclaratorInitializer -> Declarator "=" Initializer We agree up to here. . Declarator -> Identifier Here, you don't need BasicType2, and if you use it, you recurse, so using the rule Declarator -> BasicType2 Declarator here is useless.
What you describe sounds like what I'd expect. Maybe I'm missing something. The grammar shown in http://www.digitalmars.com/d/2.0/declaration.html has the following rules: BasicType2: * [ ] [ Expression ] [ Expression .. Expression ] [ Type ] delegate Parameters FunctionAttributesopt function Parameters FunctionAttributesopt Declarator: BasicType2 Declarator DeclaratorSuffixesopt BasicType2 Identifier DeclaratorSuffixesopt With this definition, I don't see how you can get Declarator->Identifier. Jerry
You are correct. BasicType2 can match nothing. It should also be able to match what it does above multiple times.
Feb 19 2009
parent reply jerry quinn <jlquinn optonline.net> writes:
Ellery Newcomer Wrote:
 Maybe I'm missing something.  The grammar shown in
http://www.digitalmars.com/d/2.0/declaration.html has the following rules:
 
 BasicType2:
         *
         [ ]
         [ Expression ]
         [ Expression .. Expression ]
         [ Type ]
         delegate Parameters FunctionAttributesopt
         function Parameters FunctionAttributesopt
 
 Declarator:
         BasicType2 Declarator DeclaratorSuffixesopt
         BasicType2 Identifier DeclaratorSuffixesopt
 
 With this definition, I don't see how you can get Declarator->Identifier.
 
 Jerry
 
You are correct. BasicType2 can match nothing. It should also be able to match what it does above multiple times.
As I'm looking at this further, there seems to be more issues. In particular, I don't think the grammar can parse: int (*x)(char); as specified. Doing so gives (my best attempt) Decl -> BasicType Declarators ; BasicType -> int Declarators -> DeclaratorInitializer DeclaratorInitializer -> Declarator Declarator -> BasicType2 Identifier DeclaratorSuffixes BasicType2 -> NULL (assuming that the grammar should be revised like this) Identifier -> BAD PARSE
Feb 19 2009
parent Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
jerry quinn wrote:
 Ellery Newcomer Wrote:
 Maybe I'm missing something.  The grammar shown in
http://www.digitalmars.com/d/2.0/declaration.html has the following rules:

 BasicType2:
         *
         [ ]
         [ Expression ]
         [ Expression .. Expression ]
         [ Type ]
         delegate Parameters FunctionAttributesopt
         function Parameters FunctionAttributesopt

 Declarator:
         BasicType2 Declarator DeclaratorSuffixesopt
         BasicType2 Identifier DeclaratorSuffixesopt

 With this definition, I don't see how you can get Declarator->Identifier.

 Jerry
You are correct. BasicType2 can match nothing. It should also be able to match what it does above multiple times.
As I'm looking at this further, there seems to be more issues. In particular, I don't think the grammar can parse: int (*x)(char); as specified. Doing so gives (my best attempt) Decl -> BasicType Declarators ; BasicType -> int Declarators -> DeclaratorInitializer DeclaratorInitializer -> Declarator Declarator -> BasicType2 Identifier DeclaratorSuffixes BasicType2 -> NULL (assuming that the grammar should be revised like this) Identifier -> BAD PARSE
yeah, if you haven't figured out by now, the grammar is a bunch of hooey. I spent like a month building an ANTLR grammar based on the above, and then realized much of it was garbage. Then I spent two months going through the source code and rewriting most of the rules. Just got done with it a week or two ago :) That was all version 1, but it looks the same, so if memory serves the above rules should look something like this: BasicType2_x: * [ ] [ Expression ] [ Expression .. Expression ] [ Type ] delegate Parameters FunctionAttributesopt function Paramters FunctionAttributesopt BasicType2: BasicType2_x BasicType2 BasicType2_x epsilon Declarator: BasicType2 Identifier DeclaratorSuffixesopt BasicType2 ( Declarator ) DeclaratorSuffixesopt Apologies for any BNF misuse
Feb 19 2009
prev sibling next sibling parent reply jerry quinn <jlquinn optonline.net> writes:
Sergey Gromov Wrote:

 Thu, 19 Feb 2009 01:30:36 -0500, jerry quinn wrote:
 
 Christopher Wright Wrote:
 
 jerry quinn wrote:
 Hi there,
 
 I'm not sure if I'm missing something, but I'm having trouble seeing that a
simple declaration will parse correctly with the D grammar.
 
 If we take a declaration statment like:
 
 int x = 3;
 
 we have (my best guess):
 
 DeclarationStatement -> Declaration
 Declaration -> Decl
 Decl -> BasicType Declarators ;
 BasicType -> int
 Declarators -> DeclaratorInitializer
 DeclaratorInitializer -> Declarator = Initializer
 Declarator -> BasicType2 Identifier
 BasicType2 -> ????
 
 I'm thinking that BasicType2 is optional here, rather than required as the
grammar shows.  Is that correct?
 
 Thanks
 Jerry
. Declaration -> Decl . Decl -> BasicType Declarators . BasicType -> "int" . Declarators -> DeclaratorInitializer . DeclaratorInitializer -> Declarator "=" Initializer We agree up to here. . Declarator -> Identifier Here, you don't need BasicType2, and if you use it, you recurse, so using the rule Declarator -> BasicType2 Declarator here is useless.
What you describe sounds like what I'd expect. Maybe I'm missing something. The grammar shown in http://www.digitalmars.com/d/2.0/declaration.html has the following rules: BasicType2: * [ ] [ Expression ] [ Expression .. Expression ] [ Type ] delegate Parameters FunctionAttributesopt function Parameters FunctionAttributesopt Declarator: BasicType2 Declarator DeclaratorSuffixesopt BasicType2 Identifier DeclaratorSuffixesopt With this definition, I don't see how you can get Declarator->Identifier. Jerry
The grammar works the other way around: int x = 3 ; int -> BasicType(int) // this is either Decl or Type, need more tokens, expect Declarators, // Declarator, or Declarator2 ----- x -> Identifier(x) // either DeclaratorInitializer (Declarators), Declarator, // IdentifierList (not expecting), StructMemberInitializer (not // expecting), or PrimaryExpression (not expecting) // therefore expecting '=' or DeclaratorSuffixes ----- = -> = // token // Identifier(x) = -> definitely DeclaratorInitializer, expecting // Initializer, that is , either void, AssignExpression, // ArrayInitializer, or StructInitializer
This is incorrect. We have BasicType(int) Identifier(x) '= ' You're suggesting the Identifier begins DeclaratorInitializer, but it must start with a Declarator. We don't have one, because Declarator must start with BasicType2. This is where I think the bug in the grammar is. If BasicType2 were optional, then the parse would complete as you showed.
 Finita la comedia.
Unfortunately, not yet fini
Feb 19 2009
parent Sergey Gromov <snake.scaly gmail.com> writes:
Thu, 19 Feb 2009 20:55:52 -0500, jerry quinn wrote:

 Sergey Gromov Wrote:
 
 Thu, 19 Feb 2009 01:30:36 -0500, jerry quinn wrote:
 
 Christopher Wright Wrote:
 
 jerry quinn wrote:
 Hi there,
 
 I'm not sure if I'm missing something, but I'm having trouble seeing that a
simple declaration will parse correctly with the D grammar.
 
 If we take a declaration statment like:
 
 int x = 3;
 
 we have (my best guess):
 
 DeclarationStatement -> Declaration
 Declaration -> Decl
 Decl -> BasicType Declarators ;
 BasicType -> int
 Declarators -> DeclaratorInitializer
 DeclaratorInitializer -> Declarator = Initializer
 Declarator -> BasicType2 Identifier
 BasicType2 -> ????
 
 I'm thinking that BasicType2 is optional here, rather than required as the
grammar shows.  Is that correct?
 
 Thanks
 Jerry
. Declaration -> Decl . Decl -> BasicType Declarators . BasicType -> "int" . Declarators -> DeclaratorInitializer . DeclaratorInitializer -> Declarator "=" Initializer We agree up to here. . Declarator -> Identifier Here, you don't need BasicType2, and if you use it, you recurse, so using the rule Declarator -> BasicType2 Declarator here is useless.
What you describe sounds like what I'd expect. Maybe I'm missing something. The grammar shown in http://www.digitalmars.com/d/2.0/declaration.html has the following rules: BasicType2: * [ ] [ Expression ] [ Expression .. Expression ] [ Type ] delegate Parameters FunctionAttributesopt function Parameters FunctionAttributesopt Declarator: BasicType2 Declarator DeclaratorSuffixesopt BasicType2 Identifier DeclaratorSuffixesopt With this definition, I don't see how you can get Declarator->Identifier. Jerry
The grammar works the other way around: int x = 3 ; int -> BasicType(int) // this is either Decl or Type, need more tokens, expect Declarators, // Declarator, or Declarator2 ----- x -> Identifier(x) // either DeclaratorInitializer (Declarators), Declarator, // IdentifierList (not expecting), StructMemberInitializer (not // expecting), or PrimaryExpression (not expecting) // therefore expecting '=' or DeclaratorSuffixes ----- = -> = // token // Identifier(x) = -> definitely DeclaratorInitializer, expecting // Initializer, that is , either void, AssignExpression, // ArrayInitializer, or StructInitializer
This is incorrect. We have BasicType(int) Identifier(x) '= ' You're suggesting the Identifier begins DeclaratorInitializer, but it must start with a Declarator. We don't have one, because Declarator must start with BasicType2. This is where I think the bug in the grammar is. If BasicType2 were optional, then the parse would complete as you showed.
Yes D2 grammar docs turn out to be wrong. I was using D1 grammar for my parsing exercise. In D1, Declarator can be just Identifier. Therefore I was able to reduce the statement correctly.
Feb 20 2009
prev sibling parent reply Jerry Quinn <jlquinn optonline.net> writes:
Ellery Newcomer Wrote:

 jerry quinn wrote:
 Ellery Newcomer Wrote:
 Maybe I'm missing something.  The grammar shown in
http://www.digitalmars.com/d/2.0/declaration.html has the following rules:

 BasicType2:
         *
         [ ]
         [ Expression ]
         [ Expression .. Expression ]
         [ Type ]
         delegate Parameters FunctionAttributesopt
         function Parameters FunctionAttributesopt

 Declarator:
         BasicType2 Declarator DeclaratorSuffixesopt
         BasicType2 Identifier DeclaratorSuffixesopt

 With this definition, I don't see how you can get Declarator->Identifier.

 Jerry
You are correct. BasicType2 can match nothing. It should also be able to match what it does above multiple times.
As I'm looking at this further, there seems to be more issues. In particular, I don't think the grammar can parse: int (*x)(char); as specified. Doing so gives (my best attempt) Decl -> BasicType Declarators ; BasicType -> int Declarators -> DeclaratorInitializer DeclaratorInitializer -> Declarator Declarator -> BasicType2 Identifier DeclaratorSuffixes BasicType2 -> NULL (assuming that the grammar should be revised like this) Identifier -> BAD PARSE
yeah, if you haven't figured out by now, the grammar is a bunch of hooey. I spent like a month building an ANTLR grammar based on the above, and then realized much of it was garbage. Then I spent two months going through the source code and rewriting most of the rules. Just got done with it a week or two ago :) That was all version 1, but it looks the same, so if memory serves the above rules should look something like this: BasicType2_x: * [ ] [ Expression ] [ Expression .. Expression ] [ Type ] delegate Parameters FunctionAttributesopt function Paramters FunctionAttributesopt BasicType2: BasicType2_x BasicType2 BasicType2_x epsilon Declarator: BasicType2 Identifier DeclaratorSuffixesopt BasicType2 ( Declarator ) DeclaratorSuffixesopt Apologies for any BNF misuse
Cool. Do you feel like posting the whole thing somewhere? As an aside comment, it might be better from a grammar perspective to make usage of BasicType2 optional, rather than have the epsilon in the BasicType2 rule itself. Then every rule would consume at least 1 token, and _opt is the only expansion shortcut needed. In the form show, you can simplify the BasicType2 rule to BasicType2: BasicType2 BasicType2_x epsilon
Feb 20 2009
parent Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
Jerry Quinn wrote:
 Ellery Newcomer Wrote:
 
 jerry quinn wrote:
 Ellery Newcomer Wrote:
 Maybe I'm missing something.  The grammar shown in
http://www.digitalmars.com/d/2.0/declaration.html has the following rules:

 BasicType2:
         *
         [ ]
         [ Expression ]
         [ Expression .. Expression ]
         [ Type ]
         delegate Parameters FunctionAttributesopt
         function Parameters FunctionAttributesopt

 Declarator:
         BasicType2 Declarator DeclaratorSuffixesopt
         BasicType2 Identifier DeclaratorSuffixesopt

 With this definition, I don't see how you can get Declarator->Identifier.

 Jerry
You are correct. BasicType2 can match nothing. It should also be able to match what it does above multiple times.
As I'm looking at this further, there seems to be more issues. In particular, I don't think the grammar can parse: int (*x)(char); as specified. Doing so gives (my best attempt) Decl -> BasicType Declarators ; BasicType -> int Declarators -> DeclaratorInitializer DeclaratorInitializer -> Declarator Declarator -> BasicType2 Identifier DeclaratorSuffixes BasicType2 -> NULL (assuming that the grammar should be revised like this) Identifier -> BAD PARSE
yeah, if you haven't figured out by now, the grammar is a bunch of hooey. I spent like a month building an ANTLR grammar based on the above, and then realized much of it was garbage. Then I spent two months going through the source code and rewriting most of the rules. Just got done with it a week or two ago :) That was all version 1, but it looks the same, so if memory serves the above rules should look something like this: BasicType2_x: * [ ] [ Expression ] [ Expression .. Expression ] [ Type ] delegate Parameters FunctionAttributesopt function Paramters FunctionAttributesopt BasicType2: BasicType2_x BasicType2 BasicType2_x epsilon Declarator: BasicType2 Identifier DeclaratorSuffixesopt BasicType2 ( Declarator ) DeclaratorSuffixesopt Apologies for any BNF misuse
Cool. Do you feel like posting the whole thing somewhere?
knock yourself out http://www.personal.utulsa.edu/~ellery-newcomer/antlrd.g D version 1, ANTLR version 2, note it isn't really complete yet; I haven't gotten around to AST construction. Oh, and don't look at the lexer part. It's ugly as sin.
 
 As an aside comment, it might be better from a grammar perspective to make
usage of BasicType2 optional, rather than have the epsilon in the BasicType2
rule itself.  Then every rule would consume at least 1 token, and _opt is the
only expansion shortcut needed.
 
 In the form show, you can simplify the BasicType2 rule to
 
 BasicType2:
   BasicType2 BasicType2_x
   epsilon
 
doh. I knew that.
Feb 20 2009