Context-Free Grammars? What about arrays?

[Jacob Carlborg]

On 2011-02-11 10:37, Jonathan M Davis wrote:
> 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

The title of the so called "dragon" book is "Compilers: Principles, 
Techniques, and Tools" and can be found here:

http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811/ref=sr_1_1?s=books&ie=UTF8&qid=1297440057&sr=1-1

It's also listed on the bookshelf page on the DigitalMars site.

-- 
/Jacob Carlborg