llvm/clang-tools-extra/pseudo/lib/grammar/LRGraph.cpp

//===--- LRGraph.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-pseudo/grammar/LRGraph.h"
#include "clang-pseudo/grammar/Grammar.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/FormatVariadic.h"
#include "llvm/Support/raw_ostream.h"

ItemSet;

namespace llvm {
// Support clang::pseudo::Item as DenseMap keys.
template <> struct DenseMapInfo<ItemSet> { … };
} // namespace llvm

namespace clang {
namespace pseudo {
namespace {

struct SortByNextSymbol { … };

// Computes a closure of the given item set S:
//  - extends the given S to contain all options for parsing next token;
//  - nonterminals after a dot are recursively expanded into the begin-state
//    of all production rules that produce that nonterminal;
//
// Given
//   Grammar rules = [ _ := E, E := E - T, E := T, T := n, T := ( E ) ]
//   Input = [ E := . T ]
// returns [ E :=  . T, T := . n, T := . ( E ) ]
State closure(ItemSet Queue, const Grammar &G) { … }

// Returns all next (with a dot advanced) kernel item sets, partitioned by the
// advanced symbol.
//
// Given
//  S = [ E := . a b, E := E . - T ]
// returns [
//   {id(a), [ E := a . b ]},
//   {id(-), [ E := E - . T ]}
// ]
std::vector<std::pair<SymbolID, ItemSet>>
nextAvailableKernelItems(const State &S, const Grammar &G) { … }

std::vector<std::pair<ExtensionID, SymbolID>>
availableRecovery(const State &S, const Grammar &G) { … }

} // namespace

std::string Item::dump(const Grammar &G) const { … }

std::string State::dump(const Grammar &G, unsigned Indent) const { … }

std::string LRGraph::dumpForTests(const Grammar &G) const { … }

LRGraph LRGraph::buildLR0(const Grammar &G) { … }

} // namespace pseudo
} // namespace clang