3 ms·

what is context free language anyway? context free grammar had a clear definition in parsing, not sure i understand how that can be extended to languages.

wtetzner 6y ago
I read it to mean that the language's grammar is context free, but I guess I'm not sure if that's what was meant.
chubot 6y ago
The OP is abusing the term "context free". He's saying it avoids "the lexer hack" [1]: 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 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 http://lua-users.org/wiki/StringsTutorial Yes: [[ mystring ]] [=[ mystring ]=] [==[ mystring ]==] No: [=[ mystring ]] # mismatched Matching this language requires a context-sensitive grammar and can't be done with a context-free grammar. It's not all that easy to prove: See the posts from Trevor Jim regarding proofs. The C language is also not context-free. [1] http://www.oilshell.org/blog/2017/12/15.html#appendix-lexing-the-c-language http://www.oilshell.org/blog/2017/12/15.html#appendix-lexing... [2] https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy
- bmn__ 6y ago
  > [CF] was discovered and described by linguists and mathematicians before any programming language existed Nitpick: that was 1956, by then a few PL did already exist.

wtetzner 6y ago

I read it to mean that the language's grammar is context free, but I guess I'm not sure if that's what was meant.

chubot 6y ago

The OP is abusing the term "context free". He's saying it avoids "the lexer hack" [1]: 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 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 http://lua-users.org/wiki/StringsTutorial Yes: [[ mystring ]] [=[ mystring ]=] [==[ mystring ]==] No: [=[ mystring ]] # mismatched Matching this language requires a context-sensitive grammar and can't be done with a context-free grammar. It's not all that easy to prove: See the posts from Trevor Jim regarding proofs. The C language is also not context-free. [1] http://www.oilshell.org/blog/2017/12/15.html#appendix-lexing-the-c-language http://www.oilshell.org/blog/2017/12/15.html#appendix-lexing... [2] https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy

bmn__ 6y ago
> [CF] was discovered and described by linguists and mathematicians before any programming language existed Nitpick: that was 1956, by then a few PL did already exist.