9 ms·

I want to implement a toy programming language, but I have questions regarding the following in that article: > Context free grammars. What this really means i

I want to implement a toy programming language, but I have questions regarding the following in that article: > Context free grammars. What this really means is the code should be parseable without having to look things up in a symbol table. C++ is famously not a context free grammar. A context free grammar, besides making things a lot simpler, means that IDEs can do syntax highlighting without integrating in most of a compiler front end, i.e. third party tools become much more likely to exist. Many complex languages, like c++, rust are not context free. We therefore need semantic analysis. What programming language features will be compromised if I stick to context free? Will the end result be as expressive as c++/rust? Any programming language that is massively adopted is context free? BTW, the toy language I want to build will be something similar to javascript.

steveklabnik 7y ago
Rust is almost context free; there’s one relatively rarely used bit that requires context. And usually it’s only one or two bytes of it.
- h-cobordism 7y ago
  You're referring to raw string literals, right?
  - steveklabnik 7y ago
    Yes. You need to include more #s than you have in the string, and it’s rare to have a ton of them, let alone a raw string literal in the first place.
    - wtetzner 7y ago
      Does that make the grammar context-sensitive, or just the lexer?
      - steveklabnik 7y ago
        This is not an area of my expertise, so I can't say.
- deleted 7y ago
  [deleted]
desc 7y ago
https://stackoverflow.com/questions/898489/what-programming-languages-are-context-free https://stackoverflow.com/questions/898489/what-programming-... 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...
- chubot 7y ago
  The two top answers are in conflict. The second answer with 43 points is closer to right: 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/ 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/ 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/haskell-is-not-context-free/ http://trevorjim.com/how-to-prove-that-a-programming-language-is-context-free/ http://trevorjim.com/how-to-prove-that-a-programming-languag... http://trevorjim.com/c-and-cplusplus-are-not-context-free/ 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)
  - WalterBright 7y ago
    The implementation of D has a lexer that is independent of the parser, and a parser that is independent of the rest of the implementation. I have resisted enhancement proposals that would put holes in those walls.
tom_mellior 7y ago
This point in the article is pretty weird (the rest is good). I don't think IDEs do a lot of parsing to do syntax highlighting, isn't it all just regex matching to identify the types of tokens? I'd be interested in real-world examples of IDEs doing something more complex to achieve syntax highlighting. And conversely, examples of imperfect syntax highlighting of C++ due to the undecidability of its input language. I mean, yes, an actual parser for C++ must be able to execute template computations, and that's a pain, but why would that be relevant to syntax highlighting? It isn't. 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.
- alpaca128 7y ago
  > I don't think IDEs do a lot of parsing to do syntax highlighting, isn't it all just regex matching to identify the types of tokens? 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.
  - dehrmann 7y ago
    IntelliJ has context-aware autocomplete. Type this.field.get and it will show methods and fields starting with get for whatever type field is. There's a lot of context needed to make that happen.
tomp 7y ago
The purpose of context-free, or rather unambiguous grammars in general, isn't for the benefit of compilers, but for the benefit of humans. A computer can parse almost everything, even regexes (with backtracking etc.), it's the humans that trip over fancy grammars.
kyllo 7y ago
Context-free has nothing to do with symbol tables, it just means that in the grammar, the left-hand side of a production rule can only have a single non-terminal symbol, which can always be replaced by the expression on the right-hand side, without ambiguity. 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.
- johannes1234321 7y ago
  > 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. The classic example, I guess, is the most vexing parse: https://en.m.wikipedia.org/wiki/Most_vexing_parse https://en.m.wikipedia.org/wiki/Most_vexing_parse """ The line TimeKeeper time_keeper(Timer()); is seemingly ambiguous, since it could be interpreted either as 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)
a1369209993 7y ago
Note that "context free grammars", in the technical sense, is completely the wrong thing. Eg, enforcing consistent indentation is not context free: foo() { return; } ↓↓↓↓↓↓↓↓↓↓↓ aaaa{ bbbbreturn; cccc} ↓↓↓↓↓↓↓↓↓↓↓ aaaabbbbcccc This is equivalent to aⁿbⁿcⁿ, which is pretty much the canonical example of a non-context-free language. 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
- qznc 7y ago
  There is a trick for indentation: Use a context-sensitive lexer in front of a context-free parser. The lexer serves indent and dedent tokens to the parser. With this trick, you can parse Python with a context-free grammar.
- bmn__ 7y ago
  There are plenty, the majority even, of programming languages that do not enforce consistent indentation. You make a false generalisation when you claim that CFG are completely the wrong thing.
- tom_mellior 7y ago
  > This is equivalent to aⁿbⁿcⁿ Is it? You only indent with spaces, so a = b = c = ' ', and the problem you claim disappears.
  - gbear605 7y ago
    I'm not sure that's a solution. The problem is verifying that the three 'n's are equal, not that 'a', 'b', and 'c' are equal. Solving this cannot be done in a context free grammar [0]. [0]: https://cs.stackexchange.com/questions/33153/is-an-bn-cn-context-free https://cs.stackexchange.com/questions/33153/is-an-bn-cn-con...
    - tom_mellior 7y ago
      Yeah, you're right. I got confused by the original phrasing.
