gi
Class Grammar

java.lang.Object
  gi.Lexicon
      gi.Grammar

Direct Known Subclasses:

LL1_Grammar, LR0_Grammar

public class Grammar
extends Lexicon

This class implements a Grammar.

Version:

1.3

Author:

© 1999-2009 Craig A. Rich <carich@csupomona.edu>

Nested Class Summary

protected static class	Grammar.ParseTree This class implements a ParseTree constructed by interpreting a source stream.
(package private) static class	Grammar.Production This class implements a Production.
protected static class	Grammar.Semantics This class implements Semantics embedded in productions and evaluated when interpreting.

Nested classes/interfaces inherited from class gi.Lexicon

Lexicon.Alphabet, Lexicon.Concatenation, Lexicon.Exception, Lexicon.Expression, Lexicon.Match, Lexicon.NonMatch, Lexicon.PosixClass, Lexicon.Range, Lexicon.Repetition, Lexicon.Set<E>, Lexicon.Singleton, Lexicon.UnicodeCategory, Lexicon.Union

Field Summary

protected static int	CONFLICT debug switch constant enables printing parsing conflicts encountered during syntax analysis.
private Map<Object,Lexicon.Set<Object>>	first The mapping from a nonterminal to its first set in this Grammar.
private Lexicon.Set<Object>	first_beta A first set computed by first(beta, start).
protected static int	FIRST_FOLLOW debug switch constant enables printing first and follow sets precomputed during syntax analysis.
private Map<Object,Lexicon.Set<Object>>	follow The mapping from a nonterminal to its follow set in this Grammar.
(package private) Map<Object,Stack<Grammar.Production>>	P The Productions put into this Grammar.
protected static int	PARSE_TREE debug switch constant enables printing each ParseTree produced by syntax analysis.
private static int	PSize The number of Productions constructed.
(package private) Object	S The start symbol of this Grammar.
protected static int	SYNTAX debug switch constant enables printing parsing decisions made during syntax analysis.
private HashSet<Object>	T The terminals put into this Grammar.

Fields inherited from class gi.Lexicon

$, debug, LEXICAL, TERMINALS, VERBOSE

Constructor Summary

protected	Grammar() Constructs an empty Grammar.
(package private)	Grammar(Grammar G) Constructs a Grammar that is a shallow copy of G.

Method Summary

(package private) Lexicon.Set<Object>	first(Object nonterminal) Returns the first set of a nonterminal.
(package private) Lexicon.Set<Object>	first(Object[] beta) Computes the first set of a phrase.
(package private) Lexicon.Set<Object>	first(Object[] beta, int start) Computes the first set of a phrase.
(package private) Lexicon.Set<Object>	follow(Object nonterminal) Returns the follow set of a nonterminal.
protected Object	grab(LineNumberReader source) Grabs a terminal from a source character stream using this Grammar.
(package private) Object	interpret(LineNumberReader source) Interprets a source character stream using an LR(1) parser around this Grammar.
void	interpret(String[] arguments) Interprets by command-line arguments using this Grammar.
(package private) boolean	nonterminal(Object X) Indicates whether a symbol is a nonterminal in this Grammar.
protected void	put(Object nonterminal, Object[] phrase) Puts a production into this Grammar.
protected void	put(Object nonterminal, Object[][] phrases) Puts productions into this Grammar.
(package private) boolean	terminal(Object X) Indicates whether a symbol is a terminal in this Grammar.

Methods inherited from class gi.Lexicon

expression, interpret, interpret, interpret, interpret, interpret, interpret, put, word

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

PSize

private static int PSize

The number of Productions constructed.

P

final Map<Object,Stack<Grammar.Production>> P

The Productions put into this Grammar. It is a mapping from a nonterminal to its Productions.

S

Object S

The start symbol of this Grammar. It is the nonterminal on the left side of the Production first put into this Grammar.

T

private final HashSet<Object> T

The terminals put into this Grammar. When empty, there is a need to discover terminals. It is computed only on demand created by terminal(X).

FIRST_FOLLOW

protected static final int FIRST_FOLLOW

debug switch constant enables printing first and follow sets precomputed during syntax analysis.

Since:

1.1

See Also:

Constant Field Values

SYNTAX

protected static final int SYNTAX

debug switch constant enables printing parsing decisions made during syntax analysis.

Since:

1.1

See Also:

Constant Field Values

CONFLICT

protected static final int CONFLICT

debug switch constant enables printing parsing conflicts encountered during syntax analysis.

Since:

1.1

See Also:

Constant Field Values

PARSE_TREE

protected static final int PARSE_TREE

debug switch constant enables printing each ParseTree produced by syntax analysis.

Since:

1.1

See Also:

Constant Field Values

first

private final Map<Object,Lexicon.Set<Object>> first

The mapping from a nonterminal to its first set in this Grammar. When empty, there is a need to compute current first sets. It is computed only on demand created by first(nonterminal).

first_beta

private final Lexicon.Set<Object> first_beta

A first set computed by first(beta, start).

follow

private final Map<Object,Lexicon.Set<Object>> follow

