Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
The Parser Zoo - language front-ends over a shared algebra
The Parser Zoo - language front-ends over a shared algebra
Abstract
Abstract
The parser zoo is a spread of language front-ends built on - a calculator, a reader, a s-expression reader, a lambda-calculus interpreter, and a Brainfuck runner - chosen to stress different corners of the library: operator precedence, recursive data, binders, comment-aware whitespace, and an esoteric language the parser also runs. The one big idea is that each grammar is written once over an abstract algebra - an of builder functions its semantic actions call - then run two ways. Hand the grammar the language's meaningful actions and it yields a useful value: a number, a native Wolfram expression, a program's output. Hand it the shared and the same grammar yields a standard, language-neutral syntax tree modelled on Wolfram's own shape. That is the whole point: meaningful language-specific parse actions, but without which a standard AST. The grammar is untouched; only the algebra is swapped.
Wolfram`Parser`
CodeParser
The standard AST
The standard AST
The neutral node vocabulary is core (the languages live in their own subcontexts, and friends). Every node is a 3-slot triple mirroring , but the operator descriptors stay language-native strings (, , ) instead of being forced into Wolfram symbols, so the same vocabulary serves a calculator, JSON, Lisp, the lambda calculus, and Brainfuck alike.
Wolfram`Parser`
Wolfram`Parser`Languages`Calculator`
Head[descriptor,children,<|meta|>]
CodeParser
"+"
":"
"'"
◼
a terminal - a literal or identifier, keeping its source text
◼
an application or call; the head is itself a node
◼
a prefix-operator application
◼
a postfix-operator application
◼
a binary-operator application
◼
a flat n-ary operator chain
◼
a ternary-operator application
◼
◼
the root node wrapping every top-level form
◼
a syntax-error token
The pieces that make the dual-algebra design work:
◼
the of builder functions that emit the standard nodes; hand it to any grammar in place of the language's own algebra
◼
◼
project a neutral tree onto -exact nodes, mapping operator descriptors to Wolfram symbols
CodeParser
Every node also carries a span in its metadata - a line-column pair . That comes from a three-part source-position toolkit, also core : is the zero-width primitive that reads the cursor offset, brackets each leaf with two s to record its offset span, and spans the composites over their children and converts every offset to the pair above.
"Source"
CodeParser
{{startLine,startColumn},{endLine,endColumn}}
Wolfram`Parser`
ParsePosition[]
{line,column}
Running over gives a tree that nests by precedence - binds tighter than - and every node carries its source span:
*
+
In[1]:=
 | CalculatorAST |
Out[1]=
ContainerNode[String,{BinaryNode[+,{LeafNode[Integer,1,Source{{1,1},{1,2}}],BinaryNode[*,{LeafNode[Integer,2,Source{{1,5},{1,6}}],LeafNode[Integer,3,Source{{1,7},{1,8}}]},Source{{1,5},{1,8}}]},Source{{1,1},{1,8}}]},Source{{1,1},{1,8}}]
A leaf spans its own text; a composite spans its children. A multi-line input makes that visible - the addition's span runs from line 1 to line 2:
In[2]:=
| CalculatorAST |
Out[2]=
ContainerNode[String,{BinaryNode[+,{LeafNode[Integer,1,Source{{1,1},{1,2}}],LeafNode[Integer,2,Source{{2,1},{2,2}}]},Source{{1,1},{2,2}}]},Source{{1,1},{2,2}}]
The neutral nodes project onto Wolfram's own shape with , which maps each operator descriptor to a Wolfram symbol ( to ):
"+"
In[3]:=
| ToCodeParser |
 | CalculatorAST |
Out[3]=
CodeParser`ContainerNode[String,{CodeParser`CallNode[CodeParser`LeafNode[Symbol,Plus,],{CodeParser`LeafNode[Integer,1,Source{{1,1},{1,2}}],CodeParser`LeafNode[Integer,2,Source{{1,3},{1,4}}]},Source{{1,1},{1,4}}]},Source{{1,1},{1,4}}]
Languages
Languages
Each language exposes the same pair of entry points - an standard-AST mode and a meaningful run - plus the / algebra pair behind them. The grammar is shared; the two entry points differ only in which algebra they feed it.
XxxAST
XxxGrammar
XxxSemantic
Calculator
Calculator
A four-function calculator with , unary minus, parentheses and bare identifiers, built with the library's so left-nested input stays linear. It stresses operator precedence and associativity.
^
◼
◼
run the same grammar to a number (identifiers stay symbolic)
◼
the grammar, parameterised over an algebra
◼
the algebra that folds to a numeric / symbolic value
JSON
JSON
A complete RFC 8259 reader. Objects and arrays nest through recursion, and the grammar exercises string escapes and the number grammar; only escape-decoding and numeric reading delegate to the kernel.
◼
◼
◼
the grammar, parameterised over an algebra
◼
the algebra that folds to a native Wolfram value
In[4]:=
| JSONImport |
Out[4]=
a{1,True}
Lisp
Lisp
An s-expression reader: atoms, parenthesised lists, the quote reader macro (), and -to-end-of-line comments. The whole language is one self-similar rule, so it leans on recursion and comment-aware whitespace.
'x
;
◼
◼
◼
a read Lisp symbol, kept distinct from a Wolfram (names like or are not Wolfram identifiers)
+
list->vector
◼
the grammar, parameterised over an algebra
◼
the algebra that reads to native Wolfram data
In[5]:=
| LispRead |
Out[5]=
{LispSymbol[+],1,{LispSymbol[max],2,3}}
Lambda calculus
Lambda calculus
The untyped lambda calculus: variables, abstraction ( or the unicode , with sugar for ), and application by juxtaposition. It stresses binders and the application/abstraction precedence split.
\x.body
λx.body
\xy.b
\x.\y.b
◼
◼
the grammar, parameterised over an algebra
◼
the algebra that compiles to native Wolfram closures
is the striking one: a Church numeral applied to and reduces to because the kernel does the substitution:
\f.\x.f(fx)
g
y
g[g[y]]
In[6]:=
| LambdaEval |
Out[6]=
g[g[y]]
Brainfuck
Brainfuck
The eight Brainfuck commands over a byte tape, where every other character is a comment. Tiny lexically, but nests arbitrarily, so it exercises recursion and comment-skipping - and the parser also runs it: each command compiles to a closure, a sequence to their right-composition, a loop to a .
[]
machine->machine
◼
◼
compile to a Wolfram closure, run it on a fresh byte tape, and return the output string
◼
the grammar, parameterised over an algebra
◼
the algebra that compiles to an executable closure
In[7]:=
| BrainfuckRun |
Out[7]=
A
Building your own front-end
Building your own front-end
To add a language, write the grammar builder once - a function whose every semantic action calls into rather than building a concrete value - then define the two algebras it runs over. Model it on : feed it for the standard tree, feed it your own for the meaningful value.
fooGrammar[alg_]
alg[...]
FooSemantic
For recursion, do not point a at a -local symbol; it can be garbage-collected once the builder returns, silently breaking the recursion. Use the recursion-cell helpers instead, which wrap a stable global symbol the way the paclet's own EBNF front-end does:
◼
allocate a recursion cell - a stable symbol for a self- or mutually-recursive production
◼
◼
give a cell its parser
The BuildingLanguageFrontEnds tech note walks through this end to end, including the battle-testing findings - how auto-splats a list-valued result, why a recursion target should be a of concrete alternatives rather than a nullable-prefixed production, and how / / thread source spans onto the standard nodes.
 |
|
""