2 ms·
> therefore parse-able as a regular language. You mean "context-free" not "regular" here, but either way, I believe that C is actually context-sensitive:
by munificent 10y ago
> therefore parse-able as a regular language.
You mean "context-free" not "regular" here, but either way, I believe that C is actually context-sensitive:
(a)(b);
Is this:
1. Evaluating "b" and casting it to type "a"?
2. Evaluating the parenthesized expression "a" which yields a function, and then calling it, passing in "b"?
The only way to distinguish the two is by knowing whether "a" is a type or not.
You could argue that as long as the parser produces a suitably vague AST, it doesn't need to know the distinction and can pass it on to later phases. I think that might work because I don't know of cases where the syntax actually diverges based on the type of a symbol.
But in practice, I think most parsers want to produce a more precise AST that distinguishes cast expressions from function calls.
- joshuata 10y agoYou are right, the regular/context-free comment was a typo. You are also correct about c being non-context-free[0]. I have just seen many explanations of language hierarchy online mistaking type-checking for language complexity that it is a pet peeve of mine. [0] http://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar http://eli.thegreenplace.net/2007/11/24/the-context-sensitiv...