-- LR0ItemsImpl.mesa -- last edit September 10, 1984 4:28:42 pm PDT DIRECTORY GrammarBasic USING[Grammar, Symbol, Production, GetRightSideSymbol, GetStartProduction, GetLength, GenProductions, GenProductionsForSymbol, GetFirstLR0Item, GetLR0ItemCollection, NoteAssociatedLR0Closure, GetAssociatedLR0Closure, NoteFirstLR0Item, NoteLR0ItemCollection], LR0ItemSetsBasic USING[CreateEmptyTentativeLR0ItemSet, GenItemsInLR0ItemSet, InsertItemInTentativeLR0ItemSet, FreezeTentativeLR0ItemSet, GenItemsInTentativeLR0ItemSet, LR0Item, LR0ItemSet, NarrowLR0ItemSet, TentativeLR0ItemSet], LR0Items USING[]; LR0ItemsImpl: CEDAR PROGRAM IMPORTS GrammarBasic, LR0ItemSetsBasic EXPORTS LR0ItemSetsBasic, LR0Items = BEGIN OPEN GrammarBasic, LR0ItemSetsBasic; LR0ItemCollection: TYPE = REF LR0ItemCollectionBody; LR0ItemCollectionBody: TYPE = RECORD[ grammar: Grammar, nextIndex: CARDINAL]; LR0ItemRef: TYPE = REF LR0ItemBody; LR0ItemBody: PUBLIC TYPE = RECORD[ collection: LR0ItemCollection, production: Production, position: CARDINAL, limit: CARDINAL, -- 0 <= position <= limit x: CARDINAL,-- item1.x = item2.x => item1 = item2 next: LR0ItemRef]; CompleteProduction: PUBLIC PROC[item: LR0Item] RETURNS[Production] = -- NIL unless the LR0Item refers to a complete production, in which case returns the production; used for generating reduction steps. BEGIN itemRef: LR0ItemRef _ item.ref; IF itemRef.position = itemRef.limit THEN RETURN[itemRef.production] ELSE RETURN[NIL]; END; GetGrammarFromLR0Item: PUBLIC PROC[item: LR0Item] RETURNS[Grammar] = BEGIN itemRef: LR0ItemRef _ item.ref; RETURN[itemRef.collection.grammar]; END; GetStartLR0Item: PUBLIC PROC[grammar: Grammar] RETURNS[LR0Item] = BEGIN production: Production _ GetStartProduction[grammar]; RETURN[GetFirstLR0Item[production]]; END; GetFirstLR0Item: PUBLIC PROC[production: Production] RETURNS[LR0Item] = BEGIN ref: LR0ItemRef _ NARROW[GrammarBasic.GetFirstLR0Item[production]]; RETURN[[ref, ref.x]]; END; GetNextLR0Item: PUBLIC PROC[item: LR0Item] RETURNS[LR0Item] = BEGIN ref: LR0ItemRef _ item.ref; nextRef: LR0ItemRef _ ref.next; IF nextRef # NIL THEN RETURN[[nextRef, nextRef.x]] ELSE RETURN[[NIL, 0]]; END; GetFirstSymbol: PUBLIC PROC[item: LR0Item] RETURNS[Symbol] = BEGIN ref: LR0ItemRef _ item.ref; IF ref.position = ref.limit THEN RETURN[NIL]; RETURN[GetRightSideSymbol[ref.production, ref.position]]; END; GetProductionAndPosition: PUBLIC PROC[item: LR0Item] RETURNS[production: Production, position: CARDINAL] = BEGIN ref: LR0ItemRef _ item.ref; RETURN[ref.production, ref.position]; END; GenV0EpsilonKernelItems: PUBLIC PROC[grammar: Grammar, for: PROC[LR0Item]] = BEGIN itemRef: LR0ItemRef _ NARROW[GrammarBasic.GetFirstLR0Item[GetStartProduction[grammar]]]; IF itemRef = NIL THEN BEGIN [] _ GetCollection[grammar]; itemRef _ NARROW[GrammarBasic.GetFirstLR0Item[GetStartProduction[grammar]]]; IF itemRef = NIL THEN ERROR; END; for[[itemRef, itemRef.x]]; END; GenKernelGoTo0Items: PUBLIC PROC[item: LR0Item, for: PROC[Symbol, LR0Item]] = BEGIN itemRef: LR0ItemRef _ item.ref; IF itemRef.position # itemRef.limit THEN for[ GetRightSideSymbol[itemRef.production, itemRef.position], [itemRef.next, itemRef.next.x]]; END; GenClose0Items: PUBLIC PROC[item: LR0Item, for: PROC[LR0Item]] = BEGIN -- this procedure uses precomputed closures for the first lr0items for each production. ExploreFirstCloseItem: PROCEDURE[firstCloseItem: LR0Item] = BEGIN -- this must be the first item of some production production: Production; position: CARDINAL; subClosure: LR0ItemSet; [production, position] _ GetProductionAndPosition[firstCloseItem]; IF position # 0 THEN ERROR; subClosure _ NarrowLR0ItemSet[GetAssociatedLR0Closure[production]]; GenItemsInLR0ItemSet[subClosure, for]; END; for[item]; GenOneLR0CloseStep[item, ExploreFirstCloseItem]; END; -- support code GetCollection: PROCEDURE[grammar: Grammar] RETURNS[LR0ItemCollection] = BEGIN collection: LR0ItemCollection _ NARROW[GetLR0ItemCollection[grammar]]; IF collection = NIL THEN BEGIN ExpandOneProduction: PROC[production: Production] = BEGIN size: CARDINAL _ GetLength[production]; next: LR0ItemRef _ NIL; FOR I: CARDINAL DECREASING IN [0..size] DO item: LR0ItemRef _ NEW[LR0ItemBody _ [collection, production, I, size, collection.nextIndex, next]]; next _ item; collection.nextIndex _ collection.nextIndex + 1; ENDLOOP; NoteFirstLR0Item[production, next]; END; CloseTheFirst: PROC[production: Production] = BEGIN first: LR0Item _ GetFirstLR0Item[production]; tentativeClosure: TentativeLR0ItemSet _ CreateEmptyTentativeLR0ItemSet[grammar]; changed: BOOLEAN _ TRUE; closure: LR0ItemSet; PossibleAddOneNewMember: PROC[possibleNewMember: LR0Item] = BEGIN IF InsertItemInTentativeLR0ItemSet[tentativeClosure, possibleNewMember] THEN changed _ TRUE; END; ConsiderOneOldMember: PROC[oldItem: LR0Item] = {GenOneLR0CloseStep[oldItem, PossibleAddOneNewMember]}; [] _ InsertItemInTentativeLR0ItemSet[tentativeClosure, first]; WHILE changed DO changed _ FALSE; GenItemsInTentativeLR0ItemSet[tentativeClosure, ConsiderOneOldMember]; ENDLOOP; closure _ FreezeTentativeLR0ItemSet[tentativeClosure]; NoteAssociatedLR0Closure[production, closure]; END; -- first create all the LR0Items, and record the first one for each production collection _ NEW[LR0ItemCollectionBody _ [grammar, 0]]; NoteLR0ItemCollection[grammar, collection]; GenProductions[grammar, ExpandOneProduction]; -- now record the closure of the first LR0Item for each production GenProductions[grammar, CloseTheFirst]; END; RETURN[collection]; END; GenOneLR0CloseStep: PROC[lr0Item: LR0Item, for: PROC[LR0Item]] = BEGIN -- DOES NOT include the original item itemRef: LR0ItemRef _ lr0Item.ref; symbol: Symbol; ExploreOneProduction: PROC[production: Production] = BEGIN closureItemRef: LR0ItemRef _ NARROW[GrammarBasic.GetFirstLR0Item[production]]; for[[closureItemRef, closureItemRef.x]]; END; IF itemRef.position = itemRef.limit THEN RETURN; symbol _ GetRightSideSymbol[itemRef.production, itemRef.position]; GenProductionsForSymbol[symbol, ExploreOneProduction]; END; END.. Ê ˜Jšœ˜J˜2J˜˜ Jšœ˜Jšœä˜äJšœ˜—J˜J˜Jšœh˜h˜Jšœ*˜*J˜J˜J˜4˜%J˜J˜—J˜J˜J˜J˜$˜"J˜J˜J˜J˜*J˜2J˜—J˜J˜˜ËJ˜J˜J˜UJ˜—J˜˜DJ˜J˜J˜#J˜J˜—˜AJ˜J˜5J˜$J˜—J˜˜GJ˜J˜CJ˜J˜J˜—˜=J˜J˜J˜J˜IJ˜J˜—˜˜J˜J˜FJ˜—J˜J˜6J˜.J˜J˜—J˜J˜NJ˜7J˜+J˜-J˜J˜BJ˜'J˜—J˜˜J˜——J˜˜@J˜+J˜"J˜J˜˜4J˜J˜NJ˜(J˜—J˜J˜J˜0J˜BJ˜J˜J˜6J˜—J˜J˜—J˜—…—Êp