Imported Upstream version 2011.07.07

9 files changed, 1778 insertions, 206 deletions

diff --git a/src/pkg/exp/regexp/syntax/Makefile b/src/pkg/exp/regexp/syntax/Makefile
index 8e0b4c1e6..97d4ad6ca 100644
--- a/src/pkg/exp/regexp/syntax/Makefile
+++ b/src/pkg/exp/regexp/syntax/Makefile
@@ -6,8 +6,11 @@ include ../../../../Make.inc
 
 TARG=exp/regexp/syntax
 GOFILES=\
+	compile.go\
 	parse.go\
 	perl_groups.go\
+	prog.go\
 	regexp.go\
+	simplify.go\
 
 include ../../../../Make.pkg
diff --git a/src/pkg/exp/regexp/syntax/compile.go b/src/pkg/exp/regexp/syntax/compile.go
new file mode 100644
index 000000000..ec9556fde
--- /dev/null
+++ b/src/pkg/exp/regexp/syntax/compile.go
@@ -0,0 +1,264 @@
+package syntax
+
+import (
+	"os"
+	"unicode"
+)
+
+// A patchList is a list of instruction pointers that need to be filled in (patched).
+// Because the pointers haven't been filled in yet, we can reuse their storage
+// to hold the list.  It's kind of sleazy, but works well in practice.
+// See http://swtch.com/~rsc/regexp/regexp1.html for inspiration.
+// 
+// These aren't really pointers: they're integers, so we can reinterpret them
+// this way without using package unsafe.  A value l denotes
+// p.inst[l>>1].Out (l&1==0) or .Arg (l&1==1). 
+// l == 0 denotes the empty list, okay because we start every program
+// with a fail instruction, so we'll never want to point at its output link.
+type patchList uint32
+
+func (l patchList) next(p *Prog) patchList {
+	i := &p.Inst[l>>1]
+	if l&1 == 0 {
+		return patchList(i.Out)
+	}
+	return patchList(i.Arg)
+}
+
+func (l patchList) patch(p *Prog, val uint32) {
+	for l != 0 {
+		i := &p.Inst[l>>1]
+		if l&1 == 0 {
+			l = patchList(i.Out)
+			i.Out = val
+		} else {
+			l = patchList(i.Arg)
+			i.Arg = val
+		}
+	}
+}
+
+func (l1 patchList) append(p *Prog, l2 patchList) patchList {
+	if l1 == 0 {
+		return l2
+	}
+	if l2 == 0 {
+		return l1
+	}
+
+	last := l1
+	for {
+		next := last.next(p)
+		if next == 0 {
+			break
+		}
+		last = next
+	}
+
+	i := &p.Inst[last>>1]
+	if last&1 == 0 {
+		i.Out = uint32(l2)
+	} else {
+		i.Arg = uint32(l2)
+	}
+	return l1
+}
+
+// A frag represents a compiled program fragment.
+type frag struct {
+	i   uint32    // index of first instruction
+	out patchList // where to record end instruction
+}
+
+type compiler struct {
+	p *Prog
+}
+
+// Compile compiles the regexp into a program to be executed.
+func Compile(re *Regexp) (*Prog, os.Error) {
+	var c compiler
+	c.init()
+	f := c.compile(re)
+	f.out.patch(c.p, c.inst(InstMatch).i)
+	c.p.Start = int(f.i)
+	return c.p, nil
+}
+
+func (c *compiler) init() {
+	c.p = new(Prog)
+	c.inst(InstFail)
+}
+
+var anyRuneNotNL = []int{0, '\n' - 1, '\n' - 1, unicode.MaxRune}
+var anyRune = []int{0, unicode.MaxRune}
+
+func (c *compiler) compile(re *Regexp) frag {
+	switch re.Op {
+	case OpNoMatch:
+		return c.fail()
+	case OpEmptyMatch:
+		return c.nop()
+	case OpLiteral:
+		if len(re.Rune) == 0 {
+			return c.nop()
+		}
+		var f frag
+		for j := range re.Rune {
+			f1 := c.rune(re.Rune[j : j+1])
+			if j == 0 {
+				f = f1
+			} else {
+				f = c.cat(f, f1)
+			}
+		}
+		return f
+	case OpCharClass:
+		return c.rune(re.Rune)
+	case OpAnyCharNotNL:
+		return c.rune(anyRuneNotNL)
+	case OpAnyChar:
+		return c.rune(anyRune)
+	case OpBeginLine:
+		return c.empty(EmptyBeginLine)
+	case OpEndLine:
+		return c.empty(EmptyEndLine)
+	case OpBeginText:
+		return c.empty(EmptyBeginText)
+	case OpEndText:
+		return c.empty(EmptyEndText)
+	case OpWordBoundary:
+		return c.empty(EmptyWordBoundary)
+	case OpNoWordBoundary:
+		return c.empty(EmptyNoWordBoundary)
+	case OpCapture:
+		bra := c.cap(uint32(re.Cap << 1))
+		sub := c.compile(re.Sub[0])
+		ket := c.cap(uint32(re.Cap<<1 | 1))
+		return c.cat(c.cat(bra, sub), ket)
+	case OpStar:
+		return c.star(c.compile(re.Sub[0]), re.Flags&NonGreedy != 0)
+	case OpPlus:
+		return c.plus(c.compile(re.Sub[0]), re.Flags&NonGreedy != 0)
+	case OpQuest:
+		return c.quest(c.compile(re.Sub[0]), re.Flags&NonGreedy != 0)
+	case OpConcat:
+		if len(re.Sub) == 0 {
+			return c.nop()
+		}
+		var f frag
+		for i, sub := range re.Sub {
+			if i == 0 {
+				f = c.compile(sub)
+			} else {
+				f = c.cat(f, c.compile(sub))
+			}
+		}
+		return f
+	case OpAlternate:
+		var f frag
+		for _, sub := range re.Sub {
+			f = c.alt(f, c.compile(sub))
+		}
+		return f
+	}
+	panic("regexp: unhandled case in compile")
+}
+
+func (c *compiler) inst(op InstOp) frag {
+	// TODO: impose length limit
+	f := frag{i: uint32(len(c.p.Inst))}
+	c.p.Inst = append(c.p.Inst, Inst{Op: op})
+	return f
+}
+
+func (c *compiler) nop() frag {
+	f := c.inst(InstNop)
+	f.out = patchList(f.i << 1)
+	return f
+}
+
+func (c *compiler) fail() frag {
+	return frag{}
+}
+
+func (c *compiler) cap(arg uint32) frag {
+	f := c.inst(InstCapture)
+	f.out = patchList(f.i << 1)
+	c.p.Inst[f.i].Arg = arg
+	return f
+}
+
+func (c *compiler) cat(f1, f2 frag) frag {
+	// concat of failure is failure
+	if f1.i == 0 || f2.i == 0 {
+		return frag{}
+	}
+
+	// TODO: elide nop
+
+	f1.out.patch(c.p, f2.i)
+	return frag{f1.i, f2.out}
+}
+
+func (c *compiler) alt(f1, f2 frag) frag {
+	// alt of failure is other
+	if f1.i == 0 {
+		return f2
+	}
+	if f2.i == 0 {
+		return f1
+	}
+
+	f := c.inst(InstAlt)
+	i := &c.p.Inst[f.i]
+	i.Out = f1.i
+	i.Arg = f2.i
+	f.out = f1.out.append(c.p, f2.out)
+	return f
+}
+
+func (c *compiler) quest(f1 frag, nongreedy bool) frag {
+	f := c.inst(InstAlt)
+	i := &c.p.Inst[f.i]
+	if nongreedy {
+		i.Arg = f1.i
+		f.out = patchList(f.i << 1)
+	} else {
+		i.Out = f1.i
+		f.out = patchList(f.i<<1 | 1)
+	}
+	f.out = f.out.append(c.p, f1.out)
+	return f
+}
+
+func (c *compiler) star(f1 frag, nongreedy bool) frag {
+	f := c.inst(InstAlt)
+	i := &c.p.Inst[f.i]
+	if nongreedy {
+		i.Arg = f1.i
+		f.out = patchList(f.i << 1)
+	} else {
+		i.Out = f1.i
+		f.out = patchList(f.i<<1 | 1)
+	}
+	f1.out.patch(c.p, f.i)
+	return f
+}
+
+func (c *compiler) plus(f1 frag, nongreedy bool) frag {
+	return frag{f1.i, c.star(f1, nongreedy).out}
+}
+
+func (c *compiler) empty(op EmptyOp) frag {
+	f := c.inst(InstEmptyWidth)
+	c.p.Inst[f.i].Arg = uint32(op)
+	f.out = patchList(f.i << 1)
+	return f
+}
+
+func (c *compiler) rune(rune []int) frag {
+	f := c.inst(InstRune)
+	c.p.Inst[f.i].Rune = rune
+	f.out = patchList(f.i << 1)
+	return f
+}
diff --git a/src/pkg/exp/regexp/syntax/parse.go b/src/pkg/exp/regexp/syntax/parse.go
index d04f25097..b6c91f7e1 100644
--- a/src/pkg/exp/regexp/syntax/parse.go
+++ b/src/pkg/exp/regexp/syntax/parse.go
@@ -79,28 +79,108 @@ const (
 type parser struct {
 	flags       Flags     // parse mode flags
 	stack       []*Regexp // stack of parsed expressions
-	numCap      int       // number of capturing groups seen
+	free        *Regexp
+	numCap      int // number of capturing groups seen
 	wholeRegexp string
+	tmpClass    []int // temporary char class work space
+}
+
+func (p *parser) newRegexp(op Op) *Regexp {
+	re := p.free
+	if re != nil {
+		p.free = re.Sub0[0]
+		*re = Regexp{}
+	} else {
+		re = new(Regexp)
+	}
+	re.Op = op
+	return re
+}
+
+func (p *parser) reuse(re *Regexp) {
+	re.Sub0[0] = p.free
+	p.free = re
 }
 
 // Parse stack manipulation.
 
 // push pushes the regexp re onto the parse stack and returns the regexp.
 func (p *parser) push(re *Regexp) *Regexp {
-	// TODO: automatic concatenation
-	// TODO: turn character class into literal
-	// TODO: compute simple
+	if re.Op == OpCharClass && len(re.Rune) == 2 && re.Rune[0] == re.Rune[1] {
+		// Single rune.
+		if p.maybeConcat(re.Rune[0], p.flags&^FoldCase) {
+			return nil
+		}
+		re.Op = OpLiteral
+		re.Rune = re.Rune[:1]
+		re.Flags = p.flags &^ FoldCase
+	} else if re.Op == OpCharClass && len(re.Rune) == 4 &&
+		re.Rune[0] == re.Rune[1] && re.Rune[2] == re.Rune[3] &&
+		unicode.SimpleFold(re.Rune[0]) == re.Rune[2] &&
+		unicode.SimpleFold(re.Rune[2]) == re.Rune[0] ||
+		re.Op == OpCharClass && len(re.Rune) == 2 &&
+			re.Rune[0]+1 == re.Rune[1] &&
+			unicode.SimpleFold(re.Rune[0]) == re.Rune[1] &&
+			unicode.SimpleFold(re.Rune[1]) == re.Rune[0] {
+		// Case-insensitive rune like [Aa] or [Δδ].
+		if p.maybeConcat(re.Rune[0], p.flags|FoldCase) {
+			return nil
+		}
+
+		// Rewrite as (case-insensitive) literal.
+		re.Op = OpLiteral
+		re.Rune = re.Rune[:1]
+		re.Flags = p.flags | FoldCase
+	} else {
+		// Incremental concatenation.
+		p.maybeConcat(-1, 0)
+	}
 
 	p.stack = append(p.stack, re)
 	return re
 }
 
-// newLiteral returns a new OpLiteral Regexp with the given flags
-func newLiteral(r int, flags Flags) *Regexp {
-	re := &Regexp{
-		Op:    OpLiteral,
-		Flags: flags,
+// maybeConcat implements incremental concatenation
+// of literal runes into string nodes.  The parser calls this
+// before each push, so only the top fragment of the stack
+// might need processing.  Since this is called before a push,
+// the topmost literal is no longer subject to operators like *
+// (Otherwise ab* would turn into (ab)*.)
+// If r >= 0 and there's a node left over, maybeConcat uses it
+// to push r with the given flags.
+// maybeConcat reports whether r was pushed.
+func (p *parser) maybeConcat(r int, flags Flags) bool {
+	n := len(p.stack)
+	if n < 2 {
+		return false
 	}
+
+	re1 := p.stack[n-1]
+	re2 := p.stack[n-2]
+	if re1.Op != OpLiteral || re2.Op != OpLiteral || re1.Flags&FoldCase != re2.Flags&FoldCase {
+		return false
+	}
+
+	// Push re1 into re2.
+	re2.Rune = append(re2.Rune, re1.Rune...)
+
+	// Reuse re1 if possible.
+	if r >= 0 {
+		re1.Rune = re1.Rune0[:1]
+		re1.Rune[0] = r
+		re1.Flags = flags
+		return true
+	}
+
+	p.stack = p.stack[:n-1]
+	p.reuse(re1)
+	return false // did not push r
+}
+
+// newLiteral returns a new OpLiteral Regexp with the given flags
+func (p *parser) newLiteral(r int, flags Flags) *Regexp {
+	re := p.newRegexp(OpLiteral)
+	re.Flags = flags
 	re.Rune0[0] = r
 	re.Rune = re.Rune0[:1]
 	return re
@@ -108,14 +188,16 @@ func newLiteral(r int, flags Flags) *Regexp {
 
 // literal pushes a literal regexp for the rune r on the stack
 // and returns that regexp.
-func (p *parser) literal(r int) *Regexp {
-	return p.push(newLiteral(r, p.flags))
+func (p *parser) literal(r int) {
+	p.push(p.newLiteral(r, p.flags))
 }
 
 // op pushes a regexp with the given op onto the stack
 // and returns that regexp.
 func (p *parser) op(op Op) *Regexp {
-	return p.push(&Regexp{Op: op, Flags: p.flags})
+	re := p.newRegexp(op)
+	re.Flags = p.flags
+	return p.push(re)
 }
 
 // repeat replaces the top stack element with itself repeated
@@ -139,12 +221,10 @@ func (p *parser) repeat(op Op, min, max int, opstr, t, lastRepeat string) (strin
 		return "", &Error{ErrMissingRepeatArgument, opstr}
 	}
 	sub := p.stack[n-1]
-	re := &Regexp{
-		Op:    op,
-		Min:   min,
-		Max:   max,
-		Flags: flags,
-	}
+	re := p.newRegexp(op)
+	re.Min = min
+	re.Max = max
+	re.Flags = flags
 	re.Sub = re.Sub0[:1]
 	re.Sub[0] = sub
 	p.stack[n-1] = re
@@ -153,60 +233,385 @@ func (p *parser) repeat(op Op, min, max int, opstr, t, lastRepeat string) (strin
 
 // concat replaces the top of the stack (above the topmost '|' or '(') with its concatenation.
 func (p *parser) concat() *Regexp {
-	// TODO: Flatten concats.
+	p.maybeConcat(-1, 0)
 
 	// Scan down to find pseudo-operator | or (.
 	i := len(p.stack)
 	for i > 0 && p.stack[i-1].Op < opPseudo {
 		i--
 	}
-	sub := p.stack[i:]
+	subs := p.stack[i:]
 	p.stack = p.stack[:i]
 
-	var re *Regexp
-	switch len(sub) {
-	case 0:
-		re = &Regexp{Op: OpEmptyMatch}
-	case 1:
-		re = sub[0]
-	default:
-		re = &Regexp{Op: OpConcat}
-		re.Sub = append(re.Sub0[:0], sub...)
+	// Empty concatenation is special case.
+	if len(subs) == 0 {
+		return p.push(p.newRegexp(OpEmptyMatch))
 	}
-	return p.push(re)
+
+	return p.push(p.collapse(subs, OpConcat))
 }
 
 // alternate replaces the top of the stack (above the topmost '(') with its alternation.
 func (p *parser) alternate() *Regexp {
-	// TODO: Flatten alternates.
-
 	// Scan down to find pseudo-operator (.
 	// There are no | above (.
 	i := len(p.stack)
 	for i > 0 && p.stack[i-1].Op < opPseudo {
 		i--
 	}
-	sub := p.stack[i:]
+	subs := p.stack[i:]
 	p.stack = p.stack[:i]
 
-	var re *Regexp
-	switch len(sub) {
-	case 0:
-		re = &Regexp{Op: OpNoMatch}
-	case 1:
-		re = sub[0]
-	default:
-		re = &Regexp{Op: OpAlternate}
-		re.Sub = append(re.Sub0[:0], sub...)
+	// Make sure top class is clean.
+	// All the others already are (see swapVerticalBar).
+	if len(subs) > 0 {
+		cleanAlt(subs[len(subs)-1])
 	}
-	return p.push(re)
+
+	// Empty alternate is special case
+	// (shouldn't happen but easy to handle).
+	if len(subs) == 0 {
+		return p.push(p.newRegexp(OpNoMatch))
+	}
+
+	return p.push(p.collapse(subs, OpAlternate))
 }
 
-func literalRegexp(s string, flags Flags) *Regexp {
-	re := &Regexp{
-		Op:    OpLiteral,
-		Flags: flags,
+// cleanAlt cleans re for eventual inclusion in an alternation.
+func cleanAlt(re *Regexp) {
+	switch re.Op {
+	case OpCharClass:
+		re.Rune = cleanClass(&re.Rune)
+		if len(re.Rune) == 2 && re.Rune[0] == 0 && re.Rune[1] == unicode.MaxRune {
+			re.Rune = nil
+			re.Op = OpAnyChar
+			return
+		}
+		if len(re.Rune) == 4 && re.Rune[0] == 0 && re.Rune[1] == '\n'-1 && re.Rune[2] == '\n'+1 && re.Rune[3] == unicode.MaxRune {
+			re.Rune = nil
+			re.Op = OpAnyCharNotNL
+			return
+		}
+		if cap(re.Rune)-len(re.Rune) > 100 {
+			// re.Rune will not grow any more.
+			// Make a copy or inline to reclaim storage.
+			re.Rune = append(re.Rune0[:0], re.Rune...)
+		}
+	}
+}
+
+// collapse returns the result of applying op to sub.
+// If sub contains op nodes, they all get hoisted up
+// so that there is never a concat of a concat or an
+// alternate of an alternate.
+func (p *parser) collapse(subs []*Regexp, op Op) *Regexp {
+	if len(subs) == 1 {
+		return subs[0]
+	}
+	re := p.newRegexp(op)
+	re.Sub = re.Sub0[:0]
+	for _, sub := range subs {
+		if sub.Op == op {
+			re.Sub = append(re.Sub, sub.Sub...)
+			p.reuse(sub)
+		} else {
+			re.Sub = append(re.Sub, sub)
+		}
+	}
+	if op == OpAlternate {
+		re.Sub = p.factor(re.Sub, re.Flags)
+		if len(re.Sub) == 1 {
+			old := re
+			re = re.Sub[0]
+			p.reuse(old)
+		}
+	}
+	return re
+}
+
+// factor factors common prefixes from the alternation list sub.
+// It returns a replacement list that reuses the same storage and
+// frees (passes to p.reuse) any removed *Regexps.
+//
+// For example,
+//     ABC|ABD|AEF|BCX|BCY
+// simplifies by literal prefix extraction to
+//     A(B(C|D)|EF)|BC(X|Y)
+// which simplifies by character class introduction to
+//     A(B[CD]|EF)|BC[XY]
+//
+func (p *parser) factor(sub []*Regexp, flags Flags) []*Regexp {
+	if len(sub) < 2 {
+		return sub
+	}
+
+	// Round 1: Factor out common literal prefixes.
+	var str []int
+	var strflags Flags
+	start := 0
+	out := sub[:0]
+	for i := 0; i <= len(sub); i++ {
+		// Invariant: the Regexps that were in sub[0:start] have been
+		// used or marked for reuse, and the slice space has been reused
+		// for out (len(out) <= start).
+		//
+		// Invariant: sub[start:i] consists of regexps that all begin
+		// with str as modified by strflags.
+		var istr []int
+		var iflags Flags
+		if i < len(sub) {
+			istr, iflags = p.leadingString(sub[i])
+			if iflags == strflags {
+				same := 0
+				for same < len(str) && same < len(istr) && str[same] == istr[same] {
+					same++
+				}
+				if same > 0 {
+					// Matches at least one rune in current range.
+					// Keep going around.
+					str = str[:same]
+					continue
+				}
+			}
+		}
+
+		// Found end of a run with common leading literal string:
+		// sub[start:i] all begin with str[0:len(str)], but sub[i]
+		// does not even begin with str[0].
+		//
+		// Factor out common string and append factored expression to out.
+		if i == start {
+			// Nothing to do - run of length 0.
+		} else if i == start+1 {
+			// Just one: don't bother factoring.
+			out = append(out, sub[start])
+		} else {
+			// Construct factored form: prefix(suffix1|suffix2|...)
+			prefix := p.newRegexp(OpLiteral)
+			prefix.Flags = strflags
+			prefix.Rune = append(prefix.Rune[:0], str...)
+
+			for j := start; j < i; j++ {
+				sub[j] = p.removeLeadingString(sub[j], len(str))
+			}
+			suffix := p.collapse(sub[start:i], OpAlternate) // recurse
+
+			re := p.newRegexp(OpConcat)
+			re.Sub = append(re.Sub[:0], prefix, suffix)
+			out = append(out, re)
+		}
+
+		// Prepare for next iteration.
+		start = i
+		str = istr
+		strflags = iflags
+	}
+	sub = out
+
+	// Round 2: Factor out common complex prefixes,
+	// just the first piece of each concatenation,
+	// whatever it is.  This is good enough a lot of the time.
+	start = 0
+	out = sub[:0]
+	var first *Regexp
+	for i := 0; i <= len(sub); i++ {
+		// Invariant: the Regexps that were in sub[0:start] have been
+		// used or marked for reuse, and the slice space has been reused
+		// for out (len(out) <= start).
+		//
+		// Invariant: sub[start:i] consists of regexps that all begin
+		// with str as modified by strflags.
+		var ifirst *Regexp
+		if i < len(sub) {
+			ifirst = p.leadingRegexp(sub[i])
+			if first != nil && first.Equal(ifirst) {
+				continue
+			}
+		}
+
+		// Found end of a run with common leading regexp:
+		// sub[start:i] all begin with first but sub[i] does not.
+		//
+		// Factor out common regexp and append factored expression to out.
+		if i == start {
+			// Nothing to do - run of length 0.
+		} else if i == start+1 {
+			// Just one: don't bother factoring.
+			out = append(out, sub[start])
+		} else {
+			// Construct factored form: prefix(suffix1|suffix2|...)
+			prefix := first
+
+			for j := start; j < i; j++ {
+				reuse := j != start // prefix came from sub[start] 
+				sub[j] = p.removeLeadingRegexp(sub[j], reuse)
+			}
+			suffix := p.collapse(sub[start:i], OpAlternate) // recurse
+
+			re := p.newRegexp(OpConcat)
+			re.Sub = append(re.Sub[:0], prefix, suffix)
+			out = append(out, re)
+		}
+
+		// Prepare for next iteration.
+		start = i
+		first = ifirst
+	}
+	sub = out
+
+	// Round 3: Collapse runs of single literals into character classes.
+	start = 0
+	out = sub[:0]
+	for i := 0; i <= len(sub); i++ {
+		// Invariant: the Regexps that were in sub[0:start] have been
+		// used or marked for reuse, and the slice space has been reused
+		// for out (len(out) <= start).
+		//
+		// Invariant: sub[start:i] consists of regexps that are either
+		// literal runes or character classes.
+		if i < len(sub) && isCharClass(sub[i]) {
+			continue
+		}
+
+		// sub[i] is not a char or char class;
+		// emit char class for sub[start:i]...
+		if i == start {
+			// Nothing to do - run of length 0.
+		} else if i == start+1 {
+			out = append(out, sub[start])
+		} else {
+			// Make new char class.
+			// Start with most complex regexp in sub[start].
+			max := start
+			for j := start + 1; j < i; j++ {
+				if sub[max].Op < sub[j].Op || sub[max].Op == sub[j].Op && len(sub[max].Rune) < len(sub[j].Rune) {
+					max = j
+				}
+			}
+			sub[start], sub[max] = sub[max], sub[start]
+
+			for j := start + 1; j < i; j++ {
+				mergeCharClass(sub[start], sub[j])
+				p.reuse(sub[j])
+			}
+			cleanAlt(sub[start])
+			out = append(out, sub[start])
+		}
+
+		// ... and then emit sub[i].
+		if i < len(sub) {
+			out = append(out, sub[i])
+		}
+		start = i + 1
+	}
+	sub = out
+
+	// Round 4: Collapse runs of empty matches into a single empty match.
+	start = 0
+	out = sub[:0]
+	for i := range sub {
+		if i+1 < len(sub) && sub[i].Op == OpEmptyMatch && sub[i+1].Op == OpEmptyMatch {
+			continue
+		}
+		out = append(out, sub[i])
+	}
+	sub = out
+
+	return sub
+}
+
+// leadingString returns the leading literal string that re begins with.
+// The string refers to storage in re or its children.
+func (p *parser) leadingString(re *Regexp) ([]int, Flags) {
+	if re.Op == OpConcat && len(re.Sub) > 0 {
+		re = re.Sub[0]
+	}
+	if re.Op != OpLiteral {
+		return nil, 0
+	}
+	return re.Rune, re.Flags & FoldCase
+}
+
+// removeLeadingString removes the first n leading runes
+// from the beginning of re.  It returns the replacement for re.
+func (p *parser) removeLeadingString(re *Regexp, n int) *Regexp {
+	if re.Op == OpConcat && len(re.Sub) > 0 {
+		// Removing a leading string in a concatenation
+		// might simplify the concatenation.
+		sub := re.Sub[0]
+		sub = p.removeLeadingString(sub, n)
+		re.Sub[0] = sub
+		if sub.Op == OpEmptyMatch {
+			p.reuse(sub)
+			switch len(re.Sub) {
+			case 0, 1:
+				// Impossible but handle.
+				re.Op = OpEmptyMatch
+				re.Sub = nil
+			case 2:
+				old := re
+				re = re.Sub[1]
+				p.reuse(old)
+			default:
+				copy(re.Sub, re.Sub[1:])
+				re.Sub = re.Sub[:len(re.Sub)-1]
+			}
+		}
+		return re
 	}
+
+	if re.Op == OpLiteral {
+		re.Rune = re.Rune[:copy(re.Rune, re.Rune[n:])]
+		if len(re.Rune) == 0 {
+			re.Op = OpEmptyMatch
+		}
+	}
+	return re
+}
+
+// leadingRegexp returns the leading regexp that re begins with.
+// The regexp refers to storage in re or its children.
+func (p *parser) leadingRegexp(re *Regexp) *Regexp {
+	if re.Op == OpEmptyMatch {
+		return nil
+	}
+	if re.Op == OpConcat && len(re.Sub) > 0 {
+		sub := re.Sub[0]
+		if sub.Op == OpEmptyMatch {
+			return nil
+		}
+		return sub
+	}
+	return re
+}
+
+// removeLeadingRegexp removes the leading regexp in re.
+// It returns the replacement for re.
+// If reuse is true, it passes the removed regexp (if no longer needed) to p.reuse.
+func (p *parser) removeLeadingRegexp(re *Regexp, reuse bool) *Regexp {
+	if re.Op == OpConcat && len(re.Sub) > 0 {
+		if reuse {
+			p.reuse(re.Sub[0])
+		}
+		re.Sub = re.Sub[:copy(re.Sub, re.Sub[1:])]
+		switch len(re.Sub) {
+		case 0:
+			re.Op = OpEmptyMatch
+			re.Sub = nil
+		case 1:
+			old := re
+			re = re.Sub[0]
+			p.reuse(old)
+		}
+		return re
+	}
+	re.Op = OpEmptyMatch
+	return re
+}
+
+func literalRegexp(s string, flags Flags) *Regexp {
+	re := &Regexp{Op: OpLiteral}
+	re.Flags = flags
 	re.Rune = re.Rune0[:0] // use local storage for small strings
 	for _, c := range s {
 		if len(re.Rune) >= cap(re.Rune) {
@@ -264,7 +669,6 @@ func Parse(s string, flags Flags) (*Regexp, os.Error) {
 			p.op(opLeftParen).Cap = p.numCap
 			t = t[1:]
 		case '|':
-			p.concat()
 			if err = p.parseVerticalBar(); err != nil {
 				return nil, err
 			}
@@ -360,7 +764,8 @@ func Parse(s string, flags Flags) (*Regexp, os.Error) {
 				}
 			}
 
-			re := &Regexp{Op: OpCharClass, Flags: p.flags}
+			re := p.newRegexp(OpCharClass)
+			re.Flags = p.flags
 
 			// Look for Unicode character group like \p{Han}
 			if len(t) >= 2 && (t[1] == 'p' || t[1] == 'P') {
@@ -371,7 +776,6 @@ func Parse(s string, flags Flags) (*Regexp, os.Error) {
 				if r != nil {
 					re.Rune = r
 					t = rest
-					// TODO: Handle FoldCase flag.
 					p.push(re)
 					break BigSwitch
 				}
@@ -381,12 +785,10 @@ func Parse(s string, flags Flags) (*Regexp, os.Error) {
 			if r, rest := p.parsePerlClassEscape(t, re.Rune0[:0]); r != nil {
 				re.Rune = r
 				t = rest
-				// TODO: Handle FoldCase flag.
 				p.push(re)
 				break BigSwitch
 			}
-
-			// TODO: Give re back to parser's pool.
+			p.reuse(re)
 
 			// Ordinary single-character escape.
 			if c, t, err = p.parseEscape(t); err != nil {
@@ -592,6 +994,35 @@ func (p *parser) parseInt(s string) (n int, rest string, ok bool) {
 	return
 }
 
+// can this be represented as a character class?
+// single-rune literal string, char class, ., and .|\n.
+func isCharClass(re *Regexp) bool {
+	return re.Op == OpLiteral && len(re.Rune) == 1 ||
+		re.Op == OpCharClass ||
+		re.Op == OpAnyCharNotNL ||
+		re.Op == OpAnyChar
+}
+
+// does re match r?
+func matchRune(re *Regexp, r int) bool {
+	switch re.Op {
+	case OpLiteral:
+		return len(re.Rune) == 1 && re.Rune[0] == r
+	case OpCharClass:
+		for i := 0; i < len(re.Rune); i += 2 {
+			if re.Rune[i] <= r && r <= re.Rune[i+1] {
+				return true
+			}
+		}
+		return false
+	case OpAnyCharNotNL:
+		return r != '\n'
+	case OpAnyChar:
+		return true
+	}
+	return false
+}
+
 // parseVerticalBar handles a | in the input.
 func (p *parser) parseVerticalBar() os.Error {
 	p.concat()
@@ -607,14 +1038,66 @@ func (p *parser) parseVerticalBar() os.Error {
 	return nil
 }
 
+// mergeCharClass makes dst = dst|src.
+// The caller must ensure that dst.Op >= src.Op,
+// to reduce the amount of copying.
+func mergeCharClass(dst, src *Regexp) {
+	switch dst.Op {
+	case OpAnyChar:
+		// src doesn't add anything.
+	case OpAnyCharNotNL:
+		// src might add \n
+		if matchRune(src, '\n') {
+			dst.Op = OpAnyChar
+		}
+	case OpCharClass:
+		// src is simpler, so either literal or char class
+		if src.Op == OpLiteral {
+			dst.Rune = appendRange(dst.Rune, src.Rune[0], src.Rune[0])
+		} else {
+			dst.Rune = appendClass(dst.Rune, src.Rune)
+		}
+	case OpLiteral:
+		// both literal
+		if src.Rune[0] == dst.Rune[0] {
+			break
+		}
+		dst.Op = OpCharClass
+		dst.Rune = append(dst.Rune, dst.Rune[0])
+		dst.Rune = appendRange(dst.Rune, src.Rune[0], src.Rune[0])
+	}
+}
+
 // If the top of the stack is an element followed by an opVerticalBar
 // swapVerticalBar swaps the two and returns true.
 // Otherwise it returns false.
 func (p *parser) swapVerticalBar() bool {
-	if n := len(p.stack); n >= 2 {
+	// If above and below vertical bar are literal or char class,
+	// can merge into a single char class.
+	n := len(p.stack)
+	if n >= 3 && p.stack[n-2].Op == opVerticalBar && isCharClass(p.stack[n-1]) && isCharClass(p.stack[n-3]) {
+		re1 := p.stack[n-1]
+		re3 := p.stack[n-3]
+		// Make re3 the more complex of the two.
+		if re1.Op > re3.Op {
+			re1, re3 = re3, re1
+			p.stack[n-3] = re3
+		}
+		mergeCharClass(re3, re1)
+		p.reuse(re1)
+		p.stack = p.stack[:n-1]
+		return true
+	}
+
+	if n >= 2 {
 		re1 := p.stack[n-1]
 		re2 := p.stack[n-2]
 		if re2.Op == opVerticalBar {
+			if n >= 3 {
+				// Now out of reach.
+				// Clean opportunistically.
+				cleanAlt(p.stack[n-3])
+			}
 			p.stack[n-2] = re1
 			p.stack[n-1] = re2
 			return true
@@ -729,6 +1212,7 @@ Switch:
 				if r > unicode.MaxRune {
 					break Switch
 				}
+				nhex++
 			}
 			if nhex == 0 {
 				break Switch
@@ -801,12 +1285,7 @@ func (p *parser) parsePerlClassEscape(s string, r []int) (out []int, rest string
 	if g.sign == 0 {
 		return
 	}
-	if g.sign < 0 {
-		r = appendNegatedClass(r, g.class)
-	} else {
-		r = appendClass(r, g.class)
-	}
-	return r, s[2:]
+	return p.appendGroup(r, g), s[2:]
 }
 
 // parseNamedClass parses a leading POSIX named character class like [:alnum:]
@@ -827,23 +1306,40 @@ func (p *parser) parseNamedClass(s string, r []int) (out []int, rest string, err
 	if g.sign == 0 {
 		return nil, "", &Error{ErrInvalidCharRange, name}
 	}
-	if g.sign < 0 {
-		r = appendNegatedClass(r, g.class)
+	return p.appendGroup(r, g), s, nil
+}
+
+func (p *parser) appendGroup(r []int, g charGroup) []int {
+	if p.flags&FoldCase == 0 {
+		if g.sign < 0 {
+			r = appendNegatedClass(r, g.class)
+		} else {
+			r = appendClass(r, g.class)
+		}
 	} else {
-		r = appendClass(r, g.class)
+		tmp := p.tmpClass[:0]
+		tmp = appendFoldedClass(tmp, g.class)
+		p.tmpClass = tmp
+		tmp = cleanClass(&p.tmpClass)
+		if g.sign < 0 {
+			r = appendNegatedClass(r, tmp)
+		} else {
+			r = appendClass(r, tmp)
+		}
 	}
-	return r, s, nil
+	return r
 }
 
-// unicodeTable returns the unicode.RangeTable identified by name.
-func unicodeTable(name string) *unicode.RangeTable {
+// unicodeTable returns the unicode.RangeTable identified by name
+// and the table of additional fold-equivalent code points.
+func unicodeTable(name string) (*unicode.RangeTable, *unicode.RangeTable) {
 	if t := unicode.Categories[name]; t != nil {
-		return t
+		return t, unicode.FoldCategory[name]
 	}
 	if t := unicode.Scripts[name]; t != nil {
-		return t
+		return t, unicode.FoldScript[name]
 	}
-	return nil
+	return nil, nil
 }
 
 // parseUnicodeClass parses a leading Unicode character class like \p{Han}
@@ -891,14 +1387,31 @@ func (p *parser) parseUnicodeClass(s string, r []int) (out []int, rest string, e
 		name = name[1:]
 	}
 
-	tab := unicodeTable(name)
+	tab, fold := unicodeTable(name)
 	if tab == nil {
 		return nil, "", &Error{ErrInvalidCharRange, seq}
 	}
-	if sign > 0 {
-		r = appendTable(r, tab)
+
+	if p.flags&FoldCase == 0 || fold == nil {
+		if sign > 0 {
+			r = appendTable(r, tab)
+		} else {
+			r = appendNegatedTable(r, tab)
+		}
 	} else {
-		r = appendNegatedTable(r, tab)
+		// Merge and clean tab and fold in a temporary buffer.
+		// This is necessary for the negative case and just tidy
+		// for the positive case.
+		tmp := p.tmpClass[:0]
+		tmp = appendTable(tmp, tab)
+		tmp = appendTable(tmp, fold)
+		p.tmpClass = tmp
+		tmp = cleanClass(&p.tmpClass)
+		if sign > 0 {
+			r = appendClass(r, tmp)
+		} else {
+			r = appendNegatedClass(r, tmp)
+		}
 	}
 	return r, t, nil
 }
@@ -907,7 +1420,8 @@ func (p *parser) parseUnicodeClass(s string, r []int) (out []int, rest string, e
 // and pushes it onto the parse stack.
 func (p *parser) parseClass(s string) (rest string, err os.Error) {
 	t := s[1:] // chop [
-	re := &Regexp{Op: OpCharClass, Flags: p.flags}
+	re := p.newRegexp(OpCharClass)
+	re.Flags = p.flags
 	re.Rune = re.Rune0[:0]
 
 	sign := +1
@@ -979,12 +1493,14 @@ func (p *parser) parseClass(s string) (rest string, err os.Error) {
 				return "", &Error{Code: ErrInvalidCharRange, Expr: rng}
 			}
 		}
-		class = appendRange(class, lo, hi)
+		if p.flags&FoldCase == 0 {
+			class = appendRange(class, lo, hi)
+		} else {
+			class = appendFoldedRange(class, lo, hi)
+		}
 	}
 	t = t[1:] // chop ]
 
-	// TODO: Handle FoldCase flag.
-
 	// Use &re.Rune instead of &class to avoid allocation.
 	re.Rune = class
 	class = cleanClass(&re.Rune)
@@ -999,10 +1515,15 @@ func (p *parser) parseClass(s string) (rest string, err os.Error) {
 // cleanClass sorts the ranges (pairs of elements of r),
 // merges them, and eliminates duplicates.
 func cleanClass(rp *[]int) []int {
+
 	// Sort by lo increasing, hi decreasing to break ties.
 	sort.Sort(ranges{rp})
 
 	r := *rp
+	if len(r) < 2 {
+		return r
+	}
+
 	// Merge abutting, overlapping.
 	w := 2 // write index
 	for i := 2; i < len(r); i += 2 {
@@ -1025,23 +1546,71 @@ func cleanClass(rp *[]int) []int {
 
 // appendRange returns the result of appending the range lo-hi to the class r.
 func appendRange(r []int, lo, hi int) []int {
-	// Expand last range if overlaps or abuts.
-	if n := len(r); n > 0 {
-		rlo, rhi := r[n-2], r[n-1]
-		if lo <= rhi+1 && rlo <= hi+1 {
-			if lo < rlo {
-				r[n-2] = lo
-			}
-			if hi > rhi {
-				r[n-1] = hi
+	// Expand last range or next to last range if it overlaps or abuts.
+	// Checking two ranges helps when appending case-folded
+	// alphabets, so that one range can be expanding A-Z and the
+	// other expanding a-z.
+	n := len(r)
+	for i := 2; i <= 4; i += 2 { // twice, using i=2, i=4
+		if n >= i {
+			rlo, rhi := r[n-i], r[n-i+1]
+			if lo <= rhi+1 && rlo <= hi+1 {
+				if lo < rlo {
+					r[n-i] = lo
+				}
+				if hi > rhi {
+					r[n-i+1] = hi
+				}
+				return r
 			}
-			return r
 		}
 	}
 
 	return append(r, lo, hi)
 }
 
+const (
+	// minimum and maximum runes involved in folding.
+	// checked during test.
+	minFold = 0x0041
+	maxFold = 0x1044f
+)
+
+// appendFoldedRange returns the result of appending the range lo-hi
+// and its case folding-equivalent runes to the class r.
+func appendFoldedRange(r []int, lo, hi int) []int {
+	// Optimizations.
+	if lo <= minFold && hi >= maxFold {
+		// Range is full: folding can't add more.
+		return appendRange(r, lo, hi)
+	}
+	if hi < minFold || lo > maxFold {
+		// Range is outside folding possibilities.
+		return appendRange(r, lo, hi)
+	}
+	if lo < minFold {
+		// [lo, minFold-1] needs no folding.
+		r = appendRange(r, lo, minFold-1)
+		lo = minFold
+	}
+	if hi > maxFold {
+		// [maxFold+1, hi] needs no folding.
+		r = appendRange(r, maxFold+1, hi)
+		hi = maxFold
+	}
+
+	// Brute force.  Depend on appendRange to coalesce ranges on the fly.
+	for c := lo; c <= hi; c++ {
+		r = appendRange(r, c, c)
+		f := unicode.SimpleFold(c)
+		for f != c {
+			r = appendRange(r, f, f)
+			f = unicode.SimpleFold(f)
+		}
+	}
+	return r
+}
+
 // appendClass returns the result of appending the class x to the class r.
 // It assume x is clean.
 func appendClass(r []int, x []int) []int {
@@ -1051,6 +1620,14 @@ func appendClass(r []int, x []int) []int {
 	return r
 }
 
+// appendFolded returns the result of appending the case folding of the class x to the class r.
+func appendFoldedClass(r []int, x []int) []int {
+	for i := 0; i < len(x); i += 2 {
+		r = appendFoldedRange(r, x[i], x[i+1])
+	}
+	return r
+}
+
 // appendNegatedClass returns the result of appending the negation of the class x to the class r.
 // It assumes x is clean.
 func appendNegatedClass(r []int, x []int) []int {
@@ -1148,10 +1725,11 @@ func negateClass(r []int) []int {
 		}
 		nextLo = hi + 1
 	}
+	r = r[:w]
 	if nextLo <= unicode.MaxRune {
 		// It's possible for the negation to have one more
 		// range - this one - than the original class, so use append.
-		r = append(r[:w], nextLo, unicode.MaxRune)
+		r = append(r, nextLo, unicode.MaxRune)
 	}
 	return r
 }
diff --git a/src/pkg/exp/regexp/syntax/parse_test.go b/src/pkg/exp/regexp/syntax/parse_test.go
index b52cab1a1..779b9afde 100644
--- a/src/pkg/exp/regexp/syntax/parse_test.go
+++ b/src/pkg/exp/regexp/syntax/parse_test.go
@@ -16,141 +16,152 @@ var parseTests = []struct {
 	Dump   string
 }{
 	// Base cases
-	{"a", "lit{a}"},
-	{"a.", "cat{lit{a}dot{}}"},
-	{"a.b", "cat{lit{a}dot{}lit{b}}"},
-	//	{ "ab", "str{ab}" },
-	{"ab", "cat{lit{a}lit{b}}"},
-	{"a.b.c", "cat{lit{a}dot{}lit{b}dot{}lit{c}}"},
-	//	{ "abc", "str{abc}" },
-	{"abc", "cat{lit{a}lit{b}lit{c}}"},
-	{"a|^", "alt{lit{a}bol{}}"},
-	//	{ "a|b", "cc{0x61-0x62}" },
-	{"a|b", "alt{lit{a}lit{b}}"},
-	{"(a)", "cap{lit{a}}"},
-	{"(a)|b", "alt{cap{lit{a}}lit{b}}"},
-	{"a*", "star{lit{a}}"},
-	{"a+", "plus{lit{a}}"},
-	{"a?", "que{lit{a}}"},
-	{"a{2}", "rep{2,2 lit{a}}"},
-	{"a{2,3}", "rep{2,3 lit{a}}"},
-	{"a{2,}", "rep{2,-1 lit{a}}"},
-	{"a*?", "nstar{lit{a}}"},
-	{"a+?", "nplus{lit{a}}"},
-	{"a??", "nque{lit{a}}"},
-	{"a{2}?", "nrep{2,2 lit{a}}"},
-	{"a{2,3}?", "nrep{2,3 lit{a}}"},
-	{"a{2,}?", "nrep{2,-1 lit{a}}"},
-	{"", "emp{}"},
-	//	{ "|", "emp{}" },  // alt{emp{}emp{}} but got factored
-	{"|", "alt{emp{}emp{}}"},
-	{"|x|", "alt{emp{}lit{x}emp{}}"},
-	{".", "dot{}"},
-	{"^", "bol{}"},
-	{"$", "eol{}"},
-	{"\\|", "lit{|}"},
-	{"\\(", "lit{(}"},
-	{"\\)", "lit{)}"},
-	{"\\*", "lit{*}"},
-	{"\\+", "lit{+}"},
-	{"\\?", "lit{?}"},
-	{"{", "lit{{}"},
-	{"}", "lit{}}"},
-	{"\\.", "lit{.}"},
-	{"\\^", "lit{^}"},
-	{"\\$", "lit{$}"},
-	{"\\\\", "lit{\\}"},
-	{"[ace]", "cc{0x61 0x63 0x65}"},
-	{"[abc]", "cc{0x61-0x63}"},
-	{"[a-z]", "cc{0x61-0x7a}"},
-	//	{ "[a]", "lit{a}" },
-	{"[a]", "cc{0x61}"},
-	{"\\-", "lit{-}"},
-	{"-", "lit{-}"},
-	{"\\_", "lit{_}"},
+	{`a`, `lit{a}`},
+	{`a.`, `cat{lit{a}dot{}}`},
+	{`a.b`, `cat{lit{a}dot{}lit{b}}`},
+	{`ab`, `str{ab}`},
+	{`a.b.c`, `cat{lit{a}dot{}lit{b}dot{}lit{c}}`},
+	{`abc`, `str{abc}`},
+	{`a|^`, `alt{lit{a}bol{}}`},
+	{`a|b`, `cc{0x61-0x62}`},
+	{`(a)`, `cap{lit{a}}`},
+	{`(a)|b`, `alt{cap{lit{a}}lit{b}}`},
+	{`a*`, `star{lit{a}}`},
+	{`a+`, `plus{lit{a}}`},
+	{`a?`, `que{lit{a}}`},
+	{`a{2}`, `rep{2,2 lit{a}}`},
+	{`a{2,3}`, `rep{2,3 lit{a}}`},
+	{`a{2,}`, `rep{2,-1 lit{a}}`},
+	{`a*?`, `nstar{lit{a}}`},
+	{`a+?`, `nplus{lit{a}}`},
+	{`a??`, `nque{lit{a}}`},
+	{`a{2}?`, `nrep{2,2 lit{a}}`},
+	{`a{2,3}?`, `nrep{2,3 lit{a}}`},
+	{`a{2,}?`, `nrep{2,-1 lit{a}}`},
+	{``, `emp{}`},
+	{`|`, `emp{}`}, // alt{emp{}emp{}} but got factored
+	{`|x|`, `alt{emp{}lit{x}emp{}}`},
+	{`.`, `dot{}`},
+	{`^`, `bol{}`},
+	{`$`, `eol{}`},
+	{`\|`, `lit{|}`},
+	{`\(`, `lit{(}`},
+	{`\)`, `lit{)}`},
+	{`\*`, `lit{*}`},
+	{`\+`, `lit{+}`},
+	{`\?`, `lit{?}`},
+	{`{`, `lit{{}`},
+	{`}`, `lit{}}`},
+	{`\.`, `lit{.}`},
+	{`\^`, `lit{^}`},
+	{`\$`, `lit{$}`},
+	{`\\`, `lit{\}`},
+	{`[ace]`, `cc{0x61 0x63 0x65}`},
+	{`[abc]`, `cc{0x61-0x63}`},
+	{`[a-z]`, `cc{0x61-0x7a}`},
+	{`[a]`, `lit{a}`},
+	{`\-`, `lit{-}`},
+	{`-`, `lit{-}`},
+	{`\_`, `lit{_}`},
+	{`abc`, `str{abc}`},
+	{`abc|def`, `alt{str{abc}str{def}}`},
+	{`abc|def|ghi`, `alt{str{abc}str{def}str{ghi}}`},
 
 	// Posix and Perl extensions
-	{"[[:lower:]]", "cc{0x61-0x7a}"},
-	{"[a-z]", "cc{0x61-0x7a}"},
-	{"[^[:lower:]]", "cc{0x0-0x60 0x7b-0x10ffff}"},
-	{"[[:^lower:]]", "cc{0x0-0x60 0x7b-0x10ffff}"},
-	//	{ "(?i)[[:lower:]]", "cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}" },
-	//	{ "(?i)[a-z]", "cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}" },
-	//	{ "(?i)[^[:lower:]]", "cc{0x0-0x40 0x5b-0x60 0x7b-0x17e 0x180-0x2129 0x212b-0x10ffff}" },
-	//	{ "(?i)[[:^lower:]]", "cc{0x0-0x40 0x5b-0x60 0x7b-0x17e 0x180-0x2129 0x212b-0x10ffff}" },
-	{"\\d", "cc{0x30-0x39}"},
-	{"\\D", "cc{0x0-0x2f 0x3a-0x10ffff}"},
-	{"\\s", "cc{0x9-0xa 0xc-0xd 0x20}"},
-	{"\\S", "cc{0x0-0x8 0xb 0xe-0x1f 0x21-0x10ffff}"},
-	{"\\w", "cc{0x30-0x39 0x41-0x5a 0x5f 0x61-0x7a}"},
-	{"\\W", "cc{0x0-0x2f 0x3a-0x40 0x5b-0x5e 0x60 0x7b-0x10ffff}"},
-	//	{ "(?i)\\w", "cc{0x30-0x39 0x41-0x5a 0x5f 0x61-0x7a 0x17f 0x212a}" },
-	//	{ "(?i)\\W", "cc{0x0-0x2f 0x3a-0x40 0x5b-0x5e 0x60 0x7b-0x17e 0x180-0x2129 0x212b-0x10ffff}" },
-	{"[^\\\\]", "cc{0x0-0x5b 0x5d-0x10ffff}"},
-	//	{ "\\C", "byte{}" },
+	{`[[:lower:]]`, `cc{0x61-0x7a}`},
+	{`[a-z]`, `cc{0x61-0x7a}`},
+	{`[^[:lower:]]`, `cc{0x0-0x60 0x7b-0x10ffff}`},
+	{`[[:^lower:]]`, `cc{0x0-0x60 0x7b-0x10ffff}`},
+	{`(?i)[[:lower:]]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
+	{`(?i)[a-z]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
+	{`(?i)[^[:lower:]]`, `cc{0x0-0x40 0x5b-0x60 0x7b-0x17e 0x180-0x2129 0x212b-0x10ffff}`},
+	{`(?i)[[:^lower:]]`, `cc{0x0-0x40 0x5b-0x60 0x7b-0x17e 0x180-0x2129 0x212b-0x10ffff}`},
+	{`\d`, `cc{0x30-0x39}`},
+	{`\D`, `cc{0x0-0x2f 0x3a-0x10ffff}`},
+	{`\s`, `cc{0x9-0xa 0xc-0xd 0x20}`},
+	{`\S`, `cc{0x0-0x8 0xb 0xe-0x1f 0x21-0x10ffff}`},
+	{`\w`, `cc{0x30-0x39 0x41-0x5a 0x5f 0x61-0x7a}`},
+	{`\W`, `cc{0x0-0x2f 0x3a-0x40 0x5b-0x5e 0x60 0x7b-0x10ffff}`},
+	{`(?i)\w`, `cc{0x30-0x39 0x41-0x5a 0x5f 0x61-0x7a 0x17f 0x212a}`},
+	{`(?i)\W`, `cc{0x0-0x2f 0x3a-0x40 0x5b-0x5e 0x60 0x7b-0x17e 0x180-0x2129 0x212b-0x10ffff}`},
+	{`[^\\]`, `cc{0x0-0x5b 0x5d-0x10ffff}`},
+	//	{ `\C`, `byte{}` },  // probably never
 
 	// Unicode, negatives, and a double negative.
-	{"\\p{Braille}", "cc{0x2800-0x28ff}"},
-	{"\\P{Braille}", "cc{0x0-0x27ff 0x2900-0x10ffff}"},
-	{"\\p{^Braille}", "cc{0x0-0x27ff 0x2900-0x10ffff}"},
-	{"\\P{^Braille}", "cc{0x2800-0x28ff}"},
-	{"\\pZ", "cc{0x20 0xa0 0x1680 0x180e 0x2000-0x200a 0x2028-0x2029 0x202f 0x205f 0x3000}"},
-	{"[\\p{Braille}]", "cc{0x2800-0x28ff}"},
-	{"[\\P{Braille}]", "cc{0x0-0x27ff 0x2900-0x10ffff}"},
-	{"[\\p{^Braille}]", "cc{0x0-0x27ff 0x2900-0x10ffff}"},
-	{"[\\P{^Braille}]", "cc{0x2800-0x28ff}"},
-	{"[\\pZ]", "cc{0x20 0xa0 0x1680 0x180e 0x2000-0x200a 0x2028-0x2029 0x202f 0x205f 0x3000}"},
+	{`\p{Braille}`, `cc{0x2800-0x28ff}`},
+	{`\P{Braille}`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
+	{`\p{^Braille}`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
+	{`\P{^Braille}`, `cc{0x2800-0x28ff}`},
+	{`\pZ`, `cc{0x20 0xa0 0x1680 0x180e 0x2000-0x200a 0x2028-0x2029 0x202f 0x205f 0x3000}`},
+	{`[\p{Braille}]`, `cc{0x2800-0x28ff}`},
+	{`[\P{Braille}]`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
+	{`[\p{^Braille}]`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
+	{`[\P{^Braille}]`, `cc{0x2800-0x28ff}`},
+	{`[\pZ]`, `cc{0x20 0xa0 0x1680 0x180e 0x2000-0x200a 0x2028-0x2029 0x202f 0x205f 0x3000}`},
+	{`\p{Lu}`, mkCharClass(unicode.IsUpper)},
+	{`[\p{Lu}]`, mkCharClass(unicode.IsUpper)},
+	{`(?i)[\p{Lu}]`, mkCharClass(isUpperFold)},
+
+	// Hex, octal.
+	{`[\012-\234]\141`, `cat{cc{0xa-0x9c}lit{a}}`},
+	{`[\x{41}-\x7a]\x61`, `cat{cc{0x41-0x7a}lit{a}}`},
 
 	// More interesting regular expressions.
-	//	{ "a{,2}", "str{a{,2}}" },
-	//	{ "\\.\\^\\$\\\\", "str{.^$\\}" },
-	{"[a-zABC]", "cc{0x41-0x43 0x61-0x7a}"},
-	{"[^a]", "cc{0x0-0x60 0x62-0x10ffff}"},
-	{"[\xce\xb1-\xce\xb5\xe2\x98\xba]", "cc{0x3b1-0x3b5 0x263a}"}, // utf-8
-	{"a*{", "cat{star{lit{a}}lit{{}}"},
+	{`a{,2}`, `str{a{,2}}`},
+	{`\.\^\$\\`, `str{.^$\}`},
+	{`[a-zABC]`, `cc{0x41-0x43 0x61-0x7a}`},
+	{`[^a]`, `cc{0x0-0x60 0x62-0x10ffff}`},
+	{`[α-ε☺]`, `cc{0x3b1-0x3b5 0x263a}`}, // utf-8
+	{`a*{`, `cat{star{lit{a}}lit{{}}`},
 
 	// Test precedences
-	//	{ "(?:ab)*", "star{str{ab}}" },
-	//	{ "(ab)*", "star{cap{str{ab}}}" },
-	//	{ "ab|cd", "alt{str{ab}str{cd}}" },
-	//	{ "a(b|c)d", "cat{lit{a}cap{cc{0x62-0x63}}lit{d}}" },
-	{"(?:ab)*", "star{cat{lit{a}lit{b}}}"},
-	{"(ab)*", "star{cap{cat{lit{a}lit{b}}}}"},
-	{"ab|cd", "alt{cat{lit{a}lit{b}}cat{lit{c}lit{d}}}"},
-	{"a(b|c)d", "cat{lit{a}cap{alt{lit{b}lit{c}}}lit{d}}"},
+	{`(?:ab)*`, `star{str{ab}}`},
+	{`(ab)*`, `star{cap{str{ab}}}`},
+	{`ab|cd`, `alt{str{ab}str{cd}}`},
+	{`a(b|c)d`, `cat{lit{a}cap{cc{0x62-0x63}}lit{d}}`},
 
 	// Test flattening.
-	{"(?:a)", "lit{a}"},
-	//	{ "(?:ab)(?:cd)", "str{abcd}" },
-	//	{ "(?:a|b)|(?:c|d)", "cc{0x61-0x64}" },
-	//	{ "a|.", "dot{}" },
-	//	{ ".|a", "dot{}" },
+	{`(?:a)`, `lit{a}`},
+	{`(?:ab)(?:cd)`, `str{abcd}`},
+	{`(?:a+b+)(?:c+d+)`, `cat{plus{lit{a}}plus{lit{b}}plus{lit{c}}plus{lit{d}}}`},
+	{`(?:a+|b+)|(?:c+|d+)`, `alt{plus{lit{a}}plus{lit{b}}plus{lit{c}}plus{lit{d}}}`},
+	{`(?:a|b)|(?:c|d)`, `cc{0x61-0x64}`},
+	{`a|.`, `dot{}`},
+	{`.|a`, `dot{}`},
+	{`(?:[abc]|A|Z|hello|world)`, `alt{cc{0x41 0x5a 0x61-0x63}str{hello}str{world}}`},
+	{`(?:[abc]|A|Z)`, `cc{0x41 0x5a 0x61-0x63}`},
 
 	// Test Perl quoted literals
-	{"\\Q+|*?{[\\E", "str{+|*?{[}"},
-	{"\\Q+\\E+", "plus{lit{+}}"},
-	{"\\Q\\\\E", "lit{\\}"},
-	{"\\Q\\\\\\E", "str{\\\\}"},
+	{`\Q+|*?{[\E`, `str{+|*?{[}`},
+	{`\Q+\E+`, `plus{lit{+}}`},
+	{`\Q\\E`, `lit{\}`},
+	{`\Q\\\E`, `str{\\}`},
 
 	// Test Perl \A and \z
-	{"(?m)^", "bol{}"},
-	{"(?m)$", "eol{}"},
-	{"(?-m)^", "bot{}"},
-	{"(?-m)$", "eot{}"},
-	{"(?m)\\A", "bot{}"},
-	{"(?m)\\z", "eot{\\z}"},
-	{"(?-m)\\A", "bot{}"},
-	{"(?-m)\\z", "eot{\\z}"},
+	{`(?m)^`, `bol{}`},
+	{`(?m)$`, `eol{}`},
+	{`(?-m)^`, `bot{}`},
+	{`(?-m)$`, `eot{}`},
+	{`(?m)\A`, `bot{}`},
+	{`(?m)\z`, `eot{\z}`},
+	{`(?-m)\A`, `bot{}`},
+	{`(?-m)\z`, `eot{\z}`},
 
 	// Test named captures
-	{"(?P<name>a)", "cap{name:lit{a}}"},
+	{`(?P<name>a)`, `cap{name:lit{a}}`},
 
 	// Case-folded literals
-	//	{ "[Aa]", "litfold{a}" },
+	{`[Aa]`, `litfold{A}`},
+	{`[\x{100}\x{101}]`, `litfold{Ā}`},
+	{`[Δδ]`, `litfold{Δ}`},
 
 	// Strings
-	//	{ "abcde", "str{abcde}" },
-	//	{ "[Aa][Bb]cd", "cat{strfold{ab}str{cd}}" },
+	{`abcde`, `str{abcde}`},
+	{`[Aa][Bb]cd`, `cat{strfold{AB}str{cd}}`},
+
+	// Factoring.
+	{`abc|abd|aef|bcx|bcy`, `alt{cat{lit{a}alt{cat{lit{b}cc{0x63-0x64}}str{ef}}}cat{str{bc}cc{0x78-0x79}}}`},
+	{`ax+y|ax+z|ay+w`, `cat{lit{a}alt{cat{plus{lit{x}}cc{0x79-0x7a}}cat{plus{lit{y}}lit{w}}}}`},
 }
 
 const testFlags = MatchNL | PerlX | UnicodeGroups
@@ -223,8 +234,9 @@ func dumpRegexp(b *bytes.Buffer, re *Regexp) {
 			}
 			if re.Flags&FoldCase != 0 {
 				for _, r := range re.Rune {
-					if unicode.ToUpper(r) != r {
+					if unicode.SimpleFold(r) != r {
 						b.WriteString("fold")
+						break
 					}
 				}
 			}
@@ -270,3 +282,69 @@ func dumpRegexp(b *bytes.Buffer, re *Regexp) {
 	}
 	b.WriteByte('}')
 }
+
+func mkCharClass(f func(int) bool) string {
+	re := &Regexp{Op: OpCharClass}
+	lo := -1
+	for i := 0; i <= unicode.MaxRune; i++ {
+		if f(i) {
+			if lo < 0 {
+				lo = i
+			}
+		} else {
+			if lo >= 0 {
+				re.Rune = append(re.Rune, lo, i-1)
+				lo = -1
+			}
+		}
+	}
+	if lo >= 0 {
+		re.Rune = append(re.Rune, lo, unicode.MaxRune)
+	}
+	return dump(re)
+}
+
+func isUpperFold(rune int) bool {
+	if unicode.IsUpper(rune) {
+		return true
+	}
+	c := unicode.SimpleFold(rune)
+	for c != rune {
+		if unicode.IsUpper(c) {
+			return true
+		}
+		c = unicode.SimpleFold(c)
+	}
+	return false
+}
+
+func TestFoldConstants(t *testing.T) {
+	last := -1
+	for i := 0; i <= unicode.MaxRune; i++ {
+		if unicode.SimpleFold(i) == i {
+			continue
+		}
+		if last == -1 && minFold != i {
+			t.Errorf("minFold=%#U should be %#U", minFold, i)
+		}
+		last = i
+	}
+	if maxFold != last {
+		t.Errorf("maxFold=%#U should be %#U", maxFold, last)
+	}
+}
+
+func TestAppendRangeCollapse(t *testing.T) {
+	// AppendRange should collapse each of the new ranges
+	// into the earlier ones (it looks back two ranges), so that
+	// the slice never grows very large.
+	// Note that we are not calling cleanClass.
+	var r []int
+	for i := 'A'; i <= 'Z'; i++ {
+		r = appendRange(r, i, i)
+		r = appendRange(r, i+'a'-'A', i+'a'-'A')
+	}
+	if string(r) != "AZaz" {
+		t.Errorf("appendRange interlaced A-Z a-z = %s, want AZaz", string(r))
+	}
+}
diff --git a/src/pkg/exp/regexp/syntax/prog.go b/src/pkg/exp/regexp/syntax/prog.go
new file mode 100644
index 000000000..6eeb3da0c
--- /dev/null
+++ b/src/pkg/exp/regexp/syntax/prog.go
@@ -0,0 +1,182 @@
+package syntax
+
+import (
+	"bytes"
+	"strconv"
+)
+
+// Compiled program.
+// May not belong in this package, but convenient for now.
+
+// A Prog is a compiled regular expression program.
+type Prog struct {
+	Inst  []Inst
+	Start int // index of start instruction
+}
+
+// An InstOp is an instruction opcode.
+type InstOp uint8
+
+const (
+	InstAlt InstOp = iota
+	InstAltMatch
+	InstCapture
+	InstEmptyWidth
+	InstMatch
+	InstFail
+	InstNop
+	InstRune
+)
+
+// An EmptyOp specifies a kind or mixture of zero-width assertions.
+type EmptyOp uint8
+
+const (
+	EmptyBeginLine EmptyOp = 1 << iota
+	EmptyEndLine
+	EmptyBeginText
+	EmptyEndText
+	EmptyWordBoundary
+	EmptyNoWordBoundary
+)
+
+// An Inst is a single instruction in a regular expression program.
+type Inst struct {
+	Op   InstOp
+	Out  uint32 // all but InstMatch, InstFail
+	Arg  uint32 // InstAlt, InstAltMatch, InstCapture, InstEmptyWidth
+	Rune []int
+}
+
+func (p *Prog) String() string {
+	var b bytes.Buffer
+	dumpProg(&b, p)
+	return b.String()
+}
+
+// MatchRune returns true if the instruction matches (and consumes) r.
+// It should only be called when i.Op == InstRune.
+func (i *Inst) MatchRune(r int) bool {
+	rune := i.Rune
+
+	// Special case: single-rune slice is from literal string, not char class.
+	// TODO: Case folding.
+	if len(rune) == 1 {
+		return r == rune[0]
+	}
+
+	// Peek at the first few pairs.
+	// Should handle ASCII well.
+	for j := 0; j < len(rune) && j <= 8; j += 2 {
+		if r < rune[j] {
+			return false
+		}
+		if r <= rune[j+1] {
+			return true
+		}
+	}
+
+	// Otherwise binary search.
+	lo := 0
+	hi := len(rune) / 2
+	for lo < hi {
+		m := lo + (hi-lo)/2
+		if c := rune[2*m]; c <= r {
+			if r <= rune[2*m+1] {
+				return true
+			}
+			lo = m + 1
+		} else {
+			hi = m
+		}
+	}
+	return false
+}
+
+// As per re2's Prog::IsWordChar. Determines whether rune is an ASCII word char.
+// Since we act on runes, it would be easy to support Unicode here.
+func wordRune(rune int) bool {
+	return rune == '_' ||
+		('A' <= rune && rune <= 'Z') ||
+		('a' <= rune && rune <= 'z') ||
+		('0' <= rune && rune <= '9')
+}
+
+// MatchEmptyWidth returns true if the instruction matches
+// an empty string between the runes before and after.
+// It should only be called when i.Op == InstEmptyWidth.
+func (i *Inst) MatchEmptyWidth(before int, after int) bool {
+	switch EmptyOp(i.Arg) {
+	case EmptyBeginLine:
+		return before == '\n' || before == -1
+	case EmptyEndLine:
+		return after == '\n' || after == -1
+	case EmptyBeginText:
+		return before == -1
+	case EmptyEndText:
+		return after == -1
+	case EmptyWordBoundary:
+		return wordRune(before) != wordRune(after)
+	case EmptyNoWordBoundary:
+		return wordRune(before) == wordRune(after)
+	}
+	panic("unknown empty width arg")
+}
+
+
+func (i *Inst) String() string {
+	var b bytes.Buffer
+	dumpInst(&b, i)
+	return b.String()
+}
+
+func bw(b *bytes.Buffer, args ...string) {
+	for _, s := range args {
+		b.WriteString(s)
+	}
+}
+
+func dumpProg(b *bytes.Buffer, p *Prog) {
+	for j := range p.Inst {
+		i := &p.Inst[j]
+		pc := strconv.Itoa(j)
+		if len(pc) < 3 {
+			b.WriteString("   "[len(pc):])
+		}
+		if j == p.Start {
+			pc += "*"
+		}
+		bw(b, pc, "\t")
+		dumpInst(b, i)
+		bw(b, "\n")
+	}
+}
+
+func u32(i uint32) string {
+	return strconv.Uitoa64(uint64(i))
+}
+
+func dumpInst(b *bytes.Buffer, i *Inst) {
+	switch i.Op {
+	case InstAlt:
+		bw(b, "alt -> ", u32(i.Out), ", ", u32(i.Arg))
+	case InstAltMatch:
+		bw(b, "altmatch -> ", u32(i.Out), ", ", u32(i.Arg))
+	case InstCapture:
+		bw(b, "cap ", u32(i.Arg), " -> ", u32(i.Out))
+	case InstEmptyWidth:
+		bw(b, "empty ", u32(i.Arg), " -> ", u32(i.Out))
+	case InstMatch:
+		bw(b, "match")
+	case InstFail:
+		bw(b, "fail")
+	case InstNop:
+		bw(b, "nop -> ", u32(i.Out))
+	case InstRune:
+		if i.Rune == nil {
+			// shouldn't happen
+			bw(b, "rune <nil>")
+		}
+		bw(b, "rune ", strconv.QuoteToASCII(string(i.Rune)), " -> ", u32(i.Out))
+	}
+}
diff --git a/src/pkg/exp/regexp/syntax/prog_test.go b/src/pkg/exp/regexp/syntax/prog_test.go
new file mode 100644
index 000000000..7be4281c2
--- /dev/null
+++ b/src/pkg/exp/regexp/syntax/prog_test.go
@@ -0,0 +1,91 @@
+package syntax
+
+import (
+	"testing"
+)
+
+var compileTests = []struct {
+	Regexp string
+	Prog   string
+}{
+	{"a", `  0	fail
+  1*	rune "a" -> 2
+  2	match
+`},
+	{"[A-M][n-z]", `  0	fail
+  1*	rune "AM" -> 2
+  2	rune "nz" -> 3
+  3	match
+`},
+	{"", `  0	fail
+  1*	nop -> 2
+  2	match
+`},
+	{"a?", `  0	fail
+  1	rune "a" -> 3
+  2*	alt -> 1, 3
+  3	match
+`},
+	{"a??", `  0	fail
+  1	rune "a" -> 3
+  2*	alt -> 3, 1
+  3	match
+`},
+	{"a+", `  0	fail
+  1*	rune "a" -> 2
+  2	alt -> 1, 3
+  3	match
+`},
+	{"a+?", `  0	fail
+  1*	rune "a" -> 2
+  2	alt -> 3, 1
+  3	match
+`},
+	{"a*", `  0	fail
+  1	rune "a" -> 2
+  2*	alt -> 1, 3
+  3	match
+`},
+	{"a*?", `  0	fail
+  1	rune "a" -> 2
+  2*	alt -> 3, 1
+  3	match
+`},
+	{"a+b+", `  0	fail
+  1*	rune "a" -> 2
+  2	alt -> 1, 3
+  3	rune "b" -> 4
+  4	alt -> 3, 5
+  5	match
+`},
+	{"(a+)(b+)", `  0	fail
+  1*	cap 2 -> 2
+  2	rune "a" -> 3
+  3	alt -> 2, 4
+  4	cap 3 -> 5
+  5	cap 4 -> 6
+  6	rune "b" -> 7
+  7	alt -> 6, 8
+  8	cap 5 -> 9
+  9	match
+`},
+	{"a+|b+", `  0	fail
+  1	rune "a" -> 2
+  2	alt -> 1, 6
+  3	rune "b" -> 4
+  4	alt -> 3, 6
+  5*	alt -> 1, 3
+  6	match
+`},
+}
+
+func TestCompile(t *testing.T) {
+	for _, tt := range compileTests {
+		re, _ := Parse(tt.Regexp, Perl)
+		p, _ := Compile(re)
+		s := p.String()
+		if s != tt.Prog {
+			t.Errorf("compiled %#q:\n--- have\n%s---\n--- want\n%s---", tt.Regexp, s, tt.Prog)
+		}
+	}
+}
diff --git a/src/pkg/exp/regexp/syntax/regexp.go b/src/pkg/exp/regexp/syntax/regexp.go
index a0c465967..00a4addef 100644
--- a/src/pkg/exp/regexp/syntax/regexp.go
+++ b/src/pkg/exp/regexp/syntax/regexp.go
@@ -33,6 +33,8 @@ type Regexp struct {
 type Op uint8
 
 // Operators are listed in precedence order, tightest binding to weakest.
+// Character class operators are listed simplest to most complex
+// (OpLiteral, OpCharClass, OpAnyCharNotNL, OpAnyChar).
 
 const (
 	OpNoMatch        Op = 1 + iota // matches no strings
@@ -58,6 +60,59 @@ const (
 
 const opPseudo Op = 128 // where pseudo-ops start
 
+// Equal returns true if x and y have identical structure.
+func (x *Regexp) Equal(y *Regexp) bool {
+	if x == nil || y == nil {
+		return x == y
+	}
+	if x.Op != y.Op {
+		return false
+	}
+	switch x.Op {
+	case OpEndText:
+		// The parse flags remember whether this is \z or \Z.
+		if x.Flags&WasDollar != y.Flags&WasDollar {
+			return false
+		}
+
+	case OpLiteral, OpCharClass:
+		if len(x.Rune) != len(y.Rune) {
+			return false
+		}
+		for i, r := range x.Rune {
+			if r != y.Rune[i] {
+				return false
+			}
+		}
+
+	case OpAlternate, OpConcat:
+		if len(x.Sub) != len(y.Sub) {
+			return false
+		}
+		for i, sub := range x.Sub {
+			if !sub.Equal(y.Sub[i]) {
+				return false
+			}
+		}
+
+	case OpStar, OpPlus, OpQuest:
+		if x.Flags&NonGreedy != y.Flags&NonGreedy || !x.Sub[0].Equal(y.Sub[0]) {
+			return false
+		}
+
+	case OpRepeat:
+		if x.Flags&NonGreedy != y.Flags&NonGreedy || x.Min != y.Min || x.Max != y.Max || !x.Sub[0].Equal(y.Sub[0]) {
+			return false
+		}
+
+	case OpCapture:
+		if x.Cap != y.Cap || x.Name != y.Name || !x.Sub[0].Equal(y.Sub[0]) {
+			return false
+		}
+	}
+	return true
+}
+
 // writeRegexp writes the Perl syntax for the regular expression re to b.
 func writeRegexp(b *bytes.Buffer, re *Regexp) {
 	switch re.Op {
@@ -68,16 +123,24 @@ func writeRegexp(b *bytes.Buffer, re *Regexp) {
 	case OpEmptyMatch:
 		b.WriteString(`(?:)`)
 	case OpLiteral:
+		if re.Flags&FoldCase != 0 {
+			b.WriteString(`(?i:`)
+		}
 		for _, r := range re.Rune {
 			escape(b, r, false)
 		}
+		if re.Flags&FoldCase != 0 {
+			b.WriteString(`)`)
+		}
 	case OpCharClass:
 		if len(re.Rune)%2 != 0 {
 			b.WriteString(`[invalid char class]`)
 			break
 		}
 		b.WriteRune('[')
-		if len(re.Rune) > 0 && re.Rune[0] == 0 && re.Rune[len(re.Rune)-1] == unicode.MaxRune {
+		if len(re.Rune) == 0 {
+			b.WriteString(`^\x00-\x{10FFFF}`)
+		} else if re.Rune[0] == 0 && re.Rune[len(re.Rune)-1] == unicode.MaxRune {
 			// Contains 0 and MaxRune.  Probably a negated class.
 			// Print the gaps.
 			b.WriteRune('^')
@@ -124,7 +187,9 @@ func writeRegexp(b *bytes.Buffer, re *Regexp) {
 		} else {
 			b.WriteRune('(')
 		}
-		writeRegexp(b, re.Sub[0])
+		if re.Sub[0].Op != OpEmptyMatch {
+			writeRegexp(b, re.Sub[0])
+		}
 		b.WriteRune(')')
 	case OpStar, OpPlus, OpQuest, OpRepeat:
 		if sub := re.Sub[0]; sub.Op > OpCapture {
@@ -203,6 +268,15 @@ func escape(b *bytes.Buffer, r int, force bool) {
 	case '\v':
 		b.WriteString(`\v`)
 	default:
+		if r < 0x100 {
+			b.WriteString(`\x`)
+			s := strconv.Itob(r, 16)
+			if len(s) == 1 {
+				b.WriteRune('0')
+			}
+			b.WriteString(s)
+			break
+		}
 		b.WriteString(`\x{`)
 		b.WriteString(strconv.Itob(r, 16))
 		b.WriteString(`}`)
diff --git a/src/pkg/exp/regexp/syntax/simplify.go b/src/pkg/exp/regexp/syntax/simplify.go
new file mode 100644
index 000000000..72390417b
--- /dev/null
+++ b/src/pkg/exp/regexp/syntax/simplify.go
@@ -0,0 +1,151 @@
+// Copyright 2011 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package syntax
+
+// Simplify returns a regexp equivalent to re but without counted repetitions
+// and with various other simplifications, such as rewriting /(?:a+)+/ to /a+/.
+// The resulting regexp will execute correctly but its string representation
+// will not produce the same parse tree, because capturing parentheses
+// may have been duplicated or removed.  For example, the simplified form
+// for /(x){1,2}/ is /(x)(x)?/ but both parentheses capture as $1.
+// The returned regexp may share structure with or be the original.
+func (re *Regexp) Simplify() *Regexp {
+	if re == nil {
+		return nil
+	}
+	switch re.Op {
+	case OpCapture, OpConcat, OpAlternate:
+		// Simplify children, building new Regexp if children change.
+		nre := re
+		for i, sub := range re.Sub {
+			nsub := sub.Simplify()
+			if nre == re && nsub != sub {
+				// Start a copy.
+				nre = new(Regexp)
+				*nre = *re
+				nre.Rune = nil
+				nre.Sub = append(nre.Sub0[:0], re.Sub[:i]...)
+			}
+			if nre != re {
+				nre.Sub = append(nre.Sub, nsub)
+			}
+		}
+		return nre
+
+	case OpStar, OpPlus, OpQuest:
+		sub := re.Sub[0].Simplify()
+		return simplify1(re.Op, re.Flags, sub, re)
+
+	case OpRepeat:
+		// Special special case: x{0} matches the empty string
+		// and doesn't even need to consider x.
+		if re.Min == 0 && re.Max == 0 {
+			return &Regexp{Op: OpEmptyMatch}
+		}
+
+		// The fun begins.
+		sub := re.Sub[0].Simplify()
+
+		// x{n,} means at least n matches of x.
+		if re.Max == -1 {
+			// Special case: x{0,} is x*.
+			if re.Min == 0 {
+				return simplify1(OpStar, re.Flags, sub, nil)
+			}
+
+			// Special case: x{1,} is x+.
+			if re.Min == 1 {
+				return simplify1(OpPlus, re.Flags, sub, nil)
+			}
+
+			// General case: x{4,} is xxxx+.
+			nre := &Regexp{Op: OpConcat}
+			nre.Sub = nre.Sub0[:0]
+			for i := 0; i < re.Min-1; i++ {
+				nre.Sub = append(nre.Sub, sub)
+			}
+			nre.Sub = append(nre.Sub, simplify1(OpPlus, re.Flags, sub, nil))
+			return nre
+		}
+
+		// Special case x{0} handled above.
+
+		// Special case: x{1} is just x.
+		if re.Min == 1 && re.Max == 1 {
+			return sub
+		}
+
+		// General case: x{n,m} means n copies of x and m copies of x?
+		// The machine will do less work if we nest the final m copies,
+		// so that x{2,5} = xx(x(x(x)?)?)?
+
+		// Build leading prefix: xx.
+		var prefix *Regexp
+		if re.Min > 0 {
+			prefix = &Regexp{Op: OpConcat}
+			prefix.Sub = prefix.Sub0[:0]
+			for i := 0; i < re.Min; i++ {
+				prefix.Sub = append(prefix.Sub, sub)
+			}
+		}
+
+		// Build and attach suffix: (x(x(x)?)?)?
+		if re.Max > re.Min {
+			suffix := simplify1(OpQuest, re.Flags, sub, nil)
+			for i := re.Min + 1; i < re.Max; i++ {
+				nre2 := &Regexp{Op: OpConcat}
+				nre2.Sub = append(nre2.Sub0[:0], sub, suffix)
+				suffix = simplify1(OpQuest, re.Flags, nre2, nil)
+			}
+			if prefix == nil {
+				return suffix
+			}
+			prefix.Sub = append(prefix.Sub, suffix)
+		}
+		if prefix != nil {
+			return prefix
+		}
+
+		// Some degenerate case like min > max or min < max < 0.
+		// Handle as impossible match.
+		return &Regexp{Op: OpNoMatch}
+	}
+
+	return re
+}
+
+// simplify1 implements Simplify for the unary OpStar,
+// OpPlus, and OpQuest operators.  It returns the simple regexp
+// equivalent to
+//
+//	Regexp{Op: op, Flags: flags, Sub: {sub}}
+//
+// under the assumption that sub is already simple, and
+// without first allocating that structure.  If the regexp
+// to be returned turns out to be equivalent to re, simplify1
+// returns re instead.
+//
+// simplify1 is factored out of Simplify because the implementation
+// for other operators generates these unary expressions.
+// Letting them call simplify1 makes sure the expressions they
+// generate are simple.
+func simplify1(op Op, flags Flags, sub, re *Regexp) *Regexp {
+	// Special case: repeat the empty string as much as
+	// you want, but it's still the empty string.
+	if sub.Op == OpEmptyMatch {
+		return sub
+	}
+	// The operators are idempotent if the flags match.
+	if op == sub.Op && flags&NonGreedy == sub.Flags&NonGreedy {
+		return sub
+	}
+	if re != nil && re.Op == op && re.Flags&NonGreedy == flags&NonGreedy && sub == re.Sub[0] {
+		return re
+	}
+
+	re = &Regexp{Op: op, Flags: flags}
+	re.Sub = append(re.Sub0[:0], sub)
+	return re
+}
diff --git a/src/pkg/exp/regexp/syntax/simplify_test.go b/src/pkg/exp/regexp/syntax/simplify_test.go
new file mode 100644
index 000000000..c8cec2183
--- /dev/null
+++ b/src/pkg/exp/regexp/syntax/simplify_test.go
@@ -0,0 +1,151 @@
+// Copyright 2011 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package syntax
+
+import "testing"
+
+var simplifyTests = []struct {
+	Regexp string
+	Simple string
+}{
+	// Already-simple constructs
+	{`a`, `a`},
+	{`ab`, `ab`},
+	{`a|b`, `[a-b]`},
+	{`ab|cd`, `ab|cd`},
+	{`(ab)*`, `(ab)*`},
+	{`(ab)+`, `(ab)+`},
+	{`(ab)?`, `(ab)?`},
+	{`.`, `.`},
+	{`^`, `^`},
+	{`$`, `$`},
+	{`[ac]`, `[ac]`},
+	{`[^ac]`, `[^ac]`},
+
+	// Posix character classes
+	{`[[:alnum:]]`, `[0-9A-Za-z]`},
+	{`[[:alpha:]]`, `[A-Za-z]`},
+	{`[[:blank:]]`, `[\t ]`},
+	{`[[:cntrl:]]`, `[\x00-\x1f\x7f]`},
+	{`[[:digit:]]`, `[0-9]`},
+	{`[[:graph:]]`, `[!-~]`},
+	{`[[:lower:]]`, `[a-z]`},
+	{`[[:print:]]`, `[ -~]`},
+	{`[[:punct:]]`, "[!-/:-@\\[-`\\{-~]"},
+	{`[[:space:]]`, `[\t-\r ]`},
+	{`[[:upper:]]`, `[A-Z]`},
+	{`[[:xdigit:]]`, `[0-9A-Fa-f]`},
+
+	// Perl character classes
+	{`\d`, `[0-9]`},
+	{`\s`, `[\t-\n\f-\r ]`},
+	{`\w`, `[0-9A-Z_a-z]`},
+	{`\D`, `[^0-9]`},
+	{`\S`, `[^\t-\n\f-\r ]`},
+	{`\W`, `[^0-9A-Z_a-z]`},
+	{`[\d]`, `[0-9]`},
+	{`[\s]`, `[\t-\n\f-\r ]`},
+	{`[\w]`, `[0-9A-Z_a-z]`},
+	{`[\D]`, `[^0-9]`},
+	{`[\S]`, `[^\t-\n\f-\r ]`},
+	{`[\W]`, `[^0-9A-Z_a-z]`},
+
+	// Posix repetitions
+	{`a{1}`, `a`},
+	{`a{2}`, `aa`},
+	{`a{5}`, `aaaaa`},
+	{`a{0,1}`, `a?`},
+	// The next three are illegible because Simplify inserts (?:)
+	// parens instead of () parens to avoid creating extra
+	// captured subexpressions.  The comments show a version with fewer parens.
+	{`(a){0,2}`, `(?:(a)(a)?)?`},                       //       (aa?)?
+	{`(a){0,4}`, `(?:(a)(?:(a)(?:(a)(a)?)?)?)?`},       //   (a(a(aa?)?)?)?
+	{`(a){2,6}`, `(a)(a)(?:(a)(?:(a)(?:(a)(a)?)?)?)?`}, // aa(a(a(aa?)?)?)?
+	{`a{0,2}`, `(?:aa?)?`},                             //       (aa?)?
+	{`a{0,4}`, `(?:a(?:a(?:aa?)?)?)?`},                 //   (a(a(aa?)?)?)?
+	{`a{2,6}`, `aa(?:a(?:a(?:aa?)?)?)?`},               // aa(a(a(aa?)?)?)?
+	{`a{0,}`, `a*`},
+	{`a{1,}`, `a+`},
+	{`a{2,}`, `aa+`},
+	{`a{5,}`, `aaaaa+`},
+
+	// Test that operators simplify their arguments.
+	{`(?:a{1,}){1,}`, `a+`},
+	{`(a{1,}b{1,})`, `(a+b+)`},
+	{`a{1,}|b{1,}`, `a+|b+`},
+	{`(?:a{1,})*`, `(?:a+)*`},
+	{`(?:a{1,})+`, `a+`},
+	{`(?:a{1,})?`, `(?:a+)?`},
+	{``, `(?:)`},
+	{`a{0}`, `(?:)`},
+
+	// Character class simplification
+	{`[ab]`, `[a-b]`},
+	{`[a-za-za-z]`, `[a-z]`},
+	{`[A-Za-zA-Za-z]`, `[A-Za-z]`},
+	{`[ABCDEFGH]`, `[A-H]`},
+	{`[AB-CD-EF-GH]`, `[A-H]`},
+	{`[W-ZP-XE-R]`, `[E-Z]`},
+	{`[a-ee-gg-m]`, `[a-m]`},
+	{`[a-ea-ha-m]`, `[a-m]`},
+	{`[a-ma-ha-e]`, `[a-m]`},
+	{`[a-zA-Z0-9 -~]`, `[ -~]`},
+
+	// Empty character classes
+	{`[^[:cntrl:][:^cntrl:]]`, `[^\x00-\x{10FFFF}]`},
+
+	// Full character classes
+	{`[[:cntrl:][:^cntrl:]]`, `.`},
+
+	// Unicode case folding.
+	{`(?i)A`, `(?i:A)`},
+	{`(?i)a`, `(?i:a)`},
+	{`(?i)[A]`, `(?i:A)`},
+	{`(?i)[a]`, `(?i:A)`},
+	{`(?i)K`, `(?i:K)`},
+	{`(?i)k`, `(?i:k)`},
+	{`(?i)\x{212a}`, "(?i:\u212A)"},
+	{`(?i)[K]`, "[Kk\u212A]"},
+	{`(?i)[k]`, "[Kk\u212A]"},
+	{`(?i)[\x{212a}]`, "[Kk\u212A]"},
+	{`(?i)[a-z]`, "[A-Za-z\u017F\u212A]"},
+	{`(?i)[\x00-\x{FFFD}]`, "[\\x00-\uFFFD]"},
+	{`(?i)[\x00-\x{10FFFF}]`, `.`},
+
+	// Empty string as a regular expression.
+	// The empty string must be preserved inside parens in order
+	// to make submatches work right, so these tests are less
+	// interesting than they might otherwise be.  String inserts
+	// explicit (?:) in place of non-parenthesized empty strings,
+	// to make them easier to spot for other parsers.
+	{`(a|b|)`, `([a-b]|(?:))`},
+	{`(|)`, `()`},
+	{`a()`, `a()`},
+	{`(()|())`, `(()|())`},
+	{`(a|)`, `(a|(?:))`},
+	{`ab()cd()`, `ab()cd()`},
+	{`()`, `()`},
+	{`()*`, `()*`},
+	{`()+`, `()+`},
+	{`()?`, `()?`},
+	{`(){0}`, `(?:)`},
+	{`(){1}`, `()`},
+	{`(){1,}`, `()+`},
+	{`(){0,2}`, `(?:()()?)?`},
+}
+
+func TestSimplify(t *testing.T) {
+	for _, tt := range simplifyTests {
+		re, err := Parse(tt.Regexp, MatchNL|Perl&^OneLine)
+		if err != nil {
+			t.Errorf("Parse(%#q) = error %v", tt.Regexp, err)
+			continue
+		}
+		s := re.Simplify().String()
+		if s != tt.Simple {
+			t.Errorf("Simplify(%#q) = %#q, want %#q", tt.Regexp, s, tt.Simple)
+		}
+	}
+}