t-gen-support.st

編譯器的語法產生器

	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 -> <epsilon>."

	^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 -> <prefix> <stuff1> | <prefix> <stuff2> and other productions without 
			the common <prefix>. To factor the common prefix, replace the problem 
			productions with A -> <prefix> An and An -> <stuff1> | <stuff2>. 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 <stuff1> and other productions of the form A -> <stuff2>. 
				To remove the left recursion, change the other productions to 
				the form A -> <stuff2> A0 and the problem productions to the 
				form A0 -> <stuff1> A0 | <epsilon>."
				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'!