Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
Building Language Front-Ends
Building Language Front-Ends
What this note covers
What this note covers
A language front-end is the part of a tool that turns source text into something the rest of the tool can work with - a syntax tree to inspect and rewrite, or a value to evaluate. The paclet ships a "parser zoo" () that builds exactly these front-ends - a calculator, JSON, Lisp, the lambda calculus, Brainfuck - on a single design idea. This note teaches that idea by building a small calculator front-end end to end, and the techniques generalize to every language in the zoo.
Languages/
The idea is one grammar, two algebras. The grammar is written once, parameterized over an algebra: an of builder functions that the grammar's semantic actions call. Run that one grammar over the standard and you get a language-neutral syntax tree. Run the same grammar over a meaningful algebra and you get a value - a number, a native Wolfram expression, a program's output. The grammar never changes; only the algebra is swapped. That is what lets a front-end produce a clean inspectable tree and a useful result without writing two parsers.
This note builds up one running calculator grammar - a function - near the top, then reuses and extends it section by section: first to emit a tree, then to evaluate to a number, then to show how recursion is wired safely. A closing section distills the sharp edges the zoo ran into while battle-testing the library.
calc[alg]
##Gotchas
The core idea: a grammar over an algebra
The core idea: a grammar over an algebra
An algebra is just an whose values are builder functions. The standard one is , defined in Parser"Binary"` entry builds a - the neutral, -shaped node for a binary-operator application:
Wolfram
`.Its
CodeParser
In[1]:=
 | ASTAlgebra |
