<p>Parsing perl is un-decidable.</p>

<p><a href="http://www.jeffreykegler.com/Home/perl-and-undecidability/perl-and-undecidability-files/TPR3.pdf?attredirects=0">http://www.jeffreykegler.com/Home/perl-and-undecidability/perl-and-undecidability-files/TPR3.pdf?attredirects=0</a></p>

<p><a href="http://www.perlmonks.org/?node_id=663393">http://www.perlmonks.org/?node_id=663393</a></p>

CC BY-SA 3.0
2011-11-30T17:13:32.947Z
I feel like this should be the punchline of a Perl joke :)
Suresh Venkat
CC BY-SA 3.0
2011-11-30T23:30:07.997Z
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
CC BY-SA 3.0
2011-12-01T05:43:03.467Z
Note: the Perl interpreter isn't yet non-deterministic, if that's a comfort to anyone :)
Roy Tinker
CC BY-SA 3.0
2011-11-30T15:06:09.880Z
2011-11-30T15:06:09.880Z
Niall Murphy
<p>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.</p>

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

<pre>if condition:
     line1
     line2
     line3
else:
     line4</pre>

<p>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.</p>

CC BY-SA 3.0
2011-11-30T07:25:08.307Z
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
CC BY-SA 3.0
2011-11-30T07:33:54.627Z
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
CC BY-SA 3.0
2011-11-30T07:47:39.110Z
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
CC BY-SA 3.0
2011-11-30T14:30:35.717Z
@DavidEppstein: To be fair, said complexity isn’t great by any means.
Jon Purdy
CC BY-SA 3.0
2011-12-20T23:57:57.997Z
Apart from the handling of INDENT/DEDENT in the lexer, Python has a very simple LL(1) grammar.
rmmh
CC BY-SA 3.0
2011-11-30T06:34:09.320Z
2011-11-30T06:34:09.320Z
David Eppstein
<p>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 <em>compile</em> time. So it is much worse than
just context-sensitive.</p>

<p><a href="http://wwwhome.math.utwente.nl/~mantheyb/journals/BotEATCS_BoehmeManthey_CompilingCPP.pdf">http://wwwhome.math.utwente.nl/~mantheyb/journals/BotEATCS_BoehmeManthey_CompilingCPP.pdf</a></p>

CC BY-SA 3.0
2011-12-04T01:38:43.127Z
Yes, but compiler are never just context-free grammars.  You should discuss the grammar itself, not the compiler.
Jeff Burdges
CC BY-SA 3.0
2011-12-04T19:53:05.487Z
@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
CC BY-SA 3.0
2011-11-30T16:11:30.453Z
2011-11-30T16:11:30.453Z
Markus Bläser
<p>I think that <em>declaration before use</em> of variables and the <em>function polymorphism</em> of the OOP languages are other examples of programming languages specifications that cannot be handled by context free grammars:</p>

<pre><code>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);
...
</code></pre>

<p>I made a little Google search and I found this article: <em>"<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.70.7166" rel="noreferrer">A Boolean Grammar for a Simple Boolean Language</a>"</em> by A.Okhotin (2004); according to him,  the real problem is  to find a programming language that is <em>completely</em> described by a formal grammar:</p>

<p><em>A toy procedural programming language is defined, and a <a href="http://en.wikipedia.org/wiki/Boolean_grammar" rel="noreferrer">Boolean grammar</a>
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.</em></p>

<p>The Introduction section of the article is short but very clarifying.</p>

CC BY-SA 3.0
2011-11-30T08:40:45.413Z
2011-11-30T14:48:49.660Z
2011-11-30T14:48:49.660Z
Marzio De Biasi
<p>I believe that C's grammar is only technically context-free in that parsers always use non-context-free techniques to support <a href="http://en.wikipedia.org/wiki/Duff%27s_device">Duff's device</a>.</p>

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

<p>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. </p>

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

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

<p>Java and assembler are probably both <em>naturally</em> context-free. </p>

