The following text and the code behind it was largely written by Angus
Griffith. It also appears in the code in markdown format in the module
The Mathics parser is an operator precedence parser that implements the precedence climbing method. The AST (Abstract Syntax Tree) produced after parsing is a kind of M-expression which is then used in evaluation.
The Wolfram language is surprisingly complex and has quite a few subtleties; this document attempts to cover the major ones. The language is documented on the Wolfram website although there are a few errors.
One primary feature of the Wolfram language is a large number of operators with precedences. It is this characteristic that makes operator precedence parsing well suited to the language. There are however a few special language features that cannot be parsed by the standard precedence climbing algorithm.
Instead of giving an introduction to precedence climbing, here are two references that explain the algorithm better than I could:
This algorithm has a natural application to the Wolfram language. Every
operator has an inbuilt precedence level which can be accessed with e.g.
In addition to precedences, operators in the Wolfram language have a
grouping attribute. Consider trying to parse the code snippet
a + b + c. There is some ambiguity in what order the operations
should be applied. Should we use left associativity
Plus[Plus[a + b] + c] or right associativity
Plus[a, Plus[b + c]]?
In fact the addition operator is usually considered fully associative,
Plus[a, b, c]. In the Wolfram language this is referred to
as ‘flat’ associativity because the expression tree is flat.
Flat associativity is not a large issue in practice as the as flat operators can be first treated as left or right associative, whichever is more efficient, and flattened once the AST is constructed.
One thing to be aware of is that parenthesis prevent the flattening of
expressions at parse time,
a * (b * c) parses as
Times[a, Times[b, c]] but is flattened immediately afterwards.
In addition to left/right associativity some operators are
non-associative. That is, an operator
? is non-associative if
a ? b ? c is not valid syntax.
The only non associative operator in the Wolfram language is
Implementation of binary operators¶
The relevant code snippet for binary operators is:
def parse_binary(self, expr1, token, p): # called with expr1 """ Implemments grammar rule: expr <- expr1 BINARY expr2 """ tag = token.tag # name of BINARY token q = binary_ops[tag] # lookup precedence of operator if q < p: return None self.consume() # consume BINARY token if tag not in right_binary_ops: # left/right grouping q += 1 expr2 = self.parse_exp(q) # parse expr2 # handle nonassoc operators if tag in nonassoc_binary_ops and expr1.get_head_name() == tag and not expr1.parenthesized: self.tokeniser.sntx_message(token.pos) raise InvalidSyntaxError() result = Node(tag, expr1, expr2) # construct the result: `BINARY[expr1, expr2]` if tag in flat_binary_ops: # flatten the tree if required result.flatten() return result
Special case: Implicit times¶
In the Wolfram language the expression
a b should parse as
Times[a b]. This seemingly simple rule actually creates lots of
In the context of precedence climbing we use the rule
E_n <- E_n E_n
n = 400 is the precedence of
The Wolfram language has two types of unary operators, prefix and
postfix. As the names suggest, prefix operators come before the
- 2 and postfix operators come after e.g.
Special case: unary minus¶
Consider the code
- - a. One might expect that this parses as
Minus[Minus[a]] but in fact the unary minus is handled at parse time
Times[-1, x]. One might expect that the answer is
Times[-1, Times[-1, a]] but in fact this
Times is flattened at
parse time and the answer is
Times[-1, -1, a]. We can recover the
expected answer by imposing parenthesis to prevent flattening, that is
Special case: unary plus¶
Unary plus on the other hand is ignored.
+a is the same
The last type of standard operator in the Wolfram language are ternary
operators. There are two ternary operators,
both are special cases. In general, they are treated like binary
Special case: Infix¶
The simplest ternary operator in the Wolfram language is
a ~ b ~ c becomes
b[a, c]. We treat this like a binary
operator but override the rule to consume an extra
~ E. The relevant
annotated code snippet is:
def e_Infix(self, expr1, token, p): # called with expr1 """ Example: expr <- expr1 ~ expr2 ~ expr3 """ q = ternary_ops['Infix'] # lookup precedence of Infix if q < p: return None self.consume() # consume first '~' expr2 = self.parse_exp(q + 1) # consume expr2 self.expect('Infix') # consume second '~' expr3 = self.parse_exp(q + 1) # consume expr3 return Node(expr2, expr1, expr3) # return expr2[expr1, expr3]
Special case: Span¶
See the section on backtracking.
Special case: Integrate¶
Integrate rule is
E <- Integrate expr1 DifferentialD expr2.
Similarly this can be handled by treating
Integrate as a prefix
operator that consumes an extra token and expression. Unlike
the precedences for the inner (
expr1) and outer (
To quote the Wolfram docs:
Forms such as
'Integral' expr1 'DifferentialD' expr2have an “outer” precedence just below
Power, as indicated in the table above, but an “inner” precedence just above
Sum. The outer precedence determines when
expr2needs to be parenthesized; the inner precedence determines when
expr1needs to be parenthesized.
This is simple to handle with precedence climbing:
def p_Integral(self, token): # `expr <- Integral expr1 DifferentialD expr2 self.consume() # consume 'Integral' inner_prec = all_ops['Sum'] + 1 # lookup inner outer_prec = all_ops['Power'] - 1 # and outer prec expr1 = self.parse_exp(inner_prec) # consume expr1 self.expect('DifferentialD') # consume 'DifferentialD' expr2 = self.parse_exp(outer_prec) # consume expr2 return Node('Integrate', expr1, expr2)
Precedence Climbing Operators¶
All the Mathics operators are specified in
mathics/core/parser/operators.py. The precedence climbing algorithm
is implemented in
mathics/core/parser/parser.py. All the special
cases are implemented as additional rules.
Methods beginning with
p_TAG declare what to do when the
token is encountered at the beginning of an expression. For example, the
first token after an open parenthesis. These rules define all the
E <- A, prefix operators,
E <- PREFIX E and also
E <- ( E ).
Methods beginning with
e_TAG are called when one expression is
already present and we encounter the
TAG token. This covers binary
E <- E BINARY E, postfix operators
E <- E POSTFIX,
E <- E TERNARY1 E TERNARY2 E, and functions
E <- E [ SEQUENCE ].
Methods beginning with
b_TAG are used for parsing boxes and can be
ignored on first reading of the parser code.
Most of the Wolfram language can be parsed with precedence climbing but
there are a few special language features that require something more.
Span operator is one example. Both
a ;; b and
a ;; are
valid syntax, the latter is equivalent to
a ;; All.
Consider the example:
a;;!b. There are four options for parsing
Span[a, Not[b]] -
Factorial[Span[a, Null]] -
Times[Span[a, All], Not[b]] -
Times[Factorial[Span[a, All]], b]
a ! b parses as
Times[Factorial[a], b] which might suggest
option 4 is correct but the precedence of
Span is lower than that of
Times so it is parsed first, top down. We might then think that
option 1 is correct, but
Not has a lower precedence than
E <- E ;; E rule cannot be applied here and we must use the
postfix form of
Span. Since the precedence of
higher than that of
Span we can apply the postfix rule for
option 3 turns out to be correct.
The problem with
Span, and also
CompoundExpression is that they
require arbitrary lookahead to see if the right hand side has lower
precedence. It’s not a large issue for
CompoundExpression which has
very low precedence but nevertheless this language quirk requires
backtracking in the parser.
Recursive descent parsers in Python¶
The lack of tail call optimization (TCO) causes some problems when
writing recursive descent (RD) parsers in python. It’s possible to write
RD parsers in an iterative style but it’s not nice. One can use
trampolining to mitigate this limitation. In practice Python provides
1000 recursions by default which should be enough for most parse trees.
1 + 2 + ... 1000!
Clarke 1986, ‘The top-down parsing of expressions’
Recursive descent parsers, shunting yard algorithm, precedence climbing, and efficient parsers with large number of operator precedences.
How to handle right/left associativity in recursive descent parsers and how to write efficient of RD parsers.
MMA docs with grouping and relative precedences.
Henry Baker 1994, ‘CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A.’, unpublished note on implementing TCO with trampolines.