diff --git a/clang/include/clang/Tooling/Syntax/Corpus.h b/clang/include/clang/Tooling/Syntax/Corpus.h
new file mode 100644
--- /dev/null
+++ b/clang/include/clang/Tooling/Syntax/Corpus.h
@@ -0,0 +1,61 @@
+//===- Corpus.h - memory arena and bookkeeping for syntax trees --- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLING_SYNTAX_CORPUS_H
+#define LLVM_CLANG_TOOLING_SYNTAX_CORPUS_H
+
+#include "clang/Basic/LangOptions.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Tooling/Syntax/Tokens.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/Allocator.h"
+
+namespace clang {
+namespace syntax {
+/// A memory arena for syntax trees. In addition, it also tracks the underlying
+/// token buffers, source manager, etc.
+class Corpus {
+public:
+  Corpus(SourceManager &SourceMgr, const LangOptions &LangOpts,
+         TokenBuffer MainFile);
+
+  const SourceManager &sourceManager() const { return SourceMgr; }
+  const LangOptions &langOptions() const { return LangOpts; }
+
+  const TokenBuffer &tokenBuffer() const;
+  llvm::BumpPtrAllocator &allocator() { return Allocator; }
+
+  /// Add \p Buffer to the underlying source manager, tokenize it and store the
+  /// resulting tokens. Useful when there is a need to materialize tokens that
+  /// were not written in user code.
+  std::pair<FileID, llvm::ArrayRef<syntax::Token>>
+  tokenizeBuffer(std::unique_ptr<llvm::MemoryBuffer> Buffer);
+
+  /// Construct a new syntax node of a specified kind. The memory for a node is
+  /// owned by the corpus and will be freed when the corpus is destroyed.
+  template <class TNode, class... Args> TNode *construct(Args &&... As) {
+    static_assert(std::is_trivially_destructible<TNode>::value,
+                  "nodes should be trivially destructible");
+    return new (Allocator) TNode(std::forward<Args>(As)...);
+  }
+
+private:
+  SourceManager &SourceMgr;
+  const LangOptions &LangOpts;
+  TokenBuffer Tokens;
+  /// IDs and storage for additional tokenized files.
+  llvm::DenseMap<FileID, std::vector<syntax::Token>> ExtraTokens;
+  /// Keeps all the allocated nodes and their intermediate data structures.
+  llvm::BumpPtrAllocator Allocator;
+};
+
+} // namespace syntax
+} // namespace clang
+
+#endif
diff --git a/clang/include/clang/Tooling/Syntax/Tree.h b/clang/include/clang/Tooling/Syntax/Tree.h
new file mode 100644
--- /dev/null
+++ b/clang/include/clang/Tooling/Syntax/Tree.h
@@ -0,0 +1,45 @@
+//===- Tree.h - syntax trees ----------------------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Syntax tree is a parse tree for the C++ source code designed to allow
+// mutations.
+//
+// The code is divided in the following way:
+//   - 'Tree/Cascade.h' defines the basic structure of the syntax tree,
+//   - 'Tree/Nodes.h' defines the concrete node classes, corresponding to the
+//   - 'Tree.h' (this file) defines basic operations for constucting and
+//      traversing a syntax tree.
+//
+// This is still work in progress and highly experimental, we leave room for
+// ourselves to completely change the design and/or implementation.
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLING_SYNTAX_TREE_H
+#define LLVM_CLANG_TOOLING_SYNTAX_TREE_H
+
+#include "clang/AST/Decl.h"
+#include "clang/Tooling/Core/Replacement.h"
+#include "clang/Tooling/Syntax/Corpus.h"
+#include "clang/Tooling/Syntax/Tree/Cascade.h"
+#include "clang/Tooling/Syntax/Tree/Nodes.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
+
+namespace clang {
+namespace syntax {
+
+/// Build a syntax tree for the main file.
+TranslationUnit *buildSyntaxTree(Corpus &C,
+                                 const clang::TranslationUnitDecl &TU);
+
+/// Perform a post-order traversal of the syntax tree, calling \p Visit at each
+/// node.
+void traverse(Node *N, llvm::function_ref<void(Node *)> Visit);
+void traverse(const Node *N, llvm::function_ref<void(const Node *)> Visit);
+
+} // namespace syntax
+} // namespace clang
+#endif
diff --git a/clang/include/clang/Tooling/Syntax/Tree/Cascade.h b/clang/include/clang/Tooling/Syntax/Tree/Cascade.h
new file mode 100644
--- /dev/null
+++ b/clang/include/clang/Tooling/Syntax/Tree/Cascade.h
@@ -0,0 +1,105 @@
+//===- Tree.h - cascade of the syntax tree --------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Defines the basic structure of the syntax tree. There are two kinds of nodes
+// in a tree:
+//   - leaf nodes correspond to a continuous subrange of tokens in expanded
+//     token stream.
+//   - composite (or tree) nodes correspond to language grammar constructs.
+//
+// The tree is initially built from an AST. Each node of a newly built tree
+// covers a continous subrange of expanded tokens (i.e. tokens after
+// preprocessing), the specific tokens coverered are stored in the leaf nodes of
+// a tree. A post-order traversal of a tree will visit leaf nodes in an order
+// corresponding the original order of expanded tokens.
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLING_SYNTAX_TREE_CASCADE_H
+#define LLVM_CLANG_TOOLING_SYNTAX_TREE_CASCADE_H
+
+#include "clang/Basic/TokenKinds.h"
+#include "clang/Tooling/Syntax/Corpus.h"
+#include "clang/Tooling/Syntax/Tree/NodeKind.h"
+#include "clang/Tooling/Syntax/Tree/NodeList.h"
+#include "llvm/ADT/ArrayRef.h"
+
+namespace clang {
+namespace syntax {
+
+class TreeNode;
+class TreeBuilder;
+class Corpus;
+
+/// A node in a syntax tree. Knows only about its parent and kind.
+class Node {
+public:
+  Node(NodeKind Kind) : Parent(nullptr), Kind(Kind) {}
+  NodeKind kind() const { return Kind; }
+
+  const TreeNode *parent() const { return Parent; }
+  TreeNode *parent() { return Parent; }
+
+  /// Dumps the structure of a subtree. For debugging and testing purposes.
+  std::string dump(const Corpus &C) const;
+  /// Dumps the tokens forming this subtree.
+  std::string dumpTokens(const Corpus &C) const;
+
+private:
+  // TreeNode is allowed to change the Parent link.
+  friend class TreeNode;
+  TreeNode *Parent;
+  NodeKind Kind;
+};
+
+
+/// A leaf node points to a consecutive range of tokens in the expanded token
+/// stream.
+class Leaf final : public Node {
+public:
+  Leaf(llvm::ArrayRef<syntax::Token> Tokens)
+      : Node(NodeKind::Leaf), Tokens(Tokens) {}
+
+  static bool classof(const Node *N) { return N->kind() == NodeKind::Leaf; }
+
+  llvm::ArrayRef<syntax::Token> tokens() const { return Tokens; }
+
+private:
+  llvm::ArrayRef<Token> Tokens;
+};
+
+/// A composite tree node that has children.
+class TreeNode : public Node {
+public:
+  using Node::Node;
+  static bool classof(const Node *N) { return N->kind() > NodeKind::Leaf; }
+
+  llvm::ArrayRef<Node *> children() {
+    return llvm::makeArrayRef(Children.begin(), Children.end());
+  }
+  llvm::ArrayRef<const Node *> children() const {
+    return llvm::makeArrayRef(Children.begin(), Children.end());
+  }
+
+protected:
+  /// Find a leaf with a single token of a corresponding kind.
+  /// EXPECTS: the leaf node of a corresponding kind is found.
+  /// ENSURES: the result is non-null.
+  syntax::Leaf* findLeaf(tok::TokenKind K);
+
+private:
+  /// Appends \p Child to the list of children and and sets the parent pointer.
+  /// A very low-level operation that does not check any invariants, only used
+  /// by TreeBuilder.
+  void appendChildLowLevel(Corpus &C, Node *Child);
+  friend class TreeBuilder;
+
+  NodeList Children;
+};
+
+} // namespace syntax
+} // namespace clang
+
+#endif
diff --git a/clang/include/clang/Tooling/Syntax/Tree/NodeKind.h b/clang/include/clang/Tooling/Syntax/Tree/NodeKind.h
new file mode 100644
--- /dev/null
+++ b/clang/include/clang/Tooling/Syntax/Tree/NodeKind.h
@@ -0,0 +1,26 @@
+//===- NodeKind.h - an enum listing nodes of a syntax tree ----*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLING_SYNTAX_TREE_NODEKIND_H
+#define LLVM_CLANG_TOOLING_SYNTAX_TREE_NODEKIND_H
+#include "llvm/ADT/StringRef.h"
+namespace clang {
+namespace syntax {
+/// A kind of a syntax node, used for implementing casts.
+enum class NodeKind {
+  Leaf,
+  RecoveryNode,
+  TranslationUnit,
+  TopLevelDecl,
+  CompoundStatement,
+};
+/// For debugging purposes.
+llvm::StringRef toString(NodeKind K);
+
+} // namespace syntax
+} // namespace clang
+#endif
diff --git a/clang/include/clang/Tooling/Syntax/Tree/NodeList.h b/clang/include/clang/Tooling/Syntax/Tree/NodeList.h
new file mode 100644
--- /dev/null
+++ b/clang/include/clang/Tooling/Syntax/Tree/NodeList.h
@@ -0,0 +1,111 @@
+//===- NodeList.h ---------------------------------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// A helper for storing a mutable of nodes allocated in an arena.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_SYNTAX_TREE_NODELIST_H
+#define LLVM_CLANG_TOOLING_SYNTAX_TREE_NODELIST_H
+
+#include "llvm/Support/Allocator.h"
+#include <algorithm>
+#include <cstddef>
+#include <type_traits>
+
+namespace clang {
+namespace syntax {
+namespace detail {
+template <class T> class BumpAllocVector;
+}
+class Node;
+/// Like vector<Node*>, but allocates all the memory in the BumpPtrAllocator.
+/// Can be dropped without running the destructor.
+using NodeList = detail::BumpAllocVector<Node *>;
+
+namespace detail {
+/// A vector that requests memory from BumpPtrAllocator and has a trivial
+/// destructor. Syntax tree nodes use it to store children.
+/// FIXME: make implementation more sanitizer-friendly to allow catching
+///        out-of-bounds accesses.
+template <class T> class BumpAllocVector {
+  // Make sure the elements do not require their destructors to run.
+  static_assert(std::is_trivially_destructible<T>::value,
+                "T must be trivially destructible");
+  // Assumption to simplify the implementation. We only store pointers, so this
+  // should hold.
+  static_assert(std::is_trivially_copyable<T>::value,
+                "T must be trivially copyable.");
+
+public:
+  T *begin() { return Begin; }
+  T *end() { return End; }
+
+  const T *begin() const { return Begin; }
+  const T *end() const { return End; }
+
+  bool empty() const { return begin() == end(); }
+  size_t size() const { return End - Begin; }
+  size_t capacity() const { return StorageEnd - Begin; }
+
+  void push_back(llvm::BumpPtrAllocator &A, T Element) {
+    if (StorageEnd == End)
+      Grow(A);
+    *End = Element;
+    ++End;
+  }
+
+  T *erase(T *Begin, T *End) {
+    std::ptrdiff_t ErasedSize = End - Begin;
+    for (auto *It = End; It != this->End; ++It) {
+      *Begin = *It;
+      ++Begin;
+    }
+    this->End -= ErasedSize;
+    return Begin;
+  }
+
+  T *insert(llvm::BumpPtrAllocator &A, T *Pos, T *Begin, T *End) {
+    unsigned ToAdd = End - Begin;
+    if (capacity() - size() < ToAdd)
+      Grow(A, size() + ToAdd);
+    std::rotate(Pos, Pos + ToAdd, End + ToAdd);
+    std::copy(Begin, End, Pos);
+    this->End += ToAdd;
+    return Pos;
+  }
+
+private:
+  void Grow(llvm::BumpPtrAllocator &A, unsigned MinSize = 0) {
+    size_t Size = End - Begin;
+
+    size_t NewCapacity = 2 * (StorageEnd - Begin);
+    if (NewCapacity == 0)
+      NewCapacity = 1;
+    while (NewCapacity < MinSize)
+      NewCapacity = 2 * NewCapacity;
+
+    T *NewStorage = A.Allocate<T>(NewCapacity);
+    std::copy(Begin, End, NewStorage);
+
+    A.Deallocate(Begin, StorageEnd - Begin);
+
+    Begin = NewStorage;
+    End = NewStorage + Size;
+    StorageEnd = NewStorage + NewCapacity;
+  }
+
+private:
+  T *Begin = nullptr;
+  T *End = nullptr;
+  T *StorageEnd = nullptr;
+};
+} // namespace detail
+
+} // namespace syntax
+} // namespace clang
+
+#endif
diff --git a/clang/include/clang/Tooling/Syntax/Tree/Nodes.h b/clang/include/clang/Tooling/Syntax/Tree/Nodes.h
new file mode 100644
--- /dev/null
+++ b/clang/include/clang/Tooling/Syntax/Tree/Nodes.h
@@ -0,0 +1,70 @@
+//===- Nodes.h - syntax nodes for C/C++ grammar constructs ----*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Syntax tree nodes for C, C++ and Objective-C grammar constructs.
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLING_SYNTAX_TREE_NODES_H
+#define LLVM_CLANG_TOOLING_SYNTAX_TREE_NODES_H
+#include "clang/Basic/TokenKinds.h"
+#include "clang/Lex/Token.h"
+#include "clang/Tooling/Syntax/Tokens.h"
+#include "clang/Tooling/Syntax/Tree/Cascade.h"
+#include "clang/Tooling/Syntax/Tree/NodeList.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/StringRef.h"
+namespace clang {
+namespace syntax {
+
+/// A root node for a translation unit. Parent is always null.
+class TranslationUnit final : public TreeNode {
+public:
+  TranslationUnit() : TreeNode(NodeKind::TranslationUnit) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::TranslationUnit;
+  }
+};
+
+/// A tree node of an unknown kind, i.e. a syntax error or a construct from the
+/// clang AST without a syntax counterpart.
+/// These nodes can appear at any place in the syntax tree.
+class RecoveryNode final : public TreeNode {
+public:
+  RecoveryNode() : TreeNode(NodeKind::RecoveryNode) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::RecoveryNode;
+  }
+};
+
+/// FIXME: this node is temporary and will be replaced with nodes for various
+///        'declarations' and 'declarators' from the C/C++ grammar
+///
+/// Represents any top-level declaration. Only there to give the syntax tree a
+/// bit of structure until we implement syntax nodes for declarations and
+/// declarators.
+class TopLevelDecl final : public TreeNode {
+public:
+  TopLevelDecl() : TreeNode(NodeKind::TopLevelDecl) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::TopLevelDecl;
+  }
+};
+
+/// Represents a compound statement.
+class CompoundStatement final : public TreeNode {
+public:
+  CompoundStatement() : TreeNode(NodeKind::CompoundStatement) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::CompoundStatement;
+  }
+
+  Leaf *lbrace();
+  Leaf *rbrace();
+};
+
+} // namespace syntax
+} // namespace clang
+#endif
diff --git a/clang/lib/Tooling/Syntax/BuildFromAST.cpp b/clang/lib/Tooling/Syntax/BuildFromAST.cpp
new file mode 100644
--- /dev/null
+++ b/clang/lib/Tooling/Syntax/BuildFromAST.cpp
@@ -0,0 +1,221 @@
+//===- BuildFromAST.cpp ---------------------------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/TokenKinds.h"
+#include "clang/Lex/Lexer.h"
+#include "clang/Tooling/Syntax/Corpus.h"
+#include "clang/Tooling/Syntax/Tokens.h"
+#include "clang/Tooling/Syntax/Tree.h"
+#include "clang/Tooling/Syntax/Tree/Cascade.h"
+#include "clang/Tooling/Syntax/Tree/Nodes.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Casting.h"
+
+using namespace clang;
+
+/// A helper class for constructing the syntax tree while traversing a clang
+/// AST. The tree is built left-to-right and bottom-up. At each point of the
+/// traversal we maintain a list of currently processed nodes.
+class syntax::TreeBuilder {
+public:
+  TreeBuilder(syntax::Corpus &Corpus) : Corpus(Corpus) {}
+
+  syntax::Corpus &corpus() { return Corpus; }
+
+  /// Populate children for \p New, assuming it covers the token range with
+  /// tokens covered located at \p First and \p Last (inclusive!).
+  /// All currently processed nodes which fall into the range between \p First
+  /// and \p Last are added as children of the new node.
+  void learnNode(SourceLocation Fist, SourceLocation Last,
+                 syntax::TreeNode *New);
+
+  /// Add a leaf node for a token starting at \p Loc.
+  void learnTokenNode(SourceLocation Loc, tok::TokenKind Kind);
+
+  /// Finish building the tree and create a root TranslationUnit node. No
+  /// further calls to learn* methods are allowed after this call.
+  void learnRoot();
+
+  /// Consume the root node.
+  syntax::TranslationUnit *root() && {
+    assert(Root);
+    assert(NodesInProgress.empty());
+    return Root;
+  }
+
+private:
+  struct RangedNode {
+    RangedNode(llvm::ArrayRef<syntax::Token> Tokens, syntax::Node *Node)
+        : Tokens(Tokens), Node(Node) {}
+
+    llvm::ArrayRef<syntax::Token> Tokens;
+    syntax::Node *Node;
+  };
+  const syntax::Token *findToken(SourceLocation TokLoc) const;
+
+  void learnNodeImpl(const syntax::Token *Begin, const syntax::Token *End,
+                     syntax::TreeNode *New);
+
+  syntax::Corpus &Corpus;
+  std::vector<RangedNode> NodesInProgress;
+  syntax::TranslationUnit *Root = nullptr;
+};
+
+namespace {
+class BuildTreeVisitor : public RecursiveASTVisitor<BuildTreeVisitor> {
+public:
+  explicit BuildTreeVisitor(ASTContext &Ctx, syntax::TreeBuilder &Builder)
+      : Builder(Builder), LangOpts(Ctx.getLangOpts()) {}
+
+  bool shouldTraversePostOrder() const { return true; }
+
+  bool TraverseDecl(Decl *D) {
+    if (!D || isa<TranslationUnitDecl>(D))
+      return RecursiveASTVisitor::TraverseDecl(D);
+    if (!llvm::isa<TranslationUnitDecl>(D->getDeclContext()))
+      return true; // Only build top-level decls for now, do not recurse.
+    return RecursiveASTVisitor::TraverseDecl(D);
+  }
+
+  bool TraverseCompoundStmt(CompoundStmt *S) {
+    Builder.learnTokenNode(S->getLBracLoc(), tok::l_brace);
+    Builder.learnTokenNode(S->getRBracLoc(), tok::r_brace);
+
+    Builder.learnNode(S->getBeginLoc(), S->getEndLoc(),
+                      corpus().construct<syntax::CompoundStatement>());
+    // (!) we do not recurse into compound statements for now.
+    return true;
+  }
+
+  bool VisitDecl(Decl *D) {
+    assert(llvm::isa<TranslationUnitDecl>(D->getDeclContext()) &&
+           "expected a top-level decl");
+    assert(!D->isImplicit());
+    Builder.learnNode(D->getBeginLoc(), D->getEndLoc(),
+                      corpus().construct<syntax::TopLevelDecl>());
+    return true;
+  }
+
+  bool WalkUpFromTranslationUnitDecl(TranslationUnitDecl *TU) {
+    Builder.learnRoot();
+    // (!) we do not want to call VisitDecl() at this point.
+    return true;
+  }
+
+private:
+  /// A small helper to save some typing.
+  syntax::Corpus &corpus() { return Builder.corpus(); }
+
+  syntax::TreeBuilder &Builder;
+  const LangOptions &LangOpts;
+};
+} // namespace
+
+void syntax::TreeBuilder::learnNode(SourceLocation First, SourceLocation Last,
+                                    syntax::TreeNode *New) {
+  assert(First.isValid());
+  assert(Last.isValid());
+  assert(First == Last ||
+         Corpus.sourceManager().isBeforeInTranslationUnit(First, Last));
+
+  learnNodeImpl(findToken(First), std::next(findToken(Last)), New);
+}
+
+void syntax::TreeBuilder::learnNodeImpl(const syntax::Token *Begin,
+                                        const syntax::Token *End,
+                                        syntax::TreeNode *New) {
+  auto FirstChild =
+      std::find_if(NodesInProgress.rbegin(), NodesInProgress.rend(),
+                   [&](const RangedNode &L) {
+                     if (&L.Tokens.front() < Begin) {
+                       assert(&L.Tokens.back() <= End);
+                       return true;
+                     }
+                     return false;
+                   })
+          .base();
+
+  syntax::Corpus &C = corpus();
+
+  auto *NextTok = Begin;
+  auto CoverUnknownTokens = [&](const syntax::Token *UpTo) {
+    if (NextTok == UpTo)
+      return;
+    assert(NextTok < UpTo);
+    auto *Recovery = C.construct<RecoveryNode>();
+    Recovery->appendChildLowLevel(
+        C, C.construct<syntax::Leaf>(llvm::makeArrayRef(NextTok, UpTo)));
+
+    New->appendChildLowLevel(C, Recovery);
+    NextTok = UpTo;
+  };
+  for (auto It = FirstChild; It != NodesInProgress.end(); ++It) {
+    // Add non-coverred ranges as recovery nodes.
+    CoverUnknownTokens(&It->Tokens.front());
+
+    New->appendChildLowLevel(corpus(), It->Node);
+    NextTok = It->Tokens.end();
+  }
+  CoverUnknownTokens(End);
+
+  NodesInProgress.erase(FirstChild, NodesInProgress.end());
+  NodesInProgress.push_back(RangedNode{llvm::makeArrayRef(Begin, End), New});
+}
+
+void syntax::TreeBuilder::learnTokenNode(SourceLocation Loc,
+                                         tok::TokenKind Kind) {
+  auto *T = findToken(Loc);
+  assert(T->kind() == Kind);
+
+  assert(NodesInProgress.empty() ||
+         NodesInProgress.back().Tokens.end() <= T &&
+             "only allowed to add a node to the end");
+
+  auto Tokens = llvm::makeArrayRef(T, 1);
+  syntax::Leaf *New = corpus().construct<syntax::Leaf>(Tokens);
+  NodesInProgress.push_back(RangedNode{Tokens, New});
+}
+
+void syntax::TreeBuilder::learnRoot() {
+  auto Tokens = Corpus.tokenBuffer().expandedTokens();
+  // Add 'eof' as a separate token node, it should not go into recovery node.
+  learnTokenNode(Tokens.back().location(), tok::eof);
+
+  learnNode(Tokens.front().location(), Tokens.back().location(),
+            corpus().construct<syntax::TranslationUnit>());
+
+  assert(NodesInProgress.size() == 1);
+  assert(NodesInProgress.front().Node->kind() ==
+         syntax::NodeKind::TranslationUnit);
+
+  Root = cast<syntax::TranslationUnit>(NodesInProgress.front().Node);
+  NodesInProgress.clear();
+}
+
+const syntax::Token *
+syntax::TreeBuilder::findToken(SourceLocation TokLoc) const {
+  auto Tokens = Corpus.tokenBuffer().expandedTokens();
+  auto &SM = Corpus.sourceManager();
+  auto It =
+      std::lower_bound(Tokens.begin(), Tokens.end(), TokLoc,
+                       [&](const syntax::Token &L, SourceLocation R) {
+                         return SM.isBeforeInTranslationUnit(L.location(), R);
+                       });
+  assert(It != Tokens.end());
+  assert(SM.getFileOffset(It->location()) == SM.getFileOffset(TokLoc));
+  return &*It;
+}
+
+syntax::TranslationUnit *
+syntax::buildSyntaxTree(Corpus &C, const TranslationUnitDecl &TU) {
+  TreeBuilder Builder(C);
+  BuildTreeVisitor(TU.getASTContext(), Builder).TraverseAST(TU.getASTContext());
+  return std::move(Builder).root();
+}
diff --git a/clang/lib/Tooling/Syntax/CMakeLists.txt b/clang/lib/Tooling/Syntax/CMakeLists.txt
--- a/clang/lib/Tooling/Syntax/CMakeLists.txt
+++ b/clang/lib/Tooling/Syntax/CMakeLists.txt
@@ -1,10 +1,17 @@
 set(LLVM_LINK_COMPONENTS Support)
 
 add_clang_library(clangToolingSyntax
+  BuildFromAST.cpp
+  Cascade.cpp
+  Corpus.cpp
+  Nodes.cpp
   Tokens.cpp
+  Tree.cpp
 
   LINK_LIBS
+  clangAST
   clangBasic
   clangFrontend
   clangLex
+  clangToolingCore
   )
