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 R_i for each state q_i of the DeterministicFiniteAutomata
2. Add the rule R_i → a R_j to the ContextFreeGrammar if δ(q_i, a) = q_j is a transition in the DeterministicFiniteAutomata
3. Add the rule R_i → ε if q_i is an accept state of the DeterministicFiniteAutomata
4. Make R₀ the start variable of the grammar, where q₀ 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)