ec.gp.ge

Class GrammarParser

java.lang.Object

ec.gp.ge.GrammarParser

All Implemented Interfaces:

Prototype, Setup, java.io.Serializable, java.lang.Cloneable

public class GrammarParser
extends java.lang.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 and Description
static java.lang.String[]	DEFAULT_REGEXES The default regular expressions for tokens in the parser.
static java.lang.String	P_PARSER

Constructor Summary

Constructors

Constructor and Description
GrammarParser()

Method Summary

Modifier and Type	Method and Description
java.lang.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,
java.util.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)}
java.util.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.
java.lang.String[]	getRegexes() Returns the regular expressions to use for tokenizing these rules.
static void	main(java.lang.String[] args) A simple testing facility.
GrammarRuleNode	parseRules(EvolutionState state, java.io.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.
java.lang.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, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

P_PARSER

public static final java.lang.String P_PARSER

See Also:

Constant Field Values

DEFAULT_REGEXES

public static final java.lang.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.

Constructor Detail

GrammarParser

public GrammarParser()

Method Detail

getRegexes

public java.lang.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 java.lang.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 Groups.
• 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 java.lang.Object

parseRules

public GrammarRuleNode parseRules(EvolutionState state,
                                  java.io.BufferedReader reader,
                                  GPFunctionSet gpfs)

Parses the rules from a grammar and returns the resulting GrammarRuleNode root.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.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 java.util.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 java.util.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(java.lang.String[] args)
                 throws java.io.FileNotFoundException

A simple testing facility.

Throws:

java.io.FileNotFoundException