Mathematica (or the Wolfram language) offers an exceptionally easy and straightforward way to generate tools like test generators, parsers, type-checkers, visualizers, and solvers from certain concise grammars. In this paper, we illustrate our methods with syntax-driven travesties (random utterances) and syntax-driven parser generation for an example grammar, F, of algebraic expressions. Elsewhere, we tested our generators on bigger grammars, for instance, the famous game Wff-n-Proof game, with inferencing; and for a small programming language from “Types and Programming Languages” by Benjamin C. Pierce, with type checking.
(Wff-n-Proof is no longer easy to find on the internet, but physical copies abound on shopping sites.)
Overview
Overview
Travesties are syntactically valid but random utterances, useful for testing. We could, for example, easily write a strategy in Python’s hypothesis testing library using methods from this paper ( https://hypothesis.readthedocs.io/en/latest/ ).
Parsers convert utterances (streams of tokens) into trees, imposing the recursive structure of the grammar. A parser generator produces a parser from a grammar. Parser generation is usually considered difficult. Think what it would take you to replicate yacc. However, our yacc-alike is trivialized because of the specific form we require of our grammars.
The grammars we found easy to process are in stripped-down Polish Prefix Form (PPF). In our version of PPF, each non-terminal in the grammar has a unique leading head symbol. Arities of functional forms, i.e., numbers of arguments, are fixed. No punctuation is needed or allowed because a head immediately dictates how many arguments: no curly braces, commas, semicolons, brackets, parentheses, etc. Also no operators, overloads, or precedence tables are needed or allowed.
We speculate that more complicated grammars, say those for C++, Python, or Haskell, can be translated into our PPF by a top-level, traditional parser that treats our PPF as an intermediate syntactical representation, completely internal to the parsing phase of a compiler. We further speculate that it might be worth the effort to transcribe complicated syntaxes into PPF because, stripped of syntactic noise, our PPFs ease the work of downstream language-processing tools like test generators, parsers, type-checkers, visualizers, and solvers.
We do not strive for academic rigor, preferring to illustrate by examples and to invite the reader to join the fun, to extend and apply our methods. We also state, up-front, that any novelty, here, comes from using Mathematica. Our techniques have been known to lisp programmers, for example, for a very long time (See my paper from 1989, “A Scheme for Interactive Graphics,” for example [link below]). The target audience, here, comprises programmers who are accustomed to working much too hard at too low a level of abstraction.
Preliminary Packages
Preliminary Packages
In[]:=
<<Utilities`CleanSlate`
If you like, move the following package onto your Mathematica $Path. The following unevaluatable cell shows where I put it on my system. I include a copy of this package here so anyone can just evaluate this notebook without installing packages. We don’t explain this code, here, we just use it. Close up this chapter so you don’t have to look at all this stuff.
<<"~/Dropbox/MMA/Packages/Jacquard.m"
Jacquard.m
Jacquard.m
Polish Prefix Grammars
Polish Prefix Grammars
Our Polish prefix grammars (PPFs) are of the form [non-terminal] [some-fixed-number-of-arguments]. Such grammars are easy to parse, and it’s easy to automatically generate parsers for such grammars.
Definitions
Definitions
Definitions are in bold-italics.
Let a grammar be a function from non-terminal symbols to productions, each of which is a list as a suit (permutation, ordered, no duplicates) of alternatives. Alternatives are ordered for zipping with travesty-generation probabilities. Logically, alternatives are unordered, i.e., a set rather than a suit.
The productions of a context-free grammar pertain anywhere in an utterance without regard to preceding or following input. Such grammars are the only ones of interest, here.
F, below, is our grammar for algebraic expressions. We assume an algebraic field with addition and multiplication following commutative, distributive, and associative laws. Mathematica automatically enforces these laws when simplifying expressions. Incidentally, Mathematica’s simplifications freely annihilate expressions multiplied by zero without checking for non-zero denominators, so watch out for that!.
In[]:=
ClearAll[F,Expr,FSum,FInt,FVar,FProd,Start];(*for"Field"*)F[Expr]=
;(*"Sum"collideswithabuilt-in.*)F[FSum]={{Plus,Expr,Expr}};(*Dowewantthebuilt-in"Plus"?*)F[FInt]={{RandomInteger}};F[FVar]={(*explicitinversestoavoidanextraterm*){x},{y},{z},{-x},{-y},{-z},{1/x},{1/y},{1/z}(*,makeasmanyasyouwant:e.g.{u},{v},{w},{p},{q},{r},{s},{t}*)};F[FProd]={{Times,Expr,Expr}};F[Start]={{Expr}};
FSum |
FProd |
FVar |
FInt |
In this example, F is a function from the non-terminal symbols Expr, FSum, FInt, FVar, FProd, and Start, each to a list (as a suit) of alternatives.
Each alternative is a list, as a sequence (ordered, duplicates allowed), of terms. The terms in an alternative must match, in both order and form, the terms in utterances.
A term is either a terminal symbol or a non-terminal symbol.
A terminal symbol is a literal — a Symbol, String, or a Number — a bottom-level expression like Plus, 42, 1/x, or -y. A terminal symbol must match exactly a token appearing in the input.
A non-terminal symbol is any term in the grammar that is not a terminal symbol. An example is Expr. A non-terminal symbol recurses back into the grammar. It’s always of Mathematica type Symbol.
A production is a suit of alternatives. The value F[Expr] above, namely {{FSum}, {FProd}, {FVar}, {FInt}}, is a production, and {FSum}, {FProd}, {FVar}, {FInt} are its alternatives. Each of these alternatives is nullary, meaning it consists of a single term. An example of a binary term is {Plus,Expr,Expr} consisting of the terminal symbol Plus and two non-terminal Expr symbols.
An utterance is a list (as a stream) of terminals like {Plus, x, y}, The utterance has the parse tree FSum[Plus,FVar[x],FVar[y]], which is a stand-in, written in our PPF grammar, for the algebraic expression x+y. The parser, which we will generate automatically from the grammar, converts utterances into parse trees. Parse trees exhibit the recursive structure of utterances, a structure imposed by the grammar.
A token is an atomic expression in the source language. Examples include a symbol, e.g., Plus or FSum; a String (we don’t use strings here, but they work just fine); or an FInt enclosing a literal integer.
The start symbol is the special, distinguished name and symbol Start, not available for other uses.
How about a pretty display for F? From the Jacquard library imported in the Preliminaries of this document, gridRules exhibits Symbols in dark blue, Lists in green boxes, lists of lists in doubled green boxes, and String terminals in dark red (we don’t have any strings in this example). This visual notation does not distinguish lists as suits, lists as sets, lists as sequences, or lists as bags. Mathematica Rules have orange boxes on the left and light-yellow boxes on the right.
In[]:=
ClearAll[visGrammar];visGrammar[g_]:=Module[{d=DownValues[g]},Zip[Function[hp,hp[[1,1,1]]]/@Unevaluated/@d,Function[hp,hp[[1,1]]]/@d,Rule]]//
gridRules
;visGrammar[F]Out[]=
|
Fish out the non-terminals from the DownValues of our grammar, F:
In[]:=
ClearAll[nonTerminalsFromGrammar];nonTerminalsFromGrammar[ps_]:=#[[1,1,1]]&/@DownValues[ps](nonTerminalsFromGrammar[F])//InputForm
Out[]//InputForm=
{Expr, FInt, FProd, FSum, FVar, Start}
The terminals in a grammar is the complement of the non-terminals against the set of all symbols, which is the union of all the right-hand sides of the productions.
In[]:=
ClearAll[allSymbols];allSymbols[ps_]:=Union@Flatten[#[[2]]&/@DownValues[ps]]
In our pretty display for allSymbols via Jacquard’s gridExpression, Symbols are in a purple background and numbers are in a light-blue background; gridExpression is a visual version of Mathematica’s built-in FullForm, so it shows the Head List explicitly, whereas gridRules above exhibits lists as colored boxes without the explicit Head List.
In[]:=
allSymbols[F]//gridExpression
Out[]=
| |||||||||
| |||||||||
| |||||||||
| |||||||||
| |||||||||
| |||||||||
| |||||||||
| |||||||||
|
| ||||||||
| |||||||||
| |||||||||
| |||||||||
| |||||||||
| |||||||||
| |||||||||
| |||||||||
|
Mathematica’s built-in InputForm is another way to visualize data.
Out[]//InputForm=
{Expr, FInt, FProd, FSum, FVar, Plus, RandomInteger, Times,
x^(-1), -x, x, y^(-1), -y, y, z^(-1), -z, z}
x^(-1), -x, x, y^(-1), -y, y, z^(-1), -z, z}
Here are the terminals from our example grammar, F, prettified by Mathematica’s automatic typesetting.
Anti-Parsing: Syntax-Driven Travesties
Anti-Parsing: Syntax-Driven Travesties
Inject Probabilities into the Grammar
Inject Probabilities into the Grammar
Transform each alternative (sequence of terms) into a list of Mathematica Rules, one rule for the probability of choosing the alternative in a travesty and another rule for the original alternative itself. Generate the probabilities with a function that maps the alternatives to a zippable list. The orders of the alternatives and of the probabilities are important only for Zip.
The following function assigns equal probabilities to every element of a list. It’s the default. Use something else if you have better estimates of appropriate probabilities for travesty generation (our travesties for Wff-n-Proof, in another document, needed non-default probabilities to generate sufficient variety).
Here is the grammar, F, probabilized:
Choose From Alternatives
Choose From Alternatives
We need a function from probabilized alternatives to a particular choice, given an input die roll.
If there is only one alternative, choose it. Access the key “alternative” in the lookup table by applying the rules via /., ReplaceAll.
If there are many alternatives, pick the first whose cumulative probability is greater than or equal to dieRoll. Track the cumulative probability by decrementing dieRoll by each looked-up probability as we recurse down the alternatives.
generateSentences [ probabilizedGrammar, groundTerm, terminalSymbols, recursionLimit:100 ]
generateSentences [ probabilizedGrammar, groundTerm, terminalSymbols, recursionLimit:100 ]
The ground term is the term to force when the recursion limit is exceeded. The default recursion limit is 100. That’s too big for algebraic expressions, where 30 is ample. But 100 or even 500 is useful in other applications.
debugPrint: helper
debugPrint: helper
It’s debatable whether to have a symbol like debugPrint for Print debugging, or to use Block[{Print=Identity},...] to switch off printing. We opt for the former.
chainExpansion
chainExpansion
This has several branches — rewrite rules. First, clear them all out in case we’ve been messing around elsewhere in the notebook.
Iterate down the terms, randomly choosing a branch to explore.
Case: exhausted the production:
Case: we have a term in the production:
Case: exceeded the recursion limit:
generateSentence [ iP, groundTerm, T, recursionLimit ]
generateSentence [ iP, groundTerm, T, recursionLimit ]
Let' s have a button to generate random sentences. We’ll be much more interesting a little bit below, but unit-test the gadgetry so far. Press this button as many times as you like.
Now we have utterances in the grammar. Let’s parse them and display them.
Data-Driven Parsing
Data-Driven Parsing
Can we write parserFromGrammar, a function that writes a parser from a grammar? Such a thing is analogous to yacc, but our version is gracefully short because it exploits convenient properties of PPF. Implementing a general-purpose parser generator is a large task. Our objective, here, is to show the straightforward principles behind such a task.
Any of our parsers takes a stream of tokens (an utterance) and a tree, then iteratively augments the tree by side effect. We don’t write down the function signature for a parser explicitly; just remember it.
Here is a parserFromGrammar that works on any of our PPF grammars:
First, inspect an example grammar to guide our work:
Next, we need functions to disassemble an utterance into its constituent pieces.
prefix,
suffix,
terminalsFromRule,
nonTerminalHeadFromRule,
arityFromPrefixRule
prefix,
suffix,
terminalsFromRule,
nonTerminalHeadFromRule,
arityFromPrefixRule
suffix,
terminalsFromRule,
nonTerminalHeadFromRule,
arityFromPrefixRule
genParserBody, parserDefFromGrammarRule
genParserBody, parserDefFromGrammarRule
For arity-0 productions:
Recurse for productions with right-hand sides
Accumulate the above overloads of parserTargetSym. For each set of terminals in a rule, write a Mathematica pattern to recognize those Mathematica Alternatives (firstPattern below). The second pattern just picks up the tree-so-far. Mathematica Alternatives are not our alternatives. They are part of Mathematica’s pattern sub-language.
Build a parser up by side-effect into a variable (parserTable, a parameter below) by scanning parserDefFromGrammarRule over all the rules in the grammar:
That’s it for the parser generator! It’s equivalent to a yacc for our massively simplified PPF grammars. It’s small because it doesn’t consider punctuation, operator precedence, and overloads in the object language of the PPF.
Build a parser from our grammar, automatically:
Make a little ad-hoc function to generate random sentences, parse them, and then typeset them in Mathematica.
Here’s an animation that exhibits typeset expressions, their leaf counts, and their parse trees. It keeps track of the biggest expression found so far, for bragging rights.
Here’s the biggest one found so far.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Algebraic expression travesties
by Brian Beckman
Wolfram Community, STAFF PICKS, January 2, 2023
https://community.wolfram.com/groups/-/m/t/3094266
by Brian Beckman
Wolfram Community, STAFF PICKS, January 2, 2023
https://community.wolfram.com/groups/-/m/t/3094266