What programming languages are context-free?

user_106236 0
Viewed 32679

Or, to be a little more precise: which programming languages are defined by a context-free grammar?

From what I gather C++ is not context-free due to things like macros and templates. My gut tells me that functional languages might be context free, but I don't have any hard data to back that up with.

Extra rep for concise examples :-)

compiler-theory context-free-grammar
9 Answers

The set of programs that are syntactically correct is context-free for almost all languages.

The set of programs that compile is not context-free for almost all languages. For example, if the set of all compiling C programs were context free, then by intersecting with a regular language (also known as a regex), the set of all compiling C programs that match

^int main\(void\) { int a+; a+ = a+; return 0; }$

would be context-free, but this is clearly isomorphic to the language a^kba^kba^k, which is well-known not to be context-free.

Dave_277310

VHDL is somewhat context sensitive:

VHDL is context-sensitive in a mean way. Consider this statement inside a process:

jinx := foo(1);

Well, depending on the objects defined in the scope of the process (and its enclosing scopes), this can be either:

  • A function call
  • Indexing an array
  • Indexing an array returned by a parameter-less function call

To parse this correctly, a parser has to carry a hierarchical symbol table (with enclosing scopes), and the current file isn't even enough. foo can be a function defined in a package. So the parser should first analyze the packages imported by the file it's parsing, and figure out the symbols defined in them.

This is just an example. The VHDL type/subtype system is a similarly context-sensitive mess that's very difficult to parse.

(Eli Bendersky, “Parsing VHDL is [very] hard”, 2009)

user_891350

Let's take Swift, where the user can define operators including operator precedence and associativity. For example, the operators + and * are actually defined in the standard library.

A context free grammar and a lexer may be able to parse a + b - c * d + e, but the semantics is "five operands a, b, c, d and e, separated by the operators +, -, * and +". That's what a parser can achieve without knowing about operators. A context free grammar and a lexer may also be able to parse a +-+ b -+- c, which is three operands a, b and c separated by operators +-+ and -+-.

A parser can "parse" a source file according to a context-free Swift grammar, but that's nowhere near the job done. Another step would be collecting knowledge about operators, and then change the semantics of a + b - c * d + e to be the same as operator+ (operator- (operator+ (a, b), operator* (c, d)), e).

So there is (or maybe there is, I havent checked to closely) a context free grammar, but it only gets you so far to parsing a program.

user_32554550
Related