Re: Universal grammar

In article <Pine.LNX.4.63.0610191210550.655@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Helmut Richter <hhr-m@xxxxxx> wrote:

The "Chomsky hierarchy" shows up as a classification of formal
mathematical grammars.

One should not overestimate the significance of that hierarchy, not even
for formal languages (of which I understand more than of natural
languages).

This is the very point I wanted to bring out - I just made a post,
attempting to illustrate this.

Chomsky type 0 grammars are undecidable which limits their
usefulness, type 1 grammars (CS) are so large a subset of decidable
languages that more or less any decidable language of practical use may be
CS but with no sensible way to construct a CS grammar or to understand
what language a CS grammar will produce. Only type 2 languages (CF) have
two nice properties:

- If the language they describe happen to have a parenthesis structure
   as is typical for CF languages, then a CF grammar reflecting this
   structure is easy to read. This is why they are used to define
   programming languages, and may be used to describe some aspects of
   natural languages.

The are of course long discussions, for example in newsgroups like
comp.compilers, comp.lang.misc, etc, over why CFGs are so popular. The
suffice for the practical implementation of languages, and there
are efficient algorithms, generating efficient parsers are probably some
of the reasons.

- For a small subset of them, nice parsing algorithms have been found. 
   This subset comprises the programming languages, if only because these
   were defined in a way that this works (FORTRAN, the oldest of these, is
   not deterministic, though).

Right now, one is GLR is coming on. It takes a deterministic parsing
algorithm, and splits the parser where the algorithm fails
to resolve ambiguities. The writer of a grammar will then have to add some
extra runtime information to handle splits and merges. For example, Bison
nowadays has a GLR built on top of its LALR(1) parser generator.

Taking the Chomsky hierarchy as a measure for complexity is, however,
questionable (see my posting <70n9i7$j6h$1@xxxxxxxxxxxxxxxxxxxxxxxxxxx>).

Right, especially in view of that grammars are in practice
typically combined with semantic actions attached to the grammar rules.

The more general formal grammars are though
in practice not used so much in favor of so called context free grammars
(CFG) combined with context dependencies implemented using semantic
actions attached to the grammar rules.

In other words, these languages are *not* context free so that some
syntactic rules are disguised as "semantic". As an engineering approach,
this is in order (use CF for what they are good for, to wit the two items
above, and use something else for the rest) but it stresses that CF
grammars do not reflect the *entire* syntactic structure underlying the
language - be it an artificial or a natural one.

Right. The is a subtle interplay between syntax (i.e. the grammar) and
semantics (the actions attached to the grammar rules), just as in all
language uses. This seems to be the way to go, making it difficult to just
think in terms of grammars and adding grammar rules only.

--
Hans Aberg
.

Relevant Pages

  • Re: Chomsky - what did he actually say?
    ... on languages, to help those linguists in their systematic study ... try to fix up your grammar to make it closer to fitting, ... innate languages are that there are innate regularities in all (or ... notion that they claim that the brain "associates" anything (it is the ...
    (comp.ai.philosophy)
  • Re: Chomsky - what did he actually say?
    ... on languages, to help those linguists in their systematic study of ... try to fix up your grammar to make it closer to fitting, ... innate languages are that there are innate regularities in all (or ... notion that they claim that the brain "associates" anything (it is the ...
    (comp.ai.philosophy)
  • Re: Chomsky - what did he actually say?
    ... on languages, to help those linguists in their systematic study of ... try to fix up your grammar to make it closer to fitting, ... innate languages are that there are innate regularities in all (or ... notion that they claim that the brain "associates" anything (it is the ...
    (comp.ai.philosophy)
  • Re: Chomsky - what did he actually say?
    ... on languages, to help those linguists in their systematic study of ... try to fix up your grammar to make it closer to fitting, ... either HMSBeagle has read Chomsky ... Or did he mean the particular grammar rules in isolation, ...
    (comp.ai.philosophy)
  • Re: Jiu Jitsu Strategies: Sports vs Reality
    ... Natural languages are full of idiosyncrasies. ... I'm not going to argue with you over whether or not someone's accent ... I haven't reinterpreted the rules of grammar. ... - you used an adjective and you should have used an Adverb. ...
    (rec.martial-arts)
Loading