On 25 Oct 2001, at 12:56, Robin Houston wrote: > Next up comes the "context-free languages". The syntax of some > programming languages is context-free. (Our own beloved Perl is a > notable exception.)
Actually very few 'real world' programming languages are truly CF. Just as with Perl, they can usually manage 98% CF, but there'll be a corner here or there that breaks things. > You'll notice that all the rewriting rules just have *one* symbol > on the left. If we relax this restriction, we can get > context-sensitive grammars (CSGs). The idea is that we can constrain > rules so that they can only be applied in certain "contexts", when > they have certain other symbols to their left or their right. [...] > Full CSGs are a *very* powerful tool. So powerful, in fact, that > they're not very useful in computing. It can take an extraordinary > amount of time to parse a string using a CSG. Actually, one of the interesting things about CSGs is that they seem to be the "maximum" for computable languages. That is, if you try to come up with almost ANY sort of concrete way to deal with a language (grammars, funny machines, "Post productions", etc), you find that context sensitive languages form a sort of 'cap' on what you can do. In particular, CSLs are the same as the set of languages computable by Turing machines, so that anything a Turing machine can do can be expressed as a context-senstive language (and vice versa, of course), which pretty much means that almost anything that one would consider 'effectively' computable by any reasonable definition of the term will be context sensitive [or less]. /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:[EMAIL PROTECTED] Pearisburg, VA --> Too many people, too few sheep <--
