More parser theory
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?

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%)

 Wed 2017-03-29 10:00

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.

 Wed 2017-03-29 12:10