The mapping from a nonterminal to its follow set in this Grammar. When empty, there is a need to compute current follow sets. It is computed only on demand created by follow(nonterminal).

Constructor Detail

Grammar

protected Grammar()

Constructs an empty Grammar.

Grammar

Grammar(Grammar G)

Constructs a Grammar that is a shallow copy of G. The fields of the new Grammar refer to the same objects as those in G.

Parameters:

G - the Grammar copied.

Method Detail

put

protected void put(Object nonterminal,
                   Object[] phrase)

Puts a production into this Grammar. The start symbol is the first nonterminal put in this Grammar.

Parameters:

nonterminal - the nonterminal added to this Grammar.

phrase - the phrase produced by nonterminal. phrase may contain nonterminals, terminals, and Semantics.

put

protected void put(Object nonterminal,
                   Object[][] phrases)

Puts productions into this Grammar. The productions are successively added using put(nonterminal, phrase).

Parameters:

nonterminal - the nonterminal on the left side of the productions.

phrases - the phrases produced by nonterminal. Each phrase in phrases may contain nonterminals, terminals, and Semantics.

nonterminal

boolean nonterminal(Object X)

Indicates whether a symbol is a nonterminal in this Grammar.

Parameters:

X - the symbol whose status is requested.

Returns:

true if X is a nonterminal in this Grammar; false otherwise.

terminal

boolean terminal(Object X)

Indicates whether a symbol is a terminal in this Grammar.

Overrides:

terminal in class Lexicon

Parameters:

X - the symbol whose status is requested.

Returns:

true if X is a terminal in this Grammar; false otherwise.

grab

protected Object grab(LineNumberReader source)
               throws Lexicon.Exception

Grabs a terminal from a source character stream using this Grammar. Invokes Lexicon.grab(source) until it returns a terminal occurring in a phrase of this Grammar or end of source. Blocks until a character is available, an I/O error occurs, or the end of the source stream is reached.

Overrides:

grab in class Lexicon

Parameters:

source - the source character stream.

Returns:

the first terminal occurring in a phrase of this Grammar.

Throws:

Lexicon.Exception - if an I/O or lexical error occurs.

interpret

Object interpret(LineNumberReader source)
           throws Lexicon.Exception

Interprets a source character stream using an LR(1) parser around this Grammar. This method is overridden by all parsers, so it is only invoked when this Grammar has not been extended by a parser.

Overrides:

interpret in class Lexicon

Parameters:

source - the source character stream.

Returns:

the ParseTree constructed by interpreting source.

Throws:

Lexicon.Exception - if an I/O, lexical, syntax or semantic error occurs.

interpret

public void interpret(String[] arguments)

Interprets by command-line arguments using this Grammar. When interpreting, the parser used will be (in order):

• The parser most recently constructed by preceding command-line arguments.
• The parser originally around this Grammar.
• An LR(1) parser.

The first I/O, lexical, syntax or semantic error that occurs when interpreting is printed to the standard error stream.

Overrides:

interpret in class Lexicon

Parameters:

arguments - the command-line arguments controlling the interpreter.

The following arguments may appear zero or more times, are processed in order, and have the following effects:

-t, --terminals

Print the set of terminals in this Grammar before subsequent syntax analyses.

-l, --lexical

Print terminals in this Grammar grabbed during subsequent syntax analyses.

-f, --firstfollow

Print first and follow sets precomputed during subsequent syntax analyses.

-s, --syntax

Print parsing decisions made during subsequent syntax analyses.

-c, --conflict

Print parsing conflicts encountered during subsequent syntax analyses.

-p, --parsetree, --tree

Print each ParseTree produced by subsequent syntax analyses.

-v, --verbose

Print maximum debugging. Equivalent to -tlfscp.

--ll1

Construct an LL(1) parser around this Grammar.

--lr0

Construct an LR(0) parser around this Grammar.

--slr1

Construct an SLR(1) parser around this Grammar.

--lr1

Construct an LR(1) parser around this Grammar.

-

Interpret the standard input stream using this Grammar.

filename

Interpret source file filename using this Grammar.

If no filename arguments are given, the standard input stream is interpreted.

first

Lexicon.Set<Object> first(Object nonterminal)

Returns the first set of a nonterminal.

Parameters:

nonterminal - the nonterminal whose first set is requested.

Returns:

first.get(nonterminal), computing first if there is a need to compute current first sets.

first

Lexicon.Set<Object> first(Object[] beta,
                          int start)

Computes the first set of a phrase.

Parameters:

beta - the phrase whose first set is computed.

start - the index at which to start computing the first set.

Returns:

first(beta[start..beta.length-1]).

first

Lexicon.Set<Object> first(Object[] beta)

Computes the first set of a phrase.

Parameters:

beta - the phrase whose first set is computed.

Returns:

first(beta).

follow

Lexicon.Set<Object> follow(Object nonterminal)

Returns the follow set of a nonterminal.

Parameters:

nonterminal - the nonterminal whose follow set is requested.

Returns:

follow.get(nonterminal), computing follow if there is a need to compute current follow sets.