xref: /llvm-project-15.0.7/clang-tools-extra/pseudo/include/clang-pseudo/grammar/LRGraph.h (revision 7d8e2742)

//===--- LRGraph.h - Build an LR automaton  ------------------*- 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
//
//===----------------------------------------------------------------------===//
//
//  LR parsers are bottom-up parsers -- they scan the input from left to right,
//  and collect the right-hand side of a production rule (called handle) on top
//  of the stack, then replace (reduce) the handle with the nonterminal defined
//  by the production rule.
//
//  This file defines LRGraph, a deterministic handle-finding finite-state
//  automaton, which is a key component in LR parsers to recognize any of
//  handles in the grammar efficiently. We build the LR table (ACTION and GOTO
//  Table) based on the LRGraph.
//
//  LRGraph can be constructed for any context-free grammars.
//  Even for a LR-ambiguous grammar, we can construct a deterministic FSA, but
//  interpretation of the FSA is nondeterministic -- we might in a state where
//  we can continue searching an handle and identify a handle (called
//  shift/reduce conflicts), or identify more than one handle (callled
//  reduce/reduce conflicts).
//
//  LRGraph is a common model for all variants of LR automatons, from the most
//  basic one LR(0), the powerful SLR(1), LR(1) which uses a one-token lookahead
//  in making decisions.
//===----------------------------------------------------------------------===//

#ifndef CLANG_PSEUDO_GRAMMAR_LRGRAPH_H
#define CLANG_PSEUDO_GRAMMAR_LRGRAPH_H

#include "clang-pseudo/grammar/Grammar.h"
#include "llvm/ADT/Hashing.h"
#include <vector>

namespace clang {
namespace pseudo {

// An LR item -- a grammar rule with a dot at some position of the body.
// e.g. a production rule A := X Y yields 3 items:
//   A := . X Y
//   A := X . Y
//   A := X Y .
// An item indicates how much of a production rule has been recognized at a
// position (described by dot), for example, A := X . Y indicates that we have
// recognized the X part from the input, and we hope next to see the input
// derivable from Y.
class Item {
public:
  static Item start(RuleID ID, const Grammar &G) {
    Item I;
    I.RID = ID;
    I.RuleLength = G.lookupRule(ID).Size;
    return I;
  }
  static Item sentinel(RuleID ID) {
    Item I;
    I.RID = ID;
    return I;
  }

  RuleID rule() const { return RID; }
  uint8_t dot() const { return DotPos; }

  bool hasNext() const { return DotPos < RuleLength; }
  SymbolID next(const Grammar &G) const {
    assert(hasNext());
    return G.lookupRule(RID).Sequence[DotPos];
  }

  Item advance() const {
    assert(hasNext());
    Item I = *this;
    ++I.DotPos;
    return I;
  }

  std::string dump(const Grammar &G) const;

  bool operator==(const Item &I) const {
    return DotPos == I.DotPos && RID == I.RID;
  }
  bool operator<(const Item &I) const {
    return std::tie(RID, DotPos) < std::tie(I.RID, I.DotPos);
  }
  friend llvm::hash_code hash_value(const Item &I) {
    return llvm::hash_combine(I.RID, I.DotPos);
  }

private:
  RuleID RID = 0;
  uint8_t DotPos = 0;
  uint8_t RuleLength = 0; // the length of rule body.
};

// A state represents a node in the LR automaton graph. It is an item set, which
// contains all possible rules that the LR parser may be parsing in that state.
//
// Conceptually, If we knew in advance what we're parsing, at any point we're
// partway through parsing a production, sitting on a stack of partially parsed
// productions. But because we don't know, there could be *several* productions
// we're partway through. The set of possibilities is the parser state, and we
// precompute all the transitions between these states.
struct State {
  // A full set of items (including non-kernel items) representing the state,
  // in a canonical order (see SortByNextSymbol in the cpp file).
  std::vector<Item> Items;

  std::string dump(const Grammar &G, unsigned Indent = 0) const;
};

// LRGraph is a deterministic finite state automaton for LR parsing.
//
// Intuitively, an LR automaton is a transition graph. The graph has a
// collection of nodes, called States. Each state corresponds to a particular
// item set, which represents a condition that could occur during the process of
// parsing a production. Edges are directed from one state to another. Each edge
// is labeled by a grammar symbol (terminal or nonterminal).
//
// LRGraph is used to construct the LR parsing table which is a core
// data-structure driving the LR parser.
class LRGraph {
public:
  // StateID is the index in States table.
  using StateID = uint16_t;

  // Constructs an LR(0) automaton.
  static LRGraph buildLR0(const Grammar &);

  // An edge in the LR graph, it represents a transition in the LR automaton.
  // If the parser is at state Src, with a lookahead Label, then it
  // transits to state Dst.
  struct Edge {
    StateID Src, Dst;
    SymbolID Label;
  };

  // A possible error recovery: choose to match some tokens against a symbol.
  //
  // e.g. a state that contains
  //   stmt := { . stmt-seq [recover=braces] }
  // has a Recovery { Src = S, Strategy=braces, Result=stmt-seq }.
  struct Recovery {
    StateID Src; // The state we are in when encountering the error.
    ExtensionID Strategy;      // Heuristic choosing the tokens to match.
    SymbolID Result;           // The symbol that is produced.
  };

  llvm::ArrayRef<State> states() const { return States; }
  llvm::ArrayRef<Edge> edges() const { return Edges; }
  llvm::ArrayRef<Recovery> recoveries() const { return Recoveries; }
  llvm::ArrayRef<std::pair<SymbolID, StateID>> startStates() const {
    return StartStates;
  }

  std::string dumpForTests(const Grammar &) const;

private:
  LRGraph(std::vector<State> States, std::vector<Edge> Edges,
          std::vector<Recovery> Recoveries,
          std::vector<std::pair<SymbolID, StateID>> StartStates)
      : States(std::move(States)), Edges(std::move(Edges)),
        Recoveries(std::move(Recoveries)), StartStates(std::move(StartStates)) {
  }

  std::vector<State> States;
  std::vector<Edge> Edges;
  std::vector<Recovery> Recoveries;
  std::vector<std::pair<SymbolID, StateID>> StartStates;
};

} // namespace pseudo
} // namespace clang

namespace llvm {
// Support clang::pseudo::Item as DenseMap keys.
template <> struct DenseMapInfo<clang::pseudo::Item> {
  static inline clang::pseudo::Item getEmptyKey() {
    return clang::pseudo::Item::sentinel(-1);
  }
  static inline clang::pseudo::Item getTombstoneKey() {
    return clang::pseudo::Item::sentinel(-2);
  }
  static unsigned getHashValue(const clang::pseudo::Item &I) {
    return hash_value(I);
  }
  static bool isEqual(const clang::pseudo::Item &LHS,
                      const clang::pseudo::Item &RHS) {
    return LHS == RHS;
  }
};
} // namespace llvm

#endif // CLANG_PSEUDO_GRAMMAR_LRGRAPH_H