doc: infix: document precedence demotion rule.

* txr.1: Add a subsection to Infix Syntax titled Precedence
Demotion Rule which describes our infix parser's enhancement
to operator precedence parsing, possibly not found
anywhere else.

1 files changed, 145 insertions, 0 deletions

diff --git a/txr.1 b/txr.1
index e33eefac..22b65d6b 100644
--- a/txr.1
+++ b/txr.1
@@ -54495,6 +54495,151 @@ first transforms to
 and then by the same rule to
 .codn "[[a (i)] (j + 1)]" .
 
+.NP* Precedence Demotion Rule
+
+The algorithm used by \*(TL's
+.code parse-infix
+introduces a novel mechanism into operator precedence parsing, called the
+.IR "precedence demotion rule" .
+
+Certain expressions exhibit an intuitive visual parallelism which is
+not captured by ordinary operator precedence parsing; the demotion
+rule is a simple, easily describable mechanism which produces the
+intuitive parses.
+
+One motivating example is an expression such as
+.code "sin x + u + cos y + v"
+which, according to static operator precedence, parses as
+.codn "(sin (+ x u (cos (+ y v))))" .
+
+The actual parse produced by
+.code parse-infix
+turns the
+.code sin
+and
+.code cos
+prefix operator terms into parallel elements on the same level
+of nesting. The
+.code +
+operator between them becomes the main connective for the expression,
+rather than the situation in the conventional parse, of the
+.code sin
+operator becoming the main operator, with the leftmost
+.code +
+between
+.code x
+and
+.code u
+being its only child:
+
+.verb
+  1> (parse-infix '(sin x + u + cos y + v))
+  (+ (sin (+ x u))
+     (cos (+ y v)))
+.brev
+
+The precedence demotion rule is this:
+
+Whenever any infix operator is immediately followed by a sequence of one or
+more consecutive prefix operators, that infix operator's precedence is
+adjusted as follows:
+
+.RS
+.IP 1.
+First, the sequence of prefix operators is scanned, to determine
+which of them last the lowest precedence.
+.IP 2.
+The precedence determined in 1 is decreased by one level.
+.IP 3.
+The resulting decremented precedence from 2 is compared to that
+of the infix operator. If the infix operator has a higher precedence,
+then that operator's precedence is lowered to match the decremented
+precedence
+.RE
+
+The precedence adjustment affects only that occurrence of the infix operator
+from whose trailing precedence operators it is calculated.
+
+.TP* Examples
+
+.verb
+  (parse-infix '(sin x + u + cos y + v))
+  ;;                       ^^^^^
+  --> (+ (sin (+ x u))
+         (cos (+ y v)))
+.brev
+
+In this example, the
+.code ^
+(caret) signs in the comment indicate the operators under consideration
+by the precedence demotion. The operator
+.code +
+is followed by a one-element sequence of prefix operators consisting of
+.codn cos .
+The
+.code cos
+operator has precedence 0; therefore, the decremented precedence calculated
+by step 2 is -1. According to the Operator Table, the
+.code +
+operator has relatively high precedence, 10. Therefore its effective
+precedence is lowered to match the calculated -1.
+At a precedence -1, the precedence of
+.code +
+operator is lower than the preceding
+.code sin
+operator, which causes it to terminate the
+.code sin
+expression, and become a connective for the
+.code sin
+and
+.code cos
+expressions.
+
+
+.verb
+  (parse-infix '(sin x + u + - cos y + v))
+  ;;                       ^^^^^^^
+  --> (+ (sin (+ x u))
+         (- (cos (+ y v))))
+.brev
+
+This example shows the action of the algorithm when the
+infix operator
+.code +
+is followed by two-element prefix operator sequence
+.codn "- cos" .
+
+Step 1 of the algorithm determines this sequence by looking
+ahead through the tokens. The prefix version of the
+.code -
+operator which immediately follows the infix
+.code +
+has a precedence of 11. The following
+.code cos
+operator has a precedence of 0. Thus step 2 takes the
+minimum precedence of 0 and calculates the decremented
+precedence of -1, as in the previous example.
+
+This example shows the necessity for scanning ahead
+and identifying a sequence of prefix operators to determine
+the least precedence. If only one prefix operator were
+examined, there would be no precedence adjustment adjustment,
+because the decremented precedence would be calculated as 10
+from the prefix
+.code -
+operator's precedence level of 11. Since
+.code +
+already has a precedence level of 10, no demotion
+would take place. This would be a problem, because simply by
+adding negation to the
+.code cos
+term, the parse would collapse to the conventional one,
+rendering the
+.code cos
+expression as a subexpression embedded in
+.codn sin 's
+argument.
+
 .coNP Function @ parse-infix
 .synb
 .mets (parse-infix << list )