Re: chomsky and compiler development (Edward G. Nilges)
17 Nov 2001 00:42:14 -0500

          From comp.compilers

Related articles
chomsky and compiler development (GenericInfoService) (2001-11-14)
Re: chomsky and compiler development (Michael J. Fromberger) (2001-11-17)
Re: chomsky and compiler development (2001-11-17)
Re: chomsky and compiler development (Marco van de Voort) (2001-11-25)
Re: chomsky and compiler development (GenericInfoService) (2001-11-25)
Re: chomsky and compiler development (Joachim Durchholz) (2001-11-29)
Re: chomsky and compiler development (Lex Spoon) (2001-11-29)
Re: chomsky and compiler development (Tanj) (2001-12-11)
Re: chomsky and compiler development (2001-12-15)
[1 later articles]
| List of all articles for this month |

From: (Edward G. Nilges)
Newsgroups: comp.compilers
Date: 17 Nov 2001 00:42:14 -0500
References: 01-11-081
Keywords: parse, history
Posted-Date: 17 Nov 2001 00:42:14 EST

"GenericInfoService" <> wrote
> Is anyone familiar with how Chomsky's Universal Grammar impacted the
> development of modern computer compilers? We're trying to find a good
> summary - like an essay - for the Software Literate which illustrates
> the key applications of his Linguistic Theory in writing Compilers.

was by Hopcroft and Ullman and was published by Addison Wesley.

Hopcroft and Ullman used the Chomsky type hierarchy by name to
classify formal grammars and to prove correspondence of each type in
sequence (regular, context free, and context sensitive) to classes of
formal automata from the finite state machine, to machines with an
auxiliary stack or stacks, up to Turing complete machines.

I programmed simulators for finite state machines and found that I
could develop parsers for regular grammars for parameter assignment in
Cobol, by representing the finite-state automaton in the form of a
table. I also noticed, in the later 1970s, that various unix tools
seemed to be implicitly based on Hopcroft and Ullman and thus
indirectly on Chomsky.

Hopcroft and Ullman were based at Princeton and Bell Labs, so I have
reason to believe that their ideas cross-fertilized yacc and lex

However, in 1994, I asked Professor Chomsky about this issue in an
online conference conducted by Z magazine, and he denied any
association between his work and that of computer language
researchers. I feel his denial was honest, for like Bertrand Russell
after Principia Mathematica, he has ever since the 1950s found more
constructive outlets for his talents. While he continues to work on
the linguistics of natural language, Chomsky appears disinterested in
computer applications.

> Any information or referrals to good sources would be much appreciated.
> Please reply here or via email.
> [Although linguists were working at the same time as some of the early
> compiler work, and there's a lot of overlap in the concepts, e.g., a
> linguist's phrase structure grammar is the same as a compiler's
> context free grammar, there's been remarkably little
> cross-fertilization. I took a course in transformational grammars in
> about 1974 and at the time it struck me as trying to create nuclear
> energy by rubbing two sticks together, with a lot of debate about the
> shape of the sticks and details of wrist motion. I don't think the
> universal grammar, the idea that people all have a grammar for
> language hard-wired in our brains, affected computing at all. -John]

I dunno. If I knew enough about Chomsky's work, I'd probably dream up
some application. Certainly, having read far more French theory than
Chomsky, I find loads of applications of deconstruction and
structuralist philosophy of language to computers in general.
However, Chomsky told me in the same online conference that he felt
that while some French work has value, Lacan seemed to him to be a

I think that what Chomsky means by universal grammar may be something
like the "Ideas" of Edmund Husserl, a German philosopher and
contemporary of Heidegger. These are concepts that must exist but
can't be described in any detail, much less incorporated into

Husserl thought that our very ability to talk to each other implies
that Ideas, like universal grammar, are hard-wired. That does not
mean that we have the capability of hard-wiring anything like them in
our computers, and the fact that Husserl definitely was a Kantian, and
Chomsky may be even if he won't admit it in polite society, implies
that we could never sufficiently wrap our minds over their own
structure...enough to code UG, or Ideas, in a satisfactory fashion.

Oh well.

Post a followup to this message

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