LATEX-L Archives

Mailing list for the LaTeX3 project


Options: Use Classic View

Use Monospaced Font
Show Text Part by Default
Show All Mail Headers

Topic: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
"Randolph J. Herber" <[log in to unmask]>
Tue, 4 Mar 1997 00:18:44 -0600
text/plain (102 lines)
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.

        Ipse dixit.

|  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,
        ISBN 0-201-10088-6.

        Allen I. Holub, Compiler Design in C, Prentice-Hall, 1990,
        ISBN 0-13-155045-4.

        *Axel T. Schreiner and H. George Friedman, Jr., Introduction
        to Compiler Construction with UNIX, Prentice Hall, 1985,
        ISBN 0-13-474396-2.

        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.