25
$\begingroup$

Practically, for a language that can eventually be compiled/transformed into system level instructions, is it necessary that it be a context free grammar?

ex: Are all programming/scripting languages context free grammars? Java is based on CFGs, but is it actually the case that all programming languages are based on CFGs?

It does not seem mandatory, but there are gaps in my understanding.

Some context for the question: I was looking at Java language specification, which also provides the grammar rules. This made me think about this question.

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ Generally I think it's just that you want the compilation problem to be computable, and parsing CFGs is nice and easy. Though I've heard some claims that, for example, recognising valid perl programs is in fact a non-computable problem. $\endgroup$
    – Janne H. Korhonen
    Commented Nov 30, 2011 at 6:59
  • 2
    $\begingroup$ actually all you really need is a turing-decidable syntax (which all CFGs are). You also could make a programming language which whose syntax is not turing-decidable, but when you make a typo the compiler might never stop while it's trying to decide whether it's is valid syntax. this is not really usefull $\endgroup$
    – ratchet freak
    Commented Nov 30, 2011 at 10:35
  • $\begingroup$ @ratchet, are you assuming the syntax must be recursively enumerable? $\endgroup$
    – David Harris
    Commented Nov 30, 2011 at 12:28
  • 4
    $\begingroup$ @JanneKorhonen: Specifically, Perl cannot be statically parsed, that is, it cannot be parsed without also being executed; since said execution could be non-terminating, parsing Perl statically would imply solving the Halting Problem. $\endgroup$
    – Jon Purdy
    Commented Nov 30, 2011 at 14:35
  • $\begingroup$ @janne I mean, post pre-processing which may entail problems that may or may not be computable, is it generally the case that the final grammar against which the program is validated against is context-free. To be more specific, post pre-processing, for identifying a rule that fits a sequence of tokens do we need to look at other tokens surrounding the sequence. I dont know if I make sense, sorry about that. I am a little confused actually. $\endgroup$
    – sandeepkunkunuru
    Commented Nov 30, 2011 at 15:04

10 Answers 10

Reset to default
22
$\begingroup$

Two times no.

First, most HPLs are not context free. While they usually have syntax based on a CFG, they also have what people call static semantics (which is also often included in the term syntax). This can include names and types which have to check out for a correct program. For instance,

class A {
  String a = "a";
  int b = a + d;
}

is a syntactically correct Java program but will not compile because d is not defined and a does not have a fitting type.

Secondly, you can parse languages that are not context-free (as obviously proven by the existence of compilers). It is only that CFGs can be parsed efficiently, while CSGs can not, in general. However, you can add certain non-context-free features while remaining efficient.

Compilers often run in phases: first tokenization (regular), then context-free parsing, then name and type analysis (context-sensitive, sometimes even harder). You can observe that behaviour by the kind of error messages you get.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Don't forget the public class Program { public static void main(String[] args) { ... } } ... Java's not going to let you get off that easy. :-) $\endgroup$
    – Roy Tinker
    Commented Dec 1, 2011 at 5:29
  • 1
    $\begingroup$ Technically, class A { ... } is completely sufficient as javac compiles stuff you can't actually execute (for lack of an entry point), too. But yea. $\endgroup$
    – Raphael
    Commented Dec 1, 2011 at 9:48
21
$\begingroup$

Parsing perl is un-decidable.

http://www.jeffreykegler.com/Home/perl-and-undecidability/perl-and-undecidability-files/TPR3.pdf?attredirects=0

http://www.perlmonks.org/?node_id=663393

Improve this answer
$\endgroup$
3
  • 6
    $\begingroup$ I feel like this should be the punchline of a Perl joke :) $\endgroup$
    – Suresh Venkat
    Commented Nov 30, 2011 at 17:13
  • 5
    $\begingroup$ Suresh: I've already made that joke, though it didn't turn out to be a very good joke, in the paper "On unlexable programming languages" in SIGBOVIK 2011 (sigbovik.org/2011/proceedings.pdf - page 79-82). $\endgroup$
    – Rob Simmons
    Commented Nov 30, 2011 at 23:30
  • 1
    $\begingroup$ Note: the Perl interpreter isn't yet non-deterministic, if that's a comfort to anyone :) $\endgroup$
    – Roy Tinker
    Commented Dec 1, 2011 at 5:43
16
$\begingroup$

I don't believe that Python's grammar is context free. The requirement that lines in the same block of code have the same amount of indentation is not the sort of thing that context free grammars handle well.

More precisely, there appears to be a homomorphism from the language of Python blocks of the form

if condition:
     line1
     line2
     line3
else:
     line4

to the non-context-free language $0^n10^n10^n$ where the first block of zeros comes from the set of spaces at the start of line1, the second block comes the set of spaces at the start of line2, the third block comes from the set of spaces at the start of line3, and the remaining lines with the else etc are there to force line1, line2, and line3 to belong to the same block.

