Class Grammar

java.lang.Object
  extended byGrammar

public class Grammar
extends java.lang.Object

This class implements context-free grammars. The productions of the grammar are stored in an array productionsArray. Each production is an object of the class Production. There are separated alphabets terminals for terminals and variables for variables plus an alphabet alphabet for their union. The usual functions First() and Follow() are implemented as methods of this class. The grammar can be read from a file where the productions are listed one by line in the form l:r with a ":" separating the two sides of each production. The initial rule should be the last one. The following grammars are included in the directory Data:
ETF.txt the ordinary ETF grammar, which is SLR but not LL(1).
ETFPrime.txt the variant of the ETF grammar which is LL(1) obtained by eliminating left recursion.
Dyck.txt the grammar of the Dyck language, which is LL(1).


Field Summary
 Alphabet alphabet
          The total alphabet.
 java.util.Set[] derive
          The set of rules with given left symbol.
 boolean[] epsilon
          The erasable symbols.
 int initial
          The initial production.
 int lgProductions
          The sum of lengths of productions .
 int nbProductions
          The number of productions.
 Production[] productionsArray
          The array of grammar productions.
 Alphabet terminals
          The terminals.
 Alphabet variables
          The variables.
 
Constructor Summary
Grammar(int n)
          Creates a grammar with n symbols.
 
Method Summary
static Grammar Dyck()
          The Dyck grammar:
S -> (S)S | "".
 void epsilon()
          Implements Epsilon().
static Grammar ETF()
          The ETF grammar :
E -> E + T
T -> T * F
F -> (E) | char .
static Grammar ETFPrime()
          The modified version of the ETF grammar which is LL(1) :
E -> Te
e -> +Te | ""
T -> Ft
t -> *Ft | ""
F -> (E) | char .
 void exploreFirstChild(short v, boolean[] mark)
          Explores the graph of First.
 void exploreSibling(short v, boolean[] mark)
          Explores the graph of Follow().
 java.util.Set first(short[] s)
          Extends the function First() to Strings.
 java.util.Set firstChild(short v)
          Implements the fuction FirstChild().
 java.util.Set follow(short v)
          Implements the function Follow().
static Grammar fromFile(java.lang.String name)
           
 void initAlphabet()
          Initializes alphabet, variables and terminals.
 void initGrammar()
          Computes derive, alphabet and epsilon.
static void main(java.lang.String[] args)
           
 java.util.Set sibling(short v)
          Implements the function Sibling().
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

productionsArray

public Production[] productionsArray
The array of grammar productions.


nbProductions

public int nbProductions
The number of productions.


lgProductions

public int lgProductions
The sum of lengths of productions .


epsilon

public boolean[] epsilon
The erasable symbols.


derive

public java.util.Set[] derive
The set of rules with given left symbol.


variables

public Alphabet variables
The variables. The set of variables is supposed to coincide with the set of left sides of productions.


terminals

public Alphabet terminals
The terminals. The terminal characters represent tokens of the lexical analysis.


alphabet

public Alphabet alphabet
The total alphabet. It is the union of the terminals and variable sets.


initial

public int initial
The initial production. Usually of the form I -> E$.

Constructor Detail

Grammar

public Grammar(int n)
Creates a grammar with n symbols.

Method Detail

fromFile

public static Grammar fromFile(java.lang.String name)
                        throws java.io.IOException
Throws:
java.io.IOException

epsilon

public void epsilon()
Implements Epsilon(). Initializes the boolean array epsilon of erasable symbols.


firstChild

public java.util.Set firstChild(short v)
Implements the fuction FirstChild().

Parameters:
v - a letter (variable or terminal)
Returns:
the sucessors of v in the graph First (terminals and variables).

exploreFirstChild

public void exploreFirstChild(short v,
                              boolean[] mark)
Explores the graph of First.

Parameters:
v - a letter (variable or terminal)
mark - the array of marks used for the exploration.

first

public java.util.Set first(short[] s)
Extends the function First() to Strings.


sibling

public java.util.Set sibling(short v)
Implements the function Sibling().

Parameters:
v - a variable
Returns:
the set Sibling(v) of sucessors of the variable v in the graph of Follow().

exploreSibling

public void exploreSibling(short v,
                           boolean[] mark)
Explores the graph of Follow().

Parameters:
v - a variable

follow

public java.util.Set follow(short v)
Implements the function Follow().

Parameters:
v - a variable
Returns:
the set of terminals in the set Follow(v)

Dyck

public static Grammar Dyck()
The Dyck grammar:
S -> (S)S | "".


ETF

public static Grammar ETF()
The ETF grammar :
E -> E + T
T -> T * F
F -> (E) | char .


ETFPrime

public static Grammar ETFPrime()
The modified version of the ETF grammar which is LL(1) :
E -> Te
e -> +Te | ""
T -> Ft
t -> *Ft | ""
F -> (E) | char .


initAlphabet

public void initAlphabet()
Initializes alphabet, variables and terminals.


initGrammar

public void initGrammar()
Computes derive, alphabet and epsilon.


toString

public java.lang.String toString()

main

public static void main(java.lang.String[] args)
                 throws java.io.IOException
Throws:
java.io.IOException