Re: chomsky and compiler development

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


Just my 2c.
Regards,
Joachim

Return to the comp.compilers page.
Search the comp.compilers archives again.