3 ms·

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-termina

by kyllo 6y ago

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.

johannes1234321 6y ago
> 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 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)
- kyllo 6y ago
  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.
signaru 6y ago
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)
- foldr 6y ago
  A context free grammar can handle this fine - as you can see from the EBNF - so no, it's not an example.
- kyllo 6y ago
  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>
bmn__ 6y ago
> 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
- kyllo 6y ago
  You're right, I meant that each valid RHS matches one and only one LHS--but that's also true of CSGs.

by kyllo 6y ago

johannes1234321 6y ago

> 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 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)

kyllo 6y ago
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.

signaru 6y ago

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)

foldr 6y ago
A context free grammar can handle this fine - as you can see from the EBNF - so no, it's not an example.
kyllo 6y ago
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>

bmn__ 6y ago

> 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

kyllo 6y ago
You're right, I meant that each valid RHS matches one and only one LHS--but that's also true of CSGs.