14
$\begingroup$

Which language class are today's modern programming languages like Java, JavaScript, and Python in?

It appears (?) they are not context-free and not regular languages.

Are these programming languages context-sensitive or decidable languages? I am very confused!

I know that context-free is more powerful than regular languages and that context-sensitive is more powerful than context-free.

Are modern programming languages both context-free and context-sensitive?

$\endgroup$
1
  • 7
    $\begingroup$ @nirshahar "It has a grammar therefore it is context free" is not correct. It is fine and easy to define grammars which describe a language that is not context free. $\endgroup$ May 9 at 19:28
62
$\begingroup$

Practically no programming language, modern or ancient, is truly context-free, regardless of what people will tell you. But it hardly matters. Every programming language can be parsed; otherwise, it wouldn't be very useful. So all the deviations from context freeness have been dealt with.

What people usually mean when they tell you that programming languages are context-free because somewhere in the documentation there's a context-free grammar, is that the set of well-formed programs (that is, the "language" in the sense of formal language theory) is a subset of a context-free grammar, conditioned by a set of constraints written in the rest of the language documentation. That's mostly how programs are parsed: a context-free grammar is used, which recognises all valid and some invalid programs, and then the resulting parse tree is traversed to apply the constraints.

To justify describing the language as "context-free", there's a tendency to say that these constraints are "semantic" (and therefore not part of the language syntax). [Note 1] But that's not a very meaningful use of the word "semantic", since rules like "every variable must be declared" (which is common, if by no means universal) is certainly syntactic in the sense that you can easily apply it without knowing anything about the meaning of the various language constructs. All it requires is verifying that a symbol used in some scope also appears in a declaration in an enclosing scope. However, the "also appears" part makes this rule context-sensitive.

That rule is somewhat similar to the constraints mentioned in this post about Javascript (linked to from one of your comments to your question): that neither a Javascript object definition nor a function parameter list can define the same identifier twice, another rule which is both clearly context-sensitive and clearly syntactic.

