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

Question

I'm trying to understand context-sensitive grammars, and I understand why languages like

1. {ww | w is a string}
2. {aⁿ bⁿ cⁿ | a,b,c are symbols}

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?

Mignonmignonette

This question was reposted and migrated and finally ended up on Computer Science: Can someone give a simple but non-toy example of a context-sensitive grammar? – Immersionism

Moreover, I voted to have this deleted. – Mignonmignonette

Answer 1

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 <TENSE> --> 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.}

Expansion

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. – Mignonmignonette

@Mignonmignonette : thanksI will sure answer you, Its night in India..N Happy new year! :) – Expansion

@Mignonmignonette ask your question here ..I will try it myself ..you can flag to move question – Expansion

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... – Mignonmignonette

@Mignonmignonette I have flagged to shift, You can also do. – Expansion

Since this answer has been written, other grammars that are efficient and do the work described above, namely the accord between nouns and verbs. Check the subject of Feature-based CFG or FCFG stackoverflow.com/search?q=FCFG or #35963850 – Poundage

@Poundage annotated CFGs are not CFG – Expansion