SPTL grammar: expressions

Now that we've seen how names work in SPTL, we'll take a look at how to build expressions.

We start with a simple declaration: an expr consists of a boolexpr, followed by zero or more sets consisting of a boolop and another boolexpr. But what's a boolexpr? Simple, it's a relexpr followed optionally by a relop and another relexpr. And so on.

Here's the BNF, building all the way to factor, which has several options including (expr), which takes us back to the beginning.

The purpose of this hierarchy is to set precedence rules for the order of evaluation. Due to the nature of a recursive descent parser, items that appear later in this list will be evaluated first.

expr = boolexpr { boolop boolexpr }

boolexpr = relexpr [ relop relexpr ]

boolop = '&&' | '||'

relexpr = [ '-' ] term { addop term }

relop = '<' | '>' | '==' | '<=' | '>=' | '!='

term = factor { multop factor }

addop = '+' | '-'

factor = constant | varname | funcname | '(' expr ')' | negate

multop = '*' | '/' | '%'

negate = '!' factor

constant = boolconstant | numconstant | stringconstant

For example, the expression x + 3 < y * 2 can be parsed like this:

expr
-> boolexpr
-> relexpr relop relexpr
-> term addop term "<" term
-> factor "+" factor "<" factor mulop factor
-> varname "+" constant "<" varname "*" constant
-> "x" "+" 3 "<" "y" "*" "2"

But to really see how this works, we'll need to simulate a tree structure:

      <
   -------
  /       \
  +        \
 ---        *
/   \      ---
x   3     /   \
          y   2

Atrocious ascii drawing, I know. I need to get a graphical graphing tool. If you have any suggestions, let me know in the comments.

Anyway, the y * 2 will be evaluated first, since it is at the lowest level of the tree. Next to be evaluated will be x + 3. In this example, since these are on opposite sides of the < sign, the relative order between them does not matter. In other expressions, it will. Once the values of x + 3 and y * 2 are known, they can be compared with each other. If x + 3 is less than y * 2 the value of the entire expression is true, otherwise the value is false.

What I don't know at this point is how it will work to have boolean, string, and numeric constants in the same expression hierarchy. Somehow, the parser will have to be able to evaluate, for example, true + 3 >= 7, or 10 + "this", and return a sensible answer.

As I build the compiler I'll have to figure out how that will work. Probably the solution is to assign all string and numeric constants a boolean value for boolean expressions, and all string and boolean constants a numeric value for arithmetic expressions. Any variables, since SPTL is a dynamically typed language, must be able to be evaluated as a boolean, number, or string, depending on the context.

We're getting closer to having a working language.