Re: chomsky and compiler development

There were plenty of other grammatical/syntactic formalisms early in
the last century, which arguably more directly lead to computer
languages.


Turing used an algebraic scheme. Markov in the 30's came up with a
pattern directed scheme which is formally equivalent to Turing
machines and in some sense the ancestor of pattern/string languages
such as macros, Snobol, even van Wijngarden grammars. Then there is
predicate calculus with its roots in the 19th century that leads via
Church to LISP, arguably the first computer language with explicit
roots in theory. It is not clear that FORTRAN or COBOL were designed
with formalism behind them - more like they simply stumbled forward by
trial and error, with the theory added to compilers later. But when
the theory came, though Chomsky was fashionable, the logical apparatus
for analysis was available from other sources too. Most of the actual
algorithms used went well beyond what anyone working on human
languages was doing, since human languages are too sloppy to give any
incentive for strict, optimized lexical or syntactic compilers.


Van Wijngarten's Algol-68 work was often talked about in terms of
Chomskian levels of grammar. I don't know if van-W himself was aware
of that at the time, or this was adduced by others reviewing his work.
There was also the related Vienna notation used for the syntax and
semantic description of PL/I, possibly similar things happened for
Ada.


Chomsky's deep structures, if they even exist, had no effect. They've
been of some interest in studying language acquisition by other
species and of course as a hypothesis in investigating human language.
They may have some currency in work on automatic translation of human
language, some of which tries to resolve multiple languages into a
common underlying set of primitives. I have not seen anything really
lucid on this though, it seems to get mixed in with common-sense or
domain-specific knowledge bases which are also needed to disambiguate
the texts.


"Joachim Durchholz" <joachim_d@gmx.de> wrote in message
> > 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.

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