LATEX-L Archives

Mailing list for the LaTeX3 project

LATEX-L@LISTSERV.UNI-HEIDELBERG.DE

Options: Use Forum View

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

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

Print Reply
Subject:
From:
Hans Aberg <[log in to unmask]>
Reply To:
Mailing list for the LaTeX3 project <[log in to unmask]>
Date:
Mon, 3 Mar 1997 19:23:47 +0100
Content-Type:
text/plain
Parts/Attachments:
text/plain (110 lines)
"Randolph J. Herber" <[log in to unmask]> wrote:

>        Your following comments are not pertinent to my comments above.
>
>        You may feel that you are making up nomenclature to describe your
>        proposed algorithms.  But, in fact, you are using nomenclature
>        with already assigned meaning in the field of computer language
>        processing.
>
>        Furthermore, you ``added insult to injury'' by deleting my
>        provision of the proper nomenclature from the field of computer
>        language processing that does pertain to your proposed changes
>        to TeX's handling of its input, to wit:
>
>
>                I believe that what you intended is the distinction of
>                context free and context sensitive languages.  From
>                what I have read in the TeX book, the tokenizer of TeX
>                is context sensitive with a single character look-ahead
>                and the TeX language based on the recognized tokens is
>                context free.
>
>                It is a significant change in the behavior of the TeX
>                language to change it from being context free to being
>                context sensitive.  But, it may be a necessary change.
>                Most modern computer languages are context sensitive
>                with a single token look ahead.  A few look ahead two
>                tokens in some situations.  I imagine that some look
>                ahead three tokens.  Parser generators for single token
>                look ahead readily are availed.
>
>                What you are proposing is a change from zero token look
>                ahead to one token look ahead.
>
>        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

  This looks like a "flame". :-)

  When I spoke about deterministic parsing versus non-deterministic
parsing, that is what I meant.
  The problem is simply that when you make a simple 1-lookhead parsing (=
deterministic parsing), TeX strips out the brackets "{}", so you cannot
pass the stuff to the next routine, when doing parsing in that generality
(even though it is possible in special cases).
  Therefore, a way, in TeX, to get around it, is to pick down a rather
large argument, surely containing what you intend parse. Then you parse
that stuff until something is going wrong. If something is going wrong,
then you return to the original, unparsed argument, killing off whatever
you have parsed so far. This is called non-deterministic parsing.

  The best way of understanding these problems, is to sit down and write a
parser in TeX. It is extremely difficult.

>        My observations above pertain to all languages which have syntax.
>        TeX is a language which has syntax.  Therefore, it is such a language.

  TeX is not really a computer language, but a computer program, as matters
stand right now, with severe memory limits. If you would want to
demonstrate that TeX is a Turing machine, you would need to demonstrate
that it can handle an infinite binary strip of paper. But if you do, then
what? It has absolute no practical importance for any TeX macro package
implementation.

  I can note that even though it is possible to translate non-deterministic
automatas into deterministic automatas, space of the latter may depend
exponentially on the space of the former, making it not possible in
practise.

  And how should that be implemented in TeX?

  The problem with writing parsers in TeX is that the information you need
for the parsing cannot easily be extracted without being corrupted.


>        Deciding whether TeX should have a context free or a context
>        sensitive grammar is an appropriate topic for this forum.

  This group does not discuss changes to TeX itself; try
    NTS-L Distribution list <[log in to unmask]>
which is project for developing a new TeX.

>|  The third thing one must consider, is that a computer language is not
>|only used to manipulate logical data, but logical data that has a semantic
>|interpreation attached to it. Any logical transformation must keep track of
>|that semantic interpretation, and this is related to the practicality
>|question, I guess.
>
>        At the syntax level of language processing, the semantics do
>        not pertain.  At the semantics level of language processing,
>        semantics is the entire purpose of the processing.  Any
>        compiler or interpreter that does any semantics processing
>        must handle the semantics processing that is dictated by the
>        specifications indicated by the semantics associated with
>        the syntactical elements.

  When I mentioned this, I was not thinking of "computer language
semantics", but the semantics of the objects of the real world, which we
use computers to describe.
  Therefore, logically (Turing) equivalent computer languages react rather
differently when interacting with the rest of the world. :-)

  Hans Aberg

ATOM RSS1 RSS2