org.metasyntactic.math.automata
Class ContextFreeGrammar

java.lang.Object
  |
  +--org.metasyntactic.math.automata.ContextFreeGrammar
All Implemented Interfaces:
FiniteAutomata, java.io.Serializable
Direct Known Subclasses:
AugmentedGrammar

public class ContextFreeGrammar
extends java.lang.Object
implements FiniteAutomata

Context-free grammars are a more powerful method of describing languages. Such grammars can describe certain features that have a recursive structure which makes them useful in a variety of applications.

The collection of langauges associated with context-free grammars are called context-free languages. They include all the regular languages and many additional languages.

A context-free grammar is a 4-tuple (V, Σ, R, S), where

  1. V is a finite set called the variables,
  2. Σ is a finite set, disjoint from V, called the terminals,
  3. R is a finite set of productions, with each production being a variable and a string of variables and terminals, and
  4. S∈V is the start variable

See Also:
PushdownAutomata, Serialized Form

Nested Class Summary
protected static class ContextFreeGrammar.CFGSymbol
           
 
Field Summary
protected  java.util.Map cachedFirst
           
protected  java.util.Map cachedFollow
           
protected  boolean inChomskyNormalForm
           
protected  java.util.Set nullable
           
protected  java.util.Set productions
           
protected  java.util.Map productionVarToYield
           
protected  java.lang.Object startVariable
           
protected  java.util.Set terminals
           
protected  java.util.Set variables
           
 
Constructor Summary
ContextFreeGrammar(DeterministicFiniteAutomata dfa)
          Constructs a ContextFreeGrammar for the langauge accepted by this DeterministicFiniteAutomata.
ContextFreeGrammar(java.util.Set variables, java.util.Set terminals, java.util.Set productions, java.lang.Object startVariable)
          Creates a new ContextFreeGrammar.
 
Method Summary
 boolean accept(java.util.Iterator iterator)
           
 AugmentedGrammar augment()
          If G is a grammar with start symbol S, the G', the augmented grammar for G, is G with a new start symbol S' and production S' → S.
protected  void computeAux()
           
protected  void computeFirst()
           
protected  void computeFollow()
           
protected  void computeNullable()
           
protected  java.util.Set first(java.util.List string)
          If α is any string of grammar symbols, let first(α) be the set of terminals that begin the string derived from α.
protected  java.util.Set first(java.lang.Object X)
           
protected  java.util.Set follow(java.lang.Object A)
           
 java.util.Set getProductions()
          Returns a mutable view of the productions of this CFG
 java.lang.Object getStartVariable()
          Returns the start variable for this CFG
 java.util.Set getTerminals()
          Returns a mutable view of the terminals of this CFG
 java.util.Set getVariables()
          Returns a mutable view of the variables of this CFG
protected  boolean isNullable(java.util.Collection vars)
           
protected  boolean isNullable(java.lang.Object var)
           
static void main(java.lang.String[] args)
           
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

variables

protected java.util.Set variables

terminals

protected java.util.Set terminals

productions

protected java.util.Set productions

startVariable

protected java.lang.Object startVariable

nullable

protected java.util.Set nullable

productionVarToYield

protected java.util.Map productionVarToYield

cachedFirst

protected java.util.Map cachedFirst

cachedFollow

protected java.util.Map cachedFollow

inChomskyNormalForm

protected boolean inChomskyNormalForm
Constructor Detail

ContextFreeGrammar

public ContextFreeGrammar(DeterministicFiniteAutomata dfa)
Constructs a ContextFreeGrammar for the langauge accepted by this DeterministicFiniteAutomata. The construction is simple. You can convert and DeterministicFiniteAutomata into an equivalent ContextFreeGrammar as follows:
  1. Make a variable Ri for each state qi of the DeterministicFiniteAutomata
  2. Add the rule Ri → a Rj to the ContextFreeGrammar if δ(qi, a) = qj is a transition in the DeterministicFiniteAutomata
  3. Add the rule Ri → ε if qi is an accept state of the DeterministicFiniteAutomata
  4. Make R0 the start variable of the grammar, where q0 is the start state of the machine


ContextFreeGrammar

public ContextFreeGrammar(java.util.Set variables,
                          java.util.Set terminals,
                          java.util.Set productions,
                          java.lang.Object startVariable)
Creates a new ContextFreeGrammar.

Parameters:
variables - V is a finite set called the variables
productions - R is a finite set of productions, with each production being a variable and a string of variables and terminals
Method Detail

getVariables

public java.util.Set getVariables()
Returns a mutable view of the variables of this CFG

Returns:
a mutable view of the variables of this CFG

getTerminals

public java.util.Set getTerminals()
Returns a mutable view of the terminals of this CFG

Returns:
a mutable view of the terminals of this CFG

getProductions

public java.util.Set getProductions()
Returns a mutable view of the productions of this CFG

Returns:
a mutable view of the productions of this CFG

getStartVariable

public java.lang.Object getStartVariable()
Returns the start variable for this CFG

Returns:
the start variable for this CFG

augment

public AugmentedGrammar augment()
If G is a grammar with start symbol S, the G', the augmented grammar for G, is G with a new start symbol S' and production S' → S. The purpose of this new starting production is to indicate to the parser when it should stop parsing and announce acceptance of the input. That is, acceptance occurs when and only when the parser is about to reduce S' → S.

Returns:
the augmented version of this ContextFreeGrammar

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object

computeAux

protected void computeAux()

computeNullable

protected void computeNullable()

computeFirst

protected void computeFirst()

computeFollow

protected void computeFollow()

first

protected java.util.Set first(java.lang.Object X)

first

protected java.util.Set first(java.util.List string)
If α is any string of grammar symbols, let first(α) be the set of terminals that begin the string derived from α. If α → ε, then ε is also in first(α).

Parameters:
string - A string of grammar symbols to find the first set for

follow

protected java.util.Set follow(java.lang.Object A)

isNullable

protected boolean isNullable(java.util.Collection vars)

isNullable

protected boolean isNullable(java.lang.Object var)

accept

public boolean accept(java.util.Iterator iterator)
Specified by:
accept in interface FiniteAutomata
Parameters:
iterator - A string over some alphabet Σ
Returns:
true if this machine accepts w

main

public static void main(java.lang.String[] args)