froh 7y ago
Notwithstanding the other comments on context free vs sensitive, the 2014 article predates the language server protocol, which neatly moves the support for programming languages from the IDE to a stand alone tool tied to the language: https://microsoft.github.io/language-server-protocol/ https://microsoft.github.io/language-server-protocol/ https://en.m.wikipedia.org/wiki/Language_Server_Protocol https://en.m.wikipedia.org/wiki/Language_Server_Protocol So that IDE support point has become much weaker, if not moot.

steveklabnik 7y ago

Rust is almost context free; there’s one relatively rarely used bit that requires context. And usually it’s only one or two bytes of it.

h-cobordism 7y ago
You're referring to raw string literals, right?
- steveklabnik 7y ago
  Yes. You need to include more #s than you have in the string, and it’s rare to have a ton of them, let alone a raw string literal in the first place.
  - wtetzner 7y ago
    Does that make the grammar context-sensitive, or just the lexer?
    - steveklabnik 7y ago
      This is not an area of my expertise, so I can't say.
deleted 7y ago
[deleted]

desc 7y ago

https://stackoverflow.com/questions/898489/what-programming-languages-are-context-free https://stackoverflow.com/questions/898489/what-programming-... 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...

chubot 7y ago
The two top answers are in conflict. The second answer with 43 points is closer to right: 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/ 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/ 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/haskell-is-not-context-free/ http://trevorjim.com/how-to-prove-that-a-programming-language-is-context-free/ http://trevorjim.com/how-to-prove-that-a-programming-languag... http://trevorjim.com/c-and-cplusplus-are-not-context-free/ 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)
- WalterBright 7y ago
  The implementation of D has a lexer that is independent of the parser, and a parser that is independent of the rest of the implementation. I have resisted enhancement proposals that would put holes in those walls.

tom_mellior 7y ago

This point in the article is pretty weird (the rest is good). I don't think IDEs do a lot of parsing to do syntax highlighting, isn't it all just regex matching to identify the types of tokens? I'd be interested in real-world examples of IDEs doing something more complex to achieve syntax highlighting. And conversely, examples of imperfect syntax highlighting of C++ due to the undecidability of its input language. I mean, yes, an actual parser for C++ must be able to execute template computations, and that's a pain, but why would that be relevant to syntax highlighting? It isn't. 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.

alpaca128 7y ago
> I don't think IDEs do a lot of parsing to do syntax highlighting, isn't it all just regex matching to identify the types of tokens? 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.
- dehrmann 7y ago
  IntelliJ has context-aware autocomplete. Type this.field.get and it will show methods and fields starting with get for whatever type field is. There's a lot of context needed to make that happen.

tomp 7y ago

The purpose of context-free, or rather unambiguous grammars in general, isn't for the benefit of compilers, but for the benefit of humans. A computer can parse almost everything, even regexes (with backtracking etc.), it's the humans that trip over fancy grammars.

kyllo 7y ago

Context-free has nothing to do with symbol tables, it just means that in the grammar, the left-hand side of a production rule can only have a single non-terminal symbol, which can always be replaced by the expression on the right-hand side, without ambiguity. 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.

johannes1234321 7y ago
> 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. The classic example, I guess, is the most vexing parse: https://en.m.wikipedia.org/wiki/Most_vexing_parse https://en.m.wikipedia.org/wiki/Most_vexing_parse """ The line TimeKeeper time_keeper(Timer()); is seemingly ambiguous, since it could be interpreted either as 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)

a1369209993 7y ago

Note that "context free grammars", in the technical sense, is completely the wrong thing. Eg, enforcing consistent indentation is not context free: foo() { return; } ↓↓↓↓↓↓↓↓↓↓↓ aaaa{ bbbbreturn; cccc} ↓↓↓↓↓↓↓↓↓↓↓ aaaabbbbcccc This is equivalent to aⁿbⁿcⁿ, which is pretty much the canonical example of a non-context-free language. 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

qznc 7y ago
There is a trick for indentation: Use a context-sensitive lexer in front of a context-free parser. The lexer serves indent and dedent tokens to the parser. With this trick, you can parse Python with a context-free grammar.
bmn__ 7y ago
There are plenty, the majority even, of programming languages that do not enforce consistent indentation. You make a false generalisation when you claim that CFG are completely the wrong thing.
tom_mellior 7y ago
> This is equivalent to aⁿbⁿcⁿ Is it? You only indent with spaces, so a = b = c = ' ', and the problem you claim disappears.
- gbear605 7y ago
  I'm not sure that's a solution. The problem is verifying that the three 'n's are equal, not that 'a', 'b', and 'c' are equal. Solving this cannot be done in a context free grammar [0]. [0]: https://cs.stackexchange.com/questions/33153/is-an-bn-cn-context-free https://cs.stackexchange.com/questions/33153/is-an-bn-cn-con...
  - tom_mellior 7y ago
    Yeah, you're right. I got confused by the original phrasing.

froh 7y ago

Notwithstanding the other comments on context free vs sensitive, the 2014 article predates the language server protocol, which neatly moves the support for programming languages from the IDE to a stand alone tool tied to the language: https://microsoft.github.io/language-server-protocol/ https://microsoft.github.io/language-server-protocol/ https://en.m.wikipedia.org/wiki/Language_Server_Protocol https://en.m.wikipedia.org/wiki/Language_Server_Protocol So that IDE support point has become much weaker, if not moot.