Hacker News new | past | comments | ask | show | jobs | submit login

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.



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

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 ]==]
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...

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


> [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.


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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: