diff options
| -rw-r--r-- | txr.1 | 145 |
1 files changed, 145 insertions, 0 deletions
@@ -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 ) |