# What algorithm to use to parse expressions in this simple language?

I don't want to include the entirety of my language, but I think the relevant part is:

``````<expr> ::= <logical>
|  <comparison>
|  <constant>
|  <subtraction>
|  <multiplication>
|  <division>

<logical> ::= <expr> "AND" <expr>
|  <expr> "OR" <expr>
|  "NOT" <expr>
|  "(" <expr> ")"

<comparison> ::= <expr> "==" <expr>
|  <expr> "!=" <expr>
|  <expr> "<=" <expr>
|  <expr> ">=" <expr>
|  <expr> "<" <expr>
|  <expr> ">" <expr>
``````

What I'm trying to do is turn some code that looks like:

``````IF @var + 2 == 4 THEN
something will happen
ELSE
something else will happen
ENDIF
``````

And turn it into a Syntax tree. The reason I would like a syntax tree is that this is code that's to be run in an interpreter and may need to be run several times throught the program (and @var may be different values each time). The tricksy part for me so far is that this isn't really an interpreter, the code is actually expressing an interactive story, something like Twine.

I've started writing the parser and all is going well until I hit the point of expressions. I've written a shunting yard algorithm before to produce Reverse Polish Notation, and I believe I've managed to have the shunting yard algorithm to output a syntax tree (by popping and pushing nodes onto the output stack instead of just numbers and operators); but I don't really understand how to incorporate the boolean / logical operators.

Is there an algorithm that can handle both purely math expressions like 1+2 as well as my `AND` and `==` expressions?

Do I need to rethink my syntax above?

• "The tricksy part for me so far is that this isn't really an interpreter, the code is actually expressing an interactive story, something like Twine." What is the relevance of this? – user214290 Jul 6 '18 at 11:45
• I'm not sure exactly where you're having trouble, but I would guess that the structure of the grammar is getting in your way. Most resources on parsing and grammars have an example grammar for expressions (e.g. math-cs.gordon.edu/courses/cps222/examples-2015/Recursion/…) Have you considered building off that? – user214290 Jul 6 '18 at 11:46
• @JETM I thought it might be important. Can I use a shunting yard algorithm to parse the comparison operators? Like... what's their precedence?.... I think I just realised the answer to my own question... – NeomerArcana Jul 6 '18 at 12:17
• The logical operators are generally just low-precedence operators, so it should be possible to integrate them nicely into your operator precedence parser (such as the shunting-yard algorithm). Just take care to properly sort out the precedence of all operators first. However, you might want to consider using an existing parser generator with support for expression parsing, e.g. any LALR parser generator. – amon Jul 6 '18 at 12:31
• Is "use an existing parser generator/library" an acceptable 'algorithm'? – whatsisname Jul 6 '18 at 15:02

As it stands, the grammar you've specified is an ambiguous grammar. i.e. something like

``````a AND b OR c
``````

could have two parse trees, depending on how you parenthesize.

The role of Shunting-yard algorithm is to remove this ambiguity. If you specify operator precedence, it gives you a unique parenthesization for your expression. So yes, while it does give you an AST for your expression, it's not really meant for parsing.

Why I say this is because if you have a proper parse tree, then every node would have an associated nonterminal (i.e. `<logical>`, `<comparison>`, etc). Whereas Shunting-yard, in essence, treats each expression to be of the same kind.

So if you were to use it, it would recognize this grammar:

``````<expr> ::= <expr> "AND" <expr>
|  <expr> "OR" <expr>
|  "NOT" <expr>
|  <expr> "==" <expr>
|  <expr> "!=" <expr>
|  <expr> "<=" <expr>
|  <expr> ">=" <expr>
|  <expr> "<" <expr>
|  <expr> ">" <expr>
|  "(" <expr> ")"
|  <constant>
|  <subtraction>
|  <multiplication>
|  <division>
``````

But the thing is, you don't make a distinction between expression that evaluate to a numeric value vs expressions which evaluate to a boolean value in your productions. Yet, you're using different nonterminals for logical expressions and other expressions.

That is to say, your grammar – in its current form – accepts `( 1 + 2 ) AND @x`, and `( 1 == 2) >= 3` as valid.

So you might as well define your grammar to be the above grammar. And then you can incorporate it into Shunting-yard algorithm as suggested by amon in comments - by assigning precedence to the logical and relational operators.

You could use C++ Operator Precedence as a reference when assigning precedence to your logical and relational operators.

• How would I make a distinction in my grammar between numeric and boolean? – NeomerArcana Jul 7 '18 at 4:45
• And why would it be a problem for parsing, I'm afraid I don't understand the problem that if it gives me an AST, how is that not meant for parsing? – NeomerArcana Jul 7 '18 at 4:55
• @NeomerArcana it gives you an AST when you have expressions involving binary and unary operators, but it doesn't give you an AST on any arbitrary grammar which you specify, which is why I wrote that it is not "meant for parsing" – Peeyush Kushwaha Jul 7 '18 at 11:29
• @NeomerArcana if you want to make a distinction between numeric and boolean expressions in your grammar, you'd write rules like `<bool_expr> ::= <num_expr> "<=" <num_expr>` to disallow `<=` in boolean expressions, `<bool_expr> ::= <bool_expr> "OR" <bool_expr>` to disallow using OR with numeric expressions, and `<num_expr> ::= <num_expr> "+" <num_expr>` to disallow + from being used with booleans, etc. – Peeyush Kushwaha Jul 7 '18 at 11:36