diff --git a/cue/ast.go b/cue/ast.go
index 7b067bd..e1303ea 100644
--- a/cue/ast.go
+++ b/cue/ast.go
@@ -464,7 +464,8 @@
 				tokenMap[n.Op],
 				v.walk(n.X),
 			}
-		case token.GEQ, token.GTR, token.LSS, token.LEQ, token.NEQ:
+		case token.GEQ, token.GTR, token.LSS, token.LEQ,
+			token.NEQ, token.MAT, token.NMAT:
 			value = &bound{
 				newExpr(n),
 				tokenMap[n.Op],
diff --git a/cue/binop.go b/cue/binop.go
index 62fe166..c534fc9 100644
--- a/cue/binop.go
+++ b/cue/binop.go
@@ -17,6 +17,7 @@
 import (
 	"bytes"
 	"math/big"
+	"regexp"
 	"sort"
 	"strings"
 	"time"
@@ -259,12 +260,14 @@
 		pos = r.Pos()
 	}
 	e := mkBin(ctx, pos, opUnify, r, v)
-	if r.op == opNeq {
-		const msgInRange = "%v excluded by %v"
-		return ctx.mkErr(e, msgInRange, debugStr(ctx, v), debugStr(ctx, r))
+	msg := "%v not within bound %v"
+	switch r.op {
+	case opNeq, opNMat:
+		msg = "%v excluded by %v"
+	case opMat:
+		msg = "%v does not match %v"
 	}
-	const msgInRange = "%v not within bound %v"
-	return ctx.mkErr(e, msgInRange, debugStr(ctx, v), debugStr(ctx, r))
+	return ctx.mkErr(e, msg, debugStr(ctx, v), debugStr(ctx, r))
 }
 
 func opInfo(op op) (cmp op, norm int) {
@@ -279,6 +282,10 @@
 		return opLss, -1
 	case opNeq:
 		return opNeq, 0
+	case opMat:
+		return opMat, 2
+	case opNMat:
+		return opNMat, 3
 	}
 	panic("cue: unreachable")
 }
@@ -312,11 +319,11 @@
 
 			switch {
 			case xCat == yCat:
-				if x.op == opNeq {
+				if x.op == opNeq || x.op == opMat || x.op == opNMat {
 					if test(ctx, x, opEql, xv, yv) {
 						return x
 					}
-					break
+					break // unify the two bounds
 				}
 
 				// xCat == yCat && x.op != opNeq
@@ -416,6 +423,11 @@
 						debugStr(ctx, x), debugStr(ctx, y))
 				}
 
+			case x.op == opNeq:
+				if !test(ctx, x, y.op, xv, yv) {
+					return y
+				}
+
 			case y.op == opNeq:
 				if !test(ctx, x, x.op, yv, xv) {
 					return x
@@ -610,9 +622,21 @@
 			}
 			return x
 		case opLss, opLeq, opEql, opNeq, opGeq, opGtr:
-			return cmpTonode(src, op, strings.Compare(string(x.str), string(str)))
+			return cmpTonode(src, op, strings.Compare(x.str, str))
 		case opAdd:
 			return &stringLit{binSrc(src.Pos(), op, x, other), x.str + str}
+		case opMat:
+			b, err := regexp.MatchString(str, x.str)
+			if err != nil {
+				return ctx.mkErr(src, "error parsing regexp: %v", err)
+			}
+			return boolTonode(src, b)
+		case opNMat:
+			b, err := regexp.MatchString(str, x.str)
+			if err != nil {
+				return ctx.mkErr(src, "error parsing regexp: %v", err)
+			}
+			return boolTonode(src, !b)
 		}
 	}
 	return ctx.mkIncompatible(src, op, x, other)
diff --git a/cue/kind.go b/cue/kind.go
index a35e886..57b9928 100644
--- a/cue/kind.go
+++ b/cue/kind.go
@@ -247,7 +247,7 @@
 		if u.isAnyOf(boolKind) {
 			return boolKind | catBits, invert
 		}
-	case opEql, opNeq:
+	case opEql, opNeq, opMat, opNMat:
 		if u.isAnyOf(fixedKinds) {
 			return boolKind | catBits, false
 		}
diff --git a/cue/op.go b/cue/op.go
index 9d9c0a8..258343a 100644
--- a/cue/op.go
+++ b/cue/op.go
@@ -51,6 +51,8 @@
 
 	opEql
 	opNeq
+	opMat
+	opNMat
 
 	opLss
 	opGtr
@@ -79,8 +81,10 @@
 	opLor:  "||",
 	opNot:  "!",
 
-	opEql: "==",
-	opNeq: "!=",
+	opEql:  "==",
+	opNeq:  "!=",
+	opMat:  "=~",
+	opNMat: "!~",
 
 	opLss: "<",
 	opGtr: ">",
@@ -124,9 +128,11 @@
 	token.GTR: opGtr, // >
 	token.NOT: opNot, // !
 
-	token.NEQ: opNeq, // !=
-	token.LEQ: opLeq, // <=
-	token.GEQ: opGeq, // >=
+	token.NEQ:  opNeq,  // !=
+	token.LEQ:  opLeq,  // <=
+	token.GEQ:  opGeq,  // >=
+	token.MAT:  opMat,  // =~
+	token.NMAT: opNMat, // !~
 }
 
 var opMap = map[op]token.Token{}
