Generic Interpreter 0.9
Private API

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:
0.9
Author:
© 1999-2000 Craig A. Rich <carich@acm.org>
See Also:
Source code

Inner Class Summary
(package private) static class LR0_Grammar.Context
          This class implements a shift/reduce Context.
(package private) static class LR0_Grammar.State
          This class implements a State in an LR parser.
 
Inner classes inherited from class gi.Grammar
Grammar.ParseTree, Grammar.Production, Grammar.Semantics
 
Inner classes 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, Lexicon.Singleton, Lexicon.UnicodeCategory, Lexicon.Union
 
Field Summary
(package private)  LR0_Grammar.Context start
          The start Context.
private  Lexicon.Set states
          The states through which this parser transitions.
private  Lexicon.Set trees
          The parse trees through which this parser transitions.
 
Fields inherited from class gi.Grammar
first, firsts, follows, productions, size, terminals
 
Fields inherited from class gi.Lexicon
accepts, END_OF_SOURCE, END_OF_SOURCE_EXPRESSION, initial, transitions, word
 
Constructor Summary
protected LR0_Grammar()
          Constructs an LR(0) parser around a new empty Grammar.
protected LR0_Grammar(Grammar grammar)
          Constructs an LR(0) parser around an existing Grammar.
 
Method Summary
private  LR0_Grammar.State closure(LR0_Grammar.State from)
          Computes the null-closure of a State.
private  Lexicon.Set expected(LR0_Grammar.State state)
          Computes the terminals expected in a State.
(package private)  Grammar.ParseTree interpret(LineNumberReader source)
          Interprets a source character stream by LR shift-reduce ascent.
(package private)  Grammar.Production parse(LR0_Grammar.State state, Object lookahead)
          Computes the Production to use in a reverse rightmost derivation.
private static LR0_Grammar.State transition(LR0_Grammar.State from, Object on, LR0_Grammar.State to)
          Computes a transition from a State on a symbol.
 
Methods inherited from class gi.Grammar
first, first, follow, grab, interpret, interpret, interpret, interpret, interpret, interpret, interpret, nonterminal, put, put, terminal
 
Methods inherited from class gi.Lexicon
closure, expression, initial, put, put, recognize, state, transition, word
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait
 

Field Detail

start

final LR0_Grammar.Context start

The start Context.


states

private final Lexicon.Set states

The states through which this parser transitions.


trees

private final Lexicon.Set trees

The parse trees through which this parser transitions.

Constructor Detail

LR0_Grammar

protected LR0_Grammar()

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


LR0_Grammar

protected LR0_Grammar(Grammar grammar)

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

Parameters:
grammar - the Grammar around which the parser is constructed.
Method Detail

closure

private LR0_Grammar.State closure(LR0_Grammar.State from)

Computes the null-closure of a State.

Parameters:
from - the State whose null-closure is computed.
Returns:
the reflexive transitive closure of from under null transition.

expected

private Lexicon.Set expected(LR0_Grammar.State state)

Computes the terminals expected in a State.

Parameters:
state - the State.
Returns:
the terminals matching a shift or reduce Context in state.

interpret

Grammar.ParseTree 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.

parse

Grammar.Production parse(LR0_Grammar.State state,
                         Object lookahead)

Computes the Production to use in a reverse rightmost derivation.

Parameters:
state - the State.
lookahead - the lookahead terminal.
Returns:
the highest priority Production underlying an applicable reduce Context in state; returns null if none.

transition

private static LR0_Grammar.State transition(LR0_Grammar.State from,
                                            Object on,
                                            LR0_Grammar.State to)

Computes a transition from a State on a symbol.

Parameters:
from - the State from which the transition is made.
on - the symbol on which the transition is made.
to - the State to which the transition is made.
Returns:
the State to which the transition is made.

 

© 1999-2000 Craig A. Rich <carich@acm.org>