Re: Prior art for operator parsing trick

Kaz Kylheku <643-408-1753@kylheku.com> wrote:
w> I recently came up with neat trick in order to obtain particular
> (to me) desirable results out of an infix parser (which more
> or less follows Shunting Yard).
>
> The basic motivation is that I have certain monadic functions
> like sin, cos, log, sqrt , ... installed as very low precedence
> prefix operators. Thus:
>
> sqrt x * x + y * y
>
> means
>
> sqrt (x * x + y * y)
>
> Unfortunately, what it means is also that, say:
>
> sqrt x + x + sqrt y + y
>
> parses as:
>
> sqrt (x + x + sqrt (y + y))
>
> The symmetric-looking expression ends up with an assymetric parse.
> (Some may disagree, but my requirement is what it is.)
>
> I came up with a general modification to the algorithm so that we can
> obtain the parse
>
> sqrt (x + x) + sqrt (y + y)
>
> Here is the modification to the algorithm.
>
> When the loop is just about to process an infix operator O, we perform
> these steps before anything else:
>
> 1. Determine whether the infix operator O is immediately followed by a
> sequence of one or more consecutive prefix operators P1, P2.
>
> 2. If such a sequence is identified, we determine which of the Pi's
> has lowest precedence, and we subtract one from that precedence.
>
> 3. Then we compare the precedence of infix operator O with the
> precedence calculated in (3). If O has higher precedence, we
> *demote* it to the calculated precedence. (Only the currently
> occurring instance of that operator.)
>
> 4. We then continue with the usual algorithm, processing the operator
> stack based on comparing precedence and building nodes in the
> output tree and so on.
>
> Some live examples:
>
> 1> (parse-infix '(sin x + x + cos y + y))
> (+ (sin (+ x x))
> (cos (+ y y)))
>
> Works between - and *; unary - has higher precedence than
> additive operators, but less than multiplicative:
>
> 2> (parse-infix '(- x * x * - y * y))
> (* (- (* x x))
> (- (* y y)))
>
> This example illustrates when the algorithm finds that the precedence
> calculated from the prefix operators is higher, so the infix operator
> isn't demoted:
>
> 3> (parse-infix '(- x + x + - y + y)) ;; ... x + - y ...
> (+ (+ (+ (- x) x)
> (- y))
> y)
>
> This example shows when we have two prefix operators after the infix +,
> namely - cos. The first one has higher precedence than +, but by looking
> ahead to the second one, we calculate the demoted precedence correctly,
> resulting in the parse that I would like in that case:
>
> 4> (parse-infix '(sin x + x + - cos y + y))
> (+ (sin (+ x x))
> (- (cos (+ y y))))
>
> Someone must have come up with exactly the same thing before in all the
> decades we have been doing this; but where have they written it up?


Do you mean that


sin x + y + - - sin z


should have the same meaning as


sin(x + y) + (- (- sin(z)))


but


sin x + y + - - z


should have the same meaning as


sin(x + y + (- (- z)))


and similarly for longer chains of '-' signs? If yes, this needs
unbounded lookahead, which make any method to handle it rather
nonstandard. And frankly, such parsing looks rather obscure,
so is is possible that there are no prior art in this specific case.


There is paper "Noncanonical Extensions of LR Parsing Methods" by
M. Hutton:


https://www.eecg.toronto.edu/~mdhutton/papers/noncan.pdf


and I think that parsing expressions in your way is an example
of "LR-Regular Parsing". However, what Hutton presents is
much more general and described in terms of LR-automata and
not in terms of precedence.


--
                                                            Waldek Hebisch

Return to the comp.compilers page.
Search the comp.compilers archives again.