diff --git a/cue/parser/parser.go b/cue/parser/parser.go
index b46fa25..9d0d308 100644
--- a/cue/parser/parser.go
+++ b/cue/parser/parser.go
@@ -1104,7 +1104,8 @@
 
 	switch p.tok {
 	case token.ADD, token.SUB, token.NOT, token.MUL,
-		token.NEQ, token.LSS, token.LEQ, token.GEQ, token.GTR:
+		token.LSS, token.LEQ, token.GEQ, token.GTR,
+		token.NEQ, token.MAT, token.NMAT:
 		pos, op := p.pos, p.tok
 		c := p.openComments()
 		p.next()
diff --git a/cue/resolve_test.go b/cue/resolve_test.go
index bfac4ee..b6fbaa6 100644
--- a/cue/resolve_test.go
+++ b/cue/resolve_test.go
@@ -101,6 +101,46 @@
 			`,
 		out: `<0>{a: _|_(from source), b: _|_(from source), c: true, d: false, e: true}`,
 	}, {
+		desc: "regexp",
+		in: `
+			c1: "a" =~ "a"
+			c2: "foo" =~ "[a-z]{3}"
+			c3: "foo" =~ "[a-z]{4}"
+			c4: "foo" !~ "[a-z]{4}"
+
+			b1: =~ "a"
+			b1: "a"
+			b2: =~ "[a-z]{3}"
+			b2: "foo"
+			b3: =~ "[a-z]{4}"
+			b3: "foo"
+			b4: !~ "[a-z]{4}"
+			b4: "foo"
+
+			s1: != "b" & =~"c"      // =~"c"
+			s2: != "b" & =~"[a-z]"  // != "b" & =~"[a-z]"
+
+			e1: "foo" =~ 1
+			e2: "foo" !~ true
+			e3: != "a" & <5
+		`,
+		out: `<0>{c1: true, ` +
+			`c2: true, ` +
+			`c3: false, ` +
+			`c4: true, ` +
+
+			`b1: "a", ` +
+			`b2: "foo", ` +
+			`b3: _|_((=~"[a-z]{4}" & "foo"):"foo" does not match =~"[a-z]{4}"), ` +
+			`b4: "foo", ` +
+
+			`s1: =~"c", ` +
+			`s2: (!="b" & =~"[a-z]"), ` +
+
+			`e1: _|_(("foo" =~ 1):unsupported op =~(string, number)), ` +
+			`e2: _|_(("foo" !~ true):unsupported op !~(string, bool)), ` +
+			`e3: _|_((!="a" & <5):unsupported op &((string)*, (number)*))}`,
+	}, {
 		desc: "arithmetic",
 		in: `
 			sum: -1 + +2        // 1
@@ -476,6 +516,12 @@
 			s4: <10 & !=10              // <10
 			s5: !=2 & !=2
 
+			// TODO: could change inequality
+			s6: !=2 & >=2
+			s7: >=2 & !=2
+
+			s8: !=5 & >5
+
 			s10: >=0 & <=10 & <12 & >1   // >1  & <=10
 			s11: >0 & >=0 & <=12 & <12   // >0  & <12
 
@@ -516,6 +562,11 @@
 			`s4: <10, ` +
 			`s5: !=2, ` +
 
+			`s6: (!=2 & >=2), ` +
+			`s7: (>=2 & !=2), ` +
+
+			`s8: >5, ` +
+
 			`s10: (<=10 & >1), ` +
 			`s11: (>0 & <12), ` +
 
diff --git a/cue/scanner/scanner.go b/cue/scanner/scanner.go
index 5b8fc65..aab40d5 100644
--- a/cue/scanner/scanner.go
+++ b/cue/scanner/scanner.go
@@ -793,9 +793,19 @@
 		case '>':
 			tok = s.switch2(token.GTR, token.GEQ)
 		case '=':
-			tok = s.switch2(token.BIND, token.EQL)
+			if s.ch == '~' {
+				s.next()
+				tok = token.MAT
+			} else {
+				tok = s.switch2(token.BIND, token.EQL)
+			}
 		case '!':
-			tok = s.switch2(token.NOT, token.NEQ)
+			if s.ch == '~' {
+				s.next()
+				tok = token.NMAT
+			} else {
+				tok = s.switch2(token.NOT, token.NEQ)
+			}
 		case '&':
 			switch s.ch {
 			case '&':
diff --git a/cue/scanner/scanner_test.go b/cue/scanner/scanner_test.go
index d32b057..53d1bb0 100644
--- a/cue/scanner/scanner_test.go
+++ b/cue/scanner/scanner_test.go
@@ -136,6 +136,9 @@
 	{token.GEQ, ">=", operator},
 	{token.ELLIPSIS, "...", operator},
 
+	{token.MAT, "=~", operator},
+	{token.NMAT, "!~", operator},
+
 	{token.LPAREN, "(", operator},
 	{token.LBRACK, "[", operator},
 	{token.LBRACE, "{", operator},
diff --git a/cue/token/token.go b/cue/token/token.go
index 5238bc9..7db3329 100644
--- a/cue/token/token.go
+++ b/cue/token/token.go
@@ -72,6 +72,9 @@
 	LEQ // <=
 	GEQ // >=
 
+	MAT  // =~
+	NMAT // !~
+
 	LPAREN   // (
 	LBRACK   // [
 	LBRACE   // {
@@ -142,6 +145,9 @@
 	LEQ: "<=",
 	GEQ: ">=",
 
+	MAT:  "=~",
+	NMAT: "!~",
+
 	LPAREN:   "(",
 	LBRACK:   "[",
 	LBRACE:   "{",
@@ -214,7 +220,7 @@
 		return 3
 	case LAND:
 		return 4
-	case EQL, NEQ, LSS, LEQ, GTR, GEQ:
+	case EQL, NEQ, LSS, LEQ, GTR, GEQ, MAT, NMAT:
 		return 5
 	case ADD, SUB:
 		return 6