25

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.

sandeepkunkunuru
  • 361
  • 3
  • 7
  • 1
    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. – Janne H. Korhonen Nov 30 '11 at 06:59
  • 2
    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 – ratchet freak Nov 30 '11 at 10:35
  • @ratchet, are you assuming the syntax must be recursively enumerable? – David Harris Nov 30 '11 at 12:28
  • 4
    @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. – Jon Purdy Nov 30 '11 at 14:35
  • @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. – sandeepkunkunuru Nov 30 '11 at 15:04
  • what steps during compilation need to adhere to a grammar and what steps need not. Is there a distinction? or is grammar purely theoretical. – sandeepkunkunuru Nov 30 '11 at 15:12
  • This really doesn't seem like a research-level question. – Sam Tobin-Hochstadt Nov 30 '11 at 15:16
  • It seems that majority of answers devoted to discussion of extending class of CFG for PLs. I suppose your question could be understood in different direction: are there any PLs based on grammars which are strictly more narrow then CFG. Regular, for instance. And then, I believe, the answer is yes: plenty of DSL are possibly so. E.g. Makefile rules. – Artem Pelenitsyn Nov 30 '11 at 17:37
  • @ArtemPelenitsyn To take that to an extreme, a certain language could be said to have a grammar of .* provided one accepts that ] searches for the matching bracket at runtime, and that unmatched brackets are therefore not an error. – Random832 Nov 30 '11 at 17:42
  • I think this question would have been perfect for the upcoming Computer Science Stackexchange site which is going to be broader in scope than cstheory.SE. So, if you like this question please go ahead and commit to our proposal! – Raphael Dec 01 '11 at 18:23
  • see also what programming languages are CFL, stackoverflow – vzn Mar 08 '13 at 16:55
  • also Are the grammars of modern programming languages context-free or context-sensitive? and chomsky hierarchy and programming languages, stackoverflow – vzn Mar 08 '13 at 17:11

10 Answers10

22

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.

Raphael
  • 4,565
  • 28
  • 48
  • 3
    Don't forget the public class Program { public static void main(String[] args) { ... } } ... Java's not going to let you get off that easy. :-) – Roy Tinker Dec 01 '11 at 05:29
  • 1
    Technically, class A { ... } is completely sufficient as javac compiles stuff you can't actually execute (for lack of an entry point), too. But yea. – Raphael Dec 01 '11 at 09:48
21

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

Niall Murphy
  • 526
  • 3
  • 7
  • 6
    I feel like this should be the punchline of a Perl joke :) – Suresh Venkat Nov 30 '11 at 17:13
  • 5
    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 (http://sigbovik.org/2011/proceedings.pdf - page 79-82). – Rob Simmons Nov 30 '11 at 23:30
  • 1
    Note: the Perl interpreter isn't yet non-deterministic, if that's a comfort to anyone :) – Roy Tinker Dec 01 '11 at 05:43
16

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.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
  • 4
    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. – didest Nov 30 '11 at 07:25
  • 7
    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?

     – Max Nov 30 '11 at 07:33
  • 9
    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. – David Eppstein Nov 30 '11 at 07:47
  • 1
    @DavidEppstein: To be fair, said complexity isn’t great by any means. – Jon Purdy Nov 30 '11 at 14:30
  • 1
    Apart from the handling of INDENT/DEDENT in the lexer, Python has a very simple LL(1) grammar. – rmmh Dec 20 '11 at 23:57
13

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

Markus Bläser
  • 2,938
  • 18
  • 19
  • Yes, but compiler are never just context-free grammars. You should discuss the grammar itself, not the compiler. – Jeff Burdges Dec 04 '11 at 01:38
  • @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. – Markus Bläser Dec 04 '11 at 19:53
7

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.

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
6

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.

Jeff Burdges
  • 1,216
  • 6
  • 11
  • 2
    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) – Random832 Nov 30 '11 at 17:34
  • 1
    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. – rici May 29 '16 at 22:24
4

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.

antti.huima
  • 295
  • 1
  • 8
4

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.

ratchet freak
  • 659
  • 6
  • 9
3

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.

Kris
  • 143
  • 7
  • 1
    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. – sandeepkunkunuru Nov 30 '11 at 14:54
3

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.

evilcandybag
  • 131
  • 3