110 lines · c
1//===--------------------- DfaEmitter.h -----------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8// Defines a generic automaton builder. This takes a set of transitions and9// states that represent a nondeterministic finite state automaton (NFA) and10// emits a determinized DFA in a form that include/llvm/Support/Automaton.h can11// drive.12//13// See file llvm/TableGen/Automaton.td for the TableGen API definition.14//15//===----------------------------------------------------------------------===//16 17#ifndef LLVM_UTILS_TABLEGEN_DFAEMITTER_H18#define LLVM_UTILS_TABLEGEN_DFAEMITTER_H19 20#include "llvm/ADT/SmallVector.h"21#include "llvm/ADT/UniqueVector.h"22#include <map>23#include <set>24#include <utility>25#include <vector>26 27namespace llvm {28 29class raw_ostream;30class StringRef;31 32/// Construct a deterministic finite state automaton from possible33/// nondeterministic state and transition data.34///35/// The state type is a 64-bit unsigned integer. The generated automaton is36/// invariant to the sparsity of the state representation - its size is only37/// a function of the cardinality of the set of states.38///39/// The inputs to this emitter are considered to define a nondeterministic40/// finite state automaton (NFA). This is then converted to a DFA during41/// emission. The emitted tables can be used to by42/// include/llvm/Support/Automaton.h.43class DfaEmitter {44public:45 // The type of an NFA state. The initial state is always zero.46 using state_type = uint64_t;47 // The type of an action.48 using action_type = uint64_t;49 50 DfaEmitter() = default;51 virtual ~DfaEmitter() = default;52 53 void addTransition(state_type From, state_type To, action_type A);54 void emit(StringRef Name, raw_ostream &OS);55 56protected:57 /// Emit the C++ type of an action to OS.58 virtual void printActionType(raw_ostream &OS);59 /// Emit the C++ value of an action A to OS.60 virtual void printActionValue(action_type A, raw_ostream &OS);61 62private:63 /// The state type of deterministic states. These are only used internally to64 /// this class. This is an ID into the DfaStates UniqueVector.65 using dfa_state_type = unsigned;66 67 /// The actual representation of a DFA state, which is a union of one or more68 /// NFA states.69 using DfaState = SmallVector<state_type, 4>;70 71 /// A DFA transition consists of a set of NFA states transitioning to a72 /// new set of NFA states. The DfaTransitionInfo tracks, for every73 /// transitioned-from NFA state, a set of valid transitioned-to states.74 ///75 /// Emission of this transition relation allows algorithmic determination of76 /// the possible candidate NFA paths taken under a given input sequence to77 /// reach a given DFA state.78 using DfaTransitionInfo = SmallVector<std::pair<state_type, state_type>, 4>;79 80 /// The set of all possible actions.81 std::set<action_type> Actions;82 83 /// The set of nondeterministic transitions. A state-action pair can84 /// transition to multiple target states.85 std::map<std::pair<state_type, action_type>, std::vector<state_type>>86 NfaTransitions;87 std::set<state_type> NfaStates;88 unsigned NumNfaTransitions = 0;89 90 /// The set of deterministic states. DfaStates.getId(DfaState) returns an ID,91 /// which is dfa_state_type. Note that because UniqueVector reserves state92 /// zero, the initial DFA state is always 1.93 UniqueVector<DfaState> DfaStates;94 /// The set of deterministic transitions. A state-action pair has only a95 /// single target state.96 std::map<std::pair<dfa_state_type, action_type>,97 std::pair<dfa_state_type, DfaTransitionInfo>>98 DfaTransitions;99 100 /// Visit all NFA states and construct the DFA.101 void constructDfa();102 /// Visit a single DFA state and construct all possible transitions to new DFA103 /// states.104 void visitDfaState(const DfaState &DS);105};106 107} // namespace llvm108 109#endif110