Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have been having some fun lately exploring the development of language parsers in the context of how they fit into the Chomsky Hierarchy.

What is a good real-world (ie not theoretical) example of a context-sensitive grammar?

share|improve this question
8  
Does programming language count? –  Loki Astari Dec 13 '12 at 4:01
    
@LokiAstari Of course. –  Evan Plaice Dec 13 '12 at 4:18
2  
I guess programming languages count, but do not make for a good solution, as the complexity of context-sensitivity is normally replaced by a context-free grammar with semantic analysis instead. –  Frank Dec 13 '12 at 6:18
    
@Frank I guess my problem is, I can't really grasp what a context-sensitive languages is without applying it to some real-world usage. –  Evan Plaice Dec 13 '12 at 6:59
    
There are some human languages that may not require recursively enumerable language parsers and thus fall into the type 1 (context senstive) set of languages. cs.virginia.edu/~evans/cs3102/?p=138 –  MichaelT Dec 13 '12 at 14:38

3 Answers 3

up vote 8 down vote accepted

Good question. Although as mentioned in the comments very many programming languages are context-sensitive, that context-sensitivity is often not resolved in the parsing phase but in later phases -- that is, a superset of the language is parsed using a context-free grammar, and some of those parse trees are later filtered out.

However, that does not mean that those languages aren't context-sensitive, so here are some examples:


Haskell allows you to define functions that are used as operators, and to also define the the precedence and associativity of those operators. In other words, you can't build the correct parse tree for an operator expression like:

a @@ b @@ c ## d ## e

unless you've already parsed the precedence/associativity declarations for @@ and ##:

infixr 8 @@
infixr 6 ##

A second example is Bencode, a data language that prefixes content with its length:

<length>:<contents>

The issue with this format is that it's pretty much impossible to parse without something context-sensitive, because the only way to figure out the "field" sizes is by ... parsing the string.


A third example is XML, assuming arbitrary tag names are allowed: opening tag names must have matching close tags:

<hi>
 <bye>
 the closing tag has to match bye
 </bye>
</hi> <!-- has to match "hi" -->
share|improve this answer
    
Interesting. I knew about XML. I suspect the drive behind the XHTML 1.0 spec was to lead away from 'quirks mode' HTML interpreters which support context-sensitive exceptions to a cleaner context-free XML. –  Evan Plaice Feb 19 at 3:47
    
@EvanPlaice I'm confused by your comment -- "clean XML" is context-sensitive as I've shown in my example. –  user39685 Feb 20 at 16:47
3  
@MattFenwick I think your XML example doesn't show the true reason why XML is not context-free. The reason is that arbitrary tag names are allowed. If only a specific set of tags was allowed XML would be context free. –  Honza Brabec May 29 at 14:29
    
@HonzaBrabec you're right -- I implicitly assumed that arbitrary tag names are allowed. I should have explicitly stated that assumption. Thank you for pointing that out! –  user39685 May 29 at 16:29

As long as I know, context-sensitive grammars are used in natural language processing, only. Programming languages interpreters and compilers do not try to parse a context-free grammar because of complexity (even if some attempt has been done in the past).

Maybe, you can find some example of real use in one of these libraries:

http://en.wikipedia.org/wiki/List_of_natural_language_processing_toolkits

http://opennlp.sourceforge.net/projects.html

http://nltk.org/

http://nlp.stanford.edu/nlp/javadoc/javanlp/

share|improve this answer
2  
What about HTML 'quirks mode' and code preprocessors, wouldn't they count? –  Evan Plaice Feb 10 '13 at 1:47

Context sensitive grammars are sometimes used in descriptions of programming language semantics. Perhaps the most comprehensive use of context sensitive grammars was the Algol68 language definition. It used a two-level context free grammer (see http://en.wikipedia.org/wiki/Two-level_grammar) to describe both the syntax and semantics of Algol68 programs.

A couple of my colleagues used the van Wijngaarden grammar to direct their implementation of Algol68 (see http://en.wikipedia.org/wiki/FLACC).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.