Package ec.gp.ge

# Class GrammarParser

java.lang.Object
ec.gp.ge.GrammarParser

All Implemented Interfaces:
  `Prototype`, `Setup`, `Serializable`, `Cloneable`

public class GrammarParser extends Object implements Prototype
A GrammarParser is the basic class for parsing a GE ruleset into a parse graph of GrammarNodes. This parse graph is then later used to produce a GPIndividual from a GEIndividual in GESpecies. It is assumed that the root will represent the first rule given in the grammar.

See Also:
  - Serialized Form

- ## Field Summary

  Fields
  Modifier and Type
  Field
  Description
  `protected static final int`
  `BOOLEAN_CONSTANT`
  `protected static final int`
  `COMMENT`
  `static final String[]`
  `DEFAULT_REGEXES`
  The default regular expressions for tokens in the parser.
  `protected static final int`
  `EQUALS`
  `protected static final int`
  `FUNCTION`
  `protected static final int`
  `LPAREN`
  `protected static final int`
  `NUMERIC_CONSTANT`
  `static final String`
  `P_PARSER`
  `protected static final int`
  `PIPE`
  `protected static final int`
  `RPAREN`
  `protected static final int`
  `RULE`
  `protected static final int`
  `STRING_CONSTANT`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `GrammarParser()`

- ## Method Summary

  Modifier and Type
  Method
  Description
  `Object`
  `clone()`
  Creates a new individual cloned from a prototype, and suitable to begin use in its own evolutionary context.
  `Parameter`
  `defaultBase()`
  Returns the default base for this prototype.
  `void`
  `enumerateGrammarTree(GrammarNode gn)`
  Run BFS to enumerate the whole grammar tree into all necessary indices lists/hash-maps, we *need* to run BFS because the decoding of the "GE array to tree" works in a BFS fashion, so we need to stick with that; After enumeration, we will have four data-structures like these -- (1) productionRuleList (a flattened grammar tree): grammar-tree ==> {rule-0, rule-1, ,,, rule-(n-1)} (2) ruleToIndex: rule-0 --> 0 rule-1 --> 1 , , rule-(n-1) --> (n-1) (3) indexToRule (reverse of ruleToIndex): 0 --> rule-0 1 --> rule-1 , , n-1 --> rule-(n-1) and then, last but not the least, the relative rule index -- (4) absIndexToRelIndex: if we have two rules like " -> | " and " -> | " then, [rule] [absIndex] [relIndex] -> --> [0] --> [0] -> --> [1] --> [1] -> --> [2] --> [0] -> --> [3] --> [1] etc,
  `ArrayList`
  `gatherFirstSets(GrammarNode gn, GrammarNode parent)`
  Generate the FIRST-SET for each production rule and store them in the global hash-table, this runs a DFS on the grammar tree, the returned ArrayList is discarded and the FIRST-SETs are organized in a hash-map called "ruleToFirstSet" as follows -- rule-0 --> {FIRST-SET-0} rule-1 --> {FIRST-SET-1} , , rule-(n-1) --> {FIRST-SET-(n-1)}
  `ArrayList`
  `gatherFollowSets(GrammarNode gn, GrammarNode parent)`
  We do not have any example grammar to test with FOLLOW-SETs, so the FOLLOW-SET is empty, we need to test with a grammar that contains post-fix notations; this needs to be implemented properly with a new grammar.
  `void`
  `gatherPredictSets(GrammarNode gn, GrammarNode parent)`
  Populate the PREDICT-SET from the FIRST-SETs and the FOLLOW-SETs, as we do not have FOLLOW-SET, so FIRST-SET == PREDICT-SET; this needs to be implemented, when the FOLLOW-SETs are done properly.
  `String[]`
  `getRegexes()`
  Returns the regular expressions to use for tokenizing these rules.
  `static void`
  `main(String[] args)`
  A simple testing facility.
  `GrammarRuleNode`
  `parseRules(EvolutionState state, BufferedReader reader, GPFunctionSet gpfs)`
  Parses the rules from a grammar and returns the resulting GrammarRuleNode root.
  `void`
  `populatePredictiveParseTable(GrammarNode gn)`
  Now populate the predictive-parse table, this procedure reads hash-maps/tables for the grammar-rule indices, PREDICT-SETs etc, and assigns the corresponding values in the predictive-parse table.
  `void`
  `setup(EvolutionState state, Parameter base)`
  Sets up the object by reading it from the parameters stored in state, built off of the parameter base base.
  `String`
  `toString()`
  `boolean`
  `validateRules()`
  Checks that all grammar rules in ruleshashmap have at least one possible production

  ### Methods inherited from class java.lang.Object

  `equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait`

