Björn Höhrmann
  _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});


Grammar::Graph - Graph representation of formal grammars


  use Grammar::Graph;
  my $g = Grammar::Graph->from_grammar_formal($formal);
  my $symbols = $g->symbol_table;
  my $new_state = $g->fa_add_state();


Graph representation of formal grammars.



Constructs a new Grammar::Graph object from a Grammar::Formal object. Grammar::Graph derives from Graph. The graph has a graph attribute symbol_table with an entry for each rule identifying start_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.


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.


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's symbol_table. Recursive and cyclic references are linearised by vertices labeled with special Grammar::Graph::Start and Grammar::Graph::Final nodes, and they in turn are protected by Grammar::Graph::Prefix and linked Grammar::Graph::Suffix nodes (the former identify the rule, the latter identify the reference) to ensure the nesting relationship can be fully recovered.


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 a Grammar::Formal::CharClass node that is the union of original vertices.


Collects all vertices labeled with a Grammar::Formal::CharClass node in the graph and replaces them with vertices labeled with Grammar::Formal::CharClass nodes such that an input symbol matches at most a single Grammar::Formal::CharClass.


Removes vertices labeled with nothing or Grammar::Formal::Empty nodes by connecting all predecessors to all successors directly. The check for Grammar::Formal::Empty is exact, derived classes do not match.




  Copyright (c) 2014-2017 Bjoern Hoehrmann <>.
  This module is licensed under the same terms as Perl itself.