Prior art for operator parsing trick

Hi all,


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?


--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

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