Building a Die-Roll Parser with C# and Irony

9 09 2015

Introduction

As part of a recent project to build a system for online, play-by-post RPGs, I have been working on a system to handle rolling various amounts and types of dice. The rolling itself is relatively simple, as I’m just using the built in Random class. However, I also needed the system to pull the details of what to roll from a string provided by the user. Moreover, the user could optionally employ a variety of basic mathematical operations.

To do this I needed to develop a lexer/parser that could handle basic math as well as a custom operator, D, to signify rolling dice. The D operator would take the first operand as the number of dice and the second as the number of sides on each die.

A few examples:

  1D6         →  1-6
  2D7         →  2-14
  5+1D6       →  6-11
  (1+2)D(3*4) →  3D12 
                →  3-36

Installing Irony via NuGet

While I could have built the lexer/parser from scratch, I figured I would save some time by not reinventing the wheel. I settled on the excellent Irony library to build my “language” with. The Irony library is available through Microsoft’s NuGet package manager so I installed it using the tools built into my IDE (Visual Studio 2015). You can do this by executing the following command in the NuGet Package Manager console.

PM> Install-Package Irony

Building the Language Grammar

Note: This is an incredibly “dumbed down” overview of the incredibly complex area of language definition; for more details I suggest reading up on BNF, or Backus-Naur Form.

Irony makes setting up the grammar for a language quite easy. The elements that make up the language are split into two categories, terminals and non-terminals. These pieces are used to break the expression into a tree structure. Terminals are the pieces which can be found at the ends of branches, while everything else is non-terminal.

For example, 1 + 2 – 3 * 4 / 5 becomes:

       -
   +       /
  1 2    5   *
            3 4

As you can see from the above example, the only terminal we have is constant numerical values. Setting up number literals is particularly easy in Irony:

public class ExpressionGrammar : Grammar {
    public ExpressionGrammar() : base(caseSensitive: false) {
        var number = new NumberLiteral("number");
        number.DefaultIntTypes = new TypeCode[] { TypeCode.Int32 };
        number.Options = NumberOptions.AllowSign | NumberOptions.AllowLetterAfter;

        var rollOperatorTerminal = ToTerm("d");
        rollOperatorTerminal.AllowAlphaAfterKeyword = true;

Here I tell Irony we have a number literal, I want to call it “number,” it will be internally represented as a 32 bit integer value and can have preceding sign and be followed by a letter. The following letter becomes important later, when we implement the die roll operator. the roll operator terminal is just used later for the roll operator so it can figure out where to break things apart.

We have rather more non-terminals. The top level is an expression, which is either a term, binary expression, or roll expression. A term is either a number literal or a parenthetical epression. Binary, roll, and parenthetical expressions are all exactly what they sound like.

        var expression = new NonTerminal("Expression");
        var term = new NonTerminal("Term");
        var parentheticalExpression = 
            new NonTerminal("ParentheticalExpression");
        var binaryExpression =
            new NonTerminal("BinaryExpression", typeof(BinaryOperationNode));
        var binaryOperator = new NonTerminal("BinaryOperator", "operator");
        var rollExpression =
            new NonTerminal("RollExpression", typeof(RollOperationNode));
        var rollOperator = new NonTerminal("RollOperator", "operator");

You may have noticed that the binary and roll expressions have a type specified. This type is used to evaluate those nodes in the tree when we get to that portion of the process.

Once we’ve defined what all the non-terminals are we need to define what they look like. We do this using the | and + operators, which have been overloaded by Irony to simplify this process. The | operator is used for OR, as in either of the terms provided can be matched, while the + operator is used for concatination, as in the first term followed by the second matches.

        expression.Rule = term | binaryExpression | rollExpression;
        term.Rule = number | parentheticalExpression;
        parentheticalExpression.Rule = "(" + expression + ")";
        binaryExpression.Rule = expression + binaryOperator + expression;
        binaryOperator.Rule = ToTerm("+") | "-" | "*" | "/";
        rollExpression.Rule = expression + rollOperator + expression;
        rollOperator.Rule = rollOperatorTerminal;
    
        Root = expression;

The first block of code here sets the pattern matching for each non-terminal. The last line tells the system what the root term should be when the abstract syntax tree (AST) is built. Normally you have multiple expressions/commands in a language, but I only need to handle one expression at a time.

Next we need to do some cleanup. I start by setting the order of operations. For the most part this is the same as basic arithmetic. However I also have a new operator for rolling. For this I decided to give it the highest precedent. 3D6 * 2 usually means roll 3, six-sided dice, and multiply the total by 2, not roll three, twelve-sided dice.

        RegisterOperators(1, "+", "-");
        RegisterOperators(2, "*", "/");
        RegisterOperators(3, "d");

Finally, there are some characters which need to be treated in a unique way. In particular, parenthesis are punctuation, and need to match up. (1+2)-(3 shouldn’t work. Also, when we build the tree we don’t need all the nodes. The nodes we can skip are called “transient.” This is not strictly necessary, but it makes navigating the tree easier when a branch is just the operator with the values as children, rather than the expression with the operator as a child, which in turn has several term nodes with the actual values even deeper in the tree. I also enable AST generation here.

        MarkPunctuation("(", ")");
        RegisterBracePair("(", ")");
        MarkTransient(term, expression, binaryOperator, parentheticalExpression, rollOperator);

        LanguageFlags = LanguageFlags.CreateAst;
    }
}

Building the Custom AST Node

In the previous section we told the system to use a custom AST node class for evaluating the roll operator. The class we need to provide here has to be based on the AstNode class, and override a few methods therein. First, we need an empty constructor, and an initialization method.

public class RollOperationNode : AstNode {
    public AstNode Left, Right;
    public int LastRoll;

