Hacker News Reader

Comment by joshuata | Hacker News Reader

You are (essentially) correct. The language itself is context-free, and therefore parse-able as a regular language. Looking up identifiers in symbol tables is part of the type checking phase of compilation. This is a pretty common misconception, that type constraints effect the parsing complexity of a language. Language type only relates to the process of building an abstract syntax tree from an input, not validating it.

View on HN

> 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.

You 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-sensitiv...

Reply on news.ycombinator.com