5 ms·

> One of the best parts of Go is that the grammar is (almost) entirely context-free You mean almost regular. Almost all programming language grammars are conte

> One of the best parts of Go is that the grammar is (almost) entirely context-free You mean almost regular. Almost all programming language grammars are context-free. Regularity is a much higher bar to reach.

Crito 13y ago
Pretty sure he means 'almost' context free (as opposed to 'very' context sensitive. C is context sensitive. A language like C++ is heavily context sensitive (actually, C++'s templates make it recursively enumerable iirc, so even worse..)). Being regular would mean that you could decide it with regular expressions. Regular expressions are insufficiently powerful for matched parentheses of arbitrary depth, which is a good hint that Lisp and Go are not regular (or 'near' regular).
- mehrdada 13y ago
  > Being regular would mean that you could decide it with regular expressions. Hence almost regular. Of course, there is no concrete definition for "almost regular", but what I mean by it (Rob Pike himself also characterizes it as such too[1]), is that you get to decide which way to parse a construct quite definitely early in the token stream and you don't have to read arbitrary following tokens to figure out how to construct a parse tree branch. C++ is the exception here. Most other block oriented high level programming language (at the syntax level) are indeed fully context-free, so just being context-free does not deserve a high prize. [1]: http://www.infoq.com/presentations/Go-Google http://www.infoq.com/presentations/Go-Google
  - Crito 13y ago
    Do you have the timestamp of when in this talk Rob Pike mentions this? If he says that it is "almost regular", then that settles it in my book, but I am pretty certain that you are wrong about most block oriented high level languages being context free. C++ is an extreme case, as it's Turing complete, but C is definitely context sensitive (http://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar/ http://eli.thegreenplace.net/2007/11/24/the-context-sensitiv...), Perl is just as bad as C++ (http://www.perlmonks.org/?node_id=663393 http://www.perlmonks.org/?node_id=663393), and I can't find a link for it right now but IIRC the Java is context sensitive for some reason too.
    - mehrdada 13y ago
      In that video mentions regularity around minute 51. I have seen him using that term in person too. The blog post you mentioned is misinformed. YACC does not parse all context-free grammars. It generates LALR parsers, that parse a strict subset of context-free languages (called deterministic context free languages). Not parseable with YACC does not imply not context free. It is important to distinguish the programming language and its syntax. In most real compilers, the parser accepts a superset of the programming language and then other components of the compiler restrict it with semantic rules like type checking. What I am talking about here is the syntax only. In that sense, things like C, Java, and C# are most definitely context-free. The language specification usually comes with a context-free grammar describing the syntax. Whether you can use it to parse programs efficiently (in O(n)) and meaningfully is another matter.
      - Crito 13y ago
        If a piece of C code that parses in two different ways, depending on what other code may have also been parsed, isn't context sensitive, then what is?
        mehrdada 13y ago
        http://en.wikipedia.org/wiki/Context-sensitive_language#Examples http://en.wikipedia.org/wiki/Context-sensitive_language#Exam...
  - chrismorgan 13y ago
    You are meaning that it is an LL(k) parser. Rust is an example of an LL(1) parser. Various things that might be convenient to have in the language in certain circumstances have been rejected because they would cause ambiguity in the parser which would require arbitrary lookahead. https://en.wikipedia.org/wiki/LL_parser https://en.wikipedia.org/wiki/LL_parser
    - mehrdada 13y ago
      What I have in mind is more loosely defined than LL(k) and in a way more restrictive than a general LL(k) grammar, but LL(k) is probably a good way to formally capture something close to what I had in mind. I try to avoid using the term "almost regular" as it is imprecise. I only used it since it was relevant to the context and I'd heard Rob Pike describe Go as having almost regular syntax several times.
masklinn 13y ago
> Almost all programming language grammars are context-free. Er no, almost no programming language grammar is actually context-free (in the sense that they can be parsed unambiguously according to a context-free grammar)
- mehrdada 13y ago
  Unambiguous parsing is not a requirement for a language to be context-free. Your use of "actually context-free" is a stretch of the definition by a huge margin. In fact, the definition of a context-free language does not depend on a specific grammar at all. You can have a context-free grammar that parses a language unambiguously and another grammar that ambiguously defines the same language. It is true, however, that most formal grammars for programming languages define a strict superset of the actual language and then restrict it according to semantic rules (e.g. type checking, definite assignment rules). That is why in my original comment, I was careful to use the phrase "programming language grammars", instead of "programming languages".

Crito 13y ago

Pretty sure he means 'almost' context free (as opposed to 'very' context sensitive. C is context sensitive. A language like C++ is heavily context sensitive (actually, C++'s templates make it recursively enumerable iirc, so even worse..)). Being regular would mean that you could decide it with regular expressions. Regular expressions are insufficiently powerful for matched parentheses of arbitrary depth, which is a good hint that Lisp and Go are not regular (or 'near' regular).

mehrdada 13y ago
> Being regular would mean that you could decide it with regular expressions. Hence almost regular. Of course, there is no concrete definition for "almost regular", but what I mean by it (Rob Pike himself also characterizes it as such too[1]), is that you get to decide which way to parse a construct quite definitely early in the token stream and you don't have to read arbitrary following tokens to figure out how to construct a parse tree branch. C++ is the exception here. Most other block oriented high level programming language (at the syntax level) are indeed fully context-free, so just being context-free does not deserve a high prize. [1]: http://www.infoq.com/presentations/Go-Google http://www.infoq.com/presentations/Go-Google
- Crito 13y ago
  Do you have the timestamp of when in this talk Rob Pike mentions this? If he says that it is "almost regular", then that settles it in my book, but I am pretty certain that you are wrong about most block oriented high level languages being context free. C++ is an extreme case, as it's Turing complete, but C is definitely context sensitive (http://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar/ http://eli.thegreenplace.net/2007/11/24/the-context-sensitiv...), Perl is just as bad as C++ (http://www.perlmonks.org/?node_id=663393 http://www.perlmonks.org/?node_id=663393), and I can't find a link for it right now but IIRC the Java is context sensitive for some reason too.
  - mehrdada 13y ago
    In that video mentions regularity around minute 51. I have seen him using that term in person too. The blog post you mentioned is misinformed. YACC does not parse all context-free grammars. It generates LALR parsers, that parse a strict subset of context-free languages (called deterministic context free languages). Not parseable with YACC does not imply not context free. It is important to distinguish the programming language and its syntax. In most real compilers, the parser accepts a superset of the programming language and then other components of the compiler restrict it with semantic rules like type checking. What I am talking about here is the syntax only. In that sense, things like C, Java, and C# are most definitely context-free. The language specification usually comes with a context-free grammar describing the syntax. Whether you can use it to parse programs efficiently (in O(n)) and meaningfully is another matter.
    - Crito 13y ago
      If a piece of C code that parses in two different ways, depending on what other code may have also been parsed, isn't context sensitive, then what is?
      - mehrdada 13y ago
        http://en.wikipedia.org/wiki/Context-sensitive_language#Examples http://en.wikipedia.org/wiki/Context-sensitive_language#Exam...
- chrismorgan 13y ago
  You are meaning that it is an LL(k) parser. Rust is an example of an LL(1) parser. Various things that might be convenient to have in the language in certain circumstances have been rejected because they would cause ambiguity in the parser which would require arbitrary lookahead. https://en.wikipedia.org/wiki/LL_parser https://en.wikipedia.org/wiki/LL_parser
  - mehrdada 13y ago
    What I have in mind is more loosely defined than LL(k) and in a way more restrictive than a general LL(k) grammar, but LL(k) is probably a good way to formally capture something close to what I had in mind. I try to avoid using the term "almost regular" as it is imprecise. I only used it since it was relevant to the context and I'd heard Rob Pike describe Go as having almost regular syntax several times.

masklinn 13y ago

> Almost all programming language grammars are context-free. Er no, almost no programming language grammar is actually context-free (in the sense that they can be parsed unambiguously according to a context-free grammar)

mehrdada 13y ago
Unambiguous parsing is not a requirement for a language to be context-free. Your use of "actually context-free" is a stretch of the definition by a huge margin. In fact, the definition of a context-free language does not depend on a specific grammar at all. You can have a context-free grammar that parses a language unambiguously and another grammar that ambiguously defines the same language. It is true, however, that most formal grammars for programming languages define a strict superset of the actual language and then restrict it according to semantic rules (e.g. type checking, definite assignment rules). That is why in my original comment, I was careful to use the phrase "programming language grammars", instead of "programming languages".