Suggested RegExp Improvements
On Nov 12, 2010, at 2:52 PM, Marc Harter wrote:
After considering all the breadth this discussion could take maybe it would be wise to just focus on one issue at a time. For me, the biggest missing feature is lookbehind. Its common to most languages implementing the Perl-RegExp-syntax, it is very useful when looking for patterns that follow or don't follow a particular pattern. I guess I'm confused why lookahead made it in but not lookbehind.
This was 1998, Netscape 4 work I did in '97 was based on Perl 4(!), but we proposed to ECMA TC39 TG1 (the JS group -- things were different then, including capitalization) something based on Perl 5. We didn't get everything, and we had to rationalize some obvious quirks.
I don't remember lookbehind (which emerged in Perl 5.005 in July '98) being left out on purpose. Waldemar may recall more, I'd handed him the JS keys inside netscape.com to go do mozilla.org.
If you are game to write a proposal or mini-spec (in the style of ES5 even), let me know. I'll chat with other TC39'ers next week about this.
On 11/12/10 15:04, Brendan Eich wrote:
On Nov 12, 2010, at 2:52 PM, Marc Harter wrote:
After considering all the breadth this discussion could take maybe it would be wise to just focus on one issue at a time. For me, the biggest missing feature is lookbehind. Its common to most languages implementing the Perl-RegExp-syntax, it is very useful when looking for patterns that follow or don't follow a particular pattern. I guess I'm confused why lookahead made it in but not lookbehind.
This was 1998, Netscape 4 work I did in '97 was based on Perl 4(!), but we proposed to ECMA TC39 TG1 (the JS group -- things were different then, including capitalization) something based on Perl 5. We didn't get everything, and we had to rationalize some obvious quirks.
I don't remember lookbehind (which emerged in Perl 5.005 in July '98) being left out on purpose. Waldemar may recall more, I'd handed him the JS keys inside netscape.com to go do mozilla.org.
If you are game to write a proposal or mini-spec (in the style of ES5 even), let me know. I'll chat with other TC39'ers next week about this.
The ES3 spec was based on what was stable at the time. Perl had been experimenting with other constructs in regexp's, but there was some churn there, and I didn't want to go for features that were still in flux.
WaldemarI would be game to write up a proposal for this. When would you need this by to discuss w/ TC39?
Thanks for your consideration, Marc
Brendan et al.,
I have created a proposal for look-behind provided at this link:
docs.google.com/document/pub?id=1EUHvr1SC72g6OPo5fJjelVESpd4nI0D5NQpF3oUO5UM
I hope it is a format that will be helpful for discussion with TC39. Admittedly, I have never written one of these before so am completely open to any feedback or ways to improve the document from yourself or anyone else on this list.
Marc
Your proposal seems to allow variable length lookbehind. This isn't allowed in perl as far as I know. I just tried the following:
perl -e '"foobarbaz" =~ /a(?<=(ob|bab))/;'
which gives an error on perl5. I think if we are going to allow variable length lookbehind we should first find out why they don't have it in perl. I think the implementation is a little tricky if you want to support the full regexp language in lookbehinds.
Is there an example of a language that supports the full regexp power in lookbehinds so we can look at their experiences with implementing it?
2010/11/15 Marc Harter <wavded at gmail.com>:
On Mon, 2010-11-15 at 14:06 +0100, Erik Corry wrote:
Your proposal seems to allow variable length lookbehind. This isn't allowed in perl as far as I know. I just tried the following:
perl -e '"foobarbaz" =~ /a(?<=(ob|bab))/;'
which gives an error on perl5. I think if we are going to allow variable length lookbehind we should first find out why they don't have it in perl. I think the implementation is a little tricky if you want to support the full regexp language in lookbehinds.
This was not my intention. I am proposing zero-width lookbehind, which would not allow for the case you specified above. I will update the proposal. It is my understanding that lookahead as implemented in ECMAScript also is zero-width and not variable. This is also how Perl has implemented lookbehind.
perldoc.perl.org/perlre.html#Extended-Patterns
Updated Proposal: docs.google.com/document/pub?id=1EUHvr1SC72g6OPo5fJjelVESpd4nI0D5NQpF3oUO5UM
Is there an example of a language that supports the full regexp power in lookbehinds so we can look at their experiences with implementing it?
As far as I know Perl is the de facto standard.
2010/11/15 Marc Harter <wavded at gmail.com>:
On Mon, 2010-11-15 at 14:06 +0100, Erik Corry wrote:
Your proposal seems to allow variable length lookbehind. This isn't allowed in perl as far as I know. I just tried the following:
perl -e '"foobarbaz" =~ /a(?<=(ob|bab))/;'
which gives an error on perl5. I think if we are going to allow variable length lookbehind we should first find out why they don't have it in perl. I think the implementation is a little tricky if you want to support the full regexp language in lookbehinds.
This was not my intention. I am proposing zero-width lookbehind, which would not allow for the case you specified above. I will update the
The issue is not with the number of characters consumed by the assertion. This is indeed zero. The issue is with the width of the text matched by the disjunction inside the brackets. This is not any disjunction, but rather a restricted part of the regexp language that can only match a particular number of characters.
It seems the .Net regexp library is able to handle arbitrary content in a lookbehind. It is almost the only one.
See www.regular-expressions.info/lookaround.html#lookbehind for more details.
We could add this feature to JS. As far as I can work out it presupposes the ability to reverse an arbitrary regexp and run it backwards (stepping back and backtracking forwards). I don't think we should add it accidentally though, and perhaps the proposer should be the first to implement it.
proposal. It is my understanding that lookahead as implemented in ECMAScript also is zero-width and not variable. This is also how Perl has implemented lookbehind.
perldoc.perl.org/perlre.html#Extended-Patterns
Updated Proposal: docs.google.com/document/pub?id=1EUHvr1SC72g6OPo5fJjelVESpd4nI0D5NQpF3oUO5UM
The issue is not that the regexp doesn't match in perl. The issue is that it is not compiled at all.
On Mon, 15 Nov 2010 16:23:13 +0100, Marc Harter <wavded at gmail.com> wrote:
[look-behind allowing variable length body]
This was not my intention. I am proposing zero-width lookbehind, which would not allow for the case you specified above.
The grammar allows it. In ECMAScript it would be: "foobarbaz".match(/a(?<=(ob|bab)?)/ which would match the first "a". Had it been written "foobarbaz".match(/a(?<=(ob|bab)?.)/
I will update the proposal. It is my understanding that lookahead as implemented in ECMAScript also is zero-width and not variable. This is also how Perl has implemented lookbehind.
The look-ahead in ECMAScript has a Disjunction as content, which basically
means
that it can contain any RegExp (including quantified statements and
other lookaheads).
This works fine because the semantics of the disjunction is the same as
any other
disjunction in a RegExp: it's matched forwards from a position in the
input.
Your proposal also uses a Disjunction as body, but it's not specified how
to
evaluate that body so that it ends at the position of the assertion.
Executing a RegExp "backwards" isn't trivial. Well, mostly it is, by
symmetry,
but it's not part of the spec.
The positive look-behind should probably be allowed to contain captures
that are still participating after the assertion succeeds (mirroring the
semantics of
the positive look-ahead).
I believe PCRE allows variable length (but structurally simple)
look-behinds, where
the structure ensures that it doesn't have to do backtracking while
checking them, even
though Perl itself does not [1]. Whether that's a desired property or not
is a different
question (I would actually prefer a full backwards-executed regexp to an
artificial
restriction, but that's mainly ideology :).
[Unterminated statement detected, fixing ...]
On Tue, 16 Nov 2010 13:12:36 +0100, Lasse Reichstein
<reichsteinatwork at gmail.com> wrote:
On Mon, 15 Nov 2010 16:23:13 +0100, Marc Harter <wavded at gmail.com> wrote:
[look-behind allowing variable length body]
This was not my intention. I am proposing zero-width lookbehind, which would not allow for the case you specified above.
The grammar allows it. In ECMAScript it would be: "foobarbaz".match(/a(?<=(ob|bab)?)/ which would match the first "a". Had it been written "foobarbaz".match(/a(?<=(ob|bab)?.)/
... then it would match "a" and capture "ob", assuming semantics symmetric to look-ahead.
2010/11/16 Erik Corry <erik.corry at gmail.com>:
2010/11/15 Marc Harter <wavded at gmail.com>:
On Mon, 2010-11-15 at 14:06 +0100, Erik Corry wrote:
Your proposal seems to allow variable length lookbehind. This isn't allowed in perl as far as I know. I just tried the following:
perl -e '"foobarbaz" =~ /a(?<=(ob|bab))/;'
which gives an error on perl5. I think if we are going to allow variable length lookbehind we should first find out why they don't have it in perl. I think the implementation is a little tricky if you want to support the full regexp language in lookbehinds.
This was not my intention. I am proposing zero-width lookbehind, which would not allow for the case you specified above. I will update the
The issue is not with the number of characters consumed by the assertion. This is indeed zero. The issue is with the width of the text matched by the disjunction inside the brackets. This is not any disjunction, but rather a restricted part of the regexp language that can only match a particular number of characters.
It seems the .Net regexp library is able to handle arbitrary content in a lookbehind. It is almost the only one.
See www.regular-expressions.info/lookaround.html#lookbehind for more details.
We could add this feature to JS. As far as I can work out it presupposes the ability to reverse an arbitrary regexp and run it backwards (stepping back and backtracking forwards). I don't think we should add it accidentally though, and perhaps the proposer should be the first to implement it.
Don't you already have to do that to efficiently handle a regexp that ends at the end of the input (in JS, a non multiline $, or \z in java.util.regex parlance)? If you have the whole input string available in memory, and are trying to figure out whether a lookbehind (?<=x) matches at position p, can't you just test /(?:x)$/ against the prefix of the input of length p.
2010/11/16 Mike Samuel <mikesamuel at gmail.com>:
2010/11/16 Erik Corry <erik.corry at gmail.com>:
2010/11/15 Marc Harter <wavded at gmail.com>:
On Mon, 2010-11-15 at 14:06 +0100, Erik Corry wrote:
Your proposal seems to allow variable length lookbehind. This isn't allowed in perl as far as I know. I just tried the following:
perl -e '"foobarbaz" =~ /a(?<=(ob|bab))/;'
which gives an error on perl5. I think if we are going to allow variable length lookbehind we should first find out why they don't have it in perl. I think the implementation is a little tricky if you want to support the full regexp language in lookbehinds.
This was not my intention. I am proposing zero-width lookbehind, which would not allow for the case you specified above. I will update the
The issue is not with the number of characters consumed by the assertion. This is indeed zero. The issue is with the width of the text matched by the disjunction inside the brackets. This is not any disjunction, but rather a restricted part of the regexp language that can only match a particular number of characters.
It seems the .Net regexp library is able to handle arbitrary content in a lookbehind. It is almost the only one.
See www.regular-expressions.info/lookaround.html#lookbehind for more details.
We could add this feature to JS. As far as I can work out it presupposes the ability to reverse an arbitrary regexp and run it backwards (stepping back and backtracking forwards). I don't think we should add it accidentally though, and perhaps the proposer should be the first to implement it.
Don't you already have to do that to efficiently handle a regexp that ends at the end of the input (in JS, a non multiline $, or \z in java.util.regex parlance)?
V8 doesn't have a general form of that optimization. Do the others?
On Tue, 2010-11-16 at 13:09 +0100, Erik Corry wrote:
2010/11/15 Marc Harter <wavded at gmail.com>:
On Mon, 2010-11-15 at 14:06 +0100, Erik Corry wrote:
Your proposal seems to allow variable length lookbehind. This isn't allowed in perl as far as I know. I just tried the following:
perl -e '"foobarbaz" =~ /a(?<=(ob|bab))/;'
which gives an error on perl5. I think if we are going to allow variable length lookbehind we should first find out why they don't have it in perl. I think the implementation is a little tricky if you want to support the full regexp language in lookbehinds.
This was not my intention. I am proposing zero-width lookbehind, which would not allow for the case you specified above. I will update the
The issue is not with the number of characters consumed by the assertion. This is indeed zero. The issue is with the width of the text matched by the disjunction inside the brackets. This is not any disjunction, but rather a restricted part of the regexp language that can only match a particular number of characters.
Sorry about that. I understand you now.
It seems the .Net regexp library is able to handle arbitrary content in a lookbehind. It is almost the only one.
Yes it appears that way, I wonder how beneficial that really is? I believe keeping the same disjunction we have for lookhead in ECMA-262 would make sense at this point in time but open to pushback.
See www.regular-expressions.info/lookaround.html#lookbehind for more details.
We could add this feature to JS. As far as I can work out it presupposes the ability to reverse an arbitrary regexp and run it backwards (stepping back and backtracking forwards). I don't think we should add it accidentally though, and perhaps the proposer should be the first to implement it.
I can take a stab at writing a more detailed description on how to evaluate the Disjunction as Lasse Reichstein has pointed out (www.mail-archive.com/[email protected]/msg05218.html) but wouldn't mind help if anyone else is interested or resources to implementation specs for Perl lookbehind, I haven't found any yet, just documentation.
After considering all the breadth this discussion could take maybe it would be wise to just focus on one issue at a time. For me, the biggest missing feature is lookbehind. Its common to most languages implementing the Perl-RegExp-syntax, it is very useful when looking for patterns that follow or don't follow a particular pattern. I guess I'm confused why lookahead made it in but not lookbehind. What do people think about including this feature?
Marc