java_cup

Class lalr_item_set

public class lalr_item_set extends Object

This class represents a set of LALR items. For purposes of building these sets, items are considered unique only if they have unique cores (i.e., ignoring differences in their lookahead sets).

This class provides fairly conventional set oriented operations (union, sub/super-set tests, etc.), as well as an LALR "closure" operation (see compute_closure()).

Version: last updated: 3/6/96

Author: Scott Hudson

See Also: lalr_item lalr_state

Field Summary
protected Integerhashcode_cache
Cached hashcode for this set.
protected Hashtable_all
A hash table to implement the set.
Constructor Summary
lalr_item_set()
Constructor for an empty set.
lalr_item_set(lalr_item_set other)
Constructor for cloning from another set.
Method Summary
lalr_itemadd(lalr_item itm)
Add a singleton item, merging lookahead sets if the item is already part of the set. returns the element of the set that was added or merged into.
voidadd(lalr_item_set other)
Add a complete set, merging lookaheads where items are already in the set
Enumerationall()
Access to all elements of the set.
voidcompute_closure()
Compute the closure of the set using the LALR closure rules.
booleancontains(lalr_item itm)
Does the set contain a particular item?
booleanequals(lalr_item_set other)
Equality comparison.
booleanequals(Object other)
Generic equality comparison.
lalr_itemfind(lalr_item itm)
Return the item in the set matching a particular item (or null if not found)
lalr_itemget_one()
Remove and return one item from the set (done in hash order).
inthashCode()
Return hash code.
booleanis_subset_of(lalr_item_set other)
Is this set an (improper) subset of another?
booleanis_superset_of(lalr_item_set other)
Is this set an (improper) superset of another?
protected voidnot_null(Object obj)
Helper function for null test.
voidremove(lalr_item itm)
Remove a single item if it is in the set.
voidremove(lalr_item_set other)
Remove (set subtract) a complete set.
intsize()
Size of the set
StringtoString()
Convert to string.

Field Detail

hashcode_cache

protected Integer hashcode_cache
Cached hashcode for this set.

_all

protected Hashtable _all
A hash table to implement the set. We store the items using themselves as keys.

Constructor Detail

lalr_item_set

public lalr_item_set()
Constructor for an empty set.

lalr_item_set

public lalr_item_set(lalr_item_set other)
Constructor for cloning from another set.

Parameters: other indicates set we should copy from.

Method Detail

add

public lalr_item add(lalr_item itm)
Add a singleton item, merging lookahead sets if the item is already part of the set. returns the element of the set that was added or merged into.

Parameters: itm the item being added.

add

public void add(lalr_item_set other)
Add a complete set, merging lookaheads where items are already in the set

Parameters: other the set to be added.

all

public Enumeration all()
Access to all elements of the set.

compute_closure

public void compute_closure()
Compute the closure of the set using the LALR closure rules. Basically for every item of the form:
    [L ::= a *N alpha, l] 
  
(where N is a a non terminal and alpha is a string of symbols) make sure there are also items of the form:
    [N ::= *beta, first(alpha l)] 
  
corresponding to each production of N. Items with identical cores but differing lookahead sets are merged by creating a new item with the same core and the union of the lookahead sets (the LA in LALR stands for "lookahead merged" and this is where the merger is). This routine assumes that nullability and first sets have been computed for all productions before it is called.

contains

public boolean contains(lalr_item itm)
Does the set contain a particular item?

Parameters: itm the item in question.

equals

public boolean equals(lalr_item_set other)
Equality comparison.

equals

public boolean equals(Object other)
Generic equality comparison.

find

public lalr_item find(lalr_item itm)
Return the item in the set matching a particular item (or null if not found)

Parameters: itm the item we are looking for.

get_one

public lalr_item get_one()
Remove and return one item from the set (done in hash order).

hashCode

public int hashCode()
Return hash code.

is_subset_of

public boolean is_subset_of(lalr_item_set other)
Is this set an (improper) subset of another?

Parameters: other the other set in question.

is_superset_of

public boolean is_superset_of(lalr_item_set other)
Is this set an (improper) superset of another?

Parameters: other the other set in question.

not_null

protected void not_null(Object obj)
Helper function for null test. Throws an interal_error exception if its parameter is null.

Parameters: obj the object we are testing.

remove

public void remove(lalr_item itm)
Remove a single item if it is in the set.

Parameters: itm the item to remove.

remove

public void remove(lalr_item_set other)
Remove (set subtract) a complete set.

Parameters: other the set to remove.

size

public int size()
Size of the set

toString

public String toString()
Convert to string.