Can someone give a simple but non-toy example of a context-sensitive grammar?

I'm trying to understand context-sensitive grammars.

I understand why languages like

1. $\{ww \mid w \in A^*\}$
2. $\{a^n b^n c^n \mid n\in\mathbb{N}\}$

are not context free, but what I'd like to know if a language similar to the untyped lambda calculus is context sensitive.

I'd like to see an example of a simple, but non-toy (I consider the above toy examples), example of a context-sensitive grammar that can, for some production rule, e.g., tell whether or not some string of symbols is in scope currently (e.g. when producing the body of a function).

Are context sensitive grammars powerful enough to make undefined/undeclared/unbound variables a syntactic (rather than semantic) error?

-

migrated from cstheory.stackexchange.comJan 3 '13 at 7:16

This question came from our site for theoretical computer scientists and researchers in related fields.

Yes, I would believe this to be possible, but no I am not willing to explicitly construct that context-sensitive grammar. I will explain my answer, by splitting the question in two different parts.

(1) What would the non-toy example be? It should reflect declaration of variables. My proposal of such a language, abstracted from real programming would be something like this. The alphabet is $\{a,b,;,(,)\}$. $$\{ w_1;w_2;\dots;w_n(x_1;x_2;\dots;x_m) \mid w_i,x_j\in\{a,b\}^*, \mbox{ each }x_j\mbox{ is equal to some }w_i \}$$ That language is context-sensitive.

(2) To show it actually is context-sensitive I would use another formalism. That of a Turing machine with linear use of its tape: a linear bounded automaton LBA. I can program it to do the pattern matching/ I would consecutively consider each $x_j$ and try to match it with a proper $w_j$, letter by letter. LBA's are equivalent to context-sensitive grammars, but much easier to program.

-
Thank you for the post. I'm less familiar with LBAs as of now, so I'm less convinced with point (2). As of point (1), I'm trying to see how to construct rules that will produce, where a variable name is expected as an expression, only one of the variables in the current scope. I don't need to see a whole, formal CSG, but just an informal explanation would work. I can't imagine how to do it with multi-symbol variable names, which is a different use of context than, e.g., using a single non-terminal context to direct subject-verb number agreement in an ~English sentence derivation. –  BlueBomber Jan 2 '13 at 1:50
I on the other hand, am from a formal language background (and also not native speaker of english) and I am having trouble to understand what you exactly want to model/represent. Sorry! In my vision, in this context, $\{ ww \mid w\dots\}$ is npy only a toy example, but a part of what you want to achieve, having full copies of the same string (variable name?) –  Hendrik Jan Jan 2 '13 at 2:01
Thanks for the reply!.$$\{ww | w ... \}$$ is a toy example, and I understand why it's not context-free, but I still don't intuitively "see" how it's context-sensitive, or how a CSG would generate it. Let me try to clarify what I don't understand (there is at least one followup question, but this suffices for now): How could a CSG use a context containing multi-symbol words to generate a one of those words again in a certain production? From what I've seen, CSGs generally work by swapping characters during production and using single symbols to direct a production, but not multi-symbol words. –  BlueBomber Jan 2 '13 at 5:46
Oh. That is a rather concrete question. Without giving the grammar for $\{ ww \}$ I can say a few things. The grammar has two "boundary symbols" say $LR$. During the derivation the string looks like $LwRw$. $L$ generates a letter $a$ from the alphabet together with a copy $M_a$ that will "move" over the letters in $w$ by productions $M_ab \to bM_a$ (technically that is a monotone grammar, equivalent to CS). When the "messenger" reaches $R$ it writes its copy of the letter $M_aR \to Ra$. So longer (multisymbol) strings can be copied. –  Hendrik Jan Jan 2 '13 at 13:49

My favourite example of a context-sensitive language (CSL) is SAT. The Landweber-Kuroda Theorem says that CSL = NSPACE$[n]$. Any SAT instance has a linear-size certificate, so SAT is a CSL. See my question Context-sensitive grammar for SAT? for references and discussion.

Many other NP-hard languages are also in CSL by the same reason, such as CLIQUE.

There are also fairly natural languages in CSL that are even harder.

However, I am not aware of any way to express an arbitrary CSL as a context-sensitive grammar (CSG), other than to use Landweber's construction in Theorem 3 of his paper. In this construction, the CSG describes the reverse of the operation of the linear-bounded automaton that recognizes the CSL. Productions of the CSG describe how a particular state of the machine results from one possible move. Such a CSG is straightforward translation of the automaton into a grammar, so it is not necessarily going to correspond to language features such as being able to declare variables, but will instead be bogged down by the details of the automaton.

If you insist on a CSG rather than a CSL, and if your actual question is specifically about wanting to see a CSG for a language that involves restricted variable scoping, then Hendrik Jan's answer seems to be a good start.

-

Yes, context-sensitive grammars (CSG) are powerful enough to make undefined/undeclared/unbound variables check, but unfortunately we don't know any efficient algorithm to parse strings of CSG.

A real example of a context-sensitive language is the C programming language. A feature like declare variables first and then use them later make C-language a context-sensitive language (CSL). (I don't know about untyped lambda calculus).

And because we don't know any linear parsing algorithm for CSL (or CSG). That is the reason in compiler design, we use CFG (and its parsing algoritm only) for syntax checking since we know efficient algorithms to parse CFG (if it's in restricted form). Compilers first parse a context free feature and then later handle context-sensitive features in a problematically way (for example, checks any used variable in the symbol table if it's defined. Otherwise, it generates an error).

Also context-sensitive grammar is used in natural-language processing (NLP). And most natural languages are examples of context-sensitive languages. (I am not sure for the Sanskrit language).

I will try to explain it with a silly but simple example (it's just an idea, you can refine it):

NOUN     -->  { BlueBomber, Grijesh, I, We}
TENSE    -->  { am, was, is, were}
VERB     -->  { going, eating, working}

SENTENCE --> <NOUN> <TENSE> <VERB>


Now, using this grammar, we can generate some correct statements, but some are wrong too. For example,

SENTENCE --> <NOUN>   <TENSE>   <VERB>
Grijesh    is       working       [Correct statement]


But

             Grijesh    am       working       [wrong statement]


Reason: the value of <TENSE> depends on value <NOUN> (for example, I &lt;TENNSE> --> I am) and hence the grammar doesn't generate correct statements in the English language.

Actually we can't write a context-free grammar for complete English!

You might have noticed, any natural language translator or grammar checker doesn't works correctly (try with long statements). Because this problem comes under the context-sensitive parsing algorithm.

REFERENCE: You can watch Dr. Arun Kumar's lectures. In some lecture he explains exactly what you are interested in.

-
Thank you for the information, it will undoubtedly be helpful for others interested in this same topic, but it's only partially related to what I would I was asking. I'm not concerning myself with parsing a string generated by a CSG, but to see a simple--even silly--example of a formal CSG that generates well-formed abstractions (no unbound variables within the body of the function). I can imagine a CSG to generate correct "English" strings, as a single symbol can direct the subject/verb agreement, but with abstractions, variables are typically composed of multiple symbols. –  BlueBomber Dec 31 '12 at 18:17
@BlueBomber : thanksI will sure answer you, Its night in India..N Happy new year! :) –  Grijesh Chauhan Dec 31 '12 at 18:21
It seems I can only do that a limited number of times, and according to (this) [meta.scicomp.stackexchange.com/questions/156/…, I should delete this question and repost it in the more appropriate place... –  BlueBomber Jan 1 '13 at 7:34
@BlueBomber I have flagged to shift, You can also do. –  Grijesh Chauhan Jan 1 '13 at 7:35