Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
PrattVsPEG
PrattVsPEG
There are two ways to teach a parser that is and not . You can put the precedence in the shape of the grammar — a cascade of rules, one per precedence level — and parse it with ordered choice; that is the PEG way. Or you can put the precedence in data — a number, the binding power, on each operator — and let one small loop consume operators by strength; that is Vaughan Pratt's 1973 Top-Down Operator Precedence (TDOP), the technique behind Crockford's JavaScript parser and dozens of DSLs.
1+2*3
1+(2*3)
(1+2)*3
Wolfram`Parser`
The PEG way: precedence is grammar structure
The PEG way: precedence is grammar structure
A PEG encodes " binds tighter than " as a tower of nonterminals: an expr is a sum of terms, a term is a product of factors, a factor is a number or a parenthesised expr. Each level is its own rule, and folds the left-associative chain at that level. The rules refer back to each other through , which looks a parser up by symbol at parse time so the cycle can be written before every node exists.
*
+
In[1]:=
num=
["[0-9]+"],FromDigits;addOp=
["+"],(Plus&),
["-"],(Subtract&);mulOp=
["*"],(Times&),
["/"],(Divide&);factor=
"("],
[expr],
[")",num;term=
[factor,mulOp];expr=
[term,addOp];
[expr,"1+2*3"]
 | ParseAction |
 | ParseRegex |
| ParseChoice |
| ParseAction |
 | ParseLiteral |
| ParseAction |
| ParseLiteral |
| ParseChoice |
| ParseAction |
| ParseLiteral |
| ParseAction |
| ParseLiteral |
| ParseChoice |
| ParseBetween |
| ParseLiteral |
| ParseRecursive |
| ParseLiteral |
| ParseChainLeft |
 | ParseChainLeft |
 | Parse |
Out[1]=
7
It works, and on a flat input it is fast. But notice what the cascade costs even when it succeeds: to read the bare number , the parser still descends expr → term → factor, three rule entries for one token. Precedence lives in that descent. Every operand pays for every level above it.
1
Where PEG breaks: shared-prefix alternatives
Where PEG breaks: shared-prefix alternatives
The cascade is fine while each level has a distinct shape. It breaks when a level offers several alternatives that all begin with the same operand. The canonical case is a grammar with more than one binary family at the same tier — or, and, and (in a higher-order language) application — each written
<binary> ::= <unit> "|" <unit> | <unit> "&" <unit> | <unit> "@" <unit>
Lowered to an ordered , the three alternatives each re-parse the leading from scratch, because a PEG has no memo of what the previous alternative already matched. When can itself be a parenthesised sub-expression, that re-parse recurses, and the cost of a left-nested chain becomes O(3^depth). Here is the shape, built honestly with the combinators:
<unit>
<unit>
In[2]:=
atom=
["a"],
["b"];unit=
"("],
[logic],
[")",atom;orF=
[unit],
["|"],
[unit];andF=
[unit],
["&"],
[unit];appF=
[unit],
["@"],
[unit];logic=
orF,andF,appF,
[unit];
[logic,"((a@b)@b)"]
| ParseChoice |
| ParseLiteral |
| ParseLiteral |
| ParseChoice |
| ParseBetween |
| ParseLiteral |
| ParseRecursive |
| ParseLiteral |
| ParseSequence |
| ParseRecursive |
| ParseLiteral |
| ParseRecursive |
| ParseSequence |
| ParseRecursive |
| ParseLiteral |
| ParseRecursive |
| ParseSequence |
| ParseRecursive |
| ParseLiteral |
| ParseRecursive |
| ParseChoice |
| ParseRecursive |
| Parse |
Out[2]=
{{a,@,b},@,b}
Each extra layer of multiplies the work by three: parses the inner group and fails at , re-parses it and fails at , re-parses it a third time and succeeds — and every one of those parses repeats the same three-way split one level down. Timing the depth makes the curve unmistakable (this is the standalone measurement from ):
(…@b)
orF
@
andF
@
appF
dev/pratt-vs-peg.wls
depth | bytes | PEG ordered-choice | Pratt table |
5 | 21 | 0.085 s | 0.0001 s |
7 | 29 | 0.775 s | 0.0001 s |
9 | 37 | 7.59 s | 0.0002 s |
10 | 41 | > 15 s (timeout) | 0.0002 s |
The input grows four bytes per level; the runtime triples. That 3 is not a mystery — it is the three alternatives of the choice, each re-parsing the shared operand. No ordering or longest-match trick removes it, because all three alternatives genuinely start the same way.
The Pratt way: precedence is data
The Pratt way: precedence is data
Pratt's move is to stop encoding precedence in the grammar's shape and put it in a table. Each operator gets a binding power; the parser reads one operand, then loops: while the next operator binds tighter than the caller's threshold, consume it and its right operand, fold, repeat. The leading operand is parsed once. Two functions per token carry the behaviour — nud (null denotation: how a token acts with nothing to its left, e.g. a prefix ) and led (left denotation: how it acts on a left operand, e.g. infix ).
~
&
is that engine as a combinator: takes a unit parser and a list of precedence levels, tightest first; each operator parser returns its combining function, the same convention as .
The same expression language as the cascade above, now as one table — and it evaluates, because the operator parsers return the real arithmetic functions:
In[3]:=
num2=
["[0-9]+"],FromDigits;unit2=
"("],
[calc],
[")",num2;calc=
unit2,"InfixL",
["*"],(Times&),
["/"],(Divide&),"InfixL",
["+"],(Plus&),
["-"],(Subtract&);
[calc,"1+2*3"]
| ParseAction |
| ParseRegex |
| ParseChoice |
| ParseBetween |
| ParseLiteral |
| ParseRecursive |
| ParseLiteral |
| ParseOperatorTable |
| ParseChoice |
| ParseAction |
| ParseLiteral |
| ParseAction |
| ParseLiteral |
| ParseChoice |
| ParseAction |
| ParseLiteral |
| ParseAction |
| ParseLiteral |
| Parse |
Out[3]=
7
Same answer, but no cascade: one rule, two table rows. And the shared-prefix grammar that blew up under ordered choice is now linear, because the operand is read once and the operator is chosen by looking at the next token, not by re-parsing the operand under each hypothesis:
In[4]:=
ap=
["@"],(app&);u=
"("],
[e],
[")",
@@
/@{"a","b"},Symbol;e=
[u,{{"InfixL",ap}}];f[0]="a";f[k_]:=f[k]="("<>f[k-1]<>"@b)";
[e,f[12]]
| ParseAction |
| ParseLiteral |
| ParseChoice |
| ParseBetween |
| ParseLiteral |
| ParseRecursive |
| ParseLiteral |
| ParseAction |
| ParseChoice |
| ParseLiteral |
| ParseOperatorTable |
| Parse |
Out[4]=
app[app[app[app[app[app[app[app[app[app[app[app[a,b],b],b],b],b],b],b],b],b],b],b],b]
Depth 12 is where the PEG version needs minutes; the table returns instantly. The nud/led loop never re-parses the operand, so the 3^depth factor is simply gone.
They compose — use each where it is strong
They compose — use each where it is strong
This is not PEG or Pratt. A real grammar is mostly recognition — keywords, brackets, lists, the overall clause shape — and ordered choice with / is exactly right for that. Operator expressions are the one sub-problem where ordered choice is the wrong tool, and that is the sub-problem owns. The two nest cleanly: a table's unit parser is an ordinary back into the PEG grammar (for parenthesised groups, quantifiers, atoms), and the table is just another node the surrounding PEG can call.
A one-level, one-operator table is (or for ); the table generalises them with multiple precedence levels and prefix / postfix in a single linear pass. So the rule of thumb: PEG for the grammar, Pratt for the operators inside it.
"InfixR"
Or skip the table: memoise
Or skip the table: memoise
The table is one fix; it is not the only one. The blow-up was never really about operators — it was an ordered choice re-parsing the same operand at the same position with no memory of having done so. Packrat memoisation removes exactly that: cache each nonterminal's result keyed by , and the second and third alternatives that re-enter the operand at the same spot hit the cache instead of re-parsing. The exponential collapses to linear with no change to the grammar — the same ordered-choice rules from the blow-up section above, run under with one option:
{rule,position}
In[5]:=
| Parse |
Out[5]=
{{{a,@,a},@,a},@,a}
On the real TPTP THF grammar this is not hand-waving: the un-overridden, ordered-choice grammar that times out at 13 bytes parses a 121-byte nested formula in ~0.12 s with — within noise of the Pratt override (~0.11 s). Same linearity, by a completely different route.
"Memoize"->True
So which do you reach for?
◼
Memoisation is the general lever. It makes any backtracking PEG linear, not just operator grammars, and it changes nothing about the grammar — the published BNF stays the parser. The cost is O(input × rules) memory (one cell per rule per position), and it does not, by itself, give you operator semantics: the output is still whatever the raw rules produce.
◼
Pratt is the targeted lever. It costs O(1) extra memory and folds precedence and associativity into the result directly — the / / terms come out shaped correctly — but you hand-write the binding-power table instead of reading it off the BNF.
And
Or
ForAll
They are not rivals. ships both, and TPTP uses each where it is strong: the THF connectives go through the Pratt for clean terms with no memo table, while is the one-flag escape hatch for any other recursive grammar that happens to backtrack.
Wolfram`Parser`
"Memoize"->True
The payoff: TPTP THF
The payoff: TPTP THF
The motivating case is real. The THF (Typed Higher-order Form) grammar has exactly the pathological rule — , three alternatives over a shared — and on the published BNF the ordered-choice parser times out on a 13-byte formula.
<thf_binary_assoc>::=<thf_or_formula>|<thf_and_formula>|<thf_apply_formula>
<thf_unit_formula>
now overrides that rule with a over , with (application), , , the nonassoc connectives, prefix , and / as table entries. The blow-up is gone — a 321-byte nested formula parses in under a third of a second — and the higher-order structure comes back as clean Wolfram Language terms:
<thf_unitary_formula>
@
&
|
~
=
!=
In[6]:=
 | TPTPImport |
Out[6]=
$Failed[Axioms]
Quantifiers nest, -lambdas survive as binders, application curries:
^
In[7]:=
| TPTPImport |
Out[7]=
$Failed[Axioms]
That is the whole argument in one place: the grammar shape PEG could only parse exponentially, Pratt parses in a line — and the binding-power table that does it is the same / idea Pratt wrote down in 1973.
nud
led
""