News for hackers. Stuff that matters.
Re:The naked truth about writing a programming language (2014) by kyllo on Saturday May 02, 2020 @09:17PM (#23056150)
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.

Re:The naked truth about writing a programming language (2014) by johannes1234321 on Saturday May 02, 2020 @10:33PM (#23056445)
> 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

"""

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)

Re:The naked truth about writing a programming language (2014) by kyllo on Sunday May 03, 2020 @06:22PM (#23062368)
Yes and programming languages are human interfaces to machine instructions, so context sensitivity can be manageable and even desirable to human users of the language, even if it makes the implementation of the language interpreter more complex or less elegant. Programming language designers make this trade-off all the time.
Re:The naked truth about writing a programming language (2014) by bmn__ on Sunday May 03, 2020 @06:54AM (#23058227)
> without ambiguity

This is not a distinguishing feature. (I'm assuming you meant something else.) Example of a CFG with ambiguity:

    S → S S
    S → x
Re:The naked truth about writing a programming language (2014) by kyllo on Sunday May 03, 2020 @06:11PM (#23062274)
You're right, I meant that each valid RHS matches one and only one LHS--but that's also true of CSGs.
Re:The naked truth about writing a programming language (2014) by signaru on Sunday May 03, 2020 @03:33AM (#23057488)
In BASIC the equal symbol "=" can mean assignment or equality depending on "context". Is this an example of a non context free?

On the other hand, I've seen EBNF definition of BASIC (VB, actually). Is this a contradiction?

(just someone still learning)

Re:The naked truth about writing a programming language (2014) by kyllo on Sunday May 03, 2020 @06:17PM (#23062325)
It's still context-free, the reason is because by the time you hit the '=' symbol you already know whether you're in a <Statement> or a <Compare Exp> production rule, based on the preceding symbols (namely the LET keyword), based on these excerpts from the BASIC EBNF:

    <Statement>   ::= CLOSE '#' Integer
                    | DATA <Constant List> 
                    [...]    
                    | LET Id '=' <Expression> 
                    [...]
                    | Remark

    <Compare Exp> ::= <Add Exp> '='  <Compare Exp> 
                    | <Add Exp> '<>' <Compare Exp> 
                    | <Add Exp> '><' <Compare Exp> 
                    | <Add Exp> '>'  <Compare Exp> 
                    | <Add Exp> '>=' <Compare Exp> 
                    | <Add Exp> '<'  <Compare Exp> 
                    | <Add Exp> '<=' <Compare Exp> 
                    | <Add Exp>
Re:The naked truth about writing a programming language (2014) by foldr on Sunday May 03, 2020 @04:38AM (#23057745)
A context free grammar can handle this fine - as you can see from the EBNF - so no, it's not an example.