LINGUIST List 4.1075

Mon 20 Dec 1993

Sum: Regular expressions in context-free rules, OK use

Editor for this issue: <>

Directory

1. , Summary: Regular Expressions in Context-free Rules
2. Ali Aghbar, Sum: OK Use

In response to my query (on LINGUIST and on THEORYNT) about who
first allowed regular expressions to appear in context-free
rules, I received a lot of mail, none of which supplied
the answer directly. In fact, there appears to be no
such thing as THE answer.

Thus, while trying to follow up a number of leads which
I received and which for the most part involved references
to papers that appeared in the sixties in the Comm. of the
Assoc. for Computing Machinery, I found that none of the
specific references were relevant, but stumbled across the
following:

In 1962 I. N. Rabinowitz "Report on the Algorithmic Language
FORTRAN II", CACM 5(6):327-337 invented a notation that allows
you specify that a given element can be recurr between n and m
times. In 1964, K. E. Iverson "A Method of Syntax Specification",
CACM 7(10): 588-589 proposed using the asterisk in context-free
rules on the right hand side to refer back to the left hand side,
e.g., A -> * B would mean A -> A B but in effect it can also
be read as A -> any number of B's. In 1965, Lee Schmidt "On
Syntax Specification", CACM 8(5): 262, explicitly refers to
a notation for saying "zero or more of" X which takes the form
of something that looks like the function sign before X, and
refers to Rabinowitz as an apparent inspiration. In 1966,
we have two relevant pieces: B. M. Leavenworth, "Syntax Macros
and Extended Translation", CACM 9(11): 790-793 refers to the
use of three dots (...) following a sign as meaning '1 or more
times' in IBM's documentation of the PL/1 language in the same
year; and finally finally John W. Carr III and Jerome Weiland,
"A Nonrecursive Method of Syntax Specification", CACM 9(4): 267-269,
introduce the current notation of A* for 'zero or more occurrences
of A' into CFGs and refer generally to the "use of the Kleene
regular expression notation" (of which this is of course just
one instance). Carr and Weiland explicitly recognize Iverson
as the person who inspired them to see the need for this kind
of notation and, of course, acknowledge Kleene for inventing
regular expressions in the first place.

In addition, however, in the book Jean Sammet, Programming
Languages, which several people told me to read, I find
a reference to the use of the three-dot notation (same as
noted above for PL/1 in 1966) in the 1965 Cobol documentation.

It thus seems that these ideas were all over the place,
at least in the programming language community, but at the
same time several linguists have suggested that they recall
some discussion of this topic at MIT at roughly the same
time. Unfortunately, I have not been able to come up with
any specifics on this, not to mention published references.

If any of this jogs anybody's recollections, please let me
know, as I would like to form as complete a picture as
possible of this little piece of history.

Alexis Manaster Ramer

Thanks to many fellow-netters who responded to my Dec. 7 query on
on research on the USE of OK, which I posted on behalf of a
graduate student of mine. I will clip and insert below some of
the relevant responses I have received.

If you know of other research on the use of OK which I have not
included here, please let me know.

Ali A. Aghbar
BITNET address: AAGHBARIUP.BITNET
Network address: AAGHBARGROVE.IUP.EDU

===================================================

[I RECEIVED QUITE A FEW RESPONSES ON THE ORIGIN OF OK. THE WORK
OF ALLAN WALKER READ WAS MENTIONED BY QUITE A FEW PEOPLE, SO I
WILL CLIP ONLY ONE OF THE RESPONSES. Ali Aghbar]

Allen Walker Read did a very thorough study of this. There are
several papers in American Speech, Vol. 39, 1964, and citations
to earlier papers in the bibliography. He examined newspapers
from the mid 1830's (I think) and found that it came from "Old
Kinderhook" (the party slogan for Martin van Buren), and there
was also evidence that it came from "Ol Korect" (All Correct).

Bob krovetzcs.umass.edu
===================================================

I once did a study of OK (plus right and alright) in the Londohn-
Lund Corpus of spoken English. It's called 'Carry-on signals in
English conversation' and occurs in Mejs, W. (ed) 1987. Corpus
Linguistics and Beyond. Amsterdam: Rodopi.

Anna-Brita Stenstr|m
NetMail%"Stenstroemeng.uib.no"
===================================================

Try e-mailing Maria Pak (pakcogsci.berkeley.edu) and/or Elena
Escalera (escaleracogsci.berkeley.edu). I think one of them (I
don't remember which) did some work on `OK'.

Joyce Tang Boyland (jtangcogsci.berkeley.edu)

[NOTE: I ALREADY SENT AN E-MAIL TO MARIA PAK BUT MY MESSAGE COULD
NOT BE DELIVERED. Ali Aghbar]
===================================================

I believe beth ann hockey presented a paper at LSA a couple of
years ago on the use of "okay" as a discourse marker. I'm sorry
I can't be more specific, but I believe it was between about 1988
and 1992. She's out of the country at the moment, but if there's
no great rush you can e-mail her at bethlinc.cis.upenn.edu and
i'm sure she'll respond when she returns.

betty birner: bettybabel.ling.upenn.edu

Also mentioned by niv%csa.cs.technion.ac.ilcs.Technion.AC.IL
===================================================

I was delighted to learn that your graduate student is studying
OK. I hope s/he will look at my paper:

Condon, Sherri L. The Discourse Functions of OK. Semiotica 60,
1986, 73-101.

In the paper I cite Merritt's 1978 paper, which is still the only
relatively recent one I am aware of...

Sherri Condon
University of Southwestern Louisiana (Universite des Acadiens)