    public RollOperationNode() { }
    
    public override void Init(AstContext context, ParseTreeNode treeNode) { 
        base.Init(context, treeNode);
        var nodes = treeNode.GetMappedChildNodes();
        Left = AddChild("Arg", nodes[0]);
        Right = AddChild("Arg", nodes[2]);
        var operatorToken = nodes[1].FindToken();
        ErrorAnchor = operatorToken.Location;
    }

This is mostly boilerplate code. We trigger the base init first, then pull in the node data. We store the children for later evaluation, and find the operator so that, in the event of an error, the parser can tell the user where the problem originated.

Next we need to tell the system how to evaluate these rolls. This is a relatively simple process, as I have factored the actual rolling logic into a utility class we can take a look at later. First I evaluate the child nodes (can’t roll the dice until I know how many and what kind to roll). Next I get the random result, store it in case I need it later, and return the result. The thread changes are for Irony.

    protected override object DoEvaluate(ScriptThread thread) {
        thread.CurrentNode = this;
        var leftValue = (int)Left.Evaluate(thread);
        var rightValue = (int)Right.Evaluate(thread);
        var result = new Dice().Roll(leftValue, rightValue);
        thread.CurrentNode = Parent;
        LastRoll = result;
        return result;
    }
}

Building the Utility Classes

Finally, we need a few utility classes to fill in some blanks and make using the parser a bit easier. We will start with the Dice class I just used in the operator evaluation logic. It is definitely not good practice to be initializing the Random instance each time, and there are far better alternatives, but this will suffice for testing.

public class Dice {
    private Random random;

    public Dice() {
        random = new Random();
    }

    public int Roll(int numberOfDice, int sidesPerDie) {
        int total = 0;
        for(int i=0; i<numberOfDice; ++i) {
            total += random.Next(1, sidesPerDie + 1);
        }
        return total;
    }
}

Pretty simple. We need to add a couple easy methods to the grammar class as well. First we need to override the BuildAst method so that the tree will build properly, and spit out errors if it fails. Obviously it would be better here to spit out more useful errors, but it will work for now. We also add a method to retrieve the runtime, which lets us shorten the next bit of code.

    public override void BuildAst(LanguageData language, ParseTree parseTree) {
        var opHandler = new OperatorHandler(language.Grammar.CaseSensitive);
        Util.Check(!parseTree.HasErrors(), "ParseTree has errors, cannot build AST.");
        var astContext = new InterpreterAstContext(language, opHandler);
        var astBuilder = new AstBuilder(astContext);
        astBuilder.BuildAst(parseTree);
    }

    public LanguageRuntime CreateRuntime(LanguageData language) {
        return new LanguageRuntime(language);
    }

Finally we need a class to help with triggering the roll. This is again mostly boilerplate code, so we don’t want to be re-typing it every time we evaluate an expression.

public class RollHelper {
    public void Roll(string expression) {
        var grammar = new ExpressionGrammar();
        LanguageData language = new LanguageData(grammar);
        Parser parser = new Parser(language);
        ParseTree parseTree = parser.Parse(expression);

        grammar.BuildAst(language, parseTree);
        ParseTreeNode root = parseTree.Root;
        var astNode = root.AstNode as AstNode;

        var runtime = grammar.CreateRuntime(language);
        var scriptApp = new ScriptApp(runtime);
        var thread = new ScriptThread(scriptApp);
        var value = astNode.Evaluate(thread);
    }
}

Summary

With all this we should be able to evaluate the expressions I used as examples at the beginning of this post. I hope to later expand this system to allow for basic variable evaluation so users could embed character stats, weapon/armor specs and so on into their rolls, but that will be a challenge for another time.

Advertisements




Shadowrun Dice Roller

5 04 2012

Continuing my adventures in Shadowrun-related Python programming: been working with a couple friends to develop a set of tools for rolling checks, tests and so on for a table-top Shadowrun game.  Nothing exciting yet – Daniel wrote almost all the code for the checks, all I’ve done is make a slightly nicer command-line interface for it.  But when I get the spare time I’m going to look into implementing the SOML files, so that character data can be read in, examined, and used to make rolls.





Disgaea Geosolver, not so useful…

25 09 2009

Dang, I thought about it a bit more and realized you can solve them by simply putting all the blocks except the void on on one color, putting the void on another color, then destroying a block of the same color as the tile you put the void one on… guess that idea’s gone… maybe I’ll try making a Sudoku solver or something…





Disgaea Geosolver

25 09 2009

I recently started playing Disgaea: Afternoon of Darkness, and found myself taking every possible chance to solve the geo-panel puzzles presented in many of the levels. Unfortunately, I also find myself making mistakes regularly, and despite the simplicity of the puzzles, my memory (or lack thereof) makes it difficult for me to plan out the entire thing before actually doing it.

To help with this, I’ve developed a program that will solve the puzzles Read the rest of this entry »