Björn Höhrmann


Grammar::Graph::Simplify - Simplify Grammar::Graph objects


  use Grammar::Graph;
  use Grammar::Graph::Simplify;
  my $g = Grammar::Graph->from_grammar_formal($formal);
  $g->fa_merge_equivalent_vertices($start_vertex, $final_vertex);


Extension methods for Grammar::Graph objects that simplify Grammars when possible.


fa_merge_equivalent_vertices($start_vertex, $final_vertex)

This method is added to Grammar::Graph objects and when called it attempts to merge equivalent vertices in the object between the given $start_vertex and $final_vertex. Ideally, the start vertex does not have incoming edges, and the final vertex does not have outgoing edges. The code is untested for when they do. It relies on being able to determine whether two labeled vertices have an equivalent label and there is currently no extension functionality to consider any but the standard labels. It dies when there are unrecognised labels. For the sentinel labels Grammar::Graph::Prefix and Grammar::Graph::Suffix vertices are merged only when matching pairs are equivalent.

The code relies on the link attributes of sentinel labels to determine which pairs are matching pairs, but then does not make any attempt to correct the link attributes, so it can be run only once on a given Grammar::Graph object. The code dies if an attempt is made to run the method a second time (it uses a graph attribute to maintain this state).




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