Summary: 'C', is it's grammar context sensitive ?

[Christopher R Volpe]

In article <1990Aug30.223440.7377 at NCoast.ORG>, ramsey at NCoast.ORG (Cedric
Ramsey) writes:
|>When I wrote the last message I was had the notion that typedef names
|>could be used before they are declared, in ansi 'C'. I guess that was 
|>a false assumption. Because the following, I think, is illegal:
|>
|>typedef struct vehical {
|>  make_t make;
|>  style_t style;
|>  owner_t owner;
|>} vehical_t;
|>
|>typedef ... owner_t;
|>typedef ... make_t;
|>typedef ... style_t;

Yeah, it's illegal. The only thing that can be used without an explicit
declaration is a function, which would then be implicitly declared
as returning int. 
|>
|>The compiler must know ahead of time that make_t, style_t and owner_t 
|>are type names. That way, the scanner, it could lookup the name in the 
|>symbol table and see that it is a typedef name and return TYPEDEF_NAME.
|>I don't have the ansi draft; only K&R2. K&R2 doesn't mention, at least
|>I don't recall reading it, that typedef names must occur before they are
|>used so these points a purely speculative. Also K&R2 doesn't specify if
|>the following is legal:
|>
|>typedef unsigned char uchar_t;
|>uchar_t uchar_t;
|>
|>I would say that this is illegal, even though uchar_t is not a keyword.
|>Why, because ... I don't know, maybe because it would be harder to parse.

It's illegal because typedef names are in the same name space as
objects according to section A11.1 of K&R2. Therefore, an identifier
cannot be declared as both a typedef name and an object in the
same scope. The typedef name can be redeclared in an inner block, however.

|>
|>In lue of the above speculations, the compiler wouldn't have to make 
|>multiple passes to collect typedef names. I hope this is true or 
|>the grammar at back of K&R2 would not be acceptable to yacc, as claimed,
|>without a rewrite, I could be wrong though.  

The grammar is not claimed to be acceptable to yacc as-is. Section
A13 says that the grammar is acceptable to yacc if the production
"typedef_name: identifier" is removed and typedef_name is made a 
terminal symbol.

|>If you guys agree that 'C' is context sensitive then what languages
|>truely are context-free, if any. 

Let's clarify some terminology here: First, all context free languages
are context sensitive and all context free grammars are context sensitive.
There is a hierarchy involved here. The concepts are not mutually
exclusive, but rather the former is a superset of the latter. When you
say "context sensitive", you really mean "non context free". Second, there
is a distinction between a grammar being context free and a language
being context free. A language is context free if it can be completely
described by a context free grammar. The C grammar is context free but
it does not fully describe the language. No programming language that
requires that any identifiers be declared before they are used is a 
context free language. Such requirements are almost always enforced
semantically rather than syntactically in order to allow use of a 
context free grammar. (This is done using a symbol table.) Pascal
is not a context free language either, for the same reason.

==================
Chris Volpe
G.E. Corporate R&D
volpecr at crd.ge.com