Hacker News new | ask | show | jobs
by wtetzner 3302 days ago
Context free grammars are perfectly capable of expressing matched curly braces, even with unbounded nesting. Am I missing something?
1 comments

Yes, thinking about it that alone is not sufficient. Still, I'd claim that most languages are not context free.

CPP (Pre-processor) aside, C is not context free due to typedef making identifiers ambiguous. Also if-then-else? Since C++ templates are turing-complete, the grammar is probably unrestricted.

Python is not context free due to

    if ...:
        stmt1
        if ...:
           stmt2
        stmt3
stmt3 and stmt1 have to share the same level of indentation to form a valid Python program, but they might contain arbitrary indentation within brackets.