gi
Class LR0_Grammar

java.lang.Object
  gi.Lexicon
      gi.Grammar
          gi.LR0_Grammar

Direct Known Subclasses:

LR1_Grammar, SLR1_Grammar

public class LR0_Grammar
extends Grammar

This class implements an LR(0) parser around a Grammar. The parser adapts to changes in the underlying Grammar. Semantics in a phrase are evaluated during a bottom-up parse, from left to right after all subtrees rooted in the phrase have been constructed. Attributes throughout the phrase are available during evaluation. LR(0) parsing is not very practical, since it ignores lookahead information and is easily confused, but it forms a basis around which SLR(1) and LR(1) parsers are constructed.

Version:

1.3

Author:

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

Nested Class Summary

(package private) static class	LR0_Grammar.Context This class implements an LR(0) Context.
(package private) static class	LR0_Grammar.Set<E extends LR0_Grammar.Context> This class implements a Set of LR(0) Contexts.

Nested classes/interfaces inherited from class gi.Grammar

Grammar.ParseTree, Grammar.Production, Grammar.Semantics

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.Singleton, Lexicon.UnicodeCategory, Lexicon.Union

Field Summary

(package private) static Object

S$ The augmented start symbol.

Fields inherited from class gi.Grammar

CONFLICT, FIRST_FOLLOW, P, PARSE_TREE, S, SYNTAX

Fields inherited from class gi.Lexicon

$, debug, LEXICAL, TERMINALS, VERBOSE

Constructor Summary

protected	LR0_Grammar() Constructs an LR(0) parser around a new empty Grammar.
protected	LR0_Grammar(Grammar G) Constructs an LR(0) parser around an existing Grammar.

Method Summary

(package private) LR0_Grammar.Set<LR0_Grammar.Context>	closure(LR0_Grammar.Set<LR0_Grammar.Context> C) Computes the reflexive transitive closure of a Set of LR(0) Contexts under empty transition.
(package private) Lexicon.Set<Object>	expected(LR0_Grammar.Set<LR0_Grammar.Context> C) Computes the terminals expected in a Set of LR(0) Contexts.
(package private) LR0_Grammar.Set<LR0_Grammar.Context>	initial() Computes the initial state of the LR(0) DFA.
(package private) Object	interpret(LineNumberReader source) Interprets a source character stream by LR shift-reduce ascent.
(package private) Grammar.Production	parse(LR0_Grammar.Set<LR0_Grammar.Context> C, Object a) Computes the Production to use in a reverse rightmost derivation.
String	toString() Returns the string representation of this parser, specifically "LR(0)".
(package private) LR0_Grammar.Set<LR0_Grammar.Context>	transition(LR0_Grammar.Set<LR0_Grammar.Context> C, Object X) Computes a transition from a Set of LR(0) Contexts on a symbol.

Methods inherited from class gi.Grammar

first, first, first, follow, grab, interpret, nonterminal, put, put, terminal

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, wait, wait, wait

Field Detail

S$

static final Object S$

The augmented start symbol.

Constructor Detail

LR0_Grammar

protected LR0_Grammar()

Constructs an LR(0) parser around a new empty Grammar.

LR0_Grammar

protected LR0_Grammar(Grammar G)

Constructs an LR(0) parser around an existing Grammar.

Parameters:

G - the Grammar around which the parser is constructed.

Method Detail

transition

LR0_Grammar.Set<LR0_Grammar.Context> transition(LR0_Grammar.Set<LR0_Grammar.Context> C,
                                                Object X)

Computes a transition from a Set of LR(0) Contexts on a symbol.

Parameters:

C - the Set of LR(0) Contexts from which the transition is made.

X - the symbol on which the transition is made.

Returns:

the Set of LR(0) Contexts to which the transition is made.

closure

LR0_Grammar.Set<LR0_Grammar.Context> closure(LR0_Grammar.Set<LR0_Grammar.Context> C)

Computes the reflexive transitive closure of a Set of LR(0) Contexts under empty transition.

Parameters:

C - the Set of LR(0) Contexts whose reflexive transitive closure is computed under empty transition.

Returns:

the reflexive transitive closure of C under empty transition.

initial

LR0_Grammar.Set<LR0_Grammar.Context> initial()

Computes the initial state of the LR(0) DFA.

Returns:

the initial state of the LR(0) DFA.

parse

Grammar.Production parse(LR0_Grammar.Set<LR0_Grammar.Context> C,
                         Object a)

Computes the Production to use in a reverse rightmost derivation.

Parameters:

C - the Set of LR(0) Contexts.

a - the lookahead terminal.

Returns:

the highest priority Production underlying an applicable reduce Context in C; returns null if none.

expected

Lexicon.Set<Object> expected(LR0_Grammar.Set<LR0_Grammar.Context> C)

Computes the terminals expected in a Set of LR(0) Contexts.

Parameters:

C - the Set of LR(0) Contexts.

Returns:

the terminals matching a shift or reduce Context in C.

interpret

Object interpret(LineNumberReader source)
           throws Lexicon.Exception

Interprets a source character stream by LR shift-reduce ascent.

Overrides:

interpret in class Grammar

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.

toString

public String toString()

Returns the string representation of this parser, specifically "LR(0)".

Overrides:

toString in class Object

Returns:

the string representation of this parser, specifically "LR(0)".

Since:

1.1