Class Grammar

java.lang.Object
  Grammar

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