Ken Walker kindly responds to my query about parsing strategies (or at
least one of the many queries):
For example, the production
s ::= t | s "+" t
(For those who want to get in this game, quick read Griswold & Griswold,
chapter 15.)
can be parsed with a procedure something like
procedure s()
x := []
push(x, t()) | fail
while ="+" do
push(x, t()) | stop("syntax error")
return x
end
(I haven't tested this code; in any event it needs to be a little more
sophisticated.) This pattern of left recursion comes up a lot in
programming languages. Is it common in natural languages?
Yes, it's fairly common. One case in point is the 's construction.
You can define a noun phrase as a combination of articles, simple
nouns, adjectives, relative clauses, etc. This works fairly well
using a simple phrase structure grammar. However, as soon as you try
to include 's, you have to define a noun phrase as a noun phrase fol-
lowed by an 's. E.g. -
the queen of England
the queen of England's throne
The phrase "the queen of England" is a noun phrase, and so is "the queen
of England's throne." You can see immediately how there's left recursion
here. Any time you get a postpositions (which is what 's really is -
it's not a "case" or an affix of any kind) you'll have this problem of
left recursion. Sumerian, which is one language I've studied, is all
postpositions - no prepositions at all. In fact, you can often do a
mirror-image lexical calque of a phrase and have it come out as acceptable
English.
The problem with natural language parsing strategies that don't permit
elegant left-recursion is that they don't mirror the apparent ability
for people to handle both sorts of recursion in any given languages.
Normally a language will use one or the other predominantly, but often
there is mixing (as in English).
One way out is to permit X levels of left recursion, with X representing
the number of levels beyond which people get confused, and don't really
talk that way. The problem with this is that people might perhaps really
be using an internal grammar that permits infinite recursion, but that
they just can't fully realize the grammar. This seems a bit silly to
me.
I have to admit that my main interest is in the sounds - the phonemes,
or systmatic pronunciation units - of ancient Semitic languages.
Someone who is more into the suntax of natural languages, please jump
in here --->
From @s.ms.uky.edu:mtbb95@ms.uky.edu Fri Apr 27 14:29:16 1990
Received: from e.ms.uky.edu by megaron.cs.arizona.edu (5.59-1.7/15) via SMTP
id AA21281; Fri, 27 Apr 90 14:29:16 MST
Received: from s.ms.uky.edu by g.ms.uky.edu id aa24729; 27 Apr 90 16:48 EDT
From: Bob Maras <mtbb95@ms.uky.edu>
Date: Fri, 27 Apr 90 16:47:52 EDT
X-Mailer: Mail User's Shell (6.4 2/14/89)
To: icon-group@cs.arizona.edu, mtbb95@ms.uky.edu
Subject: Removal
Message-Id: <9004271647.aa22801@s.s.ms.uky.edu>
Status: O
Please remove my name from your Icon mailing list of users. I appreciate the fine effort you are making and wish each of you the very best. I have enjoyed
your information very much.
Robert Maras
--
_ _
( ) __ ( )
| O O | B O B M A R A S
/ __ \ /
( \/ ) __/
\ \__/ /
\____/
|_/\_| H A P P Y C O M P U T I N G !!!
From icon-group-request@arizona.edu Fri Apr 27 17:54:28 1990
Resent-From: icon-group-request@arizona.edu
Received: from Maggie.Telcom.Arizona.EDU by megaron.cs.arizona.edu (5.59-1.7/15) via SMTP
id AA06635; Fri, 27 Apr 90 17:54:28 MST
Received: from ucbvax.Berkeley.EDU by Arizona.EDU; Fri, 27 Apr 90 17:54 MST
Received: by ucbvax.Berkeley.EDU (5.63/1.41) id AA27061; Fri, 27 Apr 90
17:39:16 -0700
Received: from USENET by ucbvax.Berkeley.EDU with netnews for