- ## Field Details

  - ### P_PARSER

    public static final String P_PARSER
    See Also:
      - Constant Field Values

  - ### DEFAULT_REGEXES

    public static final String[] DEFAULT_REGEXES
    The default regular expressions for tokens in the parser. If you'd like to change minor features of the regular expressions, override the getRegexes() method in a subclass to return a different array. Note that if you INSERT a new regular expression into the middle of these, the values of the various token constants ("LPAREN", "RULE", etc.) will be wrong, so you will need to override or modify the methods which use them.

  - ### COMMENT

    protected static final int COMMENT
    See Also:
      - Constant Field Values

  - ### LPAREN

    protected static final int LPAREN
    See Also:
      - Constant Field Values

  - ### RPAREN

    protected static final int RPAREN
    See Also:
      - Constant Field Values

  - ### RULE

    protected static final int RULE
    See Also:
      - Constant Field Values

  - ### PIPE

    protected static final int PIPE
    See Also:
      - Constant Field Values

  - ### EQUALS

    protected static final int EQUALS
    See Also:
      - Constant Field Values

  - ### NUMERIC_CONSTANT

    protected static final int NUMERIC_CONSTANT
    See Also:
      - Constant Field Values

  - ### BOOLEAN_CONSTANT

    protected static final int BOOLEAN_CONSTANT
    See Also:
      - Constant Field Values

  - ### STRING_CONSTANT

    protected static final int STRING_CONSTANT
    See Also:
      - Constant Field Values

  - ### FUNCTION

    protected static final int FUNCTION
    See Also:
      - Constant Field Values

- ## Constructor Details

  - ### GrammarParser

    public GrammarParser()

