3 ms·

Python is not context free.

by peterwoo 14y ago

masklinn 14y ago
And there's no way java is. Not sure about Go.
- lucian1900 14y ago
  The Java language specification includes a description of the language as a context free grammar. That alone does not make it a nice language, of course.
  - masklinn 14y ago
    > The Java language specification includes a description of the language as a context free grammar. I can only assume that it's lying its pants off, as I noted in an other subthread `(a) - (b)` can't be parsed (to an AST) without knowing the identity of `a` in the current scope: if it's a type the expression is a cast of `-(b)` to `a`, if it's a value it's a subtraction of `(b)` from `(a)`.
    - peterwoo 14y ago
      It can be parsed to an AST -- as you note, it can be parsed into two ASTs. It's called an ambiguous grammar, which can still be context free.
      - masklinn 14y ago
        > It can be parsed to an AST -- as you note, it can be parsed into two ASTs. By "it can't be parsed to an AST" I meant "it can't be parsed to a useful AST used to run or generate code" on its own, it needs to be disambiguated through contextual information before anything can be done with the prospective subtree. Sorry for the lack of clarity. > It's called an ambiguous grammar, which can still be context free. The only way to disambiguate is to provide expression context (namely visible name bindings at this point), it's essentially the same problem Eli Bendersky described when talking about C grammar's context-sensitivity: http://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar/ http://eli.thegreenplace.net/2007/11/24/the-context-sensitiv...
Scaevolus 14y ago
Indentation is handled by the lexer, not the parser. The parser is context free-- LL(1), actually. The lexer maintains one extra stack to track indentations, meaning it's more of a PDA than a DFA, but the actual complication is mild.
- peterwoo 14y ago
  The language is not context free, although I agree there is a parsing solution which is not terribly complex.
  - lucian1900 14y ago
    It is context free. INDENT and OUTDENT are directly equivalent to { and } in other grammars.
    - peterwoo 14y ago
      The difference is that INDENT and OUTDENT have to be defined by context-sensitive productions. Even if this occurs in what would otherwise be the "lexing" stage of the parser.

Python is not context free.

masklinn 14y ago

And there's no way java is. Not sure about Go.

lucian1900 14y ago
The Java language specification includes a description of the language as a context free grammar. That alone does not make it a nice language, of course.
- masklinn 14y ago
  > The Java language specification includes a description of the language as a context free grammar. I can only assume that it's lying its pants off, as I noted in an other subthread `(a) - (b)` can't be parsed (to an AST) without knowing the identity of `a` in the current scope: if it's a type the expression is a cast of `-(b)` to `a`, if it's a value it's a subtraction of `(b)` from `(a)`.
  - peterwoo 14y ago
    It can be parsed to an AST -- as you note, it can be parsed into two ASTs. It's called an ambiguous grammar, which can still be context free.
    - masklinn 14y ago
      > It can be parsed to an AST -- as you note, it can be parsed into two ASTs. By "it can't be parsed to an AST" I meant "it can't be parsed to a useful AST used to run or generate code" on its own, it needs to be disambiguated through contextual information before anything can be done with the prospective subtree. Sorry for the lack of clarity. > It's called an ambiguous grammar, which can still be context free. The only way to disambiguate is to provide expression context (namely visible name bindings at this point), it's essentially the same problem Eli Bendersky described when talking about C grammar's context-sensitivity: http://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar/ http://eli.thegreenplace.net/2007/11/24/the-context-sensitiv...

Scaevolus 14y ago

Indentation is handled by the lexer, not the parser. The parser is context free-- LL(1), actually. The lexer maintains one extra stack to track indentations, meaning it's more of a PDA than a DFA, but the actual complication is mild.

peterwoo 14y ago
The language is not context free, although I agree there is a parsing solution which is not terribly complex.
- lucian1900 14y ago
  It is context free. INDENT and OUTDENT are directly equivalent to { and } in other grammars.
  - peterwoo 14y ago
    The difference is that INDENT and OUTDENT have to be defined by context-sensitive productions. Even if this occurs in what would otherwise be the "lexing" stage of the parser.