In addition, many languages require non-context-free transformations prior to the parse; these transformations are as much part of the grammar of the language as anything else. For example:

  • Layout sensitive block syntax, as in Python, Haskell and many data description languages. (Context-sensitive because parsing requires that all whitespace prefixes in a block be the same length.)

  • Macros, as in Rust, C-family languages, Scheme and Lisp, and a vast number of others. Also, template expansion, at least in the way that it is done in C++.

  • User-definable operators with user-definable precedences, as in Haskell, Swift and Scala. (Scala doesn't really have user-definable precedence, but I think it is still context-sensitive. I might be wrong, though.)

None of this in any way diminishes the value of context-free parsing, neither in practical nor theoretical terms. Most parsers are and will continue to be fundamentally based on some context-free algorithm. Despite a lot of trying, no-one yet has come up with a grammar formalism which is both more powerful than context-free grammars and associated with an algorithm for transforming a grammar into a parser without adding hand-written code. (To be clear: the goal I refer to is a formalism which is more powerful than context-free grammars, so that it can handle constraints like "variables must be declared before they are used" and the other features mentioned above, but without being so powerful that it is Turing complete and therefore undecidable.)

Notes

  1. Excluding rules which cannot be implemented in a context-free grammar in order to say that the language is context-free strikes me as a most peculiar way to define context-freeness. Of course, if you remove all context-sensitive aspects of a language, you end up with a context-free superset, but it's no longer the same language.
$\endgroup$
22
  • 2
    $\begingroup$ FWIW, I've seen claims that the C++ grammar is undecidable, even if I never found a proof for that. Template metaprogramming, being Turing powerful, does make type checking undecidable, but I don't know if it also interferes with parsing that much to make it undecidable as well. $\endgroup$
    – chi
    May 9 at 7:59
  • 13
    $\begingroup$ @chi: there's an old answer of mine on SO which shows the idea. You define a template class with a single boolean template argument and specialise the two possibilities. The specialisation on true has a public template member class named x. In the other one, the member x is an integer. Then you instantiate templ<pred>.x<42>(0). Now you need to figure out if pred is true or false in order to know whether x<42>(0) is a call to a templated constructor of member type x, or the comparison between 0 and the comparison of scalar member x with 42. $\endgroup$
    – rici
    May 9 at 8:17
  • 2
    $\begingroup$ Or you can leave out the 0. Then it's well-formed if pred is true and a syntax error if it's false. In any case, the parse is determined by the compile time evaluation of pred; if that's undecidable, so is the parse. $\endgroup$
    – rici
    May 9 at 8:19
  • 3
    $\begingroup$ Great answer. Similar remarks hold about how the word "regular expressions" are used in practical programming languages. They go beyond literal regular expressions but have enough basic similarity to justify the terminology. $\endgroup$ May 9 at 11:38
  • 4
    $\begingroup$ @gnasher729: pretty well any language can be parsed by first transforming the input using a context free transducer and then passing the result through an ad hoc computation performed by Turing complete mechanism. That makes the cfg useful. But it doesn't make the language context-free. A language is context free iff you can determine whether or not a sentence is part of the language using a PDA. This question is tagged formal-languages and in that context, Swift is not a context-free language. That's not a criticism of Swift nor does it say cfg parsing is pointless. It's just a fact. $\endgroup$
    – rici
    May 10 at 13:56
3
$\begingroup$

The boundary between context-free and context-sensitive is only determined by one thing: whether or not it can be decided with a nondeterministic pushdown automata.

With respect to grammar specifically, most practical programming languages are almost context-free if not context-free, but the context-free/context-sensitive distinction isn't nearly as important as the ease of parsing. It's possible to create a context-free language that is difficult to parse or is ambiguous, and it is also possible to create a context-sensitive language that is easy to parse. Remember, the computers we use to parse programming languages are functionally equivalent to Turing machines (if given infinite memory) and are limited by the fact that they are deterministic. The determinism is the practical limiting factor that informs our choice in grammars that programming languages will use, so the boundary between context-free and context-sensitive is less practically interesting than the boundary between deterministic and nondeterministic.

$LL_k$ and $LALR_k$ grammars form specific subsets of deterministic context-free grammars that can be parsed with generated tables within programs that simulate a deterministic pushdown automaton (which is less powerful than a nondeterministic one).

On the other hand, $PEG$ grammars have a handful of features that technically fall under the context-sensitive umbrella, however they can be parsed in linear time with generated code, which outperforms generalized nondeterministic context-free parsing (The best known algorithm for CFGs is somewhere between quadratic and cubic time. This class of grammars includes certain obscure features that are technically context-free but are hard to parse- I don't know of any examples off the top of my head). PEGs have become quite popular for modern languages, and even Python has adopted its use for upcoming versions and new languages such as Zig have been using them from the beginning.

Having a "more powerful" grammar doesn't matter at all for the power of a programming language because the computing model they represent can simulate a Turing machine. In fact, it's often the opposite because "more powerful" grammars tend to be more difficult to parse and are therefore less friendly to both machines and computers (and slower to compile). C++ is a particularly notorious offender in this realm, with templates (and how they are expanded) having the ability to affect the parse tree. In fact, C++ is not even decidable because templates are Turing complete.

$\endgroup$
2
$\begingroup$

For a detailed discussion how C as standardized in 2011 (see ISO/IEC 9899:2011 – Programming languages – C) diverges from context freeness you might want to look at Jourdan and Poitier, "A simple, possibly correct LR parser for C11", ACM Transactions on Programming Languages and Systems 39:4 (Aug 2017), article 14. And that one assumes preprocessed code (already mangled by the C preprocessor).

Note that the preprocessor has no idea or respect for C syntax, and can be (perversely) used to rename keywords and partially replace syntax. An (in)famous example is the dialect of C deformed into almost-Algol in which Bourne wrote his original version of the Unix shell (see the V7 shell source).

The history of Algol 68 with its two-level grammar (the idea was to have a grammar generating a grammar tailored to the program) is also a data point showing programming languages are not context free.

Even a language with extremely simple "context free" syntax like Scheme as described by the R7RS (its syntax isn't much more than "open parenthesis has to be closed") is accompanied by a lot of non-context-free restrictions in its description.

$\endgroup$
1
$\begingroup$

On top of what others have said, many modern programming languages come with explicit disambiguation rules, and non-compiler-writers are often not aware of just how often these are applied.

Most modern programming languages have a two-level grammar, split into lexical analysis and syntax analysis. The lexical language in particular is almost always based on two disambiguation rules:

  • Some lexemes take precedence over others. For example, an identifier is a sequence of characters of a certain form which isn't a keyword. This can be expressed as a grammar or regular expression (regular languages are closed under set difference), but it's difficult
  • Lexemes are as long as possible. This is known as the "maximal munch rule". So, for example, ifwhile is a single identifier rather than the two keywords if and while.

Similarly, it is possible to solve the "dangling else" problem with an unambiguous grammar, but it's more typically solved using a CFG form of the maximal munch rule ("prefer shift to reduce" in LR speak).

Having said that, there are languages whose grammars are inherently ambiguous, and disambiguation must happen semantically. The C family of languages famously has several places where this occurs:

  • In C, foo(bar); is a function call if foo is an identifier, or a declaration of a variable named bar if foo is a type name. In C++, it could also be a function-style cast of bar to type foo.
  • In C++, foo bar(); could be a declaration of a function named bar, or it could be a declaration of a variable named bar using the default constructor of foo.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.