Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(57)

Issue 9638: More automaton translation (Closed)

Created:
12 years, 1 month ago by Christian Plesner Hansen
Modified:
9 years, 7 months ago
Reviewers:
Lasse Reichstein
CC:
v8-dev
Visibility:
Public.

Description

- Implemented some more translation from asts to automata, including upper/lower bounded repetition, captures, positive and negative forward assertions, etc. - Un-templateified automaton nodes.

Patch Set 1 #

Unified diffs Side-by-side diffs Delta from patch set Stats (+507 lines, -425 lines) Patch
M src/ast.h View 12 chunks +35 lines, -2 lines 2 comments Download
M src/globals.h View 1 chunk +4 lines, -0 lines 0 comments Download
M src/jsregexp.h View 2 chunks +10 lines, -8 lines 1 comment Download
M src/jsregexp.cc View 5 chunks +412 lines, -343 lines 6 comments Download
M src/parser.h View 1 chunk +2 lines, -3 lines 0 comments Download
M src/parser.cc View 2 chunks +15 lines, -13 lines 0 comments Download
M test/cctest/test-regexp.cc View 6 chunks +29 lines, -56 lines 0 comments Download

Messages

Total messages: 3 (0 generated)
Christian Plesner Hansen
I'll attach an example of the output from the graph translation in an email follow-up ...
12 years, 1 month ago (2008-11-06 15:24:58 UTC) #1
Lasse Reichstein
LGTM, with questions. I will need an explanation :) http://codereview.chromium.org/9638/diff/1/2 File src/ast.h (right): http://codereview.chromium.org/9638/diff/1/2#newcode1216 Line ...
12 years, 1 month ago (2008-11-06 16:46:44 UTC) #2
Christian Plesner Hansen
12 years, 1 month ago (2008-11-06 17:34:42 UTC) #3
http://codereview.chromium.org/9638/diff/1/2
File src/ast.h (right):

http://codereview.chromium.org/9638/diff/1/2#newcode1216
Line 1216: virtual RegExpNode* ToNode(RegExpCompiler* compiler,
It used to be but when I wanted to add the on_failure argument it became
unmanageable.

http://codereview.chromium.org/9638/diff/1/4
File src/jsregexp.cc (right):

http://codereview.chromium.org/9638/diff/1/4#newcode1057
Line 1057: //
Good points all -- I'm just adding TODOs for now.

http://codereview.chromium.org/9638/diff/1/4#newcode1061
Line 1061: int reg = needs_counter ? compiler->AllocateRegister() : -1;
Yes.  My idea was to add a few transformations at parse time to turn <x>? into
(?:|<x>) and <x>+ into <x><x>*.

http://codereview.chromium.org/9638/diff/1/4#newcode1121
Line 1121: RegExpNode* proceed = ActionNode::EndSubmatch(on_success);
This is based on a long discussion I had with Erik and we're pretty confident
that this matches the specified semantics though something simpler may also
work.

What sets lookahead apart from other expressions (well, one of the things) is
that you're not allowed to backtrack into lookahead once you've completed it;
it's on page 139 in the spec.  In the positive case (and the negative is the
same in principle) you may use backtracking as part of matching the lookahead
itself, but once you've found a match you have to clear any pending backtracks
that were set up to avoid backtracking back into the lookahead again later. 
That's what a submatch does: basically sets up a "scope" where you can push any
number of backtracks you want but if the need arises you can zap them all in one
go using EscapeSubmatch.

Powered by Google App Engine
This is Rietveld 408576698