Path: csiph.com!weretis.net!feeder9.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: Kaz Kylheku <643-408-1753@kylheku.com>
Newsgroups: comp.compilers
Subject: Prior art for operator parsing trick
Date: Sat, 05 Apr 2025 23:22:57 -0000
Organization: Compilers Central
Sender: johnl%iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <25-04-002@comp.compilers>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="10974"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, question
Posted-Date: 05 Apr 2025 20:52:26 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers:3641

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