4 ms·

The thing that makes C have a context-sensitive grammar is parsing non-keyword type names (typedefs), not the preprocessor, which is a separate text transformat

The thing that makes C have a context-sensitive grammar is parsing non-keyword type names (typedefs), not the preprocessor, which is a separate text transformation run before the C parser sees the text. The specific problem is this has two parses: foo * bar; It's either an expression multiplying foo by bar; or, if foo is a type, it's a declaration of a variable foo pointing to values of type bar. The normal way this is handled is to inform the lexer of known type names (e.g. by letting it peek at the symbol table) whenever it parses an identifier, so it can produce a type name token instead.

yakubin 5y ago
This is another place where it's context-sensitive. To make everyone happy, I could rephrase my claim to "C preprocessor grammar is context-sensitive". This has practical implications for e.g. what gets substituted where by the preprocessor. And in my claim this context-sensitivity means that we get different sequences of tokens in different places for the same input. Your example shows that we get different ASTs for the same input but different type information, although we still get the same sequence of tokens. Getting a different sequence of tokens is much more confusing to me than getting a different AST (or maybe I just got used to that with a life of experience with C++). But generally I disagree that preprocessor is separate from C for the following reasons: 1. It is specified by the C standard. 2. Different C compilers implement it differently, just like they implement other parts of C differently. 3. There is some truth in the claim that it is a separate text transformation, but here I also do not agree entirely, because the C standard doesn't say that the preprocessor outputs text. It says that it outputs tokens and those tokens are then converted to tokens of C proper[1]. It is also clear that this model of "text transformation" is also not entirely what happens in real world compilers, because if it did we wouldn't get good backtraces for tokens that went out of the preprocessor after substitution. Maybe GCC serializes it to text at some point, but clearly it gets more information out of it than what a naive interpretation of the phrase "text transformation" would suggest. [1]: Translation phase 7 of the C11 standard: > Each preprocessing token is converted into a token.

yakubin 5y ago

This is another place where it's context-sensitive. To make everyone happy, I could rephrase my claim to "C preprocessor grammar is context-sensitive". This has practical implications for e.g. what gets substituted where by the preprocessor. And in my claim this context-sensitivity means that we get different sequences of tokens in different places for the same input. Your example shows that we get different ASTs for the same input but different type information, although we still get the same sequence of tokens. Getting a different sequence of tokens is much more confusing to me than getting a different AST (or maybe I just got used to that with a life of experience with C++). But generally I disagree that preprocessor is separate from C for the following reasons: 1. It is specified by the C standard. 2. Different C compilers implement it differently, just like they implement other parts of C differently. 3. There is some truth in the claim that it is a separate text transformation, but here I also do not agree entirely, because the C standard doesn't say that the preprocessor outputs text. It says that it outputs tokens and those tokens are then converted to tokens of C proper[1]. It is also clear that this model of "text transformation" is also not entirely what happens in real world compilers, because if it did we wouldn't get good backtraces for tokens that went out of the preprocessor after substitution. Maybe GCC serializes it to text at some point, but clearly it gets more information out of it than what a naive interpretation of the phrase "text transformation" would suggest. [1]: Translation phase 7 of the C11 standard: > Each preprocessing token is converted into a token.