Search code examples
context-free-grammarcontext-sensitive-grammar

What does context mean by context-free and context-sensitive grammars?


If I have something like var string = "var";, then after the first double quote the rules change, and the var does not mean the same thing as it means at the beginning of the text. After the second double quote things turn back to normal. How is that not considered context?

(Please don't use those arrows in your answer, try a natural language instead!)


Solution

  • The direction of the arrow is important, so if I can't talk about it, it's going to be difficult to explain. So, sorry, I'm going to use arrows. They really aren't complicated.

    The expression A -> ... means "an A is ...". It does not mean "... is an A". Context-free means that if A can be "..." in some context, it can be "..." in any context. But the arrow always points from category to specific; never backwards.

    In your example, an identifier is a letter followed by a bunch of alphanumeric symbols:

     identifier -> letter (letter OR digit)...
    

    So identifier could be var. That doesn't mean that var is always an identifier, as your example shows. The arrow points in one direction.

    Because the grammar is context-free, if when we are looking for an identifier in some context and we accept var as an identifier, then in any other context where we are looking for an identifier, we must also accept var.

    But there are contexts (between quotes) where we are not looking for an identifier. That's fine; the context-free condition has not been broken. The context applies in the direction of the arrow.