The following header lines retained to affect attribution:
|Date: Mon, 03 Mar 1997 21:59:39 +0100
|From: [log in to unmask] (Hans Aberg)
|Subject: Re: Shortref mechanism
|To: LaTeX3 project <[log in to unmask]>
|Cc: "Randolph J. Herber" <[log in to unmask]>
|"Randolph J. Herber" <[log in to unmask]> wrote:
|>|> Please. would you use the proper nomenclature?
|>|> The pairing from your improper nomenclature to what I believe
|>|> is the pertinent nomenclature for what you are attempting to
|>|> discuss is:
|>|> deterministic ==> context free
|>|> non-deterministic ==> context sensitive
| I get a lot of (very long) letters of this kind, demanding that I should
|use this or other terminology.
| I have an old book, "Compilers", by Robin Hunter, that on page 40 defines
|the notions "nondetermistic/deterministic parser" as whether of one can go
|back on the decision in the parsing process, or not. This is what I mean.
Your reference, Robin Hunter, probably used the phrase
``deterministic grammar'' in the sense of being unambiguous.
This is separate from whether the grammar is context sensitive.
It is possible for a context sensitive grammar to be ambiguous.
The class of change that you are proposing involves a change
from a context free to a context sensitive grammar for TeX.
My basis is the following:
Arto Salomaa, Theory of Automata, Pergamon, Oxford, 1969.
David Gries, Compiler Construcion for Digital Computers,
John Wiley, 1971, ISBN 0-471-32776-X.
Alfred V. Aho and Jeffery D. Ullman, Principles of Compiler Design,
Addison Wesley, 1977, ISBN 0-201-00022-9.
Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman, Compilers:
Principles, Techniques and Tools, Addison Wesley, 1986,
Allen I. Holub, Compiler Design in C, Prentice-Hall, 1990,
*Axel T. Schreiner and H. George Friedman, Jr., Introduction
to Compiler Construction with UNIX, Prentice Hall, 1985,
William M. McKeeman, James J. Horning, David B. Wortman,
A Compiler Generator, Prentice Hall, 1970, ISBN 0-13-155077-2.
**P.M. Lewis II, D.J. Rosenkrantz and R.E.Stearns, Compiler Design
Theory, Addison Wesley, 1978, ISBN 0-201-14455-7.
Charles N. Fischer and Richard J. LeBlanc, Jr., Crafting a Compiler,
Benjamin/Cummings, 1988, ISBN 0-8053-3201-4.
*William M. Waite and Gerhard Goos, Compiler Construction,
Springer-Verlag, 1984-1985, ISBN 0-387-90821-8.
* This book happens to use the adjective ``deterministic'' in the
sense of ``unambiguous''.
** This book happens to use the adjective ``deterministic'' applied
to parsing in the sense that a stack (pushdown) machine is used to
implement the parser or to recognize the language.
Several of these books have an extensive bibliography. None of
these bibliography mention your reference. Many of them refer
to the books which preceeded them.
| On page 231, a "context sensitive parser" is described as a method to
|handle a attribute grammars, and the like. This is not what I have in mind.
This refers to a parser. I had been refering to context free
languages and grammars. ``Attribute grammars'' are concerned
with semantics. At the level of semantics all compiler and
interpreters which process meaning, which attribute grammers
must, must be context sensitive.
| Otherwise, I do not understand how this or other terminology can solve
|the problems discussed here.
It _may_ help solve problems in communication.
| Hans Aberg
Randolph J. Herber, [log in to unmask], +1 630 840 2966,
CD/OSS/CDF CDF-PK-149O Mail Stop 234
Fermilab, Kirk & Pine Rds., P.O. Box 500, Batavia, IL 60190-0500.
(Speaking for myself and not for US, US DOE, FNAL nor URA.)
(Product, trade, or service marks herein belong to their respective owners.)
N 41 50 26.3 W 88 14 54.4 and altitude 700' approximately, WGS84 datum.