Object variableSubclass: #LR0Item instanceVariableNames: 'leftHandSide preDotSymbols postDotSymbols translationSymbol ' classVariableNames: '' poolDictionaries: '' category: 'T-gen-Support'! LR0Item comment: '================================================= Copyright (c) 1992 by Justin O. Graver. All rights reserved (with exceptions). For complete information evaluate "Object tgenCopyright." ================================================= I represent a context-free grammar production with a ''dot'' somewhere in the right hand side. I''m used in the construction of LR(0), SLR(1), and LALR(1) parsers. leftHandSide -> . => Instance Variables: leftHandSide preDotSymbols postDotSymbols translationSymbol - used for generating abstract syntax trees.'! !LR0Item methodsFor: 'state accessing'! leftHandSide ^leftHandSide! leftHandSide: argument leftHandSide := argument! postDotSymbols ^postDotSymbols! postDotSymbols: argument postDotSymbols := argument! preDotSymbols ^preDotSymbols! preDotSymbols: argument preDotSymbols := argument! translationSymbol ^translationSymbol! translationSymbol: argument translationSymbol := argument! ! !LR0Item methodsFor: 'copying'! postCopy super postCopy. self preDotSymbols: self preDotSymbols copy. self postDotSymbols: self postDotSymbols copy. ^self! ! !LR0Item methodsFor: 'private'! makeGrammarProductionWithLeftHandSide: lhs rightHandSide: rhs ^self translationSymbol isNil ifTrue: [GrammarProduction leftHandSide: lhs rightHandSide: rhs] ifFalse: [TransductionGrammarProduction leftHandSide: lhs rightHandSide: rhs translationSymbol: self translationSymbol]! ! !LR0Item methodsFor: 'conversion'! asGrammarProduction | rhs | rhs := OrderedCollection new. rhs addAll: self preDotSymbols. rhs addAll: self postDotSymbols. ^self makeGrammarProductionWithLeftHandSide: self leftHandSide rightHandSide: rhs! ! !LR0Item methodsFor: 'accessing'! augmentedGrammarStartSymbol ^self class augmentedGrammarStartSymbol! endOfInputSymbol ^self class endOfInputSymbol! ! !LR0Item methodsFor: 'printing'! printOn: aStream self leftHandSide printOn: aStream. aStream nextPutAll: ' -> '. self preDotSymbols do: [:sym | sym printOn: aStream. aStream space]. aStream nextPutAll: '. '. self postDotSymbols do: [:sym | sym printOn: aStream. aStream space]! ! !LR0Item methodsFor: 'operations'! nextSymbol "Answer the symbol immediately to the right of the dot and nil if none." ^self postDotSymbols isEmpty ifTrue: [nil] ifFalse: [self postDotSymbols first]! shift "Conceptually move the dot past the next symbol." self atEnd ifFalse: [self preDotSymbols addLast: self postDotSymbols removeFirst]! ! !LR0Item methodsFor: 'testing'! atEnd ^self postDotSymbols isEmpty! isFinalStateItem "A final state item is of the form '@@ -> S . '." ^self atEnd and: [self leftHandSide = self augmentedGrammarStartSymbol]! isLR0Item ^true! ! !LR0Item methodsFor: 'comparing'! = anItem ^anItem isLR0Item ifTrue: [self leftHandSide = anItem leftHandSide and: [self preDotSymbols = anItem preDotSymbols and: [self postDotSymbols = anItem postDotSymbols]]] ifFalse: [false]! hash "This is redefined because = is redefined." ^self leftHandSide hash bitXor: (self preDotSymbols hash bitXor: self postDotSymbols hash)! ! "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "! LR0Item class instanceVariableNames: ''! !LR0Item class methodsFor: 'constants'! augmentedGrammarStartSymbol ^#@@! endOfInputSymbol ^Character endOfInput! ! !LR0Item class methodsFor: 'instance creation'! initialItemForGrammar: grammar "After conceptually augment the grammar with the production '@@ -> S ', answer the initial item for construction of the LR CFSM." ^self leftHandSide: self augmentedGrammarStartSymbol preDotSymbols: OrderedCollection new postDotSymbols: (OrderedCollection with: grammar startSymbol with: self endOfInputSymbol)! leftHandSide: arg1 preDotSymbols: arg2 postDotSymbols: arg3 | newMe | newMe := self new. newMe leftHandSide: arg1. newMe preDotSymbols: arg2. newMe postDotSymbols: arg3. ^newMe! leftHandSide: arg1 preDotSymbols: arg2 postDotSymbols: arg3 translationSymbol: arg4 | newMe | newMe := self new. newMe leftHandSide: arg1. newMe preDotSymbols: arg2. newMe postDotSymbols: arg3. newMe translationSymbol: arg4. ^newMe! ! Object subclass: #ProductionPartition instanceVariableNames: 'leftHandSide problemProductions otherProductions ' classVariableNames: '' poolDictionaries: '' category: 'T-gen-Support'! ProductionPartition comment: '================================================= Copyright (c) 1992 by Justin O. Graver. All rights reserved (with exceptions). For complete information evaluate "Object tgenCopyright." ================================================= I represent a partition of productions for a given nonterminal into two sets, potentially problematic productions and others. I am currently used for detecting left-recursive productions and productions with common prefixes. Instance Variables: leftHandSide - the left hand side nonterminal of my productions. problemProductions - when used for left-recursion - when used for left-factoring. otherProductions .'! !ProductionPartition methodsFor: 'adding'! addOtherProduction: prod self otherProductions add: prod! addProblemProduction: prod self problemProductions add: prod! ! !ProductionPartition methodsFor: 'testing'! anyProblems ^self problemProductions isEmpty not! ! !ProductionPartition methodsFor: 'initialization'! initWithLeftHandSide: lhs self leftHandSide: lhs. self problemProductions: Set new. self otherProductions: Set new! ! !ProductionPartition methodsFor: 'state accessing'! leftHandSide ^leftHandSide! leftHandSide: argument leftHandSide := argument! otherProductions ^otherProductions! otherProductions: argument otherProductions := argument! problemProductions ^problemProductions! problemProductions: argument problemProductions := argument! ! "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "! ProductionPartition class instanceVariableNames: ''! !ProductionPartition class methodsFor: 'instance creation'! partitionProdSetForLeftFactoring: prodSet "ProdSet contains all productions for a given nonterminal. Partition these productions into two sets: a set of sets of problem productions with common prefixes and all the rest. Answer the partitioned productions." | prodPrefix newPP | prodSet isEmpty ifTrue: [self error: 'cannot partition an empty prodSet']. prodPrefix := SetDictionary new. prodSet do: [:prod | prodPrefix at: (prod rightHandSide isEmpty ifTrue: [self epsilon] ifFalse: [prod rightHandSide first]) add: prod]. newPP := self new initWithLeftHandSide: prodSet first leftHandSide. prodPrefix do: [:set | set size > 1 ifTrue: [newPP addProblemProduction: set] ifFalse: [newPP addOtherProduction: set first]]. ^newPP! partitionProdSetForLeftRecursion: prodSet "ProdSet contains all productions for a given nonterminal. Partition these productions into two sets: left-recursive problem productions and other non-left-recursive productions. Answer the partitioned productions." | newPP | prodSet isEmpty ifTrue: [self error: 'cannot partition an empty prodSet']. newPP := self new initWithLeftHandSide: prodSet first leftHandSide. prodSet do: [:prod | (prod rightHandSide isEmpty or: [prod leftHandSide ~= prod rightHandSide first]) ifTrue: [newPP addOtherProduction: prod] ifFalse: [newPP addProblemProduction: prod]]. ^newPP! ! !ProductionPartition class methodsFor: 'constants'! epsilon "Answer an object used to represent the empty string (epsilon)." ^EpsilonNode epsilon! ! Object variableSubclass: #Grammar instanceVariableNames: 'nonterminals terminals productions startSymbol nullableNonterminals firstSets followSets ' classVariableNames: '' poolDictionaries: '' category: 'T-gen-Support'! Grammar comment: '================================================= Copyright (c) 1992 by Justin O. Graver. All rights reserved (with exceptions). For complete information evaluate "Object tgenCopyright." ================================================= I represent a context-free grammar. My two main responsibilities are to compute my first and follow sets and to perform certain grammar manipulations sometimes needed to construct certain classes of parsers. The two grammar manipulations currently supported are removal of left-recursion and common prefixes (left-factoring). Instance Variables: nonterminals - nonterminals are represented by Symbols. terminals - terminals are represented by Strings. productions - order is only important from a logical point of veiw (i.e. for printing). startSymbol - a nonterminal. nullableNonterminals - those nonterminals that can derive epsilon in zero or more steps. firstSets - for each nonterminal, the terminals that could begin a sentence derivable from that nonterminal. followSets - for each nonterminal, the terminals that could appear immediately to the right of that nonterminal in some sentential form in some valid derivation sequence.'! !Grammar methodsFor: 'initialization'! computeNullableNonterminals "Compute the set of nonterminals that can derive epsilon in one or more steps." | nullables prevNullables | nullables := ((self productions select: [:prod | prod rightHandSide isEmpty]) collect: [:prod | prod leftHandSide]) asSet. prevNullables := Set new. [nullables size ~= prevNullables size] whileTrue: [prevNullables := nullables. nullables := prevNullables union: ((self productions select: [:prod | prod rightHandSideComprisedOf: prevNullables]) collect: [:prod | prod leftHandSide]) asSet]. self nullableNonterminals: nullables! init self initSymbols. self isReduced ifTrue: [self initFirstAndFollow]! initFirstAndFollow self computeNullableNonterminals. self computeFirstSets. self computeFollowSets! initSymbols | terms nonterms | terms := Set new. nonterms := Set new. self productions do: [:prod | nonterms add: prod leftHandSide. prod rightHandSide do: [:sym | sym isTerminal ifTrue: [terms add: sym] ifFalse: [nonterms add: sym]]]. self terminals: terms. self nonterminals: nonterms! ! !Grammar methodsFor: 'state accessing'! firstSets ^firstSets! firstSets: argument firstSets := argument! followSets ^followSets! followSets: argument followSets := argument! nonterminals ^nonterminals! nonterminals: argument nonterminals := argument! nullableNonterminals ^nullableNonterminals! nullableNonterminals: argument nullableNonterminals := argument! productions ^productions! productions: argument productions := argument! startSymbol ^startSymbol! startSymbol: argument startSymbol := argument! terminals ^terminals! terminals: argument terminals := argument! ! !Grammar methodsFor: 'copying'! copy "Answer a copy of myself that can be manipulated without affecting me." ^self species buildGrammarWithProductions: self copyProductions! copyProductions "Answer a 'deep' copy of my productions that can be manipulated without affecting me." ^self productions collect: [:prod | prod copy]! ! !Grammar methodsFor: 'first/follow sets'! computeFirstSets | graph | graph := self firstFollowGraph. self productions do: [:prod | prod computeFirstIn: self using: graph]. graph propagateSetUnions. self firstSets: graph nodeSetMap! computeFollowSets | graph | graph := self firstFollowGraph. self productions do: [:prod | prod computeFollowIn: self using: graph]. graph addTerminal: self epsilon toNodeLabeled: self startSymbol. "used to denote end-of-input symbol" graph propagateSetUnions. self followSets: graph nodeSetMap! firstFollowGraph ^self firstFollowGraphClass withNodesLabeled: self nonterminals! firstOfSymbolString: symbolString "Answer the set of terminals that could appear at the beginning of the argument string at some stage of a derivation. This set will include epsilon only if the whole string could derive epsilon." | first | first := Set new. symbolString do: [:sym | first := first union: (self firstSetOf: sym). (self isNullable: sym) ifFalse: [^first]]. first add: self epsilon. ^first! firstSetOf: symbol ^self firstSets at: symbol ifAbsent: ["terminal" Set with: symbol]! followSetOf: symbol ^self followSets at: symbol ifAbsent: ["terminals don't have follow sets" Set new]! ! !Grammar methodsFor: 'grammar analysis'! generableNonterminals "Answer a set of the generable nonterminals of this grammar." | generable prodMap prods prod | generable := Set with: self startSymbol. prodMap := self computeProductionMap. prods := OrderedCollection new. prods addAll: (prodMap at: self startSymbol). [prods isEmpty] whileFalse: [prod := prods removeFirst. prod rightHandSide do: [:sym | (sym isNonterminal and: [(generable includes: sym) not]) ifTrue: [generable add: sym. prods addAll: (prodMap at: sym ifAbsent: [Set new])]]]. ^generable! terminableNonterminals "Answer a set of the terminable nonterminals of this grammar." | terminable again | terminable := Set new. again := true. [again] whileTrue: [again := false. self productions do: [:prod | (terminable includes: prod leftHandSide) ifFalse: [(prod rightHandSideHasAllNontermsIn: terminable) ifTrue: [terminable add: prod leftHandSide. again := true]]]]. ^terminable! ! !Grammar methodsFor: 'empty string'! emptyRHS "Answer a right hand side that can be used in productions like A -> ." ^Array new: 0! epsilon "Answer an object used to represent the empty string (epsilon)." ^EpsilonNode epsilon! isNullable: symbol ^symbol isTerminal ifTrue: [false] ifFalse: [self nullableNonterminals includes: symbol]! ! !Grammar methodsFor: 'exception handling'! raiseNotReducedExceptionErrorString: aString self class notReducedSignal raiseErrorString: aString! ! !Grammar methodsFor: 'private'! firstFollowGraphClass ^FirstFollowGraph! grammarProductionClass ^GrammarProduction! makeProductionWithLeftHandSide: lhs rightHandSide: rhs ^self grammarProductionClass leftHandSide: lhs rightHandSide: rhs! productionPartitionClass ^ProductionPartition! ! !Grammar methodsFor: 'testing'! isReduced "Answer true if this grammar contains no non-generable nonterminals and no non-terminable nonterminals. Raise an exception and answer false otherwise." | nongen nonterm errorString | nongen := self nonterminals copy. nongen removeAll: self generableNonterminals. nonterm := self nonterminals copy. nonterm removeAll: self terminableNonterminals. ^nongen isEmpty & nonterm isEmpty ifTrue: [true] ifFalse: [errorString := ('grammar is not reduced,\ non-generable nonterminals: ' , nongen printString , '\ non-terminable nonterminals: ' , nonterm printString , '.\') withCRs. self raiseNotReducedExceptionErrorString: errorString. false]! ! !Grammar methodsFor: 'printing'! printOn: aStream self productions do: [:prod | prod printOn: aStream. aStream nextPut: $;. aStream cr]! ! !Grammar methodsFor: 'parser generation'! computeProductionMap "Answer a dictionary from nonterminals to sets of their corresponding productions." | prodMap | prodMap := SetDictionary new. self productions do: [:prod | prodMap at: prod leftHandSide add: prod]. ^prodMap! literalTerminals "Answer a collection of my non-token class terminals." ^self terminals reject: [:term | term isTokenClassTerminal]! lr1LookaheadSetFor: lr1Item ^self firstOfSymbolString: lr1Item lookaheadTail! selectSets "The select set of a production is the set of terminals that signal selection of that production in a top-down (LL(1)) parse of the input. Select sets are used in construction of the LL(1) parser table." | select first | select := Dictionary new. self productions do: [:prod | first := self firstOfSymbolString: prod rightHandSide. (first includes: self epsilon) ifTrue: [first remove: self epsilon. first addAll: (self followSetOf: prod leftHandSide)]. select at: prod put: first]. ^select! ! !Grammar methodsFor: 'manipulation support'! maxCommonPrefixFor: prodSet "Answer the maximum number of symbols the productions in prodSet share as a common prefix. This method assumes more than one element in prodSet, no dupilcate productions, and the first symbols are all the same." | n more key target | n := 2. more := true. key := prodSet first rightHandSide. [more] whileTrue: [n <= key size ifTrue: [prodSet do: [:prod | target := prod rightHandSide. n <= target size ifTrue: [(key at: n) = (target at: n) ifFalse: [more := false]] ifFalse: [more := false]]] ifFalse: [more := false]. n := n + 1]. ^n - 2! nonterminalDerivedFrom: aSymbol withSuffix: aString "Answer a new nonterminal built from the arguments and add it to my nonterminals." | newNont | newNont := (aSymbol , aString) asSymbol. self nonterminals add: newNont. ^newNont! partitionProdSetForLeftFactoring: prodSet ^self productionPartitionClass partitionProdSetForLeftFactoring: prodSet! partitionProdSetForLeftRecursion: prodSet ^self productionPartitionClass partitionProdSetForLeftRecursion: prodSet! replaceProductionsWith: prodMap "The argument maps each nonterminal to a set of corresponding productions." | newProds | newProds := OrderedCollection new. prodMap do: [:prodSet | newProds addAll: prodSet]. self productions: newProds. self initFirstAndFollow! ! !Grammar methodsFor: 'grammar manipulation'! factorCommonPrefixes | prodMap aSet oldSet | prodMap := self computeProductionMap. aSet := Set new. "On the first pass, process all production, collecting new nonterminals in aSet." prodMap copy do: [:prodSet | self leftFactor: prodSet fromMap: prodMap collectingNewNontsIn: aSet]. "Iterate over new nonterminals until no more factoring can be done." [aSet isEmpty] whileFalse: [oldSet := aSet. aSet := Set new. oldSet do: [:nt | self leftFactor: (prodMap at: nt) fromMap: prodMap collectingNewNontsIn: aSet]]. self replaceProductionsWith: prodMap! leftFactor: prodSet fromMap: prodMap collectingNewNontsIn: aSet | partition newProds nont suffix newNont n newBaseProd rhs reallyNewProds | (partition := self partitionProdSetForLeftFactoring: prodSet) anyProblems ifTrue: ["The partition contains problem productions of the form A -> | and other productions without the common . To factor the common prefix, replace the problem productions with A -> An and An -> | . Note, where a prefix has been factored from more than three productions it is possible that a new common prefix exists in the new productions. Thus, this process may need to be repeated (done by sender)." newProds := partition otherProductions. nont := partition leftHandSide. suffix := 1. partition problemProductions do: [:set | newNont := self nonterminalDerivedFrom: nont withSuffix: suffix printString. aSet add: newNont. suffix := suffix + 1. n := self maxCommonPrefixFor: set. newBaseProd := self makeProductionWithLeftHandSide: nont rightHandSide: (OrderedCollection with: newNont). rhs := set first rightHandSide. n to: 1 by: -1 do: [:i | newBaseProd rightHandSide addFirst: (rhs at: i)]. newProds add: newBaseProd. reallyNewProds := Set new. set do: [:prod | prod leftHandSide: newNont. prod rightHandSide removeFirst: n. reallyNewProds add: prod]. prodMap at: newNont put: reallyNewProds]. prodMap at: nont put: newProds]! makeLL1Transformations self removeLeftRecursion. self factorCommonPrefixes! removeLeftRecursion | prodMap partition nont newNont | prodMap := self computeProductionMap. prodMap copy do: [:prodSet | (partition := self partitionProdSetForLeftRecursion: prodSet) anyProblems ifTrue: ["The partition contains problem productions of the form A -> A and other productions of the form A -> . To remove the left recursion, change the other productions to the form A -> A0 and the problem productions to the form A0 -> A0 | ." nont := partition leftHandSide. newNont := self nonterminalDerivedFrom: nont withSuffix: '0'. prodMap at: nont put: (partition otherProductions collect: [:prod | prod rightHandSide addLast: newNont. prod]). prodMap at: newNont put: (partition problemProductions collect: [:prod | prod leftHandSide: newNont. prod rightHandSide removeFirst. prod rightHandSide addLast: newNont. prod]). (prodMap at: newNont) add: (self makeProductionWithLeftHandSide: newNont rightHandSide: self emptyRHS)]]. self replaceProductionsWith: prodMap! ! "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "! Grammar class instanceVariableNames: 'notReducedSignal '! !Grammar class methodsFor: 'state accessing'! notReducedSignal ^notReducedSignal! notReducedSignal: argument notReducedSignal := argument! ! !Grammar class methodsFor: 'class initialization'! initialize "Grammar initialize" self notReducedSignal: (Signal new nameClass: self message: #notReducedSymbol)! ! !Grammar class methodsFor: 'instance creation'! buildGrammarFrom: anArray | newGrammar | newGrammar := self new. newGrammar productions: OrderedCollection new. anArray do: [:prod | prod size = 3 ifTrue: [newGrammar productions add: (TransductionGrammarProduction leftHandSide: (prod at: 1) rightHandSide: (prod at: 2) asOrderedCollection translationSymbol: (prod at: 3))] ifFalse: [prod size = 2 ifTrue: [newGrammar productions add: (GrammarProduction leftHandSide: (prod at: 1) rightHandSide: (prod at: 2) asOrderedCollection)] ifFalse: [self error: 'wrong sized production array']]]. newGrammar startSymbol: ((anArray at: 1) at: 1). newGrammar init. ^newGrammar! buildGrammarWithProductions: prods "Assume that the left-hand side of the first production is the start symbol." ^self buildGrammarWithProductions: prods startSymbol: prods first leftHandSide! buildGrammarWithProductions: prods startSymbol: aSymbol | newGrammar | newGrammar := self new. newGrammar productions: prods. newGrammar startSymbol: aSymbol. newGrammar init. ^newGrammar! ! Set variableSubclass: #ItemSet instanceVariableNames: '' classVariableNames: '' poolDictionaries: '' category: 'T-gen-Support'! ItemSet comment: '================================================= Copyright (c) 1992 by Justin O. Graver. All rights reserved (with exceptions). For complete information evaluate "Object tgenCopyright." ================================================= ItemSets are equal if they contain equal elements.'! !ItemSet methodsFor: 'testing'! isItemSet ^true! ! !ItemSet methodsFor: 'comparing'! = anItemSet ^anItemSet isItemSet ifTrue: [self size = anItemSet size and: [self size = (self union: anItemSet) size]] ifFalse: [false]! hash "Make sure equal sets hash equally." "A good and fast hashing function will require some more thought. I used to use 'self size bitXor: self first hash' but there is no guarantee that the first's of equal sets will be the same element (even if their basicSizes are the same, due to the temporal ordering of hash collisions). If simply 'size' doesn't give reasonable performance, then try 'self inject: 0 into: [:max :each | max max: each hash]'." ^self isEmpty ifTrue: [151515] ifFalse: [self size]! ! LR0Item variableSubclass: #LR1Item instanceVariableNames: 'lookahead ' classVariableNames: '' poolDictionaries: '' category: 'T-gen-Support'! LR1Item comment: '================================================= Copyright (c) 1992 by Justin O. Graver. All rights reserved (with exceptions). For complete information evaluate "Object tgenCopyright." ================================================= I associate a lookahead symbol with a context-free grammar production with a ''dot'' somewhere in the right hand side. I''m used in the construction of LR(1) parsers. leftHandSide -> . : => Instance Variables: lookahead '! !LR1Item methodsFor: 'state accessing'! lookahead ^lookahead! lookahead: argument lookahead := argument! ! !LR1Item methodsFor: 'testing'! isLR1Item ^true! ! !LR1Item methodsFor: 'comparing'! = anItem ^anItem isLR1Item ifTrue: [self lookahead = anItem lookahead and: [super = anItem]] ifFalse: [false]! hash "This is redefined because = is redefined." ^(self leftHandSide hash bitXor: self lookahead hash) bitXor: (self preDotSymbols hash bitXor: self postDotSymbols hash)! ! !LR1Item methodsFor: 'accessing'! lookaheadTail "For an lr1 item 'B -> . A : lookahead' answer the string ' lookahead'." | string | string := self postDotSymbols copy. string removeFirst. string addLast: self lookahead. ^string! ! !LR1Item methodsFor: 'printing'! printOn: aStream super printOn: aStream. aStream nextPutAll: ': '. self lookahead printOn: aStream! ! "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "! LR1Item class instanceVariableNames: ''! !LR1Item class methodsFor: 'instance creation'! initialItemForGrammar: grammar "After conceptually augment the grammar with the production '@@ -> S ', answer the initial item for construction of the LR CFSM." ^self leftHandSide: self augmentedGrammarStartSymbol preDotSymbols: OrderedCollection new postDotSymbols: (OrderedCollection with: grammar startSymbol with: self endOfInputSymbol) lookahead: self endOfInputSymbol! leftHandSide: arg1 preDotSymbols: arg2 postDotSymbols: arg3 lookahead: arg4 | newMe | newMe := self new. newMe leftHandSide: arg1. newMe preDotSymbols: arg2. newMe postDotSymbols: arg3. newMe lookahead: arg4. ^newMe! leftHandSide: arg1 preDotSymbols: arg2 postDotSymbols: arg3 lookahead: arg4 translationSymbol: arg5 | newMe | newMe := self new. newMe leftHandSide: arg1. newMe preDotSymbols: arg2. newMe postDotSymbols: arg3. newMe lookahead: arg4. newMe translationSymbol: arg5. ^newMe! ! Object subclass: #PartitionTransitionMap instanceVariableNames: 'partition transitionMap ' classVariableNames: '' poolDictionaries: '' category: 'T-gen-Support'! PartitionTransitionMap comment: '================================================= Copyright (c) 1992 by Justin O. Graver. All rights reserved (with exceptions). For complete information evaluate "Object tgenCopyright." ================================================= I am a partition-based transition map for an ordinary fsa state. I am used as an intermediate computational object in the dfsa minimization algorithm (see #asMinimalDFSA in class FiniteStateAutomata). My responsibilities include adding new partition-based transitions and testing for transition map equivalence. Instance Variables: partition - the partition for the super state that I represent. transitionMap where = '! !PartitionTransitionMap methodsFor: 'state transitions'! goto: aPartition on: aSymbol (self transitionMap includesKey: aSymbol) ifTrue: [self error: 'these are supposed to be deterministic, what gives?']. self transitionMap at: aSymbol put: aPartition! ! !PartitionTransitionMap methodsFor: 'state accessing'! partition ^partition! partition: argument partition := argument! transitionMap ^transitionMap! transitionMap: argument transitionMap := argument! ! !PartitionTransitionMap methodsFor: 'initialization'! initWithPartition: pt self transitionMap: Dictionary new. self partition: pt! ! !PartitionTransitionMap methodsFor: 'testing'! isPartitionTransitionMap ^true! ! !PartitionTransitionMap methodsFor: 'comparing'! hasSameTransitionMapAs: aPTMap "Two partition transition maps are equivalent if they have equivalent transition maps." | map1 map2 keys1 keys2 values1 values2 | ^aPTMap isPartitionTransitionMap ifTrue: ["First, check map sizes." map1 := self transitionMap. map2 := aPTMap transitionMap. map1 size ~= map2 size ifTrue: [^false]. "Next, check map domain sizes." keys1 := map1 keys. keys2 := map2 keys. keys1 size ~= (keys1 union: keys2) size ifTrue: [^false]. "Last, check map range sizes." values1 := map1 valuesAsSet. values2 := map2 valuesAsSet. values1 size ~= (values1 union: values2) size ifTrue: [^false]. ^true] ifFalse: [false]! ! !PartitionTransitionMap methodsFor: 'printing'! printOn: aStream aStream nextPutAll: self partition hash printString; cr. self transitionMap printOn: aStream! ! "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "! PartitionTransitionMap class instanceVariableNames: ''! !PartitionTransitionMap class methodsFor: 'instance creation'! forPartition: pt ^self new initWithPartition: pt! ! LabeledDigraph variableSubclass: #FirstFollowGraph instanceVariableNames: '' classVariableNames: '' poolDictionaries: '' category: 'T-gen-Support'! FirstFollowGraph comment: '================================================= Copyright (c) 1992 by Justin O. Graver. All rights reserved (with exceptions). For complete information evaluate "Object tgenCopyright." ================================================= I am a graph consisting of FirstFollowGraphNodes used in the computation of first and follow sets. I serve as the public interface to my nodes.'! !FirstFollowGraph methodsFor: 'accessing'! nodeSetMap "Answer a map from node names (nonterminals) to sets of terminals, representing either the first or follow sets." | map | map := SetDictionary new. self nodesDo: [:node | map add: node asAssociation]. ^map! ! !FirstFollowGraph methodsFor: 'modifying'! addTerminal: term toNodeLabeled: label (self detect: [:node | node label = label]) addTerminal: term! ! !FirstFollowGraph methodsFor: 'first/follow sets'! propagateSetUnions "For each of my nodes, replace its node set with the union of its old node set and the node sets along all incoming edges. Repeat until no more changes." | changes | changes := true. [changes] whileTrue: [changes := self inject: false into: [:chngs :node | chngs | node unionWithPredecessorsChangesMe]]! ! "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "! FirstFollowGraph class instanceVariableNames: ''! !FirstFollowGraph class methodsFor: 'instance creation'! preferredNodeClass ^FirstFollowGraphNode! ! NodeLabeledDigraphNode subclass: #FirstFollowGraphNode instanceVariableNames: 'terminals ' classVariableNames: '' poolDictionaries: '' category: 'T-gen-Support'! FirstFollowGraphNode comment: '================================================= Copyright (c) 1992 by Justin O. Graver. All rights reserved (with exceptions). For complete information evaluate "Object tgenCopyright." ================================================= I represent a nonterminal of a grammar for the purpose of first and follow set computation. Instance Variables: terminals - the first or follow set of my nonterminal.'! !FirstFollowGraphNode methodsFor: 'first/follow sets'! unionWithPredecessorsChangesMe "Answer true if adding the terminals of my predecessors changes my terminals and false otherwise." | myTerms initialSize | myTerms := self terminals. initialSize := myTerms size. self predecessorsDo: [:pred | myTerms addAll: pred terminals]. ^initialSize ~= myTerms size! ! !FirstFollowGraphNode methodsFor: 'converting'! asAssociation ^Association key: self label value: self terminals! ! !FirstFollowGraphNode methodsFor: 'adding'! addTerminal: term self terminals add: term! ! !FirstFollowGraphNode methodsFor: 'initialization'! init super init. self terminals: Set new! ! !FirstFollowGraphNode methodsFor: 'state accessing'! terminals ^terminals! terminals: argument terminals := argument! ! Grammar initialize!