Package org.nineml.coffeegrinder.parser

Class ParseForest

  • Direct Known Subclasses:
    ParseForestGLL
    public class ParseForest
extends java.lang.Object
    An SPPF is a shared packed parse forest.

    The SPPF is a graph representation of all the (possibly infinite) parses that can be used to recognize the input sequence as a sentence in the grammar.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      static java.lang.String logcategory
      The logging category for log messages about the forest.

    • Constructor Summary

      Constructors 
      Constructor Description
      ParseForest​(ParserOptions options, java.lang.String priorityStyle, int defaultPriority)
      Construct a parser forest.

    • Field Detail

      • logcategory

        public static final java.lang.String logcategory
        The logging category for log messages about the forest.
        See Also:
        Constant Field Values

    • Constructor Detail

      • ParseForest

        public ParseForest​(ParserOptions options,
                   java.lang.String priorityStyle,
                   int defaultPriority)
        Construct a parser forest.
        Parameters:
        options - The options.
        priorityStyle - The priority style.
        defaultPriority - The default priority.

    • Method Detail

      • isAmbiguous

        public boolean isAmbiguous()
        Is the grammar represented by this graph ambiguous?

        A grammar is ambiguous if there are more than two parses that will recognize the input.

        Returns:
        true if the grammar is ambiguous

      • isSameSerializations

        public boolean isSameSerializations()
        Are all the serializations the same?

        Tests if it appears that all the serializations of this forest are "the same".

        This is a conservative check; if it returns true, they are all the same. If it returns false, it is still possible that they're all the same.

        Returns:
        true if the parses are all the same

      • isInfinitelyAmbiguous

        public boolean isInfinitelyAmbiguous()
        Is the grammar represented by this graph infinitely ambiguous?

        If the answer is "true", then the graph is infinitely ambiguous. If the graph is ambiguous and the anwer is "false", then all that can be said is the single parse explored to check ambiguity did not encounter infinite ambiguity. It is not an assertion that no unexplored part of the graph contains a loop.

        Returns:
        true if the parse forest is known to be infinitely ambiguous

      • getParseTreeCount

        public int getParseTreeCount()
        How many parse trees are there in this forest?

        In an infinitely ambiguous graph, there are an infinite number of parse trees. However, CoffeeGrinder will never follow the same edge twice when constructing a tree, it won't loop. So the number of available trees is always a finite number.

        Returns:
        the parse tree count

      • getAmbiguousNodes

        public java.util.List<ForestNode> getAmbiguousNodes()
        Which nodes are ambiguous?
        Returns:
        the ambiguous nodes.

      • size

        public int size()
        How big is the graph?
        Returns:
        the number of nodes in the graph

      • getNodes

        public java.util.List<ForestNode> getNodes()
        Get the nodes in the graph.
        Returns:
        the nodes in the graph.

      • getRoot

        public ForestNode getRoot()
        Return the root of the forest.
        Returns:
        The root, or null if the forest has no roots.

      • getOptions

        public ParserOptions getOptions()
        Get the options for this forest.
        Returns:
        the options.

      • serialize

        public java.lang.String serialize()
        Serialize the graph as XML.
        Returns:
        an XML serialization as a string

      • serialize

        public void serialize​(java.io.PrintStream stream)
        Serialize the graph as XML.
        Parameters:
        stream - the stream on which to write the XML serialization

      • serialize

        public void serialize​(java.lang.String filename)
        Serialize the graph as XML.

        This method attempts to write the XML to a file.

        Parameters:
        filename - the name of the file
        Throws:
        ForestException - if a error occurs attempt to write to the file

      • prune

        public void prune()
        Prune the forest.

        Pruning removes unreachable nodes: nodes that were part of the parse but did not complete.