Here's the sample output for the example Per gave us:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | 1 -> 1 12 -> 12 12* -> (* 12 0) 12*3 -> (* 12 3) 12*34 -> (* 12 34) 12*34 + -> (+ (* 12 34) 0) 12*34 + 4 -> (+ (* 12 34) 4) 12*34 + 45 -> (+ (* 12 34) 45) 12*34 + 45/ -> (+ (* 12 34) (/ 45 0)) 12*34 + 45/5 -> (+ (* 12 34) (/ 45 5)) 12*34 + 45/56 -> (+ (* 12 34) (/ 45 56)) 12*34 + 45/56 + -> (+ (+ (* 12 34) (/ 45 56)) 0) 12*34 + 45/56 + ~ -> (+ (+ (* 12 34) (/ 45 56)) (~ 0)) 12*34 + 45/56 + ~2 -> (+ (+ (* 12 34) (/ 45 56)) (~ 2)) 12*34 + 45/56 + ~25 -> (+ (+ (* 12 34) (/ 45 56)) (~ 25)) |
On top of operator precedence, arity and associativity, I also ask for the operator's neutral element, in order to have a convenient right child placeholder for binary operators. Here's an example of that in action:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | arithmetic example: ================== 1 -> 1 1 + -> (+ 1 0) 1 + 2 -> (+ 1 2) 1 + 2 * -> (+ 1 (* 2 1)) 1 + 2 * ( -> (+ 1 (* 2 1)) 1 + 2 * (3 -> (+ 1 (* 2 3)) 1 + 2 * (3 - -> (+ 1 (* 2 (- 3 0))) 1 + 2 * (3 - 4 -> (+ 1 (* 2 (- 3 4))) 1 + 2 * (3 - 4) -> (+ 1 (* 2 (- 3 4))) 1 + 2 * (3 - 4) - -> (- (+ 1 (* 2 (- 3 4))) 0) 1 + 2 * (3 - 4) - - -> (- (+ 1 (* 2 (- 3 4))) (- 0)) 1 + 2 * (3 - 4) - -5 -> (- (+ 1 (* 2 (- 3 4))) (- 5)) 1 + 2 * (3 - 4) - -5^ -> (- (+ 1 (* 2 (- 3 4))) (- (^ 5 1))) 1 + 2 * (3 - 4) - -5^6 -> (- (+ 1 (* 2 (- 3 4))) (- (^ 5 6))) 1 + 2 * (3 - 4) - -5^6+ -> (+ (- (+ 1 (* 2 (- 3 4))) (- (^ 5 6))) 0) 1 + 2 * (3 - 4) - -5^6+7 -> (+ (- (+ 1 (* 2 (- 3 4))) (- (^ 5 6))) 7) 1 + 2 * (3 - 4) - -5^6+7 + -> (+ (+ (- (+ 1 (* 2 (- 3 4))) (- (^ 5 6))) 7) 0) 1 + 2 * (3 - 4) - -5^6+7 + 8 -> (+ (+ (- (+ 1 (* 2 (- 3 4))) (- (^ 5 6))) 7) 8) 1 + 2 * (3 - 4) - -5^6+7 + 8^ -> (+ (+ (- (+ 1 (* 2 (- 3 4))) (- (^ 5 6))) 7) (^ 8 1)) 1 + 2 * (3 - 4) - -5^6+7 + 8^( -> (+ (+ (- (+ 1 (* 2 (- 3 4))) (- (^ 5 6))) 7) (^ 8 1)) 1 + 2 * (3 - 4) - -5^6+7 + 8^(9 -> (+ (+ (- (+ 1 (* 2 (- 3 4))) (- (^ 5 6))) 7) (^ 8 9)) 1 + 2 * (3 - 4) - -5^6+7 + 8^(9/ -> (+ (+ (- (+ 1 (* 2 (- 3 4))) (- (^ 5 6))) 7) (^ 8 (/ 9 1))) 1 + 2 * (3 - 4) - -5^6+7 + 8^(9/1 -> (+ (+ (- (+ 1 (* 2 (- 3 4))) (- (^ 5 6))) 7) (^ 8 (/ 9 1))) 1 + 2 * (3 - 4) - -5^6+7 + 8^(9/10 -> (+ (+ (- (+ 1 (* 2 (- 3 4))) (- (^ 5 6))) 7) (^ 8 (/ 9 10))) 1 + 2 * (3 - 4) - -5^6+7 + 8^(9/10) -> (+ (+ (- (+ 1 (* 2 (- 3 4))) (- (^ 5 6))) 7) (^ 8 (/ 9 10))) |
A couple of mildly interesting properties of this parser is that it doesn't use a lexer and that it traverses the in-memory expression tree explicitly instead of relying on recursion for precedence climbing.
I don't expect this approach to scale beyond the scope of homework, but maybe I can still reuse it for day 3.
Here's the code. The meat is mainly inside the procedure "feed".