[Prev][Next][Index][Thread]

Templates can work with precedences



(was: Re: Progress on Parsing)

> The parser works pretty well and is included below. It doesn't work
> for strings like:
> 
>      y = 1 + integral of sin(x) wrt x * cos(x)
> 
> This example screws up because the + and * operators bind tighter
> than "of" and "wrt" respectively.
...
> > 'integral' also seems to be missing
> 
> This is currently handled as a literal rather than as an operator.
> The next step will be to combine top-down parsing based on templates
> with bottom-up parsing using operator precedence analysis to avoid
> inappropriate bindings: "+ integral of" current reduces the "+" first
> which is wrong. The template would force this to be reduced to the
> right overriding the normal precedence values.
> 
> When I thought about treating integral as a prefix operator, I got
> stuck with how to handle from and to. If these were prefix operators
> you then end up with:
> 
>       {{{integral {from 0} . {to n}} of {sin.x}} wrt x}
> 
> This works I guess, but feels wrong to me. I think the use of
> templates to influence parsing makes more sense, as it breaks
> out of the limitations of using operator precedence alone.


The effect you want could probably be achieved purely by precedences:

Make "integral" a prefix operator with quite low right precedence,
lower than anything except brackets.

Make "wrt" an infix operator, with the same low left precedence as
"integral"'s right precedence, but with very high right precedence.
Then "wrt" will only bind the x on the right, and "wrt" on the left
will reach as far as "integral" does on the right -- these two will
effectively act as brackets, binding up everything between them.

(As I described in my letter about parsing -- the one which is
still missing from the mail archive -- it isn't necessary to have
a separate step for reducing brackets -- this can be done by
precedences too. If you don't find that letter soon I will try to
dig it up and resend it.

The key step was that colliding equal precedences result in "flat"
associativity; thus in the present example, "integral ... wrt x",
you would get neither {{integral {...}} wrt x} nor {integral {{...}
wrt} x} but just {integral {...} wrt x}.)

Finally, make "of" an infix operator, with low precedence (both
sides), but not as low as "integral"'s right precedence.

Then I would predict that

	y = 1 + integral of sin(x) wrt x * cos(x)

would bind in the same way as

	y = 1 + {integral {<missing> of sin(x)} wrt x} * cos(x)

where <missing> is the missing term (which you didn't yet implement,
I realize).

(I'm not necessarily advocating supplying this macro as a standard,
just suggesting that it is possible to make it work using precedences
alone, without introducing a separate prior template-parsing step which
violates them (which I'm opposed to).)