|chomsky and compiler development GenericInfoService@yahoo.com (GenericInfoService) (2001-11-14)|
|Re: chomsky and compiler development email@example.com (Michael J. Fromberger) (2001-11-17)|
|Re: chomsky and compiler development firstname.lastname@example.org (2001-11-17)|
|Re: chomsky and compiler development email@example.com (Marco van de Voort) (2001-11-25)|
|Re: chomsky and compiler development firstname.lastname@example.org (GenericInfoService) (2001-11-25)|
|Re: chomsky and compiler development email@example.com (Joachim Durchholz) (2001-11-29)|
|Re: chomsky and compiler development firstname.lastname@example.org (Lex Spoon) (2001-11-29)|
|Re: chomsky and compiler development TanjBennett@hotmail.com (Tanj) (2001-12-11)|
|Re: chomsky and compiler development email@example.com (2001-12-15)|
|Re: chomsky and compiler development JeffKenton@mediaone.net (Jeff Kenton) (2002-01-03)|
|From:||"Joachim Durchholz" <firstname.lastname@example.org>|
|Date:||29 Nov 2001 22:59:51 -0500|
|References:||01-11-081 01-11-096 01-11-104|
|Posted-Date:||29 Nov 2001 22:59:51 EST|
> Thanks for the reference to Hopcroft and Ullman. If I discover
> additional worthwhile information from some computer experts I know, I
> will post it here. One gentleman - an academic who unfortunately I
> cannot recall - a few years back opined that without Chomsky we would
> not have modern computer compilers without their context-free
> grammars. That seemed a little extreme, and I'm glad to get other
> opinions here.
That's wrong, on two accounts.
First, it's highly debatable whether the Chomsky hierarchy is more
than a nice numbering scheme; if Chomsky's work hadn't been
recognized, we'd be talking about finite-state languages, stack
languages, ??? languages (not sure how the abstract machine for
context-sensitive language is called), and Turing-machine languages,
without ever referring to the Chomsky hierarchy.
Second, only the weak half of the Chomsky hierarchy (regular and
context-free languages) is used in practice; the stronger half
(context-sensitive and what'sitsname) isn't used, at least not for
automata. If Chomsky's hierarchy had been so essential for the
development of automata, we'd have and use parsers for all Chomsky
Just my 2c.
Return to the
Search the comp.compilers archives again.