org.metasyntactic.math.automata
Class LR0Item

java.lang.Object
  |
  +--org.metasyntactic.math.automata.Production
        |
        +--org.metasyntactic.math.automata.LR0Item
All Implemented Interfaces:
java.lang.Comparable, java.io.Serializable
Direct Known Subclasses:
LR1Item

public class LR0Item
extends Production

An LR(0) item (item for short) of a grammar G is a production of G with a dot at some position of the right side. Thus, production A → XYZ yields the four items

      A → .XYZ
      A → X.YZ
      A → XY.Z
      A → XYZ.
 

See Also:
Serialized Form

Field Summary
protected  int dotPosition
           
 
Fields inherited from class org.metasyntactic.math.automata.Production
variable, yield
 
Constructor Summary
  LR0Item(java.lang.Object variable, java.util.List yield)
           
protected LR0Item(Production production, int dotPosition)
           
 
Method Summary
static java.util.Set _goto(AugmentedGrammar G_prime, java.util.Set I, java.lang.Object X)
          Goto(I, X) is defined to be the closure of the set of all items [A → αX.Β] such that [A → α.XΒ] is in I.
static java.util.Set closure(AugmentedGrammar G_prime, java.util.Set I)
          If I is a set of items for a grammar G, then closure(I) is the set of items constructed from I by the two rules: Initially, every item in I is added to closure(I) If A → α.BΒ is in closure(I) and B → γ is a production, then add the itm B → .γ to I, if is not already there.
 boolean equals(java.lang.Object o)
           
static java.util.Set getItems(Production production)
           
 java.lang.Object getSymbolAtDot()
           
 int hashCode()
           
 boolean isReduce()
           
 boolean isShift(ContextFreeGrammar g)
           
static java.util.Set items(AugmentedGrammar G_prime)
          Items returns the canonical collection of sts of LRItems for an augmented grammar G'
static void main(java.lang.String[] args)
           
 java.lang.String toString()
           
 
Methods inherited from class org.metasyntactic.math.automata.Production
compareTo, get, getVariable, getYield, toLatex
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

dotPosition

protected int dotPosition
Constructor Detail

LR0Item

public LR0Item(java.lang.Object variable,
               java.util.List yield)

LR0Item

protected LR0Item(Production production,
                  int dotPosition)
Method Detail

isReduce

public boolean isReduce()

isShift

public boolean isShift(ContextFreeGrammar g)

getSymbolAtDot

public java.lang.Object getSymbolAtDot()

getItems

public static java.util.Set getItems(Production production)

hashCode

public int hashCode()
Overrides:
hashCode in class Production

equals

public boolean equals(java.lang.Object o)
Overrides:
equals in class Production

toString

public java.lang.String toString()
Overrides:
toString in class Production

items

public static java.util.Set items(AugmentedGrammar G_prime)
Items returns the canonical collection of sts of LRItems for an augmented grammar G'


closure

public static java.util.Set closure(AugmentedGrammar G_prime,
                                    java.util.Set I)
If I is a set of items for a grammar G, then closure(I) is the set of items constructed from I by the two rules:
  1. Initially, every item in I is added to closure(I)
  2. If A → α.BΒ is in closure(I) and B → γ is a production, then add the itm B → .γ to I, if is not already there. We apply the rule until no more new items can be added to closure(I).

Intuitively, A → α.Bβ in closure(I) indicates that, at some point in the parsing process, we think we might next see a substring derivable from BΒ as input. If B → γ is a production, we also expect we might see a substring drivable from γ at this point. For this reason we also include B → .γ in closure(I).


_goto

public static java.util.Set _goto(AugmentedGrammar G_prime,
                                  java.util.Set I,
                                  java.lang.Object X)
Goto(I, X) is defined to be the closure of the set of all items [A → αX.Β] such that [A → α.XΒ] is in I. Intuitively, if I is the set of items that are valid for some viable prefix γ, then goto(I, X) is the set of items that are valid for the viable prefix X.


main

public static void main(java.lang.String[] args)