tree ← #.exp.parse expr ⍝ Infix expression parser.
[expr] is a character vector representing an expression to be parsed.
The parse is controlled by [#.exp.defns], a 4-vector of:
- order of precedence 0 1 2 3 ···
- association direction ← → ↑ (monadic)
- function name * / ln ···
- APL equivalent × ÷ ⍟ ···
disp exp.defns
┌→──────────────────────────┬──────────────┬───────────────────────────────────────────────────┬───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ │ │┌→┬─┬─┬─┬─┬─┬─┬───┬───┬───┬───┬───────┬─────┬─────┐│┌→┬─┬─┬─┬─┬─┬─┬─────────────────────────────────────┬──┬──┬──┬────────────────────────────────────────────────┬────────────────────────────────────────────────┬──────────────────────────────────────────────────────────────────┐│
│0 1 1 2 2 3 4 5 6 6 6 7 8 9│←←←←←→↑↑↑↑↑↑↑↑││,│+│-│*│/│∧│-│mod│sum│max│min│ceiling│floor│round│││ │+│-│×│÷│*│-│{0::⎕signal ⎕en ⋄ n m _←⍵,0 ⋄ m | n}│+/│⌈/│⌊/│{0::⎕signal ⎕en ⋄ num mul _←⍵,0 ⋄ mul×⌈num÷mul}│{0::⎕signal ⎕en ⋄ num mul _←⍵,0 ⋄ mul×⌊num÷mul}│{0::⎕signal ⎕en ⋄ num sig _←⍵,0 ⋄ mul←÷10*sig ⋄ mul×⌊0.5+num÷mul}││
│ │ │└→┴→┴→┴→┴→┴→┴→┴──→┴──→┴──→┴──→┴──────→┴────→┴────→┘│└⊖┴→┴→┴→┴→┴→┴→┴────────────────────────────────────→┴─→┴─→┴─→┴───────────────────────────────────────────────→┴───────────────────────────────────────────────→┴─────────────────────────────────────────────────────────────────→┘│
└~─────────────────────────→┴─────────────→┴──────────────────────────────────────────────────→┴──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────→┘
or in columns:
↑exp.defns
0 1 1 2 2 3 4 5 6 6 6 7 8 9
← ← ← ← ← → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
, + - * / ∧ - mod sum max min ceiling floor round
+ - × ÷ * - {0::⎕signal ⎕en ⋄ n m _←⍵,0 ⋄ m | n} +/ ⌈/ ⌊/ {0::⎕signal ⎕en ⋄ num mul _←⍵,0 ⋄ mul×⌈num÷mul} {0::⎕signal ⎕en ⋄ num mul _←⍵,0 ⋄ mul×⌊num÷mul} {0::⎕signal ⎕en ⋄ num sig _←⍵,0 ⋄ mul←÷10*sig ⋄ mul×⌊0.5+num÷mul}
Note that apart from power '*', dyadic operators bind left, and that monadic and
dyadic '*' and '-' have different binding strengths; see examples below.
A possible source of confusion is the distinction between "order of association"
and "direction of evaluation". For example, primitive operator '-' associates
left, so that 3-2-1 is interpreted as (3-2)-1. This mean that the evaluation
proceeds from left to right: 3-2-1 → 1-1 → 0 (in the opposite direction from
the association arrow).
[parse] signals the following errors with error number 666.
┌────────────────┬───────┐
│ Error Message │Example│
├────────────────┼───────┤
│missing operator│ 2 3 │
│missing operand │ 2+ │
│null expression │ () │
│unexpected ) │ 2) │
│missing ))··· │ ((2 │
└────────────────┴───────┘
Technical notes:
[parse] proceeds from left to right through the tokens in the expression. Oper-
ands are pushed immediately onto an output stack (acc), which accumulates the
parse tree. Operators are pushed onto a second stack (stk), where the top two
are compared. If the top operator is weaker than the second, the latter is ex-
tracted from the stack and bound with the top two items in [acc], which are re-
placed with a single item, the (larg op rarg) triple.
It is convenient to store the tokens waiting to be processed, also in a stack.
We wind up with three stacks:
⍵: Tokens waiting to be processed,
acc: Tree nodes waiting to be connected by an operator.
stk: Operators of lower binding strength than the current one.
The following illustration shows the parsing of expression 1+2-3*4∧5∧6/7+8.
Initially, all tokens are in the ⍵ stack, and acc and stk are empty. See below
for a key to the annotations. Remember, the expression is to be parsed according
to the rules of standard arithmetic, where ∧ binds tighter than *, binds tighter
than +, etc.
────────┬────────────────┬────────
acc → │ ← tokens │ ← stk
────────┼────────────────┼────────
│ 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 2│ 3*4∧5∧6/7+8│ - + ·
│ │ └≤≤┘
│ │ ←┘
────────┼────────────────┼────────
+ │ 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 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 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 2 │ │ ←┘
│ │
────────┼────────────────┼────────
+ 3 4 ∧ │ 7+8│ / ∧ * - ·
┌┴┐ ┌┴┐ │ │ └<<┘
1 2 5 6 │ │ ←┘
│ │
────────┼────────────────┼────────
+ 3 ∧ │ 7+8│ / * - ·
┌┴┐ ┌┴─┐ │ │ └≤≤┘
1 2 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 2 3 ∧ │ │ ←┘
┌┴─┐ │ │
4 ∧ │ │
┌┴┐ │ │
5 6 │ │
────────┼────────────────┼────────
+ / │ 8│ + - ·
┌┴┐ ┌┴──┐ │ │ └≤≤┘
1 2 * 7 │ │ ←┘
┌┴─┐ │ │
3 ∧ │ │
┌┴─┐ │ │
4 ∧ │ │
┌┴┐ │ │
5 6 │ │
────────┼────────────────┼────────
- │ 8│ + ·
┌──┴───┐ │ │ └>>┘
+ / │ │
┌┴┐ ┌┴──┐ │ │
1 2 * 7 │ │
┌┴─┐ │ │
3 ∧ │ │
┌┴─┐ │ │
4 ∧ │ │
┌┴┐ │ │
5 6 │ │
────────┼────────────────┼────────
- │ 8│ + ·
┌──┴───┐ │ ←┘│
+ / │ │
┌┴┐ ┌┴──┐ │ │
1 2 * 7 │ │
┌┴─┐ │ │
3 ∧ │ │
┌┴─┐ │ │
4 ∧ │ │
┌┴┐ │ │
5 6 │ │
────────┼────────────────┼────────
- 8│ │ + ·
┌──┴───┐ │ │ ←┘
+ / │ │
┌┴┐ ┌┴──┐ │ │
1 2 * 7 │ │
┌┴─┐ │ │
3 ∧ │ │
┌┴─┐ │ │
4 ∧ │ │
┌┴┐ │ │
5 6 │ │
────────┼────────────────┼────────
+ │ │ ·
┌──┴──┐ │ │
- 8 │ │
┌──┴───┐ │ │
+ / │ │
┌┴┐ ┌┴──┐ │ │
1 2 * 7 │ │
┌┴─┐ │ │
3 ∧ │ │
┌┴─┐ │ │
4 ∧ │ │
┌┴┐ │ │
5 6 │ │
────────┴────────────────┴────────
Key:
stack → top of stack to right.
← stack top of stack to left.
↑···↑ compare operators:
⍺>>⍵ ⍺ stonger than ⍵.
⍺<<⍵ ⍺ weaker than ⍵.
⍺≥≥⍵ ⍺ same strength as ⍵, associates right.
⍺≤≤⍵ ⍺ same strength as ⍵, associates left.
←┘ └→ move token left or right.
In addition to the three stacks, parse maintains two more items of state:
[dep], the current parenthesis nesting depth.
[cls], the "class" of the previous token:
_: initial state or previous token was a left paren.
a: previous token was an operand (argument).
f: previous token was an operator (function).
Together, cls, dep, ack, stk and ⍵ completely describe the parse state.
Parentheses are processed by calling the parser recursively on encountering a
'(', and pushing the result back onto the token stack as an operand, when a ')'
is reached.
When the last token (which in a correct expression, must be an operand) has been
fetched, [stk] may still contain some operators. Any remaining ones are flushed,
simply by pushing an artificially weak (strength = ¯1) dummy operator onto the
stack. This displaces all of the others, causing them to bind with their oper-
ands waiting in the accumulator.
Vectors vs. Lists vs. Recursive Tuples
--------------------------------------
A stack is often represented in APL by a _vector_. In this case, operations on
the stack are:
push: stack←(⊂head),stack
pop: head stack←(⊃stack)(1↓stack)
An alternative is to implement a recursive data structure, the _list_. A list is
either empty, or is a pair (head tail), where tail is itself a list.
push: stack←head stack
pop: head stack←stack
If each item in the stack is the same _tuple_ (a b c), we can use either a list:
push: stack←(a b c)stack
pop: (a b c)stack←stack
or a "recursive tuple", which provides marginally easier access to its top item:
push: stack←a b c stack
pop: a b c stack←stack
In general, a _vector_ consumes slightly less workspace, but is a fraction slow-
er to access than the other two. A _tuple_ is both marginally quicker and uses
less space than a _list_, but is appropriate only if all of its items have the
same structure.
[parse] uses a list for its accumulator [acc], and a recursive tuple for its op-
erand stack [stk].
To render a vector as a list, we "link-reduce" it:
list←↑{⍺ ⍵}/vector,_
where '_' is a marker that distinguishes the bottom of the list. Choosing a
_scalar_ value for the marker means that we can test for it _after_ deconstruct-
ing the list:
head tail←list
head≡_: null
Error message considerations
----------------------------
In order to place an error marker accurately under an errant token, each token
is bound with its position in the original source, and the pairing maintained
throughout the whole of the evaluation. This results in each node in the parse
tree's having a position marker. Outer nodes for which there is no corresponding
source token carry a dummy position of ¯1. The following example shows the com-
plete parse tree, together with token positions for source that has been offset
to the right by 100 spaces.
disp parse (100/' '),'2+3+4' ⍝ 100-offset expression.
┌→────────────┬───────┬─┐
│┌→┬───────┬─┐│ │ │
││ │┌→┬───┐│ ││┌→┬───┐│ │
││2││+│102││3│││+│104││4│
││ │└→┴~──┘│ ││└→┴~──┘│ │
│└→┴──────→┴→┘│ │ │
└────────────→┴──────→┴→┘
Examples:
)cs exp
[show] displays the expression tree in graphical form:
't'show parse'1+2-3+4' ⍝ +/- associate left.
+
┌─┴┐
- 4
┌─┴┐
+ 3
┌┴┐
1 2
't'show parse'1+2*3+4' ⍝ * binds tighter.
+
┌───┴┐
+ 4
┌┴─┐
1 *
┌┴┐
2 3
't'show parse'1+2*(3+4)' ⍝ ()s override binding.
+
┌┴─┐
1 *
┌┴─┐
2 +
┌┴┐
3 4
't'show parse'1*2*3+4∧5∧6' ⍝ ∧ associates right.
+
┌─┴─┐
* ∧
┌─┴┐ ┌┴─┐
* 3 4 ∧
┌┴┐ ┌┴┐
1 2 5 6
't'show parse'1+--2*3' ⍝ monadic - binds tightly right.
+
┌┴─────┐
1 *
┌───┴┐
- 3
└─┐
-
└┐
2
Back to: →Implementation_Details←