eggert [in two different messages]:
I hope this discussion helps to motivate the suggestion at the end of
RE-ASSOC to make the grammar right-associative instead of
left-associative here. If the grammar is right-associative, the
question of interpretation does not arise, since the intuitive
behavior agrees with the formal behavior.
[....]
I see that Andrew Hume writes that RE-ASSOC(1b) [right
associative concatenation] was the intended meaning.
I don't believe Andrew (explanation follows).
It's clear by now that the right answer to RE-ASSOC is either (1a) or
(1b). In other words, subpatterns follow the grammar, but the grammar
might or might not be wrong about the associativity of concatenation.
Hume and eggert, looking at the /(wee|week)..(s*)/ example, declare
(1b) to be "intuitive". They say the grammar must be wrong.
They're wrong.
When people say right-associativity is intuitive, I think that's
because they're looking at just that one example and trying to
simulate a matcher in their heads, starting with the first
parenthesized subexpression. "Ok, /week/ matches, then /night/, then
/s/ -- and that's a longest possible match, so I'm done. Isn't that
intuitive?"
No it isn't intuitive. In effect, that "intuition" is based on the
mental execution of a first-match algorithm -- stopping as soon as a
longest possible match is found. In this case, it's typographically
inviting to start by looking for a match for /(wee|week)/, but that's
a red herring.
Left-to-right maximization of subexpressions practically demands left
associativity.
Suppose that /A/ matches some prefix of S leaving a non-empty suffix
left-over. Suppose that /(B)/ matches that suffix. Then when
matching /A(B)/ against S, /A/ matches just the same in both
expressions. The leftmost subpattern is satisfied with highest
priority. With right associativity, that nice, intuitive property is
lost (as illustrated by examples I gave in an earlier message).
The more I think about it, the less I think this is a purely
theoretical consideration. When developing a long, complex pattern -
it's pretty natural for users to test it out in bits in pieces. In
other words, people will in fact write /A/, then write /(B)/, and then
expect not to be surprised when forming /A(B)/. Right-associativity
will surprise them.
-t
---
How valuable is my contribution? Share your feedback at
Affero:
http://svcs.affero.net/rm.php?r=tomlord
|