diff --git a/clang/lib/Tooling/Syntax/Cascade.cpp b/clang/lib/Tooling/Syntax/Cascade.cpp
new file mode 100644
--- /dev/null
+++ b/clang/lib/Tooling/Syntax/Cascade.cpp
@@ -0,0 +1,100 @@
+//===- Cascade.cpp --------------------------------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "clang/Tooling/Syntax/Tree/Cascade.h"
+#include "clang/Basic/TokenKinds.h"
+#include "clang/Tooling/Syntax/Tree.h"
+#include "clang/Tooling/Syntax/Tree/NodeList.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Casting.h"
+
+using namespace clang;
+
+void syntax::TreeNode::appendChildLowLevel(Corpus &C, Node *Child) {
+  assert(Child->Parent == nullptr);
+  Child->Parent = this;
+  Children.push_back(C.allocator(), Child);
+}
+
+namespace {
+static void dumpTokens(llvm::raw_ostream &OS, ArrayRef<syntax::Token> Tokens,
+                       const SourceManager &SM) {
+  assert(!Tokens.empty());
+  bool First = true;
+  for (const auto &T : Tokens) {
+    if (!First)
+      OS << " ";
+    else
+      First = false;
+    // Handle 'eof' separately, calling text() on it produces an empty string.
+    if (T.kind() == tok::eof) {
+      OS << "<eof>";
+      continue;
+    }
+    OS << T.text(SM);
+  }
+}
+
+static void dumpTree(llvm::raw_ostream &OS, const syntax::Node *N,
+                     const syntax::Corpus &C, std::vector<bool> IndentMask) {
+  if (auto *L = llvm::dyn_cast<syntax::Leaf>(N)) {
+    dumpTokens(OS, L->tokens(), C.sourceManager());
+    OS << "\n";
+    return;
+  }
+
+  auto *T = llvm::cast<syntax::TreeNode>(N);
+  OS << toString(T->kind()) << "\n";
+
+  for (auto It = T->children().begin(); It != T->children().end(); ++It) {
+    for (bool Filled : IndentMask) {
+      if (Filled)
+        OS << "| ";
+      else
+        OS << "  ";
+    }
+    if (std::next(It) == T->children().end()) {
+      OS << "`-";
+      IndentMask.push_back(false);
+    } else {
+      OS << "|-";
+      IndentMask.push_back(true);
+    }
+    dumpTree(OS, *It, C, IndentMask);
+    IndentMask.pop_back();
+  }
+}
+} // namespace
+
+std::string syntax::Node::dump(const Corpus &C) const {
+  std::string Str;
+  llvm::raw_string_ostream OS(Str);
+  dumpTree(OS, this, C, /*IndentMask=*/{});
+  return std::move(OS.str());
+}
+
+std::string syntax::Node::dumpTokens(const Corpus &C) const {
+  std::string Storage;
+  llvm::raw_string_ostream OS(Storage);
+  traverse(this, [&](const syntax::Node *N) {
+    auto *L = llvm::dyn_cast<syntax::Leaf>(N);
+    if (!L)
+      return;
+    ::dumpTokens(OS, L->tokens(), C.sourceManager());
+  });
+  return OS.str();
+}
+
+syntax::Leaf *syntax::TreeNode::findLeaf(tok::TokenKind K) {
+  auto It = llvm::find_if(Children, [K](syntax::Node *N) {
+    auto *L = dyn_cast<Leaf>(N);
+    return L && L->tokens().size() == 1 && L->tokens().front().kind() == K;
+  });
+  assert(It != Children.end());
+  return cast<Leaf>(*It);
+}
diff --git a/clang/lib/Tooling/Syntax/Corpus.cpp b/clang/lib/Tooling/Syntax/Corpus.cpp
new file mode 100644
--- /dev/null
+++ b/clang/lib/Tooling/Syntax/Corpus.cpp
@@ -0,0 +1,30 @@
+//===- Corpus.cpp ---------------------------------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "clang/Tooling/Syntax/Corpus.h"
+#include "clang/Basic/LangOptions.h"
+#include "clang/Lex/Lexer.h"
+#include "llvm/ADT/ArrayRef.h"
+
+using namespace clang;
+
+syntax::Corpus::Corpus(SourceManager &SourceMgr, const LangOptions &LangOpts,
+                       TokenBuffer Tokens)
+    : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(std::move(Tokens)) {
+}
+
+const clang::syntax::TokenBuffer &syntax::Corpus::tokenBuffer() const {
+  return Tokens;
+}
+
+std::pair<FileID, llvm::ArrayRef<syntax::Token>>
+syntax::Corpus::tokenizeBuffer(std::unique_ptr<llvm::MemoryBuffer> Input) {
+  auto FID = SourceMgr.createFileID(std::move(Input));
+  auto It = ExtraTokens.try_emplace(FID, tokenize(FID, SourceMgr, LangOpts));
+  assert(It.second && "duplicate FileID");
+  return {FID, It.first->second};
+}
diff --git a/clang/lib/Tooling/Syntax/Nodes.cpp b/clang/lib/Tooling/Syntax/Nodes.cpp
new file mode 100644
--- /dev/null
+++ b/clang/lib/Tooling/Syntax/Nodes.cpp
@@ -0,0 +1,36 @@
+//===- Nodes.cpp ----------------------------------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "clang/Tooling/Syntax/Tree/Nodes.h"
+#include "clang/Basic/TokenKinds.h"
+#include "clang/Tooling/Syntax/Tree/NodeKind.h"
+
+using namespace clang;
+
+llvm::StringRef syntax::toString(syntax::NodeKind K) {
+  switch (K) {
+  case NodeKind::TranslationUnit:
+    return "translation-unit";
+  case NodeKind::RecoveryNode:
+    return "recovery-node";
+  case NodeKind::Leaf:
+    return "tokens";
+  case NodeKind::CompoundStatement:
+    return "compound-statment";
+  case NodeKind::TopLevelDecl:
+    return "top-level-decl";
+  }
+  llvm_unreachable("invalid NodeKind");
+}
+
+syntax::Leaf *syntax::CompoundStatement::lbrace() {
+  return findLeaf(tok::l_brace);
+}
+
+syntax::Leaf *syntax::CompoundStatement::rbrace() {
+  return findLeaf(tok::r_brace);
+}
diff --git a/clang/lib/Tooling/Syntax/Tree.cpp b/clang/lib/Tooling/Syntax/Tree.cpp
new file mode 100644
--- /dev/null
+++ b/clang/lib/Tooling/Syntax/Tree.cpp
@@ -0,0 +1,30 @@
+//===- Tree.cpp - mutable syntax trees ------------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "clang/Tooling/Syntax/Tree.h"
+#include "clang/Tooling/Syntax/Tokens.h"
+#include "clang/Tooling/Syntax/Tree/Cascade.h"
+#include "clang/Tooling/Syntax/Tree/Nodes.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Casting.h"
+
+using namespace clang;
+
+void syntax::traverse(Node *N, llvm::function_ref<void(Node *)> Visit) {
+  if (auto *T = llvm::dyn_cast<TreeNode>(N)) {
+    for (auto *C : T->children())
+      traverse(C, Visit);
+  }
+  Visit(N);
+}
+
+void syntax::traverse(const Node *N,
+                      llvm::function_ref<void(const Node *)> Visit) {
+  return traverse(const_cast<Node *>(N),
+                  static_cast<llvm::function_ref<void(Node *)>>(Visit));
+}
diff --git a/clang/tools/CMakeLists.txt b/clang/tools/CMakeLists.txt
--- a/clang/tools/CMakeLists.txt
+++ b/clang/tools/CMakeLists.txt
@@ -13,6 +13,7 @@
 
 add_clang_subdirectory(clang-rename)
 add_clang_subdirectory(clang-refactor)
