NAME

Grammar::Graph - Graph representation of formal grammars

SYNOPSIS

  use Grammar::Graph;
  my $g = Grammar::Graph->from_grammar_formal($formal);
  my $symbols = $g->get_graph_attribute('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 attribute symbol_table with an entry for each rule identifying start_vertex, final_vertex, shortname, and other properties.

fa_add_state($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's symbol_table. Recursive and cyclic references are linearised by vertices labeled with special Grammar::Graph::StartOf and Grammar::Graph::FinalOf 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.

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 a Grammar::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 with Grammar::Formal::CharClass nodes such that an input symbol matches at most a single Grammar::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 for Grammar::Formal::Empty is exact, derived classes do not match.

EXPORTS

None.

AUTHOR / COPYRIGHT / LICENSE

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