# Parsing expressions pt. 1

Programs that handle role playing game dice rolls are often unsophisticated.
They usually only handle the form `XdY+Z`

where `X`

, `Y`

, and `Z`

are integers.
In this article I will lead up to a calculator that rolls dice inside simple mathematic expressions such as `2d(1d6*2)/3+1`

.
Being able to do this is often useful for things like the weakened status in D&D 4e, where all attacks do half damage.

It’s a bit difficult to jump straight to a grammar with operators like `+`

or `*`

that have the arguments to the operation on
the left and right, so I’ll start with an s-expression version of the calculator.
An s-expressions version of the above dice expression is

`(+ (/ (d 2 (* (d 1 6) 2)) 3) 1)`

.

Here are a few more examples: `(+ 1 1)`

, `(d 1 20)`

, `(+ 10 (* 10 0))`

, `6`

.

As you can see, the expression is a set of composed functions of the form `(operator value value)`

where value is either a number or another function. So here’s what we can say about our language:

- An
`expression`

is either a number or of the form`(operator expression expression ... expression)`

- An
`operator`

is`+`

,`-`

,`*`

,`/`

, or`d`

- A
`number`

is one or more consecutive digits.

This defines the language we’ve created. `(+ 19 (* 2 4))`

clearly fits the rules. Starting with the rule for expression, we can keep applying the rules until we’ve transformed it until our mathematical expression emerges:

`(operator expression expression)`

`(+ number (operator expression expression))`

`(+ 19 (* number number))`

`(+ 19 (* 2 4))`

As a counter-example, `(+ (1+2) 20)`

doesn’t fit:

`(operator expression expression)`

`(+ expression number)`

`(+ expression 20)`

`(+ (operator expression expression) 20)`

`(+ (operator number number) 20)`

`(+ (operator number 2) 20)`

- …

The expansion can’t go further because operator can’t turn into 2 due to our second rule, and number cannot turn into `+`

because of our third rule.

To evaluate expressions in this form, just apply the operator to the two argument numbers. If one of the arguments is a function instead of a number, evaluate that function and use the number result. Here’s a step by step example of an expression being evaluated:

`(+ (/ (d 2 (* (d 1 6) 2)) 3) 1)`

*Here I rolled a six-sided die and got 5*`(+ (/ (d 2 (* 5 2)) 3) 1)`

`(+ (/ (d 2 10) 3) 1)`

*Here I rolled two 10-sided dice and got a total of 12*`(+ (/ 12 3) 1)`

`(+ 4 1)`

`5`

In my next blog post, we’ll build the parser in python.