+add_clang_subdirectory(clang-syntax)
 
 if(CLANG_ENABLE_ARCMT)
   add_clang_subdirectory(arcmt-test)
diff --git a/clang/unittests/Tooling/Syntax/CMakeLists.txt b/clang/unittests/Tooling/Syntax/CMakeLists.txt
--- a/clang/unittests/Tooling/Syntax/CMakeLists.txt
+++ b/clang/unittests/Tooling/Syntax/CMakeLists.txt
@@ -3,11 +3,12 @@
   Support
   )
 
-add_clang_unittest(TokensTest
+add_clang_unittest(SyntaxTest
+  TreeTest.cpp
   TokensTest.cpp
 )
 
-target_link_libraries(TokensTest
+target_link_libraries(SyntaxTest
   PRIVATE
   clangAST
   clangBasic
diff --git a/clang/unittests/Tooling/Syntax/TreeTest.cpp b/clang/unittests/Tooling/Syntax/TreeTest.cpp
new file mode 100644
--- /dev/null
+++ b/clang/unittests/Tooling/Syntax/TreeTest.cpp
@@ -0,0 +1,155 @@
+//===- TreeTest.cpp -------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/Syntax/Tree.h"
+#include "clang/AST/ASTConsumer.h"
+#include "clang/AST/Decl.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/Frontend/FrontendAction.h"
+#include "clang/Lex/PreprocessorOptions.h"
+#include "clang/Tooling/Syntax/Corpus.h"
+#include "clang/Tooling/Syntax/Tokens.h"
+#include "clang/Tooling/Syntax/Tree/Nodes.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringRef.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <cstdlib>
+
+using namespace clang;
+
+namespace {
+class SyntaxTreeTest : public ::testing::Test {
+protected:
+  // Build a syntax tree for the code.
+  syntax::TranslationUnit *buildTree(llvm::StringRef Code) {
+    // FIXME: this code is almost the identical to the one in TokensTest. Share
+    //        it.
+    class BuildSyntaxTree : public ASTConsumer {
+    public:
+      BuildSyntaxTree(syntax::TranslationUnit *&Root,
+                      std::unique_ptr<syntax::Corpus> &Corpus,
+                      std::unique_ptr<syntax::TokenCollector> Tokens)
+          : Root(Root), Corpus(Corpus), Tokens(std::move(Tokens)) {
+        assert(this->Tokens);
+      }
+
+      void HandleTranslationUnit(ASTContext &Ctx) override {
+        Corpus = llvm::make_unique<syntax::Corpus>(
+            Ctx.getSourceManager(), Ctx.getLangOpts(),
+            std::move(*Tokens).consume());
+        Tokens = nullptr; // make sure we fail if this gets called twice.
+        Root = syntax::buildSyntaxTree(*Corpus, *Ctx.getTranslationUnitDecl());
+      }
+
+    private:
+      syntax::TranslationUnit *&Root;
+      std::unique_ptr<syntax::Corpus> &Corpus;
+      std::unique_ptr<syntax::TokenCollector> Tokens;
+    };
+
+    class BuildSyntaxTreeAction : public ASTFrontendAction {
+    public:
+      BuildSyntaxTreeAction(syntax::TranslationUnit *&Root,
+                            std::unique_ptr<syntax::Corpus> &Corpus)
+          : Root(Root), Corpus(Corpus) {}
+
+      std::unique_ptr<ASTConsumer>
+      CreateASTConsumer(CompilerInstance &CI, StringRef InFile) override {
+        // We start recording the tokens, ast consumer will take on the result.
+        auto Tokens =
+            llvm::make_unique<syntax::TokenCollector>(CI.getPreprocessor());
+        return llvm::make_unique<BuildSyntaxTree>(Root, Corpus,
+                                                  std::move(Tokens));
+      }
+
+    private:
+      syntax::TranslationUnit *&Root;
+      std::unique_ptr<syntax::Corpus> &Corpus;
+    };
+
+    constexpr const char *FileName = "./input.cpp";
+    FS->addFile(FileName, time_t(), llvm::MemoryBuffer::getMemBufferCopy(""));
+    // Prepare to run a compiler.
+    std::vector<const char *> Args = {"tok-test", "-std=c++03", "-fsyntax-only",
+                                      FileName};
+    auto CI = createInvocationFromCommandLine(Args, Diags, FS);
+    assert(CI);
+    CI->getFrontendOpts().DisableFree = false;
+    CI->getPreprocessorOpts().addRemappedFile(
+        FileName, llvm::MemoryBuffer::getMemBufferCopy(Code).release());
+    CompilerInstance Compiler;
+    Compiler.setInvocation(std::move(CI));
+    if (!Diags->getClient())
+      Diags->setClient(new IgnoringDiagConsumer);
+    Compiler.setDiagnostics(Diags.get());
+    Compiler.setFileManager(FileMgr.get());
+    Compiler.setSourceManager(SourceMgr.get());
+
+    syntax::TranslationUnit *Root = nullptr;
+    BuildSyntaxTreeAction Recorder(Root, this->Corpus);
+    if (!Compiler.ExecuteAction(Recorder)) {
+      ADD_FAILURE() << "failed to run the frontend";
+      std::abort();
+    }
+    return Root;
+  }
+
+  // Adds a file to the test VFS.
+  void addFile(llvm::StringRef Path, llvm::StringRef Contents) {
+    if (!FS->addFile(Path, time_t(),
+                     llvm::MemoryBuffer::getMemBufferCopy(Contents))) {
+      ADD_FAILURE() << "could not add a file to VFS: " << Path;
+    }
+  }
+
+  // Data fields.
+  llvm::IntrusiveRefCntPtr<DiagnosticsEngine> Diags =
+      new DiagnosticsEngine(new DiagnosticIDs, new DiagnosticOptions);
+  IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> FS =
+      new llvm::vfs::InMemoryFileSystem;
+  llvm::IntrusiveRefCntPtr<FileManager> FileMgr =
+      new FileManager(FileSystemOptions(), FS);
+  llvm::IntrusiveRefCntPtr<SourceManager> SourceMgr =
+      new SourceManager(*Diags, *FileMgr);
+  // Set after calling buildTree().
+  std::unique_ptr<syntax::Corpus> Corpus;
+};
+
+TEST_F(SyntaxTreeTest, Basic) {
+  std::pair</*Input*/ std::string, /*Expected*/ std::string> Cases[] = {{
+      R"cpp(
+int main() {}
+void foo() {}
+    )cpp",
+      R"txt(
+translation-unit
+|-top-level-decl
+| |-recovery-node
+| | `-int main ( )
+| `-compound-statment
+|   |-{
+|   `-}
+|-top-level-decl
+| |-recovery-node
+| | `-void foo ( )
+| `-compound-statment
+|   |-{
+|   `-}
+`-<eof>
+)txt"}};
+
+  for (const auto &T : Cases) {
+    auto *Root = buildTree(T.first);
+    std::string Expected = llvm::StringRef(T.second).trim().str();
+    std::string Actual = llvm::StringRef(Root->dump(*Corpus)).trim();
+    EXPECT_EQ(Expected, Actual) << "the resulting dump is:\n" << Actual;
+  }
+}
+} // namespace