Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

When a keyword means different things in different contexts, is that an example of context sensitivity?

According to this answer => in Scala is a keyword which has two different meanings: 1 to denote a function type: Double => Double and 2 to create a lambda expression: (x: Double): Double => 2*x.

How does this relate to formal grammars, i.e. does this make Scala context sensitive?

I know that most languages are not context free, but I'm not sure whether the situation I'm describing has anything to do with that.


Edit:

Seems like I don't understand context sensitive grammars well enough. I know how the production rules are supposed to look, and what they mean ("this production applies only if A is surrounded by these symbols"), but I'm just not sure how they relate to actual (programming) languages.

I think my confusion stems from reading something like "Chomsky introduced this term because a word's meaning can depend on its context", and I connected => with the term "word" in the quote, and those two uses of it being two separate contexts.

It be great if an answer would address my confusion.

like image 211
corazza Avatar asked Mar 08 '14 18:03

corazza


1 Answers

It's been a while since I've handled formal language theory, but I'll bite.

"Context-free" means that the production rules required in the corresponding grammar do not have a "context". It does not mean that a specific symbol cannot appear in different rules.


Addressing the edit: in other words (and more informally), deciding whether a language is context-free or context-sensitive boils down not to looking at the "meaning" of a specific "word" or "words". Instead, it amounts to looking at the set of all legal expressions in that language, and seeing whether you can "encode" them only by taking into account the positional relationships the component "words" have with one another. This is essentially what the Pumping Lemma checks.


For example:

S → Type"="Body
Type → "Double"
Type → "Double""=>""Double"
Body → Lambda
Body → NormalBody
NormalBody → "x"
Lambda -> "x""=>"NormalBody

Where S is of course the start symbol, uppercased IDs are nonterminals, and quoted strings are terminals. Obviously, this can generate a string like:

Double=>Double=x=>x

but the grammar is still context-free.

So just this, as in the observation that the nonterminal "=>" can appear in two "places" of the program, does not make Scala context-sensitive.

However, it does not mean that:

  • the entire Scala language is context-free,
  • it is context-sensitive - it can be even more complex,
  • if you would like to encode the semantics of Scala into a grammar, you would end up with either a context-free or a context-sensitive one.

The last thing is especially relevant since you've mentioned "meaning" in the (nomen omen) context of formal languages.

like image 141
mikołak Avatar answered Sep 23 '22 05:09

mikołak