Improve this answer
$\endgroup$
5
  • 4
    $\begingroup$ Strictly you are right, but in the context of programming languages we try to make context-free the language resulting after a preprocessing step called tokenization. I think the indentation is checked before that. $\endgroup$
    – didest
    Commented Nov 30, 2011 at 7:25
  • 7
    $\begingroup$ Yeah, the Python lexer (tokenizer) has a stack of indentation depths; the token stream has an INDENT symbol at the start of each block and a DEDENT symbol at the end which can be parsed in a context free way (INDENT and DEDENT act much like the braces in C). C has the "can't tell if declaration or expression" problem: is foo * bar; a declaration of foo as a pointer to bar or a multiplication of foo times bar? $\endgroup$
    – Max
    Commented Nov 30, 2011 at 7:33
  • 9
    $\begingroup$ Ok, sure, but then you're just hiding the same complexity in the lexer, rather than making it a finite state transducer as they often are. $\endgroup$
    – David Eppstein
    Commented Nov 30, 2011 at 7:47
  • 1
    $\begingroup$ @DavidEppstein: To be fair, said complexity isn’t great by any means. $\endgroup$
    – Jon Purdy
    Commented Nov 30, 2011 at 14:30
  • 1
    $\begingroup$ Apart from the handling of INDENT/DEDENT in the lexer, Python has a very simple LL(1) grammar. $\endgroup$
    – rmmh
    Commented Dec 20, 2011 at 23:57
13
$\begingroup$

Bodo Manthey and Martin Böhme show that every C++ Compiler is necessarily Turing complete, that is, it can compute any partial recursive function at compile time. So it is much worse than just context-sensitive.

http://wwwhome.math.utwente.nl/~mantheyb/journals/BotEATCS_BoehmeManthey_CompilingCPP.pdf

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes, but compiler are never just context-free grammars. You should discuss the grammar itself, not the compiler. $\endgroup$
    – Jeff Burdges
    Commented Dec 4, 2011 at 1:38
  • $\begingroup$ @Jeff: "Compile time" in my answer means "checking whether a given C+ source code is correct". By a slight modification of the construction in the paper, it follows that you can reduce every decidable language to the set of all correct C++ programs. $\endgroup$
    – Markus Bläser
    Commented Dec 4, 2011 at 19:53
7
$\begingroup$

I think that declaration before use of variables and the function polymorphism of the OOP languages are other examples of programming languages specifications that cannot be handled by context free grammars:

int myfun(int a) { ... }
int myfun(int a, int b) { ... }
int myfun(int a, int b, int c, ...) { ... }
...
int I_m_I_cfg = myfun(1,2);
...

I made a little Google search and I found this article: "A Boolean Grammar for a Simple Boolean Language" by A.Okhotin (2004); according to him, the real problem is to find a programming language that is completely described by a formal grammar:

A toy procedural programming language is defined, and a Boolean grammar for the set of well-formed programs in this language is constructed. This is apparently the first specification of a programming language entirely by a formal grammar.

The Introduction section of the article is short but very clarifying.

Improve this answer
$\endgroup$
0
6
$\begingroup$

I believe that C's grammar is only technically context-free in that parsers always use non-context-free techniques to support Duff's device.

Indentation based languages aren't naturally context-free either like David said, but they become context-free relative to a parameterized indentation token.

Haskell lets you change operator precedence with infix and infixl. Perl's strict pragma module is implemented using the lexical settings $^H and %^H, which make it not context-free, probably other settings too.

There are macro expander languages like TeX in which afaik parsing doesn't make sense without executing.

There are probably even two context-free grammars who's intersection isn't context-free but still describes a Turing machine.

Java and assembler are probably both naturally context-free.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Doesn't the ambiguity of (a)-b make C context-sensitive? (a could be a variable or a typedef - some other languages don't allow casting unary minus expressions for this reason) $\endgroup$
    – Random832
    Commented Nov 30, 2011 at 17:34
  • 1
    $\begingroup$ I apologize for the very delayed comment but Duff's device involves no syntactic deviations. The braces balance correctly. The C feature most often ignored in discussions about whether C is context-free is the preprocessor. I'm skeptical that there is any interpretation, however informal, of "context free" which permits using it to describe a language with a macro processor, even a well-behaved one. And the C preprocessor is anything but well-behaved. $\endgroup$
    – rici
    Commented May 29, 2016 at 22:24
4
$\begingroup$

No, and many practical languages are not context-free. For example C++ grammar is not, because in some contexts grammar resolution depends on typing information that is not context-free.

Improve this answer
$\endgroup$
4
$\begingroup$

First let me make a distinction between syntax of a programming language and the language itself.

The syntax of many languages are (at least based on) a Context Free Grammar (CFG) because these are well studied and there are algorithms which can efficiently parse a CFG and the edge case which cannot be solved by the CFG can be handled specially

However many languages are in fact not Context-Free (when declare-before-use symbols are used, for example in java, C(++), D).

Fun fact: D has a Turing-complete compile-time-function evaluation and template expansion making the language itself non-Turing-decidable. However the the creator of the language went to great lengths to make the syntax a CFG.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Name- and type analysis typically peform inherently non-context free tasks. $\endgroup$
    – Raphael
    Commented Nov 30, 2011 at 11:20
  • $\begingroup$ Template meta-programming in C++ is Turing complete. $\endgroup$
    – Jeff Burdges
    Commented Nov 30, 2011 at 15:02
3
$\begingroup$

As far as the "Are all programming/scripting languages context free grammars?" part is concerned, the answer is a definite No.

Re: the main question of "for a language that can eventually be compiled/transformed into system level instructions," I do not know why it needs necessarily to be a CFG. However, there could be better explanations coming forth.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Kris, can you give some examples of non-context free grammar based programming languages. I mean, post pre-processing which may entail problems that may or may not be computable, the final grammar against which the program is validated against. $\endgroup$
    – sandeepkunkunuru
    Commented Nov 30, 2011 at 14:54
3
$\begingroup$

A programming language needs to be based on some kind of grammar formalism, of which CFGs are an example. While CFGs are the most common (and are the usual thing taught in compiler courses at univiersities), there are other formalisms such as Parsing Expression Grammars, which you can read more about here(pdf) or on Wikipedia for a more bite sized read.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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