Out[1]=
BinaryNode[+,{a,b},]
The node is a 3-slot triple, exactly like Wolfram's own output - but the operator descriptor stays a language-native string (), not a Wolfram symbol. has a builder for each standard node shape: , , , , , , and so on.
Head[descriptor,children,<|meta|>]
CodeParser
"+"
"Leaf"
"Prefix"
"Binary"
"Infix"
"Call"
"Group"
A grammar that wants to be algebra-parametric never writes directly. It writes and lets the caller decide what that means. Hand it and the call builds a ; hand it a numeric algebra and the same call computes . That single indirection - actions call instead of a fixed head - is the whole design.
BinaryNode[...]
alg["Binary"][op,l,r]
l+r
alg[...]
Building the calculator grammar
Building the calculator grammar
Here is the running grammar for this note: a four-function calculator with , unary minus, parentheses, integer literals, and bare identifiers. It is defined once, as a builder , and every later section reuses it.
*
/
+
-
calc[alg]
Two helpers carry their weight. skips trailing whitespace, and wraps a parser so it consumes that whitespace after matching - a token recognizer that does not care about surrounding spaces. Literals and number / identifier regexes all go through , so and parse the same.
ws
tok
tok
"1 + 2"
"1+2"
Precedence is data, not structure: takes the operand parser unit and a list of precedence levels, tightest-binding first. Each operator parser returns the combining function the table folds - a unary for a prefix operator, a binary one for an infix operator - which is where the algebra enters. Parentheses re-enter the table through a recursion cell ( / / , covered in detail below).
In[2]:=
calc[alg_]:=Module{ws,tok,number,ident,unit,bin,pre,expr},expr=
[];ws=
[WhitespaceCharacter];tok[p_]:=
[p~~ws,#1&];number=
tok@
["[0-9]+"],Function[s,alg["Leaf"]["Integer",s]];ident=
tok@
["[A-Za-z][A-Za-z0-9]*"],Function[s,alg["Leaf"]["Symbol",s]];unit=
tok@
"("],
[expr],tok@
[")",number,ident;bin[op_]:=
tok@
[op],(Function[{l,r},alg["Binary"][op,l,r]])&;pre[op_]:=
tok@
[op],(Function[x,alg["Prefix"][op,x]])&;
expr,
[unit,{{{"Prefix",pre["-"]}},{{"InfixL",bin["*"]},{"InfixL",bin["/"]}},{{"InfixL",bin["+"]},{"InfixL",bin["-"]}}}];
[expr]
 | RecCell |
| ParseMany |
| ParseCharacter |
| ParseAction |
| ParseAction |
| ParseRegex |
| ParseAction |
| ParseRegex |
| ParseChoice |
| ParseBetween |
| ParseLiteral |
| RecRef |
| ParseLiteral |
| ParseAction |
| ParseLiteral |
| ParseAction |
| ParseLiteral |
 | SetRec |
| ParseOperatorTable |
| RecRef |
Every semantic action - the inside each - calls . calls , returns a function that calls , and returns one that calls . Nothing in commits to what a "Leaf", "Binary", or "Prefix" is. That is decided entirely by the algebra passed in.
alg[...]
number
alg["Leaf"]["Integer",s]
bin[op]
alg["Binary"][op,l,r]
pre[op]
alg["Prefix"][op,x]
calc
A note on the operator parsers: expects each opParser to return its combining function, not the operator string. That is the extra in and - is a function that, when the operator token matches, returns the binary builder. The table then applies that builder to the operands it has parsed.
&
bin
pre
(Function[{l,r},...])&
Running it two ways
Running it two ways
Now the payoff. The grammar above is a builder; feeding it an algebra produces a , which is callable directly on input - is exactly [parser, input].
parser["input"]
Hand the standard and parse . The result is a syntax tree, nested by precedence - binds tighter than , so the multiplication sits inside the addition's right child:
calc
"1 + 2*3"
*
+
In[3]:=
calc
["1 + 2*3"]
| ASTAlgebra |
Out[3]=
BinaryNode[+,{LeafNode[Integer,1,],BinaryNode[*,{LeafNode[Integer,2,],LeafNode[Integer,3,]},]},]
Unary minus routes through the algebra's builder, and a bare identifier becomes a - the literal text is kept, uninterpreted:
"Prefix"
"Symbol"
In[4]:=
calc
["-x"]
| ASTAlgebra |
Out[4]=
PrefixNode[-,LeafNode[Symbol,x,],]
Now define a tiny semantic algebra: the same three keys the grammar calls, but each builder produces a value instead of a node. turns an integer literal into a number (and an identifier into a ); does the arithmetic; negates.
"Leaf"
"Binary"
"Prefix"
In[5]:=
mathAlg="Leaf"Function[{kind,src},If[kind==="Integer",FromDigits[src],Symbol[src]]],"Binary"Function[{op,l,r},Switch[op,"+",l+r,"-",l-r,"*",l*r,"/",l/r]],"Prefix"Function[{op,x},-x]
Out[5]=
LeafFunction[{kind,src},If[kind===Integer,FromDigits[src],Symbol[src]]],BinaryFunction{op,l,r},Switchop,+,l+r,-,l-r,*,lr,/,,PrefixFunction[{op,x},-x]
l
r
Run the same grammar over on the same input. No tree this time - the actions fold straight to a number as the parse proceeds:
calc
mathAlg
In[6]:=
calc[mathAlg]["1 + 2*3"]
Out[6]=
7
Parentheses, precedence, and unary minus all still hold, because they live in the grammar, not the algebra:
In[7]:=
calc[mathAlg]["2*(3 + 4)"]
Out[7]=
14
Same grammar, swapped algebra: a tree front-end and an evaluator from a single source. This is precisely the split the zoo's (over ) and (over ) ship - the only difference is that the shipped grammar also handles real literals and .
^
Recursion the safe way
Recursion the safe way
The calculator's parenthesis rule is recursive: a parenthesized group contains an expression, which may itself contain another parenthesized group. The library expresses self-reference with , which holds a symbol and looks up the symbol's value at parse time. That indirection is what lets refer to the whole expression grammar before the grammar is finished being built.
unit
The trap is which symbol. [sym] keeps only sym; the actual parser lives in the symbol's value. If sym is a -local, the only live reference to it once returns is the one held inside - and a -local with a single reference can be garbage-collected. When it is, the recursion silently breaks: a parenthesized group drops its body, a nested form never parses. Worse, when the collection happens depends on unrelated load order, so the same grammar can work in one session and fail in another. That is a miserable bug to chase.
calc
The fix is the / / trio from Parserexpr = RecCell[]RecRef[expr]SetRec[expr, …]calcUnique[]`-per-rule pattern is what the paclet's own EBNF front-end uses internally.
Wolfram
`.[RecCell]()allocatesafreshglobal[Unique]()symbolkeptun-evaluatedinsidea[HoldFirst]()wrapper,soitnevergetscollected;[RecRef]()[*cell*]isthe[ParseRecursive]()referencetoit;[SetRec]()[*cell*,*parser*]givesthecellitsparser.Thatisthe
/
/
wiringalreadyin
above.Thesame
In[8]:=
depthParser=Module{nest},nest=
[];
nest,
"("]~~
[nest]~~
[")",Function[{l,inner,r},1+Max[Append[inner,0]]];
[nest]
| RecCell |
| SetRec |
| ParseAction |
| ParseLiteral |
| ParseMany |
| RecRef |
| ParseLiteral |
| RecRef |
Out[8]=
ParserCombinator
 |
|
The action receives three pieces - the , the list of inner depths from the , and the . The body adds one for the current pair and takes the deepest child (or if there are none). Fully nested input is as deep as it is wide:
"("
")"
0
In[9]:=
depthParser["((()))"]
Out[9]=
3
Siblings do not add depth - two pairs side by side inside one outer pair is depth 2:
In[10]:=
depthParser["(()())"]
Out[10]=
2
In[11]:=
depthParser["()"]
Out[11]=
1
The key takeaways: a target must outlive the builder, so use rather than a raw -local symbol; and recurse through a of concrete alternatives (or a fixed-prefix sequence like the -led rule here), never through a production that starts with a nullable parser - see the below.
"("
##Gotchas
Gotchas
Gotchas
These are the library behaviors the parser zoo ran into. Each one is cheap to avoid once you know it is there.
auto-splats a list-valued result. [p, f] calls f value when p's value is a , and otherwise. That is what makes a sequence arrive as - convenient - but it also silently splats a sub-result you wanted to keep whole, like the list from a . Two clean ways to keep a list intact: consume it as one positional element of an enclosing sequence ( with reading untouched), or collect it right at the with :
@@
f[value]
a~~b~~c
f[va,vb,vc]
a~~items~~b
#2
items
{##}
In[12]:=
 | Parse |
 | ParseAction |
| ParseMany |
| ParseLiteral |
Out[12]=
{a,a,a}
A corollary: keep the action's arity in sync with the sequence length. A length-3 sequence applied through a 2-argument silently drops the third element rather than erroring, so use a variadic when you do not want to commit to a fixed count.
{##}
Keep recursion targets stable, and non-nullable-prefixed. Two rules, both from the recursion section. The target must be a stable global symbol (), not a -local that can be garbage-collected. And the target should be a of concrete alternatives, or a rule that starts with a real token - never a production beginning with a nullable parser (a or a -quantified regex) followed by the real content. Re-entering at a nullable prefix was observed to match empty and bail out instead of recursing.
*
Source positions: a gotcha that became a feature. A semantic action receives parse values, not cursor positions - so a bare grammar like the above, whose actions only ever call on values, leaves every node's metadata empty. The minimal grammar in this note still does exactly that:
calc
alg[...]
Where to go from here
Where to go from here
For the bigger picture - how every grammar in the zoo is one algebra-parameterized builder run two ways - see the parser zoo guide. For a production-scale front-end built the same way from a published grammar file, see the Parsing TPTP tech note.