Fork me on GitHub
#instaparse
<
2017-07-10
>
mrchance15:07:21

Hi! In Instaparse, how do I specify operator precedence... I tried ordered choice, but it doesn't do what I want. Simple example:

(def tp (insta/parser "
s = expression
<expression> = binop / integer
integer = #'[0-9]+'
<binop> = times / plus
times = expression <'*'> expression
plus = expression <'+'> expression"
                      :auto-whitespace whitespace))

parser> (tp "5 + 3 * 7")
[:s [:times [:plus [:integer "5"] [:integer "3"]] [:integer "7"]]]
I have seen solutions that distinguish between add-expression and mul-expression, but that doesn't scale very well for more operators

aengelberg15:07:22

Ordered choice only works when considering parses available at a given position, not when ranking this parse here over another parse over there.

aengelberg15:07:19

So in your example, your binop / integer was making it try 5 + 3 before 5

mrchance16:07:34

ah, so I can fix it by making expression unordered? Or what's the best way?

aengelberg16:07:05

I don't think ordered choice is the best tool for "order of operations"... I'll send you another example in a sec

mrchance16:07:03

Thanks, I'll check it out

aengelberg16:07:28

notice how no ordered choice is necessary, because the grammar is structured so that the order of operations follows naturally

mrchance16:07:56

hm, ok, but my impression is that would get unwieldy when there is more operators. I'll give it a try though, I don't have that many ๐Ÿ˜‰

aengelberg16:07:33

perhaps. not sure.

aengelberg16:07:55

Hereโ€™s a potentially more elegant way of expressing it (not sure if this actually works):

expr = add-sub
add-sub = mul-div (('+' | '-') mul-div)*
mul-div = term (('*' | '/') term)*
term = number | <'('> add-sub <')'>

mrchance17:07:44

hmm, wouldn't this disallow top level multiplication terms?

mrchance17:07:47

I am already wishing I had given my own language a lisp syntax ๐Ÿ˜‰

aengelberg19:07:36

@mrchance no, it would end up as [:expr [:add-sub [:mul-div "1" "*" "2"]]]

mrchance23:07:06

right ๐Ÿ™‚ It worked, btw. For the Moment it's still quite manageable too. Thanks for the fast replies!