8

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?

6
  • 10
    Does programming language count? Dec 13, 2012 at 4:01
  • @LokiAstari Of course. Dec 13, 2012 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, 2012 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. Dec 13, 2012 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
    – user40980
    Dec 13, 2012 at 14:38

3 Answers 3

11

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" -->
4
  • 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. Feb 19, 2014 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, 2014 at 16:47
  • 4
    @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. May 29, 2014 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, 2014 at 16:29
3

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).

1

As far as I know, context-sensitive grammars are used in natural language processing, only. Programming language interpreters and compilers do not try to parse a context-sensitive grammar because of the 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/

2
  • 3
    What about HTML 'quirks mode' and code preprocessors, wouldn't they count? Feb 10, 2013 at 1:47
  • I think that's not quite true. Many programming languages have some form of context-sensitivety and are therefor not completely context-free. Pre-processors, macro-expansion,... If you search for popular programming languages if they are context-free, for many, the answer is no. Of course, this doesn't come close to the level of context that a natural language has. Dec 30, 2023 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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