More parser theory [entries|reading|network|archive]
simont

[ userinfo | dreamwidth userinfo ]
[ archive | journal archive ]

Wed 2017-03-29 08:59
More parser theory

I had a conversation recently about low-priority prefix operators in infix expression grammars, which left me mildly uncertain about what they ought to mean. So here's a quick straw poll.

Suppose I have an expression grammar in which the multiplication operator * and the addition operator + have their usual relative priority (namely, * binds more tightly, i.e. is evaluated first). Then suppose I – perhaps unwisely – introduce a prefix operator, which I'll call PFX for want of a better name, which has intermediate priority between the two, so that

  • PFX a + b behaves like (PFX a) + b, i.e. the PFX is evaluated first
  • PFX a * b behaves like PFX (a * b), i.e. the PFX is evaluated second.
That's simple enough (if unusual). But things get weirder when PFX appears on the right of another operator. Specifically, what would you imagine happens to this expression:
a * PFX b + c
in which you can't process the operators in priority order (* then PFX then +) because the PFX necessarily has to happen before the *.


Poll #18119 BODMASWTFBBQ
Open to: Registered Users, detailed results viewable to: All, participants: 10


In what order should the parser process those operators?

View Answers

PFX then * then + to give (a * (PFX b)) + c
5 (50.0%)

+ then PFX then * to give a * (PFX (b + c))
0 (0.0%)

PFX then + then * to give a * ((PFX b) + c)
0 (0.0%)

None! Report a parse error and demand some disambiguating parentheses.
4 (40.0%)

Low-priority prefix operators misparsed my grandparents, you insensitive clod
1 (10.0%)

LinkReply
[personal profile] bens_dadWed 2017-03-29 10:00
https://groups.google.com/forum/#!topic/scala-sips/ARVf1RLDw9U

We need to define a * PFX b.
Although we know that PFX a * b = PFX(a*b), we don't know that * is commutative (ie a * b = b *a ) so we cannot assume that PFX(a*b)=PFX(b*a)
or that a * PFX b = PFX b * a.

Link Reply to this | Thread
[personal profile] bens_dadWed 2017-03-29 12:10
Re: https://groups.google.com/forum/#!topic/scala-sips/ARVf1RLDw9U

Oops.
Sorry about the URL title.
I was trying to add that https://groups.google.com/forum/#!topic/scala-sips/ARVf1RLDw9U *might* be discussing a similar question, but got stuck trying to copy-n-paste on a tablet (I'm a heavy middle+right mouse button user) and failed to clean up properly when giving up.

Link Reply to this | Parent
[personal profile] hilaritaWed 2017-03-29 16:51

While I thought there was an obviously right answer, I nearly sprained my brain reaching that conclusion.

Link Reply to this
navigation
[ go | Previous Entry | Next Entry ]
[ add | to Memories ]