digitalmars.D - problem with declaration grammar?
- jerry quinn (16/16) Feb 18 2009 Hi there,
- Christopher Wright (12/35) Feb 18 2009 . Declaration -> Decl
- jerry quinn (16/51) Feb 18 2009 What you describe sounds like what I'd expect.
- Christopher Wright (3/42) Feb 19 2009 That looks to be in error.
- Sergey Gromov (32/90) Feb 19 2009 The grammar works the other way around:
- Ellery Newcomer (3/61) Feb 19 2009 You are correct. BasicType2 can match nothing. It should also be able to...
- jerry quinn (11/33) Feb 19 2009 As I'm looking at this further, there seems to be more issues. In parti...
- Ellery Newcomer (24/62) Feb 19 2009 yeah, if you haven't figured out by now, the grammar is a bunch of hooey...
- jerry quinn (5/85) Feb 19 2009 This is incorrect. We have
- Sergey Gromov (4/95) Feb 20 2009 Yes D2 grammar docs turn out to be wrong. I was using D1 grammar for my
- Jerry Quinn (7/74) Feb 20 2009 Cool. Do you feel like posting the whole thing somewhere?
- Ellery Newcomer (6/84) Feb 20 2009 knock yourself out http://www.personal.utulsa.edu/~ellery-newcomer/antlr...
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
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
Christopher Wright Wrote:jerry quinn wrote: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. JerryHi 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.
Feb 18 2009
Christopher Wright <dhasenan gmail.com> jerry quinn wrote:Christopher Wright Wrote:It's from the 1.0 grammar.jerry quinn wrote:What you describe sounds like what I'd expect.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.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
Thu, 19 Feb 2009 01:30:36 -0500, jerry quinn wrote:Christopher Wright Wrote: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.jerry quinn wrote: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. JerryHi 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.
Feb 19 2009
jerry quinn wrote:Christopher Wright Wrote:You are correct. BasicType2 can match nothing. It should also be able to match what it does above multiple times.jerry quinn wrote: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. JerryHi 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.
Feb 19 2009
Ellery Newcomer Wrote: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 PARSEMaybe 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. JerryYou are correct. BasicType2 can match nothing. It should also be able to match what it does above multiple times.
Feb 19 2009
jerry quinn wrote:Ellery Newcomer Wrote: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 misuseAs 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 PARSEMaybe 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. JerryYou are correct. BasicType2 can match nothing. It should also be able to match what it does above multiple times.
Feb 19 2009
Sergey Gromov Wrote:Thu, 19 Feb 2009 01:30:36 -0500, jerry quinn wrote: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.Christopher Wright Wrote: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 StructInitializerjerry quinn wrote: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. JerryHi 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.Finita la comedia.Unfortunately, not yet fini
Feb 19 2009
Thu, 19 Feb 2009 20:55:52 -0500, jerry quinn wrote:Sergey Gromov Wrote: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.Thu, 19 Feb 2009 01:30:36 -0500, jerry quinn wrote: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.Christopher Wright Wrote: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 StructInitializerjerry quinn wrote: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. JerryHi 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.
Feb 20 2009
Ellery Newcomer Wrote:jerry quinn wrote: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 epsilonEllery Newcomer Wrote: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 misuseAs 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 PARSEMaybe 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. JerryYou are correct. BasicType2 can match nothing. It should also be able to match what it does above multiple times.
Feb 20 2009
Jerry Quinn wrote:Ellery Newcomer Wrote: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.jerry quinn wrote:Cool. Do you feel like posting the whole thing somewhere?Ellery Newcomer Wrote: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 misuseAs 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 PARSEMaybe 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. JerryYou are correct. BasicType2 can match nothing. It should also be able to match what it does above multiple times.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 epsilondoh. I knew that.
Feb 20 2009