CC BY-SA 3.0
2011-11-30T17:34:07.183Z
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
CC BY-SA 3.0
2016-05-29T22:24:05.083Z
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
CC BY-SA 3.0
2011-11-30T07:40:19.030Z
2011-11-30T07:40:19.030Z
Jeff Burdges
<p>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.</p>

CC BY-SA 3.0
2011-11-30T08:54:38.460Z
2011-11-30T08:54:38.460Z
antti.huima
<p>First let me make a distinction between syntax of a programming language and the language itself.</p>

<p>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</p>

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

<p>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.</p>

CC BY-SA 3.0
2011-11-30T11:20:18.420Z
Name- and type analysis typically peform inherently non-context free tasks.
Raphael
CC BY-SA 3.0
2011-11-30T15:02:51.063Z
Template meta-programming in C++ is Turing complete.
Jeff Burdges
CC BY-SA 3.0
2011-11-30T10:57:13.333Z
2015-11-13T16:24:46.570Z
2015-11-13T16:24:46.570Z
ratchet freak
<p>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 <a href="http://www.brynosaurus.com/pub/lang/peg.pdf" rel="nofollow">here</a>(pdf) or <a href="http://en.wikipedia.org/wiki/Parsing_expression_grammar" rel="nofollow">on Wikipedia</a> for a more bite sized read.</p>

CC BY-SA 3.0
2011-11-30T16:46:42.753Z
2011-11-30T16:46:42.753Z
evilcandybag
<p>As far as the "Are all programming/scripting languages context free grammars?" part is concerned, the answer is a definite No. </p>

<p>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.</p>

CC BY-SA 3.0
2011-11-30T14:54:30.190Z
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
CC BY-SA 3.0
2011-11-30T09:42:29.173Z
2011-11-30T09:42:29.173Z
Kris
<p>Two times no.</p>

