uuagc

Knuth1

Synopsis

Documentation

traceST :: String -> ST s ()

Trace a message in the ST monad

data AttrType

Constructors

Inh 
Syn 
Loc 

isVertexAttr :: Vertex -> Bool

Check if a vertex is an attribute

getAttrChildName :: Vertex -> Identifier

Get the child name of an attribute

setAttrChildName :: Vertex -> Identifier -> Vertex

Set the child name of an attribute

getAttrType :: Vertex -> AttrType

Get the type of an attribute

getAttrName :: Vertex -> Identifier

Get the name of an attribute

type Edge = (Vertex, Vertex)

type IVertex = Int

graphConstruct :: [Vertex] -> ST s (DependencyGraph s)

Construct a dependency graph

graphConstructTRC :: [Vertex] -> [Edge] -> ST s (DependencyGraph s)

Construct a transitivelly closed graph

graphSuccessors :: DependencyGraph s -> Vertex -> ST s (Set Vertex)

Return all successors of a vertex

graphPredecessors :: DependencyGraph s -> Vertex -> ST s (Set Vertex)

Return all predecessors of a vertex

graphContainsEdge :: DependencyGraph s -> Edge -> ST s Bool

Check if the graph contains an edge

graphInsert :: DependencyGraph s -> Edge -> ST s ()

Insert an edge in the graph

graphInsertTRC :: DependencyGraph s -> Edge -> ST s [(IVertex, Set IVertex)]

Insert an edge in a transtive closed graph and return all other edges that were added due to transtivity

graphVertices :: DependencyGraph s -> ST s [Vertex]

Return all vertices of the graph

graphEdges :: DependencyGraph s -> ST s [Edge]

Return all edges of the graph

graphInsertEdges :: DependencyGraph s -> [Edge] -> ST s ()

Insert a list of edges in the graph

graphInsertEdgesTRC :: DependencyGraph s -> [Edge] -> ST s [Edge]

Insert a list of edges in the graph and return all other edges that were added due to transitivity

graphIsCyclic :: DependencyGraph s -> ST s Bool

Check whether the graph is cyclic

graphGetIVertex :: DependencyGraph s -> Vertex -> IVertex

Get internal representation of a vertex

graphGetVertex :: DependencyGraph s -> IVertex -> Vertex

Get external representation of a vertex

graphGetEdge :: DependencyGraph s -> IEdge -> Edge

Get external representation of an edge

graphIsTRC :: DependencyGraph s -> ST s Bool

Check if the graph is transitively closed

graphCheckConsistency :: DependencyGraph s -> ST s Bool

Check consistency of the graph (successor and predecessor sets)

graphTopSort :: DependencyGraph s -> ST s [Edge]

Add edges to the graph so that it is topologically sorted (this will not work if graph is cyclic)

graphTopSort' :: DependencyGraph s -> [IVertex] -> IVertex -> ST s [IVertex]

Helper function for graphTopSort

data NontDependencyGraph

Special wrapper for nonterminal dependency graphs (so that we can easily add other meta-information)

Constructors

NontDependencyGraph 

Fields

ndgVertices :: [Vertex]
 
ndgEdges :: [Edge]
 

data ProdDependencyGraph

Special wrapper for production dependency graphs, including mapping between child names and nonterminals

data NontDependencyGraphM s

Monadic wrapper of NontDependencyGraph

data ProdDependencyGraphM s

Monadic wrapper of ProdDependencyGraph

mkNontDependencyGraphM :: NontDependencyGraph -> ST s (NontDependencyGraphM s)

Convert a NontDependencyGraph to the corresponding monadic version

mkProdDependencyGraphM :: Bool -> ProdDependencyGraph -> ST s (ProdDependencyGraphM s)

Convert a ProdDependencyGraph to the corresponding monadic version

mkNontDependencyInformationM :: NontDependencyInformation -> ST s (NontDependencyInformationM s)

Convert a NontDependencyInformation to the corresponding monadic version

undoTransitiveClosure :: [NontDependencyInformationM s] -> ST s [NontDependencyInformationM s]

Construct the production graphs from the transitivelly closed graphs

knuth1 :: [NontDependencyInformationM s] -> ST s ()

Combine the dependency and nonterminal graphs using Knuth-1 this function assumes that the nonterminal graphs initially contains no edges

knuth1' :: [([[Edge]], NontDependencyInformationM s)] -> ST s ()

Helper function for |knuth1| which repeats the process until we are done

addProdNont :: ([[Edge]], NontDependencyInformationM s) -> ST s [Edge]

Add pending edges from the production graphs to the nonterminal graph and return the list of newly added nonterminal edges

addNontProd :: Bool -> ([Edge], NontDependencyInformationM s) -> ST s [[Edge]]

Add edges from the nonterminal graphs to the production graphs and return the list of newly added production edges and the updated graph

addNontProd' :: Bool -> [Edge] -> ProdDependencyGraphM s -> ST s [Edge]

Helper function for |addNontProd| for a single production

addBackEdges :: [([[Edge]], NontDependencyInformationM s)] -> ST s [Edge]

Add the back edges to the nonterminal graphs for creating a global ordering

addTopSortEdges :: [Edge] -> ProdDependencyGraphM s -> ST s ()

Add all resulting edges from a topsort on the nonterminal graph to the production graph this will ignore edges that will make the graph cyclic