-- LR0ItemSetsBasicImpl.mesa -- last edit August 25, 1984 1:52:07 pm PDT DIRECTORY GrammarBasic USING[Grammar, GetLR0ItemSetCollection, NoteLR0ItemSetCollection], LR0ItemSetsBasic USING[LR0Item], LR0ItemSets USING[]; LR0ItemSetsBasicImpl: CEDAR PROGRAM IMPORTS GrammarBasic EXPORTS LR0ItemSetsBasic = BEGIN OPEN GrammarBasic, LR0ItemSetsBasic; LR0ItemSetCollection: TYPE = REF LR0ItemSetCollectionBody; LR0ItemSetCollectionBody: TYPE = RECORD[ grammar: Grammar, firstSet: LR0ItemSet, hashTable: LR0HashTable]; TentativeLR0ItemSet: TYPE = REF TentativeLR0ItemSetBody; TentativeLR0ItemSetBody: PUBLIC TYPE = RECORD[ collection: LR0ItemSetCollection, firstCell: TentativeLR0ItemSetChainCell, recentCell: TentativeLR0ItemSetChainCell _ NIL]; TentativeLR0ItemSetChainCell: TYPE = REF TentativeLR0ItemSetChainCellBody; TentativeLR0ItemSetChainCellBody: TYPE = RECORD[ lr0Item: LR0Item, next: TentativeLR0ItemSetChainCell]; LR0ItemSet: TYPE = REF LR0ItemSetBody; LR0ItemSetBody: PUBLIC TYPE = RECORD[ associatedNode: REF ANY, firstChainCell: LR0ItemSetChainCell, nextSet: LR0ItemSet, nextHashSet: LR0ItemSet _ NIL]; LR0ItemSetChainCell: TYPE = REF LR0ItemSetChainCellBody; LR0ItemSetChainCellBody: TYPE = RECORD[ lr0Item: LR0Item, next: LR0ItemSetChainCell]; LR0HashTable: TYPE = REF LR0HashTableBody; LR0HashTableBody: TYPE = RECORD[slots: SEQUENCE tableSize: CARDINAL OF LR0ItemSet]; ClearLR0ItemSetsAssociatedNodes: PUBLIC PROC[grammar: Grammar] = BEGIN collection: LR0ItemSetCollection _ GetCollection[grammar]; FOR set: LR0ItemSet _ collection.firstSet, set.nextSet WHILE set # NIL DO set.associatedNode _ NIL; ENDLOOP; END; CreateEmptyTentativeLR0ItemSet: PUBLIC PROC[grammar: Grammar] RETURNS[TentativeLR0ItemSet] = BEGIN collection: LR0ItemSetCollection _ GetCollection[grammar]; set: TentativeLR0ItemSet _ NEW[TentativeLR0ItemSetBody _ [collection, NIL]]; RETURN[set]; END; -- note: this code guarantees the order of the lr0Items to conform to lr0Item.x InsertItemInTentativeLR0ItemSet: PUBLIC PROC[set: TentativeLR0ItemSet, item: LR0Item] RETURNS[newItem: BOOLEAN] = BEGIN newItem _ FALSE; IF set.recentCell # NIL AND set.recentCell.lr0Item = item THEN RETURN; FOR cell: TentativeLR0ItemSetChainCell _ set.firstCell, cell.next WHILE cell # NIL DO IF cell.lr0Item = item THEN {set.recentCell _ cell; RETURN}; IF cell.lr0Item.x > item.x THEN BEGIN -- insert new cell at front of list newCell: TentativeLR0ItemSetChainCell _ NEW[TentativeLR0ItemSetChainCellBody_[item, cell]]; set.firstCell _ set.recentCell _ newCell; RETURN[TRUE]; END; IF cell.next = NIL OR cell.next.lr0Item.x > item.x THEN BEGIN -- insert new cell following current cell newCell: TentativeLR0ItemSetChainCell _ NEW[TentativeLR0ItemSetChainCellBody_[item, cell.next]]; cell.next _ newCell; set.recentCell _ newCell; RETURN[TRUE]; END; ENDLOOP; -- set must be empty, create first new cell BEGIN newCell: TentativeLR0ItemSetChainCell _ NEW[TentativeLR0ItemSetChainCellBody_[item, NIL]]; set.firstCell _ set.recentCell _ newCell; RETURN[TRUE]; END; END; GenItemsInTentativeLR0ItemSet: PUBLIC PROC[tentativeSet: TentativeLR0ItemSet, for: PROC[LR0Item]] = BEGIN FOR cell: TentativeLR0ItemSetChainCell _ tentativeSet.firstCell, cell.next WHILE cell # NIL DO for[cell.lr0Item]; ENDLOOP; END; FreezeTentativeLR0ItemSet: PUBLIC PROC[tentativeSet: TentativeLR0ItemSet] RETURNS[LR0ItemSet] = BEGIN collection: LR0ItemSetCollection _ tentativeSet.collection; chain: LR0ItemSetChainCell _ NIL; hashCode: CARDINAL _ 0; hashIndex: CARDINAL; possibleSet: LR0ItemSet; -- note: following loop guarantees that the order of the lr0Items will be exactly the reverse of the order constructed in ObtainCleanCell, so that the order now conforms to the inverse of lr0Item.x FOR cell: TentativeLR0ItemSetChainCell _ tentativeSet.firstCell, cell.next WHILE cell # NIL DO hashCode _ hashCode + cell.lr0Item.x; chain _ NEW[LR0ItemSetChainCellBody _ [cell.lr0Item, chain]]; ENDLOOP; hashIndex _ hashCode MOD collection.hashTable.tableSize; FOR possibleSet _ collection.hashTable[hashIndex], possibleSet.nextHashSet WHILE possibleSet # NIL DO match: BOOLEAN _ TRUE; -- tentative -- we are about to scan through the lr0Items, since the possibleSet just found, and the chain just constructed, have their lr0items in the same order, we need mearly look for the first difference. newCell: LR0ItemSetChainCell _ chain; possibleCell: LR0ItemSetChainCell _ possibleSet.firstChainCell; WHILE newCell # NIL AND possibleCell # NIL DO IF newCell.lr0Item # possibleCell.lr0Item THEN {match _ FALSE; EXIT}; newCell _ newCell.next; possibleCell _ possibleCell.next; ENDLOOP; IF match AND newCell = NIL AND possibleCell = NIL THEN BEGIN -- we have a match RETURN[possibleSet]; END; ENDLOOP; -- existing one not found, so create one possibleSet _ NEW[LR0ItemSetBody _ [NIL, chain, collection.firstSet, collection.hashTable[hashIndex]]]; collection.firstSet _ possibleSet; collection.hashTable[hashIndex] _ possibleSet; RETURN[possibleSet]; END; GenItemsInLR0ItemSet: PUBLIC PROC[set: LR0ItemSet, for: PROC[LR0Item]] = BEGIN FOR cell: LR0ItemSetChainCell _ set.firstChainCell, cell.next WHILE cell # NIL DO for[cell.lr0Item]; ENDLOOP; END; GetLR0AssociatedNode: PUBLIC PROC[set: LR0ItemSet] RETURNS[REF ANY] = {RETURN[set.associatedNode]}; SetLR0AssociatedNode: PUBLIC PROC[set: LR0ItemSet, node: REF ANY] = {set.associatedNode _ node}; NarrowLR0ItemSet: PUBLIC PROCEDURE[ref: REF ANY] RETURNS[LR0ItemSet] = {RETURN[NARROW[ref]]}; NarrowTentativeLR0ItemSet: PUBLIC PROCEDURE[ref: REF ANY] RETURNS[TentativeLR0ItemSet] = {RETURN[NARROW[ref]]}; -- support code GetCollection: PROC[grammar: Grammar] RETURNS[LR0ItemSetCollection] = BEGIN collection: LR0ItemSetCollection _ NARROW[GetLR0ItemSetCollection[grammar]]; IF collection = NIL THEN BEGIN hashTable: LR0HashTable _ NEW[LR0HashTableBody[1024]]; FOR x: CARDINAL IN [0..hashTable.tableSize) DO hashTable.slots[x] _ NIL ENDLOOP; collection _ NEW[LR0ItemSetCollectionBody _ [grammar, NIL, hashTable]]; NoteLR0ItemSetCollection[grammar, collection]; END; RETURN[collection]; END; END.. -- remark: September 12, 1984 3:33:31 pm PDT: nasty bug in insert code, the items did not end up in order if the new cell should have been at front of the list. Êr˜Jšœ˜J˜/J˜˜ JšœO˜OJ˜ Jšœ˜—J˜J˜JšœS˜S˜Jšœ*˜*J˜J˜J˜J˜:˜(J˜J˜J˜—J˜J˜8˜.J˜!J˜(J˜0—J˜J˜J˜0J˜J˜$—J˜J˜&˜%J˜J˜$J˜J˜—J˜J˜8˜'J˜J˜—J˜J˜*J˜SJ˜J˜˜@J˜J˜:J˜J˜˜IJ˜J˜J˜—J˜J˜—˜\J˜J˜:J˜LJ˜J˜—J˜J˜OJ˜J˜˜qJ˜J˜J˜F˜U˜J˜ —˜J˜)J˜[J˜)J˜ J˜—˜7J˜/J˜`J˜J˜J˜ J˜—J˜—˜+J˜J˜ZJ˜)J˜ J˜—J˜—J˜˜cJ˜˜^J˜J˜—J˜—J˜˜_J˜J˜;J˜!J˜J˜J˜J˜J˜Å˜^J˜%J˜=J˜J˜—J˜8˜eJ˜#J˜ÄJ˜%J˜?J˜˜-J˜EJ˜9J˜—˜6J˜J˜J˜—J˜J˜—J˜(J˜gJ˜"J˜.J˜J˜—J˜˜HJ˜˜QJ˜J˜—J˜—J˜˜EJ˜—J˜˜CJ˜J˜—˜FJ˜J˜—˜XJ˜J˜—J˜J˜˜EJ˜J˜L˜J˜J˜6J˜PJ˜vJ˜—J˜J˜—˜J˜—J˜J˜J˜J˜ —J˜—…—vî