Language features are an orthogonal issue--you can implement any language feature with a CFG, but you just can't reuse the same keyword or operator to have different meanings in different grammatical contexts.

A classic example is that in C++ it is impossible to know whether << is brackets around template arguments, or the left bit shift operator, or the stream output operator, without arbitrary lookahead--you need to parse the rest of the statement in order to decide which one it is in the current statement's context.

Generally language designers don't choose to implement a context-sensitive grammar on purpose because they desire some feature that requires it; they strive for a context-free grammar, but end up with a handful of special cases that require context-sensitive parsing because of either convenience or legacy reasons.

Popular programming languages nearly all use custom parsers written in other (or the same) Turing-complete programming languages, so it's not "harder" to parse the context-sensitive rules, it only poses a problem if you want to use a parser generator to implement parsing for a CSG.

The classic example, I guess, is the most vexing parse: https://en.m.wikipedia.org/wiki/Most_vexing_parse

"""

The line

  TimeKeeper time_keeper(Timer());

    a variable definition [...]
    a function declaration [...]

These things you can only resolve by having the symbol tables around and checking. The parser alone can't tell.

A language could avoid this i.e. by requiring specific keywords or having more distinct syntax.

Humans (programmers) however often can deal with ambiguity, we have it in humannlanaguage as well and context on most cases helps and I argue those aren't practical problems. (While that's only opinion)

This is not a distinguishing feature. (I'm assuming you meant something else.) Example of a CFG with ambiguity:

    S → S S
    S → x

On the other hand, I've seen EBNF definition of BASIC (VB, actually). Is this a contradiction?

(just someone still learning)

    <Statement>   ::= CLOSE '#' Integer
                    | DATA <Constant List> 
                    [...]    
                    | LET Id '=' <Expression> 
                    [...]
                    | Remark

    <Compare Exp> ::= <Add Exp> '='  <Compare Exp> 
                    | <Add Exp> '<>' <Compare Exp> 
                    | <Add Exp> '><' <Compare Exp> 
                    | <Add Exp> '>'  <Compare Exp> 
                    | <Add Exp> '>=' <Compare Exp> 
                    | <Add Exp> '<'  <Compare Exp> 
                    | <Add Exp> '<=' <Compare Exp> 
                    | <Add Exp>

  foo()
      {
      return;
      }
  ↓↓↓↓↓↓↓↓↓↓↓
  aaaa{
  bbbbreturn;
  cccc}
  ↓↓↓↓↓↓↓↓↓↓↓
  aaaabbbbcccc

What you acually want is not context-free grammar, but, as TFA says:

> the code should be parseable without having to look things up in a symbol table

With this trick, you can parse Python with a context-free grammar.

Is it? You only indent with spaces, so a = b = c = ' ', and the problem you claim disappears.

[0]: https://cs.stackexchange.com/questions/33153/is-an-bn-cn-con...

Most languages have context-free syntax, which is what the article refers too. There really is no reason to sacrifice that. Even modern PHP recognises the value of having a parse tree independent of an entire compiler.

Context-free semantics is an entirely different matter, and I'm not even sure what it'd mean...

There are hardly any real-world programming languages that are context-free in any meaning of the word.

The first answer with 41 points is totally wrong: The set of programs that are syntactically correct is context-free for almost all languages

-----

A better source is this whole series by Trevor Jim, which has nice ways of relating theory to practice. He lists a bunch of reasons why you could consider nearly all programming languages not context-free.

http://trevorjim.com/parsing-not-solved/ -- hundreds of parser generators support context-free grammars, but there are almost no context-free languages in practice.

http://trevorjim.com/python-is-not-context-free/ -- A main point here is that you have to consider the lexer and parser separately. Grammars don't address this distinction, which arises in essentially all programming languages. Also there is some lexical feedback, similar in spirit to C's lexer hack.

http://trevorjim.com/haskell-is-not-context-free/

http://trevorjim.com/how-to-prove-that-a-programming-languag...

http://trevorjim.com/c-and-cplusplus-are-not-context-free/ -- the way LALR(1) conflicts are resolved in practice can make a language not context-free

(copying from a recent comment)

> Any programming language that is massively adopted is context free?

I want to have an intuition on what is context free and what is not.

Is D context free?

I mean I want to make a useful language, is being context free practical?

In the past, Pascal was widely used in teaching contexts, for both learning to program and later how to implement a compiler. I've seen Walter say in the past that he got into doing languages from a series of articles in Byte magazine that included the listings for a small Pascal compiler. For your task, you can use Oberon instead, which is a smaller and simpler than Pascal. Oberon-07 is context free up to a point, which is another way of saying that it's not context-free. It'll work well for this exercise. Don't worry about writing a full-fledged compiler, because you'd end up spending forever on the code generator backend. Instead implement half of a compiler.

Here's one project that fits the description of being one half of a compiler—a documentation generator:

https://github.com/schierlm/OberonXref/

Implementing this requires doing the lexer and the parser, but its "backend" streams out documentation pages instead of object files or assembler. The truth is, you wouldn't even need to go that far. Just do the lexer and then start implementing the parser—let's say that your program should just read in source code and then say whether it's valid or not—whether it will parse. Since Oberon is mostly context-free and the natural way to do things is to use a recursive descent parser, you'll get into a rhythm implementing things, until you run into the part that's context-sensitive, at which point things will get uncomfortable. You will find true enlightenment then. This can be done over a weekend, but if you reach the end of the first weekend and realize it will take you two, don't sweat it.

> I mean I want to make a useful language, is being context free practical?

It is. If you do the exercise above, it should be straightforward to figure out several different ways to change the grammar to eliminate context-sensitivity in your parser. You'll realize that the transformations would be minor. They won't compromise the power or practicality of the language, and it's possible to end up with one that is almost exactly the same. The biggest casualty in this case would be reworking a dubious design decision made for aesthetic reasons.

In the article about Python, the author said:

> Most languages of interest are context sensitive, and yet we are trying to use inappropriate tools (context-free grammars and context-free parser generators) to specify and parse them. This leads to bad specifications and bad implementations.

Then what do you think is a better tool to specify and parse languages?

That's unfortunately an open problem. As I mentioned here, lexing is "solved" but parsing isn't:

https://github.com/oilshell/oil/wiki/Why-Lexing-and-Parsing-...

Here are what some recent languages do:

Go: Maintain a written spec [1], with multiple hand-written parsers. (I think the main one is in Go, while gccgo has one in C++?) I believe Go used to be parsed with yacc, but they moved to a hand-written parser for error messages. It looks like [2] was an early attempt to keep it generated.

[1] https://golang.org/ref/spec

[2] https://research.swtch.com/yyerror

-----

Rust: The parser is hand-written, like Go. There's a grammar in the spec, but like Go's, it's not used to generate code, so it isn't tested. They also have an LALR(1) grammar which was suppoed to be an executable specification, but as far as I can tell that effort has not made progress recently.

It used to be done with GNU yacc but it looks like they moved to a Rust-based tool [3]

[1] https://doc.rust-lang.org/grammar.html

[2] https://github.com/rust-lang/lang-team/tree/master/working-g...

[3] https://github.com/rust-lang/wg-grammar/tree/master/grammar

-----

So basically the state of the art is fairly laborious. It's basically write down the grammar, implement it by hand, and try not to make any mistakes. If you need to implement it again, which is extremely common (e.g. for gccgo, for Rust's language server), also try not to make any mistakes.

When you need to change the language, update the spec, and change all the parsers by hand.

I've written multiple recursive-descent parsers based on grammars, and it's not hard if you have examples to test with, but mistakes can easily creep in.

Rely on users to report bugs. There is a "long tail" of programs that will tickle various corner cases.

-----

Here's the approach I took with Oil:

How to Parse Shell Like a Programming Language http://www.oilshell.org/blog/2019/02/07.html

which is basically to do as much work as possible in the lexer, use a high-level programming language translated to C++ for the parser, and to use a DSL for specifying the AST. This approach keeps the mistakes and tedium down because shell is an extremely large language syntactically. (It could be the biggest of any language except for perhaps Perl. Shell is relatively small semantically, but huge syntactically (which is why I'm preoccupied with parsing :) ).

So why does this happen? Couldn't context-free language parsers emulate a lexer by treating individual characters as symbols?

- The lexer recognizes a set of strings of characters.

- The parser recognizes a set of strings of tokens (as returned by the lexer)

But those two languages will have different power in general, so, like Jim points out, when you say something like "Python is context-free" or "Haskell context-free", it's not clear what you're talking about. And it's really false under any reasonable interpretation.

So you can consider them separately, and make a precise statement. But if there's feedback between the two, then you can't do that anymore. The theory doesn't tell you any properties a that the (lexer + parser + feedback mechanism) possess.

That is, regular languages and context-free languages have all sorts of properties proven about them, including ones that let you write code generators. You don't get any of those properties when you have ad hoc feedback mechanism between the lexer and parser.

----

Someone could come up with formalisms for specific types of feedback.

I think OCaml's Menhir has done some of this, but I don't remember the details off hand.

They have written parsers for C (CompCert) and POSIX shell and addressed some of the gaps between theory and practice. I don't use it but they're at least tackling the right problems.

But note that C uses a specific type of feedback (the lexer hack), which isn't identical to what other languages use. So you would have to come up with a formalism for each one, and probably nobody has done that.

https://github.com/haskell/haddock/issues/12

Context free grammars. What this really means is the code should be parseable without having to look things up in a symbol table

That's NOT what context free means. That's a narrow view from someone designing a C-like language and trying to avoid a very specific property of C.

Another example of being context-sensitive, which has nothing to do with symbol tables, is that resolving LALR(1) conflicts in a yacc-style grammar can make the language not context-free. To resolve ambiguity the parser is doing stuff "outside" the grammar.

----

"Context free" is a mathematical term with a precise definition. It's a class of languages that's part of the Chomsky hierarchy [2], which was discovered and described by linguists and mathematicians before any programming language existed, and has applications outside programming languages. Wikipedia does a good job:

https://en.wikipedia.org/wiki/Context-free_grammar

A formal grammar is considered "context free" when its production rules can be applied regardless of the context of a nonterminal. No matter which symbols surround it, the single nonterminal on the left hand side can always be replaced by the right hand side. This is what distinguishes it from a context-sensitive grammar.

Simple examples of languages that's are context-sensitive (not context-free): Lua string literals, Rust raw strings (see other comments in this thread), and shell here docs:

http://lua-users.org/wiki/StringsTutorial

Yes:

    [[ mystring ]]
    [=[ mystring ]=]
    [==[ mystring ]==]

    [=[ mystring ]]    # mismatched

The C language is also not context-free.

[1] http://www.oilshell.org/blog/2017/12/15.html#appendix-lexing...

[2] https://en.wikipedia.org/wiki/Chomsky_hierarchy

Nitpick: that was 1956, by then a few PL did already exist.

Do they? I haven't done a survey of languages but I would guess most are context-sensitive.

That makes using a CFG parser practical and hacking around the problems caused by CS does not take much effort.

Now, there are valid reasons for running a proper language frontend from the IDE: Error reporting of all kinds, not just syntax but also type errors and whatever else the compiler likes to complain about. But there the IDE should not try to replicate the parser. Parsing only a context-free surface language will not catch type errors, exactly because enforcing a static type system requires one to "look things up in a symbol table". So the actual compiler should provide an IDE-friendly mode where it runs its frontend and reports errors back, and the IDE should not try to roll its own version of this.

In other words, the IDE is not relevant either way.

> Any programming language that is massively adopted is context free?

Statically typed languages require semantic analysis and symbol table lookups, so they are out.

And yet we have context-free grammars for all widely adopted statically typed programming languages. And we also have additional semantic checks for all of them. The notion of a "context free programming language" being one that has context free syntax and no semantic checks at all is not a useful notion. Don't worry about it while designing your language.

By contrast, Python is more dynamic, and so the refactoring in PyCharm is pretty weak. It usually catches some of what it needs, but I often need to find the rest. It does appear to be the case that PyCharm is doing flow analysis to infer types. I.e., even PyCharm is doing more than regex matching.

The former is easy, the latter is impossible with regexes only. Which tells you that they are very different things. For refactoring you need not only a proper parse, but also the ability to "look things up in symbol tables". Which is what I said: There are good reasons to run a proper language frontend from the IDE. But syntax highlighting isn't one of these reasons. And refactoring isn't possible with only a simple parse without using symbol tables.

> Statically typed languages require semantic analysis and symbol table lookups, so they are out.

Isn't that the typechecker, not the parser?

Anyway I'm just posting now as I first read this comment when you posted it and tried to recall this blog post by the infamous Steve Yegge, and just finally did: http://steve-yegge.blogspot.com/2007/06/rich-programmer-food...

IntelliJ highlights variables etc. differently if they're unused and can highlight different identifiers in different colors. Not sure about other current IDEs.

That said I never felt like I needed such features, normal syntax highlighting does the job pretty well for me.

Variable renaming respecting scope, function renaming that updates the name at the call sights but ignoring overloads, function extraction... and so on. You may not use it or indeed use eclipse at all.

I can't tell you about the details, clearly something going on beyond syntax highlighting via keyword regex matching. With a beefy enough box it all works well enough.

https://en.m.wikipedia.org/wiki/Language_Server_Protocol

So that IDE support point has become much weaker, if not moot.