[C] declarationSpecifiers is too greedy, take initDeclaratorList as typedefName

[kevemueller]

I am parsing C with the current C grammar in Java language and try to make sense of the parse tree.
I believe to have found a bug similar to #1979, in which a typedef appears instead of a directDeclarator.
As illustration, first a good parse:

typedef unsigned const int* x;

parses as:

Note the clear distinction between declarationSpecifiers and initDeclaratorList.

Whereas the following

typedef unsigned const int x;

parses as

The initDeclaratorList is missing, instead of being a directDeclarator the x is treated as yet another typeSpecifier.

The same erratic behaviour can be observed with

extern int* x;
extern int x;

The former being parsed properly, the latter not.

I am currently trying to write some post-processing logic to detect this, but it is not easy to distinguish the cases and it definitely messes with the situation at the wrong place (in the visitor) instead of in the grammar.

Any help is appreciated, this is currently a major blocker for proceeding with ANTLR (and this grammar).

[kaby76]

In the input string extern int x;, the x is parsed as a declarationSpecifier. It should be parsed as an initDeclaratorList. You can see this because the grammar is ambiguous:

11/14-06:37:56 ~/issues/g4-current/c/Generated-CSharp
$ trparse --ambig x | trtree
CSharp 0 x success 0.0449465
compilationUnit
├── translationUnit
│   ├── externalDeclaration
│   │   └── declaration
│   │       ├── declarationSpecifiers
│   │       │   ├── declarationSpecifier
│   │       │   │   └── storageClassSpecifier
│   │       │   │       └── Extern
│   │       │   │           └── "extern"
│   │       │   └── declarationSpecifier
│   │       │       └── typeSpecifier
│   │       │           ├── Attribute Whitespace Value ' ' chnl:HIDDEN
│   │       │           └── Int
│   │       │               └── "int"
│   │       ├── initDeclaratorList
│   │       │   └── initDeclarator
│   │       │       └── declarator
│   │       │           ├── pointer
│   │       │           │   └── Star
│   │       │           │       └── "*"
│   │       │           └── directDeclarator
│   │       │               ├── Attribute Whitespace Value ' ' chnl:HIDDEN
│   │       │               └── Identifier
│   │       │                   └── "x"
│   │       └── Semi
│   │           └── ";"
│   └── externalDeclaration
│       └── declaration
│           ├── declarationSpecifiers
│           │   ├── declarationSpecifier
│           │   │   └── storageClassSpecifier
│           │   │       ├── Attribute Newline Value '\r\n' chnl:HIDDEN
│           │   │       └── Extern
│           │   │           └── "extern"
│           │   ├── declarationSpecifier
│           │   │   └── typeSpecifier
│           │   │       ├── Attribute Whitespace Value ' ' chnl:HIDDEN
│           │   │       └── Int
│           │   │           └── "int"
│           │   └── declarationSpecifier
│           │       └── typeSpecifier
│           │           └── typedefName
│           │               ├── Attribute Whitespace Value ' ' chnl:HIDDEN
│           │               └── Identifier
│           │                   └── "x"
│           └── Semi
│               └── ";"
├── Attribute Newline Value '\r\n' chnl:HIDDEN
└── EOF
    └── ""

compilationUnit
├── translationUnit
│   ├── externalDeclaration
│   │   └── declaration
│   │       ├── declarationSpecifiers
│   │       │   ├── declarationSpecifier
│   │       │   │   └── storageClassSpecifier
│   │       │   │       └── Extern
│   │       │   │           └── "extern"
│   │       │   └── declarationSpecifier
│   │       │       └── typeSpecifier
│   │       │           ├── Attribute Whitespace Value ' ' chnl:HIDDEN
│   │       │           └── Int
│   │       │               └── "int"
│   │       ├── initDeclaratorList
│   │       │   └── initDeclarator
│   │       │       └── declarator
│   │       │           ├── pointer
│   │       │           │   └── Star
│   │       │           │       └── "*"
│   │       │           └── directDeclarator
│   │       │               ├── Attribute Whitespace Value ' ' chnl:HIDDEN
│   │       │               └── Identifier
│   │       │                   └── "x"
│   │       └── Semi
│   │           └── ";"
│   └── externalDeclaration
│       └── declaration
│           ├── declarationSpecifiers
│           │   ├── declarationSpecifier
│           │   │   └── storageClassSpecifier
│           │   │       ├── Attribute Newline Value '\r\n' chnl:HIDDEN
│           │   │       └── Extern
│           │   │           └── "extern"
│           │   └── declarationSpecifier
│           │       └── typeSpecifier
│           │           ├── Attribute Whitespace Value ' ' chnl:HIDDEN
│           │           └── Int
│           │               └── "int"
│           ├── initDeclaratorList
│           │   └── initDeclarator
│           │       └── declarator
│           │           └── directDeclarator
│           │               ├── Attribute Whitespace Value ' ' chnl:HIDDEN
│           │               └── Identifier
│           │                   └── "x"
│           └── Semi
│               └── ";"
├── Attribute Newline Value '\r\n' chnl:HIDDEN
└── EOF
    └── ""


11/14-06:38:02 ~/issues/g4-current/c/Generated-CSharp
$

Essentially, the grammar needs to disallow the interpretation of "x" as a typeSpecifier. To do that, it needs a symbol table. The tricky part is that the semantic predicate must be "hoisted" to be contained in declarationSpecifiers. This is the one thing I cannot stand about Antlr.

[kevemueller]

Is that short for it will never work? I have no feelings about ANTLR, I remember passing by here several times over the last decades and always ending up writing my own parser instead. But for "C" this did not look like a viable option, so I dived in...

Just For the record, here is the current workaround that I use inside public T visitDeclaration(final DeclarationContext ctx);

It detects the illegal combinations of empty initDeclaratorList and pops the last typedef from the declarationSpecifiers. Quite a hack, I trust I will trip over it later in time.

	final DeclarationSpecifiersContext declarationSpecifiers = ctx.declarationSpecifiers();
	final InitDeclaratorListContext initDeclaratorList = ctx.initDeclaratorList();
	final List<InitDeclarator> initDeclarators;
	if (null == initDeclaratorList) {
		final DeclarationSpecifierContext fix = (DeclarationSpecifierContext) declarationSpecifiers
				.getChild(declarationSpecifiers.getChildCount() - 1);
		declarationSpecifiers.removeLastChild();
		final String identifier = fix.typeSpecifier().typedefName().Identifier().getText();
		initDeclarators = List.of(new InitDeclarator(0, identifier));
	} else {
		initDeclarators = visitInitDeclaratorList(initDeclaratorList).getValue();
	}

[kaby76]

Yes, the grammar cannot work without semantics. The ISO Spec EBNF is insufficient to get the right parse. It is also the reason why the generated parse is slow, because Antlr4 computes all possible parse states until it can make--or is forced to make--a decision ultimately for the parse. Antlr4 is a great tool to discover why a grammar is poorly written. But, if the grammar is left as is with ambiguities y and max-k's, it performs terribly.

In the near term, I'll add a symbol table to address this problem, and likely a few others.

Going forward, the grammar, which is derived from a draft of the ISO Spec, will be preserved to illustrate why the ISO Spec EBNF requires semantics.

In the long term, the plan is to purchase the ISO Spec, scrape the EBNF, convert it to Antlr4, refactor, and add semantic predicates — all completely automated and reproducible, so that future versions of the ISO Spec can be handled. No one should be hand-editing the grammar.

In addition, a macro processor needs to be added. I'm not sure whether to write that from the Spec, or to use a native processor. Parsing cannot be performed on a pre-processed C input.

[galacticstudios]

Could it be fixed by changing declarationSpecifiers? Right now, it seems to allow any number of specs, so that you could write 'float int foo;', which obviously makes no sense.

It seems to me a variable can have a declarationSpecifier, either int, float, typedefName, long, etc. - but only one of those. Some of those declarationSpecifiers can be modified, like an int can be modified with long, signed, or unsigned. But a typedef name can't be modified by another declarationSpecifier.

Maybe the solution is to split up declarationSpecifier into the base types and the types that can be modified. Also have a rule with the allowable modifiers. Then, instead of the declarationSpecifiers rule, have a rule that's more strict about what it will allow.

[kaby76]

You could try fiddling with the grammar and see if you can solve the problem.

But, this is what I was thinking of. Add a predicate to the expression declarationSpecifier+ in declarationSpecifiers. See the modified rule below. The "symbol table" function would query the lookahead to test the symbol "x" and return "false" because it is not a type. In this implementation, I wrote a stub. A real symbol table would need to be implemented, but it's not hard to do.

grammar C;

@parser::members {
bool IsType()
{
	bool IsType()
	{
		return (this.InputStream as CommonTokenStream).LT(1).Text != "x";
	}
}

declarationSpecifiers
    : ( {this.IsType()}? declarationSpecifier)+
    ;

With this modification, parsing extern int x; would yield the correct tree, remove the ambiguity, and keep the grammar identical to the EBNF in the ISO Spec, more or less (see "Section 6.7 Declarations" in https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2310.pdf).

[kevemueller]

Keeping the grammar close to the ISO Spec EBNF has a lot of merits. It should accept the same language.
I understand that ANTLR4 can actually do, what @kaby76 explained in his previous comment and make the grammar "smarter".
Personally I have now switched to CDT to parse my input, but I would definitely come back here as ANTLR4 is way lighter and straightforward to use.

[kaby76]

I started PR #4682 to fix this and other problems. I'm not sure whether I will fix the max-k problems in this round but at least some of the ambiguity. I will update to ISO/IEC 9899:2024 in another PR.