- ## Method Details

  - ### getRegexes

    public String[] getRegexes()
    Returns the regular expressions to use for tokenizing these rules. By default DEFAULT_REGEXES are returned.

  - ### defaultBase

    public Parameter defaultBase()
    Description copied from interface: `Prototype`
    Returns the default base for this prototype. This should generally be implemented by building off of the static base() method on the DefaultsForm object for the prototype's package. This should be callable during setup(...).
    Specified by:
      `defaultBase` in interface `Prototype`

  - ### setup

    public void setup(EvolutionState state, Parameter base)
    Description copied from interface: `Prototype`
    Sets up the object by reading it from the parameters stored in state, built off of the parameter base base. If an ancestor implements this method, be sure to call super.setup(state,base); before you do anything else.

    For prototypes, setup(...) is typically called once for the prototype instance; cloned instances do not receive the setup(...) call. setup(...) may be called more than once; the only guarantee is that it will get called at least once on an instance or some "parent" object from which it was ultimately cloned.

    Specified by:
      `setup` in interface `Prototype`
    Specified by:
      `setup` in interface `Setup`

  - ### clone

    public Object clone()
    Description copied from interface: `Prototype`
    Creates a new individual cloned from a prototype, and suitable to begin use in its own evolutionary context.

    Typically this should be a full "deep" clone. However, you may share certain elements with other objects rather than clone hem, depending on the situation:

    - If you hold objects which are shared with other instances, don't clone them.
    - If you hold objects which must be unique, clone them.
    - If you hold objects which were given to you as a gesture of kindness, and aren't owned by you, you probably shouldn't clone them.
    - DON'T attempt to clone: Singletons, Cliques, or Populations, or Subpopulation.
    - Arrays are not cloned automatically; you may need to clone an array if you're not sharing it with other instances. Arrays have the nice feature of being copyable by calling clone() on them.

    Implementations.

    - If no ancestor of yours implements clone(), and you have no need to do clone deeply, and you are abstract, then you should not declare clone().
    - If no ancestor of yours implements clone(), and you have no need to do clone deeply, and you are not abstract, then you should implement it as follows:

      ``

           public Object clone()
               {
               try
                   {
                   return super.clone();
                   }
               catch ((CloneNotSupportedException e)
                   { throw new InternalError(); } // never happens
               }

    - If no ancestor of yours implements clone(), but you need to deep-clone some things, then you should implement it as follows:

      ``

           public Object clone()
               {
               try
                   {
                   MyObject myobj = (MyObject) (super.clone());

                   // put your deep-cloning code here...
                   }
               catch ((CloneNotSupportedException e)
                   { throw new InternalError(); } // never happens
               return myobj;
               }

    - If an ancestor has implemented clone(), and you also need to deep clone some things, then you should implement it as follows:

      ``

           public Object clone()
               {
               MyObject myobj = (MyObject) (super.clone());

               // put your deep-cloning code here...

               return myobj;
               }

    Specified by:
      `clone` in interface `Prototype`
    Overrides:
      `clone` in class `Object`

  - ### parseRules

    public GrammarRuleNode parseRules(EvolutionState state, BufferedReader reader, GPFunctionSet gpfs)
    Parses the rules from a grammar and returns the resulting GrammarRuleNode root.

  - ### toString

    public String toString()
    Overrides:
      `toString` in class `Object`

  - ### validateRules

    public boolean validateRules()
    Checks that all grammar rules in ruleshashmap have at least one possible production
    Returns:
      true if grammar rules are properly defined, false otherwise

  - ### enumerateGrammarTree

    public void enumerateGrammarTree(GrammarNode gn)
    Run BFS to enumerate the whole grammar tree into all necessary indices lists/hash-maps, we *need* to run BFS because the decoding of the "GE array to tree" works in a BFS fashion, so we need to stick with that; After enumeration, we will have four data-structures like these -- (1) productionRuleList (a flattened grammar tree): grammar-tree ==> {rule-0, rule-1, ,,, rule-(n-1)} (2) ruleToIndex: rule-0 --> 0 rule-1 --> 1 , , rule-(n-1) --> (n-1) (3) indexToRule (reverse of ruleToIndex): 0 --> rule-0 1 --> rule-1 , , n-1 --> rule-(n-1) and then, last but not the least, the relative rule index -- (4) absIndexToRelIndex: if we have two rules like " -> | " and " -> | " then, [rule] [absIndex] [relIndex] -> --> [0] --> [0] -> --> [1] --> [1] -> --> [2] --> [0] -> --> [3] --> [1] etc,

  - ### gatherFirstSets

    public ArrayList gatherFirstSets(GrammarNode gn, GrammarNode parent)
    Generate the FIRST-SET for each production rule and store them in the global hash-table, this runs a DFS on the grammar tree, the returned ArrayList is discarded and the FIRST-SETs are organized in a hash-map called "ruleToFirstSet" as follows -- rule-0 --> {FIRST-SET-0} rule-1 --> {FIRST-SET-1} , , rule-(n-1) --> {FIRST-SET-(n-1)}

  - ### gatherFollowSets

    public ArrayList gatherFollowSets(GrammarNode gn, GrammarNode parent)
    We do not have any example grammar to test with FOLLOW-SETs, so the FOLLOW-SET is empty, we need to test with a grammar that contains post-fix notations; this needs to be implemented properly with a new grammar.

  - ### gatherPredictSets

    public void gatherPredictSets(GrammarNode gn, GrammarNode parent)
    Populate the PREDICT-SET from the FIRST-SETs and the FOLLOW-SETs, as we do not have FOLLOW-SET, so FIRST-SET == PREDICT-SET; this needs to be implemented, when the FOLLOW-SETs are done properly.

  - ### populatePredictiveParseTable

    public void populatePredictiveParseTable(GrammarNode gn)
    Now populate the predictive-parse table, this procedure reads hash-maps/tables for the grammar-rule indices, PREDICT-SETs etc, and assigns the corresponding values in the predictive-parse table.

  - ### main

    public static void main(String[] args) throws FileNotFoundException
    A simple testing facility.
    Throws:
      `FileNotFoundException`