util: Adding regex support.

Change-Id: I33d84f4ae9076ff5a9db5232f2955f4be0ed820c
diff --git a/src/util/regex.hpp b/src/util/regex.hpp
new file mode 100644
index 0000000..0e7d6a0
--- /dev/null
+++ b/src/util/regex.hpp
@@ -0,0 +1,21 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_HPP
+#define NDN_REGEX_HPP
+
+#include "regex/regex-top-matcher.hpp"
+
+namespace ndn
+{
+
+typedef RegexTopMatcher Regex;
+
+}
+
+#endif
+
diff --git a/src/util/regex/regex-backref-manager.cpp b/src/util/regex/regex-backref-manager.cpp
new file mode 100644
index 0000000..ed17250
--- /dev/null
+++ b/src/util/regex/regex-backref-manager.cpp
@@ -0,0 +1,29 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "regex-backref-manager.hpp"
+
+namespace ndn
+{
+
+RegexBackrefManager::~RegexBackrefManager()
+{ m_backRefs.clear(); }
+
+int 
+RegexBackrefManager::pushRef(ptr_lib::shared_ptr<RegexMatcher> matcher)
+{
+  int last = m_backRefs.size();
+  m_backRefs.push_back(matcher);
+
+  return last;
+}
+
+void
+RegexBackrefManager::popRef()
+{ m_backRefs.pop_back(); }
+
+}//ndn
diff --git a/src/util/regex/regex-backref-manager.hpp b/src/util/regex/regex-backref-manager.hpp
new file mode 100644
index 0000000..7604b42
--- /dev/null
+++ b/src/util/regex/regex-backref-manager.hpp
@@ -0,0 +1,46 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_BACKREF_MANAGER_HPP
+#define NDN_REGEX_BACKREF_MANAGER_HPP
+
+#include <vector>
+#include "../../common.hpp"
+
+namespace ndn
+{
+
+class RegexMatcher;
+
+class RegexBackrefManager
+{
+public:
+  RegexBackrefManager(){}
+    
+  virtual ~RegexBackrefManager();
+    
+  int 
+  pushRef(ptr_lib::shared_ptr<RegexMatcher> matcher);
+    
+  void 
+  popRef();
+
+  int 
+  size()
+  { return m_backRefs.size(); }
+    
+  ptr_lib::shared_ptr<RegexMatcher> 
+  getBackRef(int i)
+  { return m_backRefs[i]; }
+    
+private:
+  std::vector<ptr_lib::shared_ptr<RegexMatcher> > m_backRefs;
+};
+
+}//ndn
+
+#endif
diff --git a/src/util/regex/regex-backref-matcher.cpp b/src/util/regex/regex-backref-matcher.cpp
new file mode 100644
index 0000000..1982623
--- /dev/null
+++ b/src/util/regex/regex-backref-matcher.cpp
@@ -0,0 +1,57 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include <boost/regex.hpp>
+
+#include "regex-backref-matcher.hpp"
+#include "regex-pattern-list-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexBackrefMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+
+RegexBackrefMatcher::RegexBackrefMatcher(const string expr, ptr_lib::shared_ptr<RegexBackrefManager> backRefManager)
+  : RegexMatcher (expr, EXPR_BACKREF, backRefManager)
+{
+  // _LOG_TRACE ("Enter RegexBackrefMatcher Constructor: ");
+  // compile();
+  // _LOG_TRACE ("Exit RegexBackrefMatcher Constructor: ");
+}
+
+void 
+RegexBackrefMatcher::compile()
+{
+  // _LOG_TRACE ("Enter RegexBackrefMatcher::compile()");
+
+  string errMsg = "Error: RegexBackrefMatcher.Compile(): ";
+    
+  // _LOG_DEBUG ("m_backRefManager: " << m_backRefManager);
+
+  int lastIndex = m_expr.size() - 1;
+  if('(' == m_expr[0] && ')' == m_expr[lastIndex]){
+    // m_backRefManager->pushRef(this);
+
+    ptr_lib::shared_ptr<RegexMatcher> matcher = ptr_lib::make_shared<RegexPatternListMatcher>(m_expr.substr(1, lastIndex - 1), m_backrefManager);
+    m_matcherList.push_back(matcher);
+      
+  }
+  else
+    throw RegexMatcher::Error(errMsg + " Unrecognoized format " + m_expr);
+    
+  // _LOG_TRACE ("Exit RegexBackrefMatcher::compile");
+}
+
+}//ndn
+
+
+
+
diff --git a/src/util/regex/regex-backref-matcher.hpp b/src/util/regex/regex-backref-matcher.hpp
new file mode 100644
index 0000000..de04b19
--- /dev/null
+++ b/src/util/regex/regex-backref-matcher.hpp
@@ -0,0 +1,43 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_BACKREF_MATCHER_HPP
+#define NDN_REGEX_BACKREF_MATCHER_HPP
+
+#include "regex-matcher.hpp"
+
+#include <boost/enable_shared_from_this.hpp>
+
+namespace ndn
+{
+
+class RegexBackrefMatcher : public RegexMatcher
+{
+public:
+  RegexBackrefMatcher(const std::string expr, ptr_lib::shared_ptr<RegexBackrefManager> backRefManager);
+    
+  virtual ~RegexBackrefMatcher(){}
+
+  void 
+  lateCompile()
+  {
+    compile();
+  }
+
+protected:
+  virtual void 
+  compile();
+    
+private:
+  int m_refNum;
+};
+
+}//ndn
+
+#endif
+
+
diff --git a/src/util/regex/regex-component-matcher.cpp b/src/util/regex/regex-component-matcher.cpp
new file mode 100644
index 0000000..e3bbe0e
--- /dev/null
+++ b/src/util/regex/regex-component-matcher.cpp
@@ -0,0 +1,87 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "regex-component-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexComponentMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+
+RegexComponentMatcher::RegexComponentMatcher (const string & expr, 
+                                              ptr_lib::shared_ptr<RegexBackrefManager> backRefManager, 
+                                              bool exact)
+  : RegexMatcher (expr, EXPR_COMPONENT, backRefManager),
+    m_exact(exact)
+{
+  // _LOG_TRACE ("Enter RegexComponentMatcher Constructor: ");
+  compile();
+  // _LOG_TRACE ("Exit RegexComponentMatcher Constructor: ");
+}
+
+void 
+RegexComponentMatcher::compile ()
+{
+  // _LOG_TRACE ("Enter RegexComponentMatcher::compile");
+
+  m_componentRegex = boost::regex (m_expr);
+
+  m_pseudoMatcher.clear();
+  m_pseudoMatcher.push_back(ptr_lib::make_shared<RegexPseudoMatcher>());
+
+  for (int i = 1; i < m_componentRegex.mark_count(); i++)
+    {
+      ptr_lib::shared_ptr<RegexPseudoMatcher> pMatcher = ptr_lib::make_shared<RegexPseudoMatcher>();
+      m_pseudoMatcher.push_back(pMatcher);
+      m_backrefManager->pushRef(ptr_lib::static_pointer_cast<RegexMatcher>(pMatcher));
+    }
+    
+
+  // _LOG_TRACE ("Exit RegexComponentMatcher::compile");
+}
+
+bool
+RegexComponentMatcher::match (const Name & name, const int & offset, const int & len)
+{
+  // _LOG_TRACE ("Enter RegexComponentMatcher::match ");
+
+  m_matchResult.clear();
+
+  if("" == m_expr)
+    {
+      m_matchResult.push_back(name.get(offset));
+      return true;
+    }
+
+  if(true == m_exact)
+    {
+      boost::smatch subResult;
+      string targetStr = name.get(offset).toEscapedString();
+      if(boost::regex_match(targetStr, subResult, m_componentRegex))
+        {
+          for (int i = 1; i < m_componentRegex.mark_count(); i++)
+            {
+              m_pseudoMatcher[i]->resetMatchResult();
+              m_pseudoMatcher[i]->setMatchResult(subResult[i]);
+            }
+          m_matchResult.push_back(name.get(offset));
+          return true;
+        }
+    }
+  else
+    {
+      throw RegexMatcher::Error("Non-exact component search is not supported yet!");
+    }
+
+  return false;
+}
+
+} //ndn
diff --git a/src/util/regex/regex-component-matcher.hpp b/src/util/regex/regex-component-matcher.hpp
new file mode 100644
index 0000000..830b45c
--- /dev/null
+++ b/src/util/regex/regex-component-matcher.hpp
@@ -0,0 +1,54 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_COMPONENT_HPP
+#define NDN_REGEX_COMPONENT_HPP
+
+#include <boost/regex.hpp>
+
+#include "regex-matcher.hpp"
+#include "regex-pseudo-matcher.hpp"
+
+
+namespace ndn
+{    
+class RegexComponentMatcher : public RegexMatcher
+{
+public:
+  /**
+   * @brief Create a RegexComponent matcher from expr
+   * @param expr The standard regular expression to match a component
+   * @param backRefManager The back reference manager
+   * @param exact The flag to provide exact match
+   */
+  RegexComponentMatcher(const std::string& expr, 
+                        ptr_lib::shared_ptr<RegexBackrefManager> backRefManager, 
+                        bool exact = true);
+    
+  virtual ~RegexComponentMatcher() {};
+
+  virtual bool 
+  match(const Name & name, const int & offset, const int &len = 1);
+
+protected:
+  /**
+   * @brief Compile the regular expression to generate the more matchers when necessary
+   * @returns true if compiling succeeds
+   */
+  virtual void 
+  compile();
+    
+private:
+  bool m_exact;
+  boost::regex m_componentRegex;
+  std::vector<ptr_lib::shared_ptr<RegexPseudoMatcher> > m_pseudoMatcher;
+    
+};
+    
+}//ndn
+
+#endif
diff --git a/src/util/regex/regex-component-set-matcher.cpp b/src/util/regex/regex-component-set-matcher.cpp
new file mode 100644
index 0000000..dddebfc
--- /dev/null
+++ b/src/util/regex/regex-component-set-matcher.cpp
@@ -0,0 +1,179 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "regex-component-set-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexComponentSetMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+RegexComponentSetMatcher::RegexComponentSetMatcher(const string expr, ptr_lib::shared_ptr<RegexBackrefManager> backRefManager)
+  : RegexMatcher(expr, EXPR_COMPONENT_SET, backRefManager),
+    m_include(true)
+{
+  // _LOG_TRACE ("Enter RegexComponentSetMatcher Constructor");
+  compile();
+  // _LOG_TRACE ("Exit RegexComponentSetMatcher Constructor");
+}
+
+RegexComponentSetMatcher::~RegexComponentSetMatcher()
+{
+  // set<Ptr<RegexComponent> >::iterator it = m_components.begin();
+
+  // for(; it != m_components.end(); it++)
+  //   delete *it;
+}
+
+void 
+RegexComponentSetMatcher::compile()
+{
+  // _LOG_TRACE ("Enter RegexComponentSetMatcher::compile");
+
+  string errMsg = "Error: RegexComponentSetMatcher.compile(): ";
+  int index = 0;
+
+
+  switch(m_expr[0]){
+  case '<':
+    return compileSingleComponent();
+  case '[':
+    {
+      int lastIndex = m_expr.size() - 1;
+      if(']' != m_expr[lastIndex])
+        throw RegexMatcher::Error(errMsg + " No matched ']' " + m_expr);
+      
+      if('^' == m_expr[1]){
+        m_include = false;
+        compileMultipleComponents(2, lastIndex);
+      }
+      else
+        compileMultipleComponents(1, lastIndex);
+      break;
+    }
+  default:
+    throw RegexMatcher::Error(errMsg + "Parsing error in expr " + m_expr);
+  }
+
+  // _LOG_TRACE ("Exit RegexComponentSetMatcher::compile");
+}
+
+void 
+RegexComponentSetMatcher::compileSingleComponent()
+{
+  // _LOG_TRACE ("Enter RegexComponentSetMatcher::compileSingleComponent");
+
+  string errMsg = "Error: RegexComponentSetMatcher.compileSingleComponent: ";
+
+  int end = extractComponent(1);
+
+  if(m_expr.size() != end)
+    throw RegexMatcher::Error(errMsg + m_expr);
+  else{
+    // _LOG_DEBUG ("RegexComponentSetMatcher::compileSingleComponent expr: " << m_expr.substr(1, end - 2));
+    ptr_lib::shared_ptr<RegexComponentMatcher> component = ptr_lib::make_shared<RegexComponentMatcher>(m_expr.substr(1, end - 2), m_backrefManager);
+    m_components.insert(component);
+      
+  }
+
+  // _LOG_TRACE ("Exit RegexComponentSetMatcher::compileSingleComponent");
+}
+
+void 
+RegexComponentSetMatcher::compileMultipleComponents(const int start, const int lastIndex)
+{
+  // _LOG_TRACE ("Enter RegexComponentSetMatcher::compileMultipleComponents");
+
+  string errMsg = "Error: RegexComponentSetMatcher.compileMultipleComponents: ";
+
+  int index = start;
+  int tmp_index = start;
+    
+  while(index < lastIndex){
+    if('<' != m_expr[index])
+      throw RegexMatcher::Error(errMsg + "Component expr error " + m_expr);
+      
+    tmp_index = index + 1;
+    index = extractComponent(tmp_index);
+
+    ptr_lib::shared_ptr<RegexComponentMatcher> component = ptr_lib::make_shared<RegexComponentMatcher>(m_expr.substr(tmp_index, index - tmp_index - 1), m_backrefManager);
+    m_components.insert(component);
+  }
+    
+  if(index != lastIndex)
+    throw RegexMatcher::Error(errMsg + "Not sufficient expr to parse " + m_expr);        
+
+  // _LOG_TRACE ("Exit RegexComponentSetMatcher::compileMultipleComponents");
+}
+
+bool 
+RegexComponentSetMatcher::match(const Name & name, const int & offset, const int & len)
+{
+  // _LOG_TRACE ("Enter RegexComponentSetMatcher::match");
+
+  bool matched = false;
+
+  /* componentset only matches one component */
+  if(len != 1){
+    // _LOG_DEBUG ("Match Fail: ComponentSet matches only one component");
+    return false;
+  }
+
+  set<ptr_lib::shared_ptr<RegexComponentMatcher> >::iterator it = m_components.begin();
+
+  for(; it != m_components.end(); it++){
+    if((*it)->match(name, offset, len)){
+      matched = true;
+      break;
+    }
+  }
+    
+  m_matchResult.clear();
+
+  if(m_include ? matched : !matched){
+    m_matchResult.push_back(name.get(offset));
+    return true;
+  }
+  else 
+    return false;
+}
+
+int 
+RegexComponentSetMatcher::extractComponent(int index)
+{
+  // _LOG_TRACE ("Enter RegexComponentSetMatcher::extractComponent");
+
+  int lcount = 1;
+  int rcount = 0;
+
+  while(lcount > rcount){
+    switch(m_expr[index]){
+    case '<':
+      lcount++;
+      break;
+
+    case '>':
+      rcount++;
+      break;
+
+    case 0:
+      throw RegexMatcher::Error("Error: square brackets mismatch");
+      break;
+    }
+    index++;
+
+  }
+
+  // _LOG_TRACE ("Exit RegexComponentSetMatcher::extractComponent");
+  return index;
+
+}
+
+}//ndn
diff --git a/src/util/regex/regex-component-set-matcher.hpp b/src/util/regex/regex-component-set-matcher.hpp
new file mode 100644
index 0000000..d4c576e
--- /dev/null
+++ b/src/util/regex/regex-component-set-matcher.hpp
@@ -0,0 +1,61 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef REGEX_COMPONENT_SET_MATCHER_HPP
+#define REGEX_COMPONENT_SET_MATCHER_HPP
+
+#include <set>
+
+#include "regex-matcher.hpp"
+#include "regex-component-matcher.hpp"
+
+namespace ndn
+{
+
+class RegexComponentSetMatcher : public RegexMatcher
+{
+
+public:
+  /**
+   * @brief Create a RegexComponentSetMatcher matcher from expr
+   * @param expr The standard regular expression to match a component
+   * @param exact The flag to provide exact match
+   * @param backRefNum The starting back reference number
+   */
+  RegexComponentSetMatcher(const std::string expr, ptr_lib::shared_ptr<RegexBackrefManager> backRefManager);    
+
+  virtual ~RegexComponentSetMatcher();
+
+  virtual bool 
+  match(const Name & name, const int & offset, const int & len = 1);
+
+protected:    
+  /**
+   * @brief Compile the regular expression to generate the more matchers when necessary
+   * @returns true if compiling succeeds
+   */
+  virtual void 
+  compile();
+
+private:
+  int
+  extractComponent(int index);
+
+  void
+  compileSingleComponent();
+    
+  void
+  compileMultipleComponents(const int start, const int lastIndex);
+
+private:
+  std::set<ptr_lib::shared_ptr<RegexComponentMatcher> > m_components;
+  bool m_include;
+};
+
+}//ndn
+
+#endif
diff --git a/src/util/regex/regex-matcher.cpp b/src/util/regex/regex-matcher.cpp
new file mode 100644
index 0000000..b83aa2e
--- /dev/null
+++ b/src/util/regex/regex-matcher.cpp
@@ -0,0 +1,78 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "regex-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+RegexMatcher::RegexMatcher(const std::string& expr, 
+                           const RegexExprType& type,  
+                           ptr_lib::shared_ptr<RegexBackrefManager> backrefManager) 
+  : m_expr(expr), 
+    m_type(type),
+    m_backrefManager(backrefManager)
+{
+  if(NULL == m_backrefManager)
+    m_backrefManager = ptr_lib::shared_ptr<RegexBackrefManager>(new RegexBackrefManager);
+}
+
+RegexMatcher::~RegexMatcher()
+{}
+
+bool 
+RegexMatcher::match (const Name& name, const int& offset, const int& len)
+{
+  // _LOG_TRACE ("Enter RegexMatcher::match");
+  bool result = false;
+
+  m_matchResult.clear();
+
+  if(recursiveMatch(0, name, offset, len))
+    {
+      for(int i = offset; i < offset + len ; i++)
+        m_matchResult.push_back(name.get(i));
+      result = true;
+    }
+  else
+    {
+      result = false;
+    }
+
+  // _LOG_TRACE ("Exit RegexMatcher::match");
+  return result;
+}
+  
+bool 
+RegexMatcher::recursiveMatch(const int& mId, const Name& name, const int& offset, const int& len)
+{
+  // _LOG_TRACE ("Enter RegexMatcher::recursiveMatch");
+
+  int tried = len;
+
+  if(mId >= m_matcherList.size())
+    return (len != 0 ? false : true);
+    
+  ptr_lib::shared_ptr<RegexMatcher> matcher = m_matcherList[mId];
+
+  while(tried >= 0)
+    {
+      if(matcher->match(name, offset, tried) && recursiveMatch(mId + 1, name, offset + tried, len - tried))
+        return true;      
+      tried--;
+    }
+
+  return false;
+}
+
+}//ndn
+
diff --git a/src/util/regex/regex-matcher.hpp b/src/util/regex/regex-matcher.hpp
new file mode 100644
index 0000000..ba465ac
--- /dev/null
+++ b/src/util/regex/regex-matcher.hpp
@@ -0,0 +1,85 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+
+#ifndef NDN_REGEX_MATCHER_H
+#define NDN_REGEX_MATCHER_H
+
+#include <string>
+#include "../../name.hpp"
+#include "regex-backref-manager.hpp"
+
+namespace ndn
+{
+class RegexMatcher;
+
+class RegexMatcher
+{
+public:
+  struct Error : public std::runtime_error { Error(const std::string &what) : std::runtime_error(what) {} };
+
+  enum RegexExprType{
+    EXPR_TOP,
+
+    EXPR_PATTERNLIST,
+
+    EXPR_REPEAT_PATTERN,
+      
+    EXPR_BACKREF,
+    EXPR_COMPONENT_SET,
+    EXPR_COMPONENT,
+
+    EXPR_PSEUDO
+  };    
+
+  RegexMatcher(const std::string& expr, 
+               const RegexExprType& type,  
+               ptr_lib::shared_ptr<RegexBackrefManager> backrefManager = ptr_lib::shared_ptr<RegexBackrefManager>());
+
+  virtual 
+  ~RegexMatcher();
+
+  virtual bool 
+  match(const Name& name, const int& offset, const int& len);
+
+  /**
+   * @brief get the matched name components
+   * @returns the matched name components
+   */
+  const std::vector<Name::Component>& 
+  getMatchResult() const
+  { return m_matchResult; }
+
+  const std::string&
+  getExpr() const
+  { return m_expr; } 
+
+protected:
+  /**
+   * @brief Compile the regular expression to generate the more matchers when necessary
+   * @returns true if compiling succeeds
+   */
+  virtual void 
+  compile() = 0;
+
+private:
+  bool 
+  recursiveMatch(const int& mId, const Name& name, const int& offset, const int& len);
+
+
+protected:
+  const std::string m_expr;
+  const RegexExprType m_type; 
+  ptr_lib::shared_ptr<RegexBackrefManager> m_backrefManager;
+  std::vector<ptr_lib::shared_ptr<RegexMatcher> > m_matcherList;
+  std::vector<Name::Component> m_matchResult;
+
+};
+}//ndn
+
+
+#endif
diff --git a/src/util/regex/regex-pattern-list-matcher.cpp b/src/util/regex/regex-pattern-list-matcher.cpp
new file mode 100644
index 0000000..28f0037
--- /dev/null
+++ b/src/util/regex/regex-pattern-list-matcher.cpp
@@ -0,0 +1,162 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "regex-pattern-list-matcher.hpp"
+#include "regex-backref-matcher.hpp"
+#include "regex-repeat-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexPatternListMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+RegexPatternListMatcher::RegexPatternListMatcher(const string expr, ptr_lib::shared_ptr<RegexBackrefManager> backrefManager)
+  :RegexMatcher(expr, EXPR_PATTERNLIST, backrefManager)
+{
+  // _LOG_TRACE ("Enter RegexPatternListMatcher Constructor");
+  compile();
+  // _LOG_TRACE ("Exit RegexPatternListMatcher Constructor");
+}
+  
+void 
+RegexPatternListMatcher::compile()
+{
+  // _LOG_TRACE ("Enter RegexPatternListMatcher::compile");
+
+  const int len = m_expr.size();
+  int index = 0;
+  int subHead = index;
+    
+  while(index < len){
+    subHead = index;
+
+    if(!extractPattern(subHead, &index))
+      throw RegexMatcher::Error("RegexPatternListMatcher compile: cannot compile");
+  }
+  // _LOG_TRACE ("Exit RegexPatternListMatcher::compile");
+}
+
+bool 
+RegexPatternListMatcher::extractPattern(int index, int* next)
+{
+  // _LOG_DEBUG ("Enter RegexPatternListMatcher::ExtractPattern()");
+
+  string errMsg = "Error: RegexPatternListMatcher.ExtractSubPattern(): ";
+    
+  const int start = index;
+  int end = index;
+  int indicator = index;
+    
+
+  // _LOG_DEBUG ("m_expr: " << m_expr << " index: " << index);
+
+  switch(m_expr[index]){
+  case '(':
+    index++;
+    index = extractSubPattern('(', ')', index);
+    indicator = index;
+    end = extractRepetition(index);
+    if(indicator == end){
+      ptr_lib::shared_ptr<RegexMatcher> matcher = ptr_lib::make_shared<RegexBackrefMatcher>(m_expr.substr(start, end - start), m_backrefManager);
+      m_backrefManager->pushRef(matcher);
+      boost::dynamic_pointer_cast<RegexBackrefMatcher>(matcher)->lateCompile();
+
+      m_matcherList.push_back(matcher);
+    }
+    else
+      m_matcherList.push_back(ptr_lib::make_shared<RegexRepeatMatcher>(m_expr.substr(start, end - start), m_backrefManager, indicator - start));
+    break;
+      
+  case '<':
+    index++;
+    index = extractSubPattern ('<', '>', index);
+    indicator = index;
+    end = extractRepetition(index);
+    m_matcherList.push_back(ptr_lib::make_shared<RegexRepeatMatcher>(m_expr.substr(start, end - start), m_backrefManager, indicator - start));
+    break;
+
+  case '[':
+    index++;
+    index = extractSubPattern ('[', ']', index);
+    indicator = index;
+    end = extractRepetition(index);
+    m_matcherList.push_back(ptr_lib::make_shared<RegexRepeatMatcher>(m_expr.substr(start, end - start), m_backrefManager, indicator - start));
+    break;
+
+  default:
+    throw RegexMatcher::Error("Error: unexpected syntax");
+  }
+
+  *next = end;
+
+  return true;
+}
+  
+int 
+RegexPatternListMatcher::extractSubPattern(const char left, const char right, int index)
+{
+  // _LOG_DEBUG ("Enter RegexPatternListMatcher::ExtractSubPattern()");
+
+  int lcount = 1;
+  int rcount = 0;
+
+  while(lcount > rcount){
+
+    if(index >= m_expr.size())
+      throw RegexMatcher::Error("Error: parenthesis mismatch");
+
+    if(left == m_expr[index])
+      lcount++;
+
+    if(right == m_expr[index])
+      rcount++;
+
+    index++;
+  }
+  return index;
+}
+
+int 
+RegexPatternListMatcher::extractRepetition(int index)
+{
+  // _LOG_DEBUG ("Enter RegexPatternListMatcher::ExtractRepetition()");
+
+  int exprSize = m_expr.size();
+
+  // _LOG_DEBUG ("expr: " << m_expr << " index: " << index << " char: " << (index == exprSize ? 0 : m_expr[index]));
+
+  string errMsg = "Error: RegexPatternListMatcher.ExtractRepetition(): ";
+    
+  if(index == exprSize)
+    return index;
+    
+  if(('+' == m_expr[index] || '?' == m_expr[index] || '*' == m_expr[index])){
+    return ++index;
+  }
+
+    
+  if('{' == m_expr[index]){
+    while('}' != m_expr[index]){
+      index++;
+      if(index == exprSize)
+        break;
+    }
+    if(index == exprSize)
+      throw RegexMatcher::Error(errMsg + "Missing right brace bracket");
+    else
+      return ++index;
+  }
+  else{
+    // _LOG_DEBUG ("return index: " << index);
+    return index;
+  }
+}
+
+}//ndn
diff --git a/src/util/regex/regex-pattern-list-matcher.hpp b/src/util/regex/regex-pattern-list-matcher.hpp
new file mode 100644
index 0000000..7240905
--- /dev/null
+++ b/src/util/regex/regex-pattern-list-matcher.hpp
@@ -0,0 +1,44 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_PATTERN_LIST_MATCHER_HPP
+#define NDN_REGEX_PATTERN_LIST_MATCHER_HPP
+
+#include <string>
+
+#include "regex-matcher.hpp"
+
+namespace ndn
+{
+
+class RegexPatternListMatcher : public RegexMatcher
+{
+public:
+  RegexPatternListMatcher(const std::string expr, ptr_lib::shared_ptr<RegexBackrefManager> backRefManager);
+    
+  virtual ~RegexPatternListMatcher(){};
+
+protected:    
+  virtual void 
+  compile();
+
+private:
+  bool 
+  extractPattern(int index, int* next);
+    
+  int 
+  extractSubPattern(const char left, const char right, int index);
+    
+  int 
+  extractRepetition(int index);
+
+private:
+
+};
+}//ndn
+
+#endif
diff --git a/src/util/regex/regex-pseudo-matcher.cpp b/src/util/regex/regex-pseudo-matcher.cpp
new file mode 100644
index 0000000..abebaff
--- /dev/null
+++ b/src/util/regex/regex-pseudo-matcher.cpp
@@ -0,0 +1,30 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "regex-pseudo-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexPseudoMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+RegexPseudoMatcher::RegexPseudoMatcher()
+  :RegexMatcher ("", EXPR_PSEUDO)
+{}
+
+void 
+RegexPseudoMatcher::setMatchResult(const string & str)
+{ m_matchResult.push_back(Name::Component((const uint8_t *)str.c_str(), str.size())); }
+    
+void 
+RegexPseudoMatcher::resetMatchResult()
+{ m_matchResult.clear(); }
+
+}//ndn
diff --git a/src/util/regex/regex-pseudo-matcher.hpp b/src/util/regex/regex-pseudo-matcher.hpp
new file mode 100644
index 0000000..9bb1e9f
--- /dev/null
+++ b/src/util/regex/regex-pseudo-matcher.hpp
@@ -0,0 +1,36 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_PSEUDO_MATCHER_HPP
+#define NDN_REGEX_PSEUDO_MATCHER_HPP
+
+#include "regex-matcher.hpp"
+
+namespace ndn
+{
+class RegexPseudoMatcher : public RegexMatcher
+{
+public:
+  RegexPseudoMatcher();
+
+  ~RegexPseudoMatcher() 
+  {}
+
+  virtual void 
+  compile() 
+  {}
+
+  void 
+  setMatchResult(const std::string& str);
+
+  void 
+  resetMatchResult();
+};
+
+}//ndn
+
+#endif
diff --git a/src/util/regex/regex-repeat-matcher.cpp b/src/util/regex/regex-repeat-matcher.cpp
new file mode 100644
index 0000000..d121b9e
--- /dev/null
+++ b/src/util/regex/regex-repeat-matcher.cpp
@@ -0,0 +1,193 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include <limits>
+#include <stdlib.h>
+
+#include <boost/regex.hpp>
+
+#include "regex-repeat-matcher.hpp"
+#include "regex-backref-matcher.hpp"
+#include "regex-component-set-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexRepeatMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+RegexRepeatMatcher::RegexRepeatMatcher(const string expr, ptr_lib::shared_ptr<RegexBackrefManager> backrefManager, int indicator)
+  : RegexMatcher (expr, EXPR_REPEAT_PATTERN, backrefManager),
+    m_indicator(indicator)
+{
+  // _LOG_TRACE ("Enter RegexRepeatMatcher Constructor");
+  compile();
+  // _LOG_TRACE ("Exit RegexRepeatMatcher Constructor");
+}
+
+void 
+RegexRepeatMatcher::compile()
+{
+  // _LOG_TRACE ("Enter RegexRepeatMatcher::compile");
+    
+  ptr_lib::shared_ptr<RegexMatcher> matcher;
+
+  if('(' == m_expr[0]){
+    matcher = ptr_lib::make_shared<RegexBackrefMatcher>(m_expr.substr(0, m_indicator), m_backrefManager);
+    m_backrefManager->pushRef(matcher);
+    boost::dynamic_pointer_cast<RegexBackrefMatcher>(matcher)->lateCompile();
+  }
+  else{
+    matcher = ptr_lib::make_shared<RegexComponentSetMatcher>(m_expr.substr(0, m_indicator), m_backrefManager);
+  }
+  m_matcherList.push_back(matcher);
+      
+  parseRepetition();
+
+  // _LOG_TRACE ("Exit RegexRepeatMatcher::compile");
+
+}
+
+bool 
+RegexRepeatMatcher::parseRepetition()
+{
+  // _LOG_DEBUG ("Enter RegexRepeatMatcher::ParseRepetition()" << m_expr << " indicator: " << m_indicator);
+
+  string errMsg = "Error: RegexRepeatMatcher.ParseRepetition(): ";
+    
+  int exprSize = m_expr.size();
+  int intMax = numeric_limits<int>::max();
+    
+  if(exprSize == m_indicator){
+    m_repeatMin = 1;
+    m_repeatMax = 1;
+
+    return true;
+  }
+  else{
+    if(exprSize == (m_indicator + 1)){
+      if('?' == m_expr[m_indicator]){
+        m_repeatMin = 0;
+        m_repeatMax = 1;
+        return true;
+      }
+      if('+' == m_expr[m_indicator]){
+        m_repeatMin = 1;
+        m_repeatMax = intMax;
+        return true;
+      }
+      if('*' == m_expr[m_indicator]){
+        m_repeatMin = 0;
+        m_repeatMax = intMax;
+        return true;
+      }
+    }
+    else{
+      string repeatStruct = m_expr.substr(m_indicator, exprSize - m_indicator);
+      int rsSize = repeatStruct.size();
+      int min = 0;
+      int max = 0;
+
+      if(boost::regex_match(repeatStruct, boost::regex("\\{[0-9]+,[0-9]+\\}"))){
+        int separator = repeatStruct.find_first_of(',', 0);
+        min = atoi(repeatStruct.substr(1, separator - 1).c_str());
+        max = atoi(repeatStruct.substr(separator + 1, rsSize - separator - 2).c_str());
+      }
+      else if(boost::regex_match(repeatStruct, boost::regex("\\{,[0-9]+\\}"))){
+        int separator = repeatStruct.find_first_of(',', 0);
+        min = 0;
+        max = atoi(repeatStruct.substr(separator + 1, rsSize - separator - 2).c_str());
+      }
+      else if(boost::regex_match(repeatStruct, boost::regex("\\{[0-9]+,\\}"))){
+        int separator = repeatStruct.find_first_of(',', 0);
+        min = atoi(repeatStruct.substr(1, separator).c_str());
+        max = intMax;
+      }
+      else if(boost::regex_match(repeatStruct, boost::regex("\\{[0-9]+\\}"))){
+        min = atoi(repeatStruct.substr(1, rsSize - 1).c_str());
+        max = min;
+      }
+      else
+        throw RegexMatcher::Error(errMsg + "Unrecognized format "+ m_expr);
+        
+      if(min > intMax || max > intMax || min > max)
+        throw RegexMatcher::Error(errMsg + "Wrong number " + m_expr);
+          
+      m_repeatMin = min;
+      m_repeatMax = max;
+        
+      return true;
+    }
+  }
+  return false;
+}
+
+bool
+RegexRepeatMatcher::match(const Name & name, const int & offset, const int & len)
+{
+  // _LOG_TRACE ("Enter RegexRepeatMatcher::match");
+
+  m_matchResult.clear();
+
+  if (0 == m_repeatMin)
+    if (0 == len)
+      return true;
+
+  if (recursiveMatch(0, name, offset, len))
+    {
+      for (int i = offset; i < offset + len; i++)
+        m_matchResult.push_back(name.get(i));
+      return true;
+    }
+  else
+    return false;
+}
+
+bool 
+RegexRepeatMatcher::recursiveMatch(int repeat, const Name & name, const int & offset, const int & len)
+{
+  // _LOG_TRACE ("Enter RegexRepeatMatcher::recursiveMatch");
+
+  // _LOG_DEBUG ("repeat: " << repeat << " offset: " << offset << " len: " << len);
+  // _LOG_DEBUG ("m_repeatMin: " << m_repeatMin << " m_repeatMax: " << m_repeatMax);
+
+  int tried = len;
+  ptr_lib::shared_ptr<RegexMatcher> matcher = m_matcherList[0];
+
+  if (0 < len && repeat >= m_repeatMax)
+    {
+      // _LOG_DEBUG("Match Fail: Reach m_repeatMax && More components");
+      return false;
+    }
+
+  if (0 == len && repeat < m_repeatMin)
+    {
+      // _LOG_DEBUG("Match Fail: No more components && have NOT reached m_repeatMin " << len << ", " << m_repeatMin);
+      return false;
+    }
+
+  if (0 == len && repeat >= m_repeatMin)
+    {
+      // _LOG_DEBUG("Match Succeed: No more components && reach m_repeatMin");
+      return true;
+    }
+    
+  while(tried >= 0)
+    {
+      // _LOG_DEBUG("Attempt tried: " << tried);
+
+      if (matcher->match(name, offset, tried) and recursiveMatch(repeat + 1, name, offset + tried, len - tried))
+        return true;
+      // _LOG_DEBUG("Failed at tried: " << tried);
+      tried --;
+    }
+
+  return false;
+}
+}//ndn
diff --git a/src/util/regex/regex-repeat-matcher.hpp b/src/util/regex/regex-repeat-matcher.hpp
new file mode 100644
index 0000000..9cc0212
--- /dev/null
+++ b/src/util/regex/regex-repeat-matcher.hpp
@@ -0,0 +1,53 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_REPEAT_MATCHER_HPP
+#define NDN_REGEX_REPEAT_MATCHER_HPP
+
+#include "regex-matcher.hpp"
+
+namespace ndn
+{
+
+class RegexRepeatMatcher : public RegexMatcher
+{
+public:
+  RegexRepeatMatcher(const std::string expr, ptr_lib::shared_ptr<RegexBackrefManager> backRefManager, int indicator);
+    
+  virtual ~RegexRepeatMatcher(){}
+
+  virtual bool 
+  match(const Name & name, const int & offset, const int & len);
+
+protected:
+  /**
+   * @brief Compile the regular expression to generate the more matchers when necessary
+   * @returns true if compiling succeeds
+   */
+  virtual void 
+  compile();
+
+
+private:
+  bool 
+  parseRepetition();
+
+  bool 
+  recursiveMatch (int repeat,
+                  const Name & name,
+                  const int & offset,
+                  const int &len);
+  
+private:
+  int m_indicator;
+  int m_repeatMin;
+  int m_repeatMax;
+};
+
+}//ndn
+
+#endif
diff --git a/src/util/regex/regex-top-matcher.cpp b/src/util/regex/regex-top-matcher.cpp
new file mode 100644
index 0000000..3e7d4ce
--- /dev/null
+++ b/src/util/regex/regex-top-matcher.cpp
@@ -0,0 +1,246 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include <stdlib.h>
+
+#include "regex-top-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexTopMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+
+RegexTopMatcher::RegexTopMatcher(const string & expr, const string & expand)
+  : RegexMatcher(expr, EXPR_TOP),
+    m_expand(expand),
+    m_secondaryUsed(false)
+{
+  // _LOG_TRACE ("Enter RegexTopMatcher Constructor");
+
+  m_primaryBackRefManager = ptr_lib::make_shared<RegexBackrefManager>();
+  m_secondaryBackRefManager = ptr_lib::make_shared<RegexBackrefManager>();
+  compile();
+
+  // _LOG_TRACE ("Exit RegexTopMatcher Constructor");
+}
+
+RegexTopMatcher::~RegexTopMatcher()
+{
+  // delete m_backRefManager;
+}
+
+void 
+RegexTopMatcher::compile()
+{
+  // _LOG_TRACE ("Enter RegexTopMatcher::compile");
+
+  string errMsg = "Error: RegexTopMatcher.Compile(): ";
+
+  string expr = m_expr;
+
+  if('$' != expr[expr.size() - 1])
+    expr = expr + "<.*>*";
+  else
+    expr = expr.substr(0, expr.size()-1);
+
+  if('^' != expr[0])
+    m_secondaryMatcher = ptr_lib::make_shared<RegexPatternListMatcher>("<.*>*" + expr, m_secondaryBackRefManager);
+  else
+    expr = expr.substr(1, expr.size()-1);
+
+  // _LOG_DEBUG ("reconstructed expr: " << expr);
+                                                        
+                                                        
+  m_primaryMatcher = ptr_lib::make_shared<RegexPatternListMatcher>(expr, m_primaryBackRefManager);
+
+  // _LOG_TRACE ("Exit RegexTopMatcher::compile");
+}
+
+bool 
+RegexTopMatcher::match(const Name & name)
+{
+  // _LOG_DEBUG("Enter RegexTopMatcher::match");
+
+  m_secondaryUsed = false;
+
+  m_matchResult.clear();
+
+  if(m_primaryMatcher->match(name, 0, name.size()))
+    {
+      m_matchResult = m_primaryMatcher->getMatchResult();
+      return true;
+    }
+  else
+    {
+      if (NULL != m_secondaryMatcher && m_secondaryMatcher->match(name, 0, name.size()))
+        {
+          m_matchResult = m_secondaryMatcher->getMatchResult();
+          m_secondaryUsed = true;
+          return true;
+        }
+      return false;
+    }
+}
+  
+bool 
+RegexTopMatcher::match (const Name & name, const int & offset, const int & len)
+{
+  return match(name);
+}
+
+Name 
+RegexTopMatcher::expand (const string & expandStr)
+{
+  // _LOG_TRACE("Enter RegexTopMatcher::expand");
+
+  Name result;
+    
+  ptr_lib::shared_ptr<RegexBackrefManager> backRefManager = (m_secondaryUsed ? m_secondaryBackRefManager : m_primaryBackRefManager);
+    
+  int backRefNum = backRefManager->size();
+
+  string expand;
+    
+  if(expandStr != "")
+    expand = expandStr;
+  else
+    expand = m_expand;
+
+  int offset = 0;
+  while(offset < expand.size())
+    {
+      string item = getItemFromExpand(expand, offset);
+      if(item[0] == '<')
+        {
+          result.append(item.substr(1, item.size() - 2));
+        }
+      if(item[0] == '\\')
+        {
+
+          int index = atoi(item.substr(1, item.size() - 1).c_str());
+
+          if(0 == index){
+            vector<Name::Component>::iterator it = m_matchResult.begin();
+            vector<Name::Component>::iterator end = m_matchResult.end();
+            for(; it != end; it++)
+              result.append (*it);
+          }
+          else if(index <= backRefNum)
+            {
+              vector<Name::Component>::const_iterator it = backRefManager->getBackRef (index - 1)->getMatchResult ().begin();
+              vector<Name::Component>::const_iterator end = backRefManager->getBackRef (index - 1)->getMatchResult ().end();
+              for(; it != end; it++)
+                result.append (*it);
+            }
+          else
+            throw RegexMatcher::Error("Exceed the range of back reference!");
+        }   
+    }
+  return result;
+}
+
+string
+RegexTopMatcher::getItemFromExpand(const string & expand, int & offset)
+{
+  // _LOG_TRACE("Enter RegexTopMatcher::getItemFromExpand ");
+  int begin = offset;
+
+  if(expand[offset] == '\\')
+    {
+      offset++;
+      if(offset >= expand.size())
+        throw RegexMatcher::Error("wrong format of expand string!");
+
+      while(expand[offset] <= '9' and expand[offset] >= '0'){
+        offset++;
+        if(offset > expand.size())
+          throw RegexMatcher::Error("wrong format of expand string!");
+      }
+      if(offset > begin + 1)
+        return expand.substr(begin, offset - begin);
+      else
+        throw RegexMatcher::Error("wrong format of expand string!");
+    }
+  else if(expand[offset] == '<')
+    {
+      offset++;
+      if(offset >= expand.size())
+        throw RegexMatcher::Error("wrong format of expand string!");
+        
+      int left = 1;
+      int right = 0;
+      while(right < left)
+        {
+          if(expand[offset] == '<')
+            left++;
+          if(expand[offset] == '>')
+            right++;            
+          offset++;
+          if(offset >= expand.size())
+            throw RegexMatcher::Error("wrong format of expand string!");
+        }
+      return expand.substr(begin, offset - begin);
+    }
+  else
+    throw RegexMatcher::Error("wrong format of expand string!");
+}
+
+ptr_lib::shared_ptr<RegexTopMatcher>
+RegexTopMatcher::fromName(const Name& name, bool hasAnchor)
+{
+  Name::const_iterator it = name.begin();
+  string regexStr("^");
+    
+  for(; it != name.end(); it++)
+    {
+      regexStr.append("<");
+      regexStr.append(convertSpecialChar(it->toEscapedString()));
+      regexStr.append(">");
+    }
+
+  if(hasAnchor)
+    regexStr.append("$");
+
+  return ptr_lib::make_shared<RegexTopMatcher>(regexStr);
+}
+
+string
+RegexTopMatcher::convertSpecialChar(const string& str)
+{
+  string newStr;
+  for(int i = 0; i < str.size(); i++)
+    {
+      char c = str[i];
+      switch(c)
+        {
+        case '.':
+        case '[':
+        case '{':
+        case '}':
+        case '(':
+        case ')':
+        case '\\':
+        case '*':
+        case '+':
+        case '?':
+        case '|':
+        case '^':
+        case '$':
+          newStr.push_back('\\');
+        default:
+          newStr.push_back(c);
+        }
+    }
+
+  return newStr;
+}
+
+}//ndn
diff --git a/src/util/regex/regex-top-matcher.hpp b/src/util/regex/regex-top-matcher.hpp
new file mode 100644
index 0000000..764726f
--- /dev/null
+++ b/src/util/regex/regex-top-matcher.hpp
@@ -0,0 +1,60 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_TOP_MATCHER_HPP
+#define NDN_REGEX_TOP_MATCHER_HPP
+
+#include <string>
+
+#include "regex-matcher.hpp"
+#include "regex-pattern-list-matcher.hpp"
+
+namespace ndn
+{
+class RegexTopMatcher: public RegexMatcher
+{
+public:
+  RegexTopMatcher(const std::string & expr, const std::string & expand = "");
+    
+  virtual ~RegexTopMatcher();
+
+  bool 
+  match(const Name & name);
+
+  virtual bool
+  match (const Name & name, const int & offset, const int & len);
+
+  virtual Name 
+  expand (const std::string & expand = "");
+
+  static ptr_lib::shared_ptr<RegexTopMatcher>
+  fromName(const Name& name, bool hasAnchor=false);
+
+protected:
+  virtual void 
+  compile();
+
+private:
+  std::string
+  getItemFromExpand(const std::string & expand, int & offset);
+
+  static std::string
+  convertSpecialChar(const std::string& str);
+
+private:
+  const std::string m_expand;
+  ptr_lib::shared_ptr<RegexPatternListMatcher> m_primaryMatcher;
+  ptr_lib::shared_ptr<RegexPatternListMatcher> m_secondaryMatcher;
+  ptr_lib::shared_ptr<RegexBackrefManager> m_primaryBackRefManager;
+  ptr_lib::shared_ptr<RegexBackrefManager> m_secondaryBackRefManager;
+  bool m_secondaryUsed;
+};
+
+}
+
+#endif
+
diff --git a/tests/test-regex.cpp b/tests/test-regex.cpp
new file mode 100644
index 0000000..75ca0fe
--- /dev/null
+++ b/tests/test-regex.cpp
@@ -0,0 +1,449 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include <boost/test/unit_test.hpp>
+
+#include "util/regex/regex-backref-manager.hpp"
+#include "util/regex/regex-component-matcher.hpp"
+#include "util/regex/regex-component-set-matcher.hpp"
+#include "util/regex/regex-pattern-list-matcher.hpp"
+#include "util/regex/regex-repeat-matcher.hpp"
+#include "util/regex/regex-backref-matcher.hpp"
+#include "util/regex/regex-top-matcher.hpp"
+#include "util/regex.hpp"
+
+#include <iostream>
+
+using namespace ndn;
+using namespace std;
+
+BOOST_AUTO_TEST_SUITE(TestRegex)
+
+BOOST_AUTO_TEST_CASE(ComponentMatcher)
+{
+
+  ptr_lib::shared_ptr<RegexBackrefManager> backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  ptr_lib::shared_ptr<RegexComponentMatcher> cm = ptr_lib::make_shared<RegexComponentMatcher>("a", backRef);
+  bool res = cm->match(Name("/a/b/"), 0, 1);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 1);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexComponentMatcher>("a", backRef);
+  res = cm->match(Name("/a/b/"), 1, 1);
+  BOOST_CHECK_EQUAL(res, false);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexComponentMatcher>("(c+)\\.(cd)", backRef);
+  res = cm->match(Name("/ccc.cd/b/"), 0, 1);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 1);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("ccc.cd"));
+  BOOST_CHECK_EQUAL(backRef->getBackRef (0)->getMatchResult ()[0].toEscapedString(), string("ccc"));
+  BOOST_CHECK_EQUAL(backRef->getBackRef (1)->getMatchResult ()[0].toEscapedString(), string("cd"));
+}
+
+BOOST_AUTO_TEST_CASE (ComponentSetMatcher)
+{
+
+  ptr_lib::shared_ptr<RegexBackrefManager> backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  ptr_lib::shared_ptr<RegexComponentSetMatcher> cm = ptr_lib::make_shared<RegexComponentSetMatcher>("<a>", backRef);
+  bool res = cm->match(Name("/a/b/"), 0, 1);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 1);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+    
+  res = cm->match(Name("/a/b/"), 1, 1);
+  BOOST_CHECK_EQUAL(res, false);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+    
+  res = cm->match(Name("/a/b/"), 0, 2);
+  BOOST_CHECK_EQUAL(res, false);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexComponentSetMatcher>("[<a><b><c>]", backRef);
+  res = cm->match(Name("/a/b/d"), 1, 1);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 1);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("b"));
+
+  res = cm->match(Name("/a/b/d"), 2, 1);
+  BOOST_CHECK_EQUAL(res, false);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+ 
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexComponentSetMatcher>("[^<a><b><c>]", backRef);
+  res = cm->match(Name("/b/d"), 1, 1);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 1);    
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("d"));
+
+}
+
+BOOST_AUTO_TEST_CASE (RepeatMatcher)
+{
+
+  ptr_lib::shared_ptr<RegexBackrefManager> backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  ptr_lib::shared_ptr<RegexRepeatMatcher> cm = ptr_lib::make_shared<RegexRepeatMatcher>("[<a><b>]*", backRef, 8);
+  bool res = cm->match(Name("/a/b/c"), 0, 0);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+
+  cm->match(Name("/a/b/c"), 0, 2);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 2);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+
+
+
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexRepeatMatcher>("[<a><b>]+", backRef, 8);
+  res = cm->match(Name("/a/b/c"), 0, 0);
+  BOOST_CHECK_EQUAL(res, false);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+
+  res = cm->match(Name("/a/b/c"), 0, 2);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 2);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+
+
+
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexRepeatMatcher>("<.*>*", backRef, 4);
+  res = cm->match(Name("/a/b/c/d/e/f/"), 0, 6);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 6);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[2].toEscapedString(), string("c"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[3].toEscapedString(), string("d"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[4].toEscapedString(), string("e"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[5].toEscapedString(), string("f"));
+
+
+
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexRepeatMatcher>("<>*", backRef, 2);
+  res = cm->match(Name("/a/b/c/d/e/f/"), 0, 6);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 6);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[2].toEscapedString(), string("c"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[3].toEscapedString(), string("d"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[4].toEscapedString(), string("e"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[5].toEscapedString(), string("f"));
+
+
+
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexRepeatMatcher>("<a>?", backRef, 3);
+  res = cm->match(Name("/a/b/c"), 0, 0);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+
+  cm = ptr_lib::make_shared<RegexRepeatMatcher>("<a>?", backRef, 3);
+  res = cm->match(Name("/a/b/c"), 0, 1);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 1);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+
+  cm = ptr_lib::make_shared<RegexRepeatMatcher>("<a>?", backRef, 3);
+  res = cm->match(Name("/a/b/c"), 0, 2);
+  BOOST_CHECK_EQUAL(res, false);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+
+
+
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexRepeatMatcher>("[<a><b>]{3}", backRef, 8);
+  res = cm->match(Name("/a/b/a/d/"), 0, 2);
+  BOOST_CHECK_EQUAL(res, false);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+
+  res = cm->match(Name("/a/b/a/d/"), 0, 3);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 3);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[2].toEscapedString(), string("a"));
+
+  res = cm->match(Name("/a/b/a/d/"), 0, 4);
+  BOOST_CHECK_EQUAL(res, false);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+
+
+
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexRepeatMatcher>("[<a><b>]{2,3}", backRef, 8);
+  res = cm->match(Name("/a/b/a/d/e/"), 0, 2);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 2);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+
+  res = cm->match(Name("/a/b/a/d/e/"), 0, 3);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 3);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[2].toEscapedString(), string("a"));
+
+  res = cm->match(Name("/a/b/a/b/e/"), 0, 4);
+  BOOST_CHECK_EQUAL(res, false);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+
+  res = cm->match(Name("/a/b/a/d/e/"), 0, 1);
+  BOOST_CHECK_EQUAL(res, false);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+
+
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexRepeatMatcher>("[<a><b>]{2,}", backRef, 8);
+  res = cm->match(Name("/a/b/a/d/e/"), 0, 2);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 2);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+
+  res = cm->match(Name("/a/b/a/b/e/"), 0, 4);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 4);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[2].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[3].toEscapedString(), string("b"));
+
+  res = cm->match(Name("/a/b/a/d/e/"), 0, 1);
+  BOOST_CHECK_EQUAL(res, false);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+
+
+    
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexRepeatMatcher>("[<a><b>]{,2}", backRef, 8);
+  res = cm->match(Name("/a/b/a/b/e/"), 0, 3);
+  BOOST_CHECK_EQUAL(res, false);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+
+  res = cm->match(Name("/a/b/a/b/e/"), 0, 2);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 2);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+
+  res = cm->match(Name("/a/b/a/d/e/"), 0, 1);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 1);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+
+  res = cm->match(Name("/a/b/a/d/e/"), 0, 0);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+}
+
+BOOST_AUTO_TEST_CASE (BackRefMatcher)
+{
+
+  ptr_lib::shared_ptr<RegexBackrefManager> backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  ptr_lib::shared_ptr<RegexBackrefMatcher> cm = ptr_lib::make_shared<RegexBackrefMatcher>("(<a><b>)", backRef);
+  backRef->pushRef(boost::static_pointer_cast<RegexMatcher>(cm));
+  cm->lateCompile();
+  bool res = cm->match(Name("/a/b/c"), 0, 2);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 2);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(backRef->size(), 1);
+
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexBackrefMatcher>("(<a>(<b>))", backRef);
+  backRef->pushRef(cm);
+  cm->lateCompile();
+  res = cm->match(Name("/a/b/c"), 0, 2);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 2);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(backRef->size(), 2);
+  BOOST_CHECK_EQUAL(backRef->getBackRef (0)->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(backRef->getBackRef (0)->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(backRef->getBackRef (1)->getMatchResult ()[0].toEscapedString(), string("b"));
+}
+
+BOOST_AUTO_TEST_CASE (BackRefMatcherAdvanced)
+{
+
+  ptr_lib::shared_ptr<RegexBackrefManager> backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  ptr_lib::shared_ptr<RegexRepeatMatcher> cm = ptr_lib::make_shared<RegexRepeatMatcher>("([<a><b>])+", backRef, 10);
+  bool res = cm->match(Name("/a/b/c"), 0, 2);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 2);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(backRef->size(), 1);
+  BOOST_CHECK_EQUAL(backRef->getBackRef (0)->getMatchResult ()[0].toEscapedString(), string("b"));
+}
+
+BOOST_AUTO_TEST_CASE (BackRefMatcherAdvanced2)
+{
+
+  ptr_lib::shared_ptr<RegexBackrefManager> backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  ptr_lib::shared_ptr<RegexPatternListMatcher> cm = ptr_lib::make_shared<RegexPatternListMatcher>("(<a>(<b>))<c>", backRef);
+  bool res = cm->match(Name("/a/b/c"), 0, 3);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 3);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[2].toEscapedString(), string("c"));
+  BOOST_CHECK_EQUAL(backRef->size(), 2);
+  BOOST_CHECK_EQUAL(backRef->getBackRef (0)->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(backRef->getBackRef (0)->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(backRef->getBackRef (1)->getMatchResult ()[0].toEscapedString(), string("b"));
+}
+
+BOOST_AUTO_TEST_CASE (PatternListMatcher)
+{
+
+  ptr_lib::shared_ptr<RegexBackrefManager> backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  ptr_lib::shared_ptr<RegexPatternListMatcher> cm = ptr_lib::make_shared<RegexPatternListMatcher>("<a>[<a><b>]", backRef);
+  bool res = cm->match(Name("/a/b/c"), 0, 2);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 2);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexPatternListMatcher>("<>*<a>", backRef);
+  res = cm->match(Name("/a/b/c"), 0, 1);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 1);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexPatternListMatcher>("<>*<a>", backRef);
+  res = cm->match(Name("/a/b/c"), 0, 2);
+  BOOST_CHECK_EQUAL(res, false);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+
+  backRef = ptr_lib::make_shared<RegexBackrefManager>();
+  cm = ptr_lib::make_shared<RegexPatternListMatcher>("<>*<a><>*", backRef);
+  res = cm->match(Name("/a/b/c"), 0, 3);
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 3);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[2].toEscapedString(), string("c"));
+
+}
+
+BOOST_AUTO_TEST_CASE (TopMatcher)
+{
+
+  ptr_lib::shared_ptr<RegexTopMatcher> cm = ptr_lib::make_shared<RegexTopMatcher>("^<a><b><c>");
+  bool res = cm->match(Name("/a/b/c/d"));
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 4);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[2].toEscapedString(), string("c"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[3].toEscapedString(), string("d"));
+
+  cm = ptr_lib::make_shared<RegexTopMatcher>("<b><c><d>$");
+  res = cm->match(Name("/a/b/c/d"));
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 4);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[2].toEscapedString(), string("c"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[3].toEscapedString(), string("d"));
+
+  cm = ptr_lib::make_shared<RegexTopMatcher>("^<a><b><c><d>$");
+  res = cm->match(Name("/a/b/c/d"));
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 4);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[2].toEscapedString(), string("c"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[3].toEscapedString(), string("d"));
+
+  res = cm->match(Name("/a/b/c/d/e"));
+  BOOST_CHECK_EQUAL(res, false);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 0);
+
+  cm = ptr_lib::make_shared<RegexTopMatcher>("<a><b><c><d>");
+  res = cm->match(Name("/a/b/c/d"));
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 4);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[2].toEscapedString(), string("c"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[3].toEscapedString(), string("d"));
+
+
+  cm = ptr_lib::make_shared<RegexTopMatcher>("<b><c>");
+  res = cm->match(Name("/a/b/c/d"));
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 4);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[0].toEscapedString(), string("a"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[1].toEscapedString(), string("b"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[2].toEscapedString(), string("c"));
+  BOOST_CHECK_EQUAL(cm->getMatchResult ()[3].toEscapedString(), string("d"));
+}
+
+BOOST_AUTO_TEST_CASE (TopMatcherAdvanced)
+{
+  ptr_lib::shared_ptr<Regex> cm = ptr_lib::make_shared<Regex>("^(<.*>*)<.*>");
+  bool res = cm->match(Name("/n/a/b/c"));
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 4);
+  BOOST_CHECK_EQUAL(cm->expand("\\1"), Name("/n/a/b/"));
+
+  cm = ptr_lib::make_shared<Regex>("^(<.*>*)<.*><c>(<.*>)<.*>");
+  res = cm->match(Name("/n/a/b/c/d/e/"));
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 6);
+  BOOST_CHECK_EQUAL(cm->expand("\\1\\2"), Name("/n/a/d/"));
+
+  cm = ptr_lib::make_shared<Regex>("(<.*>*)<.*>$");
+  res = cm->match(Name("/n/a/b/c/"));
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 4);
+  BOOST_CHECK_EQUAL(cm->expand("\\1"), Name("/n/a/b/"));
+
+  cm = ptr_lib::make_shared<Regex>("<.*>(<.*>*)<.*>$");
+  res = cm->match(Name("/n/a/b/c/"));
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 4);
+  BOOST_CHECK_EQUAL(cm->expand("\\1"), Name("/a/b/"));
+
+  cm = ptr_lib::make_shared<Regex>("<a>(<>*)<>$");
+  res = cm->match(Name("/n/a/b/c/"));
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 4);
+  BOOST_CHECK_EQUAL(cm->expand("\\1"), Name("/b/"));
+
+  cm = ptr_lib::make_shared<Regex>("^<ndn><(.*)\\.(.*)><DNS>(<>*)<>");
+  res = cm->match(Name("/ndn/ucla.edu/DNS/yingdi/mac/ksk-1/"));
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 6);
+  BOOST_CHECK_EQUAL(cm->expand("<ndn>\\2\\1\\3"), Name("/ndn/edu/ucla/yingdi/mac/"));
+
+  cm = ptr_lib::make_shared<Regex>("^<ndn><(.*)\\.(.*)><DNS>(<>*)<>", "<ndn>\\2\\1\\3");
+  res = cm->match(Name("/ndn/ucla.edu/DNS/yingdi/mac/ksk-1/"));
+  BOOST_CHECK_EQUAL(res, true);
+  BOOST_CHECK_EQUAL(cm->getMatchResult ().size(), 6);
+  BOOST_CHECK_EQUAL(cm->expand(), Name("/ndn/edu/ucla/yingdi/mac/"));
+}
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/wscript b/wscript
index acc8d77..fdf8615 100644
--- a/wscript
+++ b/wscript
@@ -86,7 +86,7 @@
         conf.define('HAVE_CXX11', 1)
     else:
         if conf.options.use_system_boost:
-            USED_BOOST_LIBS = 'system filesystem date_time iostreams'
+            USED_BOOST_LIBS = 'system filesystem date_time iostreams regex'
             if conf.env['WITH_TESTS']:
                 USED_BOOST_LIBS += " unit_test_framework"