```"Randolph J. Herber" <[log in to unmask]> writes:

>|  I cannot follow the details in your reasoning, but I can note that with
>|deterministic parsing, the method generally used in LaTeX, conditional
> ^^^^^^^^^^^^^ ^^^^^^^                                      ^^^^^^^^^^^
>|parsing have such limits.
> ^^^^^^^
>|  But with non-deterministic parsing more general things can be done:
>            ^^^^^^^^^^^^^^^^^
>|  For example, I just made a definition command that can produce commands
>|having optional arguments; in this general approach, I had to switch from
>|LaTeX style deterministic parsing to non-deterministic parsing.

>To someone that has written several small compilers and has studied automata
>theory at the doctorate level, your word choice as high-lighted above is
>quite jarring.  By using a power automaton, a non-deterministic automaton
>can be reduced to a deterministic automaton.  Therefore, one does not gain
>any power of expression by using a non-deterministic automaton, rather one
>only gains compaction of the description.

This reasoning would be true in a ny sufficiently general purpose, but
TeX is not such a language (or it is unknown if it is).
The second thing is that, even though something may be theoretically
possible, it may be practically impossible, because you simply do not have
time to both  doing that implemntation, and pay your bills.
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.

With TeX the problem is this:

You have a variable #1 equal to some parameter text, say ##1##2.
When #1 pick up an argument, in the first pass, an argument of the form
{section}{theorem}
will be transformed into
sectiontheorem,
so, when writing an deterministic parser by hand, on puts back the argument
to the next command as {##1}{##2}, say if you want to put it back all. Now,
working in this generality, there is no obvious way of transforming
#1 --> #1_new
by a command doing
##1##2 --> {##1}{##2}
implicitly.

By reverting to non-deterministic parsing, one can get around this
problem, by first picking up some text that surely contains the original
##1##2, and then sending this original text to the next command, instead of
the partially parsed by #1 (which may be corrupted).

But this does not solve Frank Mittelbach's problem, as he pointed out.

>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.

TeX is highly context sensitive, and this is much of the point with TeX:
Each environment or grouping has its own set of local variables, which can
be used to change the context rather radically. This is unrelated to the
stuff I discussed above.

Hans Aberg
```