Context-Free Grammars? What about arrays?

[Jonathan M Davis]

On Friday 11 February 2011 01:03:21 %u wrote:
> Hi,
> 
> I think I'm having a little trouble understanding what's meant by
> context-free grammar. I've read that D is context-free, but is it really?
> What about an expression like:
> 
> int[U] s;
> 
> ? You can't tell -- without looking at the context -- whether U is a data
> type or a number, and so because associative arrays and regular arrays are
> syntactically different elements of the language, the syntax of D is tied
> in with its semantics, just like in C++.
> 
> So is D really context-free? Or am I misunderstanding the meaning of the
> term?

Yes. You're misunderstanding. It's actually quite difficult to parse a language if 
its grammar isn't context-free. You really should read up in context-free 
grammars if you want to understand it properly.

Context-free means that it's unambiguous as to which grammar rule is to be 
applied at any point during the parsing process. In this case, U is a symbol. 
The parser probably doesn't care about much more than that. That symbol could 
end up being a number or a type. And actually, it probably isn't even that hard. 
U is a class, struct, alias, or template argument. The template argument and 
alias would be substituted with a real type or value before the compiler had to 
determine what type int[U] was.

Not to mention, the context-free grammar is entirely for parsing tokens into an 
abstract syntax tree. The compiler then has to do whatever it does with the AST 
to actually generate assembly from it. So, as long as the parser can parse it 
into the AST, it could be the next stage's problem to determine what that really 
means.

Regardless, I suggest that you read a compiler book if you really want to 
understand context-free grammars. I have "Compiler Construction: Principles and 
Practices" by Kenneth C. Louden, which is quite good, but the most popular one 
is the so-called "dragon" book. I'm not sure what it's actual title is though.

- Jonathan M Davis