<p>First, most HPLs are not context free. While they usually have syntax based on a CFG, they also have what people call <em>static semantics</em> (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,</p>

<pre><code>class A {
  String a = "a";
  int b = a + d;
}
</code></pre>

<p>is a syntactically correct Java program but will not compile because <code>d</code> is not defined and <code>a</code> does not have a fitting type.</p>

<p>Secondly, you <em>can</em> 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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-12-01T05:29:24.830Z
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
CC BY-SA 3.0
2011-12-01T09:48:05.713Z
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
CC BY-SA 3.0
2011-11-30T11:26:26.320Z
2011-12-01T09:49:26.663Z
2011-12-01T09:49:26.663Z
Raphael
<p>Practically, for a language that can eventually be compiled/transformed into system level instructions, is it necessary that it be a context free grammar?</p>

<p>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?</p>

<p>It does not seem mandatory, but there are gaps in my understanding.</p>

<p>Some context for the question: I was looking at Java language specification, which also provides the grammar <a href="http://java.sun.com/docs/books/jls/third_edition/html/syntax.html#18.1">rules</a>. This made me think about this question.</p>

CC BY-SA 3.0
2011-11-30T06:59:35.113Z
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
CC BY-SA 3.0
2011-11-30T10:35:19.927Z
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
CC BY-SA 3.0
2011-11-30T12:28:29.050Z
@ratchet, are you assuming the syntax must be recursively enumerable?
David Harris
CC BY-SA 3.0
2011-11-30T14:35:38.233Z
@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
CC BY-SA 3.0
2011-11-30T15:04:47.697Z
@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
CC BY-SA 3.0
2011-11-30T15:12:51.397Z
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
CC BY-SA 3.0
2011-11-30T15:16:02.390Z
This really doesn't seem like a research-level question.
Sam Tobin-Hochstadt
CC BY-SA 3.0
2011-11-30T17:37:12.767Z
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
CC BY-SA 3.0
2011-11-30T17:42:07.243Z
@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
CC BY-SA 3.0
2011-12-01T18:23:44.720Z
I think this question would have been perfect for the upcoming [Computer Science](http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=pdx8p7tVWqozXN85c5ibxQ2) 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
CC BY-SA 3.0
2013-03-08T16:55:10.680Z
see also [what programming languages are CFL](http://stackoverflow.com/questions/898489/what-programming-languages-are-context-free), stackoverflow
vzn
CC BY-SA 3.0
2013-03-08T17:11:20.907Z
also [Are the grammars of modern programming languages context-free or context-sensitive?](http://stackoverflow.com/questions/9652436/) and [chomsky hierarchy and programming languages](http://stackoverflow.com/questions/2929507/chomsky-hierarchy-and-programming-languages), stackoverflow
vzn
<pl.programming-languages><context-free>
For a language to be programmable, is it mandatory that it be based on a context free grammar
sandeepkunkunuru
# For a language to be programmable, is it mandatory that it be based on a context free grammar

(Asked by: username_0 on 2011-11-30)

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](http://java.sun.com/docs/books/jls/third_edition/html/syntax.html#18.1). This made me think about this question.

**Tags:** pl.programming-languages, context-free
> **Comments:**
> **username_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.  
> **username_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  
> **username_3**: @ratchet, are you assuming the syntax must be recursively enumerable?  
> **username_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.  
> **username_0**: @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.  
> **username_0**: what steps during compilation need to adhere to a grammar and what steps need not. Is there a distinction? or is grammar purely theoretical.  
> **username_5**: This really doesn't seem like a research-level question.  
> **username_6**: 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.  
> **username_7**: @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.  
> **username_8**: I think this question would have been perfect for the upcoming [Computer Science](http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=pdx8p7tVWqozXN85c5ibxQ2) 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!  
> **username_9**: see also [what programming languages are CFL](http://stackoverflow.com/questions/898489/what-programming-languages-are-context-free), stackoverflow  
> **username_9**: also [Are the grammars of modern programming languages context-free or context-sensitive?](http://stackoverflow.com/questions/9652436/) and [chomsky hierarchy and programming languages](http://stackoverflow.com/questions/2929507/chomsky-hierarchy-and-programming-languages), stackoverflow  

---

## 10 answers

### Answer by username_8 on 2011-11-30. Score: 22 | Accepted answer

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.

> **Comments:**
> **username_13**: Don't forget the `public class Program { public static void main(String[] args) { ... } }` ... Java's not going to let you get off that easy. :-)  
> **username_8**: Technically, `class A { ... }` is completely sufficient as `javac` compiles stuff you can't actually execute (for lack of an entry point), too. But yea.  

---

### Answer by username_10 on 2011-11-30. Score: 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>

> **Comments:**
> **username_11**: I feel like this should be the punchline of a Perl joke :)  
> **username_12**: 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).  
> **username_13**: Note: the Perl interpreter isn't yet non-deterministic, if that's a comfort to anyone :)  

---

### Answer by username_14 on 2011-11-30. Score: 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.

> **Comments:**
> **username_15**: 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.  
> **username_16**: 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`?  
> **username_14**: 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.  
> **username_4**: @DavidEppstein: To be fair, said complexity isn’t great by any means.  
> **username_17**: Apart from the handling of INDENT/DEDENT in the lexer, Python has a very simple LL(1) grammar.  

---

### Answer by username_18 on 2011-11-30. Score: 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>

> **Comments:**
> **username_19**: Yes, but compiler are never just context-free grammars.  You should discuss the grammar itself, not the compiler.  
> **username_18**: @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.  

---

### Answer by username_20 on 2011-11-30. Score: 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.


---

### Answer by username_19 on 2011-11-30. Score: 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](http://en.wikipedia.org/wiki/Duff%27s_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.

> **Comments:**
> **username_7**: 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)  
> **username_21**: 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.  

---

### Answer by username_22 on 2011-11-30. Score: 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.


---

### Answer by username_2 on 2011-11-30. Score: 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.

> **Comments:**
> **username_8**: Name- and type analysis typically peform inherently non-context free tasks.  
> **username_19**: Template meta-programming in C++ is Turing complete.  

---

### Answer by username_23 on 2011-11-30. Score: 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](http://www.brynosaurus.com/pub/lang/peg.pdf)(pdf) or [on Wikipedia](http://en.wikipedia.org/wiki/Parsing_expression_grammar) for a more bite sized read.


---

### Answer by username_24 on 2011-11-30. Score: 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.

> **Comments:**
> **username_0**: 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.  

---

