_copy_predecessors(
$self
,
$rd
->{start_vertex},
$s1
);
_copy_successors(
$self
,
$rd
->{start_vertex},
$s1
);
graph_isolate_vertex(
$self
->g,
$rd
->{start_vertex});
_copy_predecessors(
$self
,
$rd
->{final_vertex},
$s2
);
_copy_successors(
$self
,
$rd
->{final_vertex},
$s2
);
graph_isolate_vertex(
$self
->g,
$rd
->{final_vertex});
$self
->g->add_edge(
$rd
->{start_vertex},
$s1
);
$self
->g->add_edge(
$s2
,
$rd
->{final_vertex});
NAME
Grammar::Graph - Graph representation of formal grammars
SYNOPSIS
use
Grammar::Graph;
my
$g
= Grammar::Graph->from_grammar_formal(
$formal
);
my
$symbols
=
$g
->symbol_table;
my
$new_state
=
$g
->fa_add_state();
...
DESCRIPTION
Graph representation of formal grammars.
METHODS
from_grammar_formal($grammar_formal)
-
Constructs a new
Grammar::Graph
object from a Grammar::Formal object.Grammar::Graph
derives from Graph. The graph has a graph attributesymbol_table
with an entry for each rule identifyingstart_vertex
,final_vertex
,shortname
, and other properties. fa_add_state(p =
$label)>-
Adds a new vertex to the graph and optionally labeles it with the supplied label. The vertex should be assumed to be a random integer. Care should be taken when adding vertices to the graph through other means to avoid clashes.
fa_all_e_reachable($v)
-
Returns the successors of $v and transitively any successors that can be reached without going over a vertex labeled by something other than
Grammar::Formal::Empty
-derived objects. In other words, all the vertices that can be reached without going over an input symbol. fa_expand_references()
-
Modifies the graph such that vertices are no longer labeled with
Grammar::Formal::Reference
nodes provided there is an entry for the referenced symbol in the Graph'ssymbol_table
. Recursive and cyclic references are linearised by vertices labeled with specialGrammar::Graph::Start
andGrammar::Graph::Final
nodes, and they in turn are protected byGrammar::Graph::Prefix
and linkedGrammar::Graph::Suffix
nodes (the former identify the rule, the latter identify the reference) to ensure the nesting relationship can be fully recovered. fa_merge_character_classes()
-
Vertices labeled with a
Grammar::Formal::CharClass
node that share the same set of predecessors and successors are merged into a single vertex labeled with aGrammar::Formal::CharClass
node that is the union of original vertices. fa_separate_character_classes()
-
Collects all vertices labeled with a
Grammar::Formal::CharClass
node in the graph and replaces them with vertices labeled withGrammar::Formal::CharClass
nodes such that an input symbol matches at most a singleGrammar::Formal::CharClass
. fa_remove_useless_epsilons()
-
Removes vertices labeled with nothing or
Grammar::Formal::Empty
nodes by connecting all predecessors to all successors directly. The check forGrammar::Formal::Empty
is exact, derived classes do not match.
EXPORTS
None.
AUTHOR / COPYRIGHT / LICENSE
Copyright (c) 2014-2017 Bjoern Hoehrmann <bjoern
@hoehrmann
.de>.
This module is licensed under the same terms as Perl itself.