1 "{ Package: 'stx:goodies/petitparser/analyzer/tests' }"

     2 

     3 PPAbstractParserTest subclass:#PPAnalyzerTest

     4 	instanceVariableNames:''

     5 	classVariableNames:''

     6 	poolDictionaries:''

     7 	category:'PetitAnalyzer-Tests'

     8 !

     9 

    10 

    11 !PPAnalyzerTest class methodsFor:'accessing'!

    12 

    13 packageNamesUnderTest

    14 	^ #('PetitAnalyzer')

    15 ! !

    16 

    17 !PPAnalyzerTest methodsFor:'accessing'!

    18 

    19 grammarA

    20 	"Güting, Erwig, Übersetzerbau, Springer (p.63)"

    21 

    22 	| grammar |

    23 	grammar := Dictionary new.

    24 	

    25 	" terminals "

    26 	grammar at: #a put: $a asParser.

    27 	grammar at: #b put: $b asParser.

    28 	grammar at: #c put: $c asParser.

    29 	grammar at: #d put: $d asParser.

    30 	grammar at: #e put: nil asParser.

    31 	

    32 	" non terminals "

    33 	grammar at: #B put: (grammar at: #b) / (grammar at: #e).

    34 	grammar at: #A put: (grammar at: #a) / (grammar at: #B).

    35 	grammar at: #S put: (grammar at: #A) , (grammar at: #B) , (grammar at: #c) , (grammar at: #d).

    36 	

    37 	^ grammar	

    38 !

    39 

    40 grammarB

    41 	"The canonical grammar to exercise first- and follow-set calculation, probably originally from the dragon-book."

    42 

    43 	| grammar |

    44 	grammar := Dictionary new.

    45 	#(E Ep T Tp F) 		do: [ :each | grammar at: each put: (PPUnresolvedParser named: each) ].

    46 		

    47 	(grammar at: #E)		def: (grammar at: #T) , (grammar at: #Ep).

    48 	(grammar at: #Ep)	def: ($+ asParser , (grammar at: #T) , (grammar at: #Ep)) optional.

    49 	

    50 	(grammar at: #T)		def: (grammar at: #F) , (grammar at: #Tp).

    51 	(grammar at: #Tp)	def: ($* asParser , (grammar at: #F) , (grammar at: #Tp)) optional.

    52 	

    53 	(grammar at: #F)		def: ($( asParser , (grammar at: #E) , $) asParser) / $i asParser.

    54 			

    55 	#(E Ep T Tp F) 		do: [ :each | (grammar at: each) name: each ].

    56 	

    57 	^ grammar

    58 !

    59 

    60 grammarC

    61 	"A highly recrusive grammar."

    62 

    63 	| grammar |

    64 	grammar := PPUnresolvedParser new.

    65 	grammar def: (grammar , $+ asParser , grammar) / $1 asParser.

    66 	^ grammar

    67 !

    68 

    69 grammarD

    70 	"A highly ambiguous grammar from: Saichaitanya Jampana. Exploring the problem of ambiguity in context-free grammars. Masters thesis, Oklahoma State Un                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    

    71 !

    72 

    73 grammarE

    74 	"The most stupid parser, it just references itself and never consumes anything. All algorithms should survive such an attack."

    75 

    76 	| parser |

    77 	parser := PPDelegateParser new.

    78 	parser setParser: parser.

    79 	^ parser

    80 ! !

    81 

    82 !PPAnalyzerTest methodsFor:'testing'!

    83 

    84 testAllNamedParsers

    85 	| p1 p2 p3 |

    86 	p1 := (#digit asParser name: 'a').

    87 	p2 := (#digit asParser name: 'b') star.

    88 	p3 := (#digit asParser name: 'c') token end.

    89 	self assert: p1 allNamedParsers size = 1.

    90 	self assert: p1 allNamedParsers first name = 'a'.

    91 	self assert: p2 allNamedParsers size = 1.

    92 	self assert: p2 allNamedParsers first name = 'b'.

    93 	self assert: p3 allNamedParsers size = 1.

    94 	self assert: p3 allNamedParsers first name = 'c'

    95 !

    96 

    97 testAllParsers

    98 	| p1 p2 p3 |

    99 	p1 := #lowercase asParser.

   100 	p2 := p1 ==> #asUppercase.

   101 	p3 := PPUnresolvedParser new.

   102 	p3 def: p2 / p3.

   103 	self assert: p1 allParsers size = 1.

   104 	self assert: p2 allParsers size = 2.

   105 	self assert: p3 allParsers size = 3

   106 !

   107 

   108 testInnerChildren

   109 	| p1 p2 p3 |

   110 	p1 := (#digit asParser name: 'a').

   111 	p2 := (#digit asParser star name: 'b').

   112 	p3 := (#digit asParser name: 'c') token star end.

   113 	self assert: p1 innerChildren isEmpty.

   114 	self assert: p2 innerChildren size = 1.

   115 	self assert: (p2 innerChildren allSatisfy: [ :each | each name isNil ]).

   116 	self assert: p3 innerChildren size = 2.

   117 	self assert: (p3 innerChildren allSatisfy: [ :each | each name isNil ])

   118 !

   119 

   120 testIsNullable

   121 	self assert: $a asParser star isNullable.

   122 	self assert: nil asParser isNullable.

   123 

   124 	self deny: $a asParser plus isNullable.	

   125 	self deny: PPLiteralSequenceParser new isNullable.

   126 	self deny: PPLiteralObjectParser new isNullable.

   127 	self deny: PPPredicateParser new isNullable.

   128 	self deny: PPChoiceParser new isNullable.

   129 	self deny: PPSequenceParser new isNullable.

   130 	self deny: PPAndParser new isNullable.

   131 	self deny: PPTokenParser new isNullable

   132 !

   133 

   134 testIsTerminal

   135 	self assert: PPEpsilonParser new isTerminal.

   136 	self assert: PPFailingParser new isTerminal.

   137 	self assert: PPPluggableParser new isTerminal.

   138 	self assert: PPLiteralObjectParser new isTerminal.

   139 	self assert: PPLiteralSequenceParser new isTerminal.

   140 	self assert: PPPredicateObjectParser new isTerminal.

   141 	self assert: PPPredicateSequenceParser new isTerminal.

   142 	

   143 	self deny: ($a asParser / $b asParser) isTerminal.

   144 	self deny: ($a asParser , $b asParser) isTerminal.

   145 	self deny: ($a asParser and) isTerminal.

   146 	self deny: ($a asParser not) isTerminal

   147 !

   148 

   149 testNamedChildren

   150 	| p1 p2 p3 p4 |

   151 	p1 := (#digit asParser name: 'a').

   152 	p2 := (#digit asParser name: 'b') star.

   153 	p3 := (#digit asParser name: 'c') token end.

   154 	p4 := ((#digit asParser name: 'c') token name: 'd') end.

   155 	self assert: p1 namedChildren isEmpty.

   156 	self assert: p2 namedChildren size = 1.

   157 	self assert: p2 namedChildren first name = 'b'.

   158 	self assert: p3 namedChildren size = 1.

   159 	self assert: p3 namedChildren first name = 'c'.

   160 	self assert: p4 namedChildren size = 1.

   161 	self assert: p4 namedChildren first name = 'd'

   162 ! !

   163 

   164 !PPAnalyzerTest methodsFor:'testing-cycleset'!

   165 

   166 testCycleSetGrammarA

   167 	self grammarA do: [ :each | self assert: each cycleSet isEmpty ]

   168 !

   169 

   170 testCycleSetGrammarB

   171 	self grammarB do: [ :each | self assert: each cycleSet isEmpty ]

   172 !

   173 

   174 testCycleSetGrammarC

   175 	| grammar cycleSet |

   176 	grammar := self grammarC.

   177 	cycleSet := grammar cycleSet.

   178 	self assert: (cycleSet size = 2).

   179 	self assert: (cycleSet includes: grammar)

   180 !

   181 

   182 testCycleSetGrammarD

   183 	| grammar cycleSet |

   184 	grammar := self grammarD.

   185 	

   186 	cycleSet := (grammar at: #S) cycleSet.

   187 	self assert: (cycleSet size = 4).

   188 	self assert: (cycleSet includes: (grammar at: #A)).

   189 	self assert: (cycleSet includes: (grammar at: #S)).

   190 	

   191 	cycleSet := (grammar at: #A) cycleSet.

   192 	self assert: (cycleSet size = 4).

   193 	self assert: (cycleSet includes: (grammar at: #A)).

   194 	self assert: (cycleSet includes: (grammar at: #S)).

   195 

   196 	cycleSet := (grammar at: #B) cycleSet.

   197 	self assert: (cycleSet size = 2).

   198 	self assert: (cycleSet includes: (grammar at: #B))

   199 !

   200 

   201 testCycleSetGrammarE

   202 	| grammar cycleSet |

   203 	grammar := self grammarE.

   204 	cycleSet := grammar cycleSet.

   205 	self assert: (cycleSet size = 1).

   206 	self assert: (cycleSet includes: grammar)

   207 !

   208 

   209 testCycleSetInChoice

   210 	| parser cycleSet |

   211 	parser := PPUnresolvedParser new.

   212 	parser def: parser / $a asParser.

   213 	cycleSet := parser cycleSet.

   214 	self assert: (cycleSet size = 1).

   215 	self assert: (cycleSet includes: parser).

   216 	

   217 	parser := PPUnresolvedParser new.

   218 	parser def: $a asParser / parser.

   219 	cycleSet := parser cycleSet.

   220 	self assert: (cycleSet size = 1).

   221 	self assert: (cycleSet includes: parser).

   222 !

   223 

   224 testCycleSetInSequence

   225 	| parser cycleSet |

   226 	parser := PPUnresolvedParser new.

   227 	parser def: parser , $a asParser.

   228 	cycleSet := parser cycleSet.

   229 	self assert: (cycleSet size = 1).

   230 	self assert: (cycleSet includes: parser).

   231 	

   232 	parser := PPUnresolvedParser new.

   233 	parser def: nil asParser , parser.

   234 	cycleSet := parser cycleSet.

   235 	self assert: (cycleSet size = 1).

   236 	self assert: (cycleSet includes: parser).

   237 	

   238 	parser := PPUnresolvedParser new.

   239 	parser def: $a asParser , parser.

   240 	cycleSet := parser cycleSet.

   241 	self assert: cycleSet isEmpty

   242 ! !

   243 

   244 !PPAnalyzerTest methodsFor:'testing-firstset'!

   245 

   246 testFirstSetExpression

   247 	| grammar |

   248 	grammar := PPArithmeticParser new.

   249 	self assert: grammar start firstSet includes: '(-0123456789' epsilon: false.

   250 	self assert: grammar addition firstSet includes: '(-0123456789' epsilon: false.

   251 	self assert: grammar factors firstSet includes:  '(-0123456789' epsilon: false.

   252 	self assert: grammar multiplication firstSet includes:  '(-0123456789' epsilon: false.

   253 	self assert: grammar number firstSet includes: '-0123456789' epsilon: false.

   254 	self assert: grammar parentheses firstSet includes: '(' epsilon: false.

   255 	self assert: grammar power firstSet includes: '(-0123456789' epsilon: false.

   256 	self assert: grammar primary firstSet includes: '(-0123456789' epsilon: false.

   257 	self assert: grammar terms firstSet includes: '(-0123456789' epsilon: false

   258 !

   259 

   260 testFirstSetGrammarA

   261 	| grammar |

   262 	grammar := self grammarA.

   263 	self assert: (grammar at: #a) firstSet includes: 'a' epsilon: false.

   264 	self assert: (grammar at: #b) firstSet includes: 'b' epsilon: false.

   265 	self assert: (grammar at: #c) firstSet includes: 'c' epsilon: false.

   266 	self assert: (grammar at: #d) firstSet includes: 'd' epsilon: false.

   267 	self assert: (grammar at: #e) firstSet includes: '' epsilon: true.

   268 	self assert: (grammar at: #S) firstSet includes: 'abc' epsilon: false.

   269 	self assert: (grammar at: #A) firstSet includes: 'ab' epsilon: true.

   270 	self assert: (grammar at: #B) firstSet includes: 'b' epsilon: true

   271 !

   272 

   273 testFirstSetGrammarB

   274 	| grammar |

   275 	grammar := self grammarB.

   276 	self assert: (grammar at: #E) firstSet includes: '(i' epsilon: false.

   277 	self assert: (grammar at: #Ep) firstSet includes: '+' epsilon: true.

   278 	self assert: (grammar at: #T) firstSet includes: '(i' epsilon: false.

   279 	self assert: (grammar at: #Tp) firstSet includes: '*' epsilon: true.

   280 	self assert: (grammar at: #F) firstSet includes: '(i' epsilon: false

   281 !

   282 

   283 testFirstSetGrammarC

   284 	| grammar |

   285 	grammar := self grammarC.

   286 	self assert: grammar firstSet includes: '1' epsilon: false

   287 !

   288 

   289 testFirstSetGrammarD

   290 	| grammar |

   291 	grammar := self grammarD.

   292 	self assert: (grammar at: #S) firstSet includes: 'ab' epsilon: false.

   293 	self assert: (grammar at: #A) firstSet includes: 'ab' epsilon: false.

   294 	self assert: (grammar at: #B) firstSet includes: 'a' epsilon: false.

   295 	self assert: (grammar at: #a) firstSet includes: 'a' epsilon: false.

   296 	self assert: (grammar at: #b) firstSet includes: 'b' epsilon: false

   297 !

   298 

   299 testFirstSetGrammarE

   300 	self assert: self grammarE firstSet includes: '' epsilon: false

   301 !

   302 

   303 testFirstSetLambda

   304 	| grammar |

   305 	grammar := PPLambdaParser new.

   306 	self assert: grammar start firstSet includes: '(ABCDEFGHIJKLMNOPQRSTUVWXYZ\abcdefghijklmnopqrstuvwxyz' epsilon: false.

   307 	self assert: grammar abstraction firstSet includes: '\' epsilon: false.

   308 	self assert: grammar application firstSet includes: '(' epsilon: false.

   309 	self assert: grammar expression firstSet includes: '(ABCDEFGHIJKLMNOPQRSTUVWXYZ\abcdefghijklmnopqrstuvwxyz' epsilon: false.

   310 	self assert: grammar variable firstSet includes: 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz' epsilon: false

   311 ! !

   312 

   313 !PPAnalyzerTest methodsFor:'testing-followset'!

   314 

   315 testFollowSetExampleA

   316 	| grammar followSets |

   317 	grammar := self grammarA.

   318 	followSets := (grammar at: #S) followSets.

   319 	self assert: (followSets at: (grammar at: #a)) includes: 'bc' epsilon: false.

   320 	self assert: (followSets at: (grammar at: #b)) includes: 'bc' epsilon: false.

   321 	self assert: (followSets at: (grammar at: #c)) includes: 'd' epsilon: false.

   322 	self assert: (followSets at: (grammar at: #d)) includes: '' epsilon: true.

   323 	self assert: (followSets at: (grammar at: #e)) includes: 'bc' epsilon: false.

   324 	self assert: (followSets at: (grammar at: #S)) includes: '' epsilon: true.

   325 	self assert: (followSets at: (grammar at: #A)) includes: 'bc' epsilon: false.

   326 	self assert: (followSets at: (grammar at: #B)) includes: 'bc' epsilon: false

   327 !

   328 

   329 testFollowSetExampleB

   330 	| grammar followSets |

   331 	grammar := self grammarB.

   332 	followSets := (grammar at: #E) followSets.

   333 	self assert: (followSets at: (grammar at: #E)) includes: ')' epsilon: true.

   334 	self assert: (followSets at: (grammar at: #Ep)) includes: ')' epsilon: true.

   335 	self assert: (followSets at: (grammar at: #T)) includes: ')+' epsilon: true.

   336 	self assert: (followSets at: (grammar at: #Tp)) includes: ')+' epsilon: true.

   337 	self assert: (followSets at: (grammar at: #F)) includes: ')*+' epsilon: true

   338 !

   339 

   340 testFollowSetExampleC

   341 	self assert: self grammarC followSet includes: '+' epsilon: true

   342 !

   343 

   344 testFollowSetExampleD

   345 	| grammar followSets |

   346 	grammar := self grammarD.

   347 	followSets := (grammar at: #S) followSets.

   348 	self assert: (followSets at: (grammar at: #S)) includes: 'a' epsilon: true.

   349 	self assert: (followSets at: (grammar at: #A)) includes: 'ab' epsilon: true.

   350 	self assert: (followSets at: (grammar at: #B)) includes: 'ab' epsilon: true.

   351 	self assert: (followSets at: (grammar at: #a)) includes: 'ab' epsilon: true.

   352 	self assert: (followSets at: (grammar at: #b)) includes: 'ab' epsilon: true

   353 !

   354 

   355 testFollowSetExampleE

   356 	self assert: self grammarE followSet includes: '' epsilon: true

   357 ! !

   358 

   359 !PPAnalyzerTest methodsFor:'testing-transform'!

   360 

   361 testDelegateReplace

   362 	| one other delegate |

   363 	one := $a asParser.

   364 	other := $b asParser.

   365 	delegate := one token.

   366 	self assert: delegate children first == one.

   367 	self deny: delegate children first == other.

   368 	

   369 	delegate replace: other with: one.

   370 	self assert: delegate children first == one.

   371 	self deny: delegate children first == other.

   372 	

   373 	delegate replace: one with: other.

   374 	self deny: delegate children first == one.

   375 	self assert: delegate children first == other

   376 !

   377 

   378 testListReplace

   379 	| one other another list |

   380 	one := $a asParser.

   381 	other := $b asParser.

   382 	another := $c asParser.

   383 	list := one , another , one.

   384 	self assert: list children first == one.

   385 	self assert: list children second == another.

   386 	self assert: list children last == one.

   387 	

   388 	list replace: other with: one.

   389 	self assert: list children first == one.

   390 	self assert: list children second == another.

   391 	self assert: list children last == one.

   392 	

   393 	list replace: one with: other.

   394 	self assert: list children first == other.

   395 	self assert: list children second == another.

   396 	self assert: list children last == other.

   397 	

   398 	list replace: another with: one.

   399 	self assert: list children first == other.

   400 	self assert: list children second == one.

   401 	self assert: list children last == other

   402 !

   403 

   404 testRepetitionReplace

   405 	| one two otherone othertwo repetition |

   406 	one := $a asParser.

   407 	two := $b asParser.

   408 	otherone := $1 asParser.

   409 	othertwo := $2 asParser.

   410 	

   411 	repetition := one starLazy: two.

   412 	self assert: repetition children first == one.

   413 	self assert: repetition children second == two.

   414 	

   415 	repetition replace: one with: otherone.

   416 	self assert: repetition children first == otherone.

   417 	self assert: repetition children second == two.

   418 	

   419 	repetition replace: two with: othertwo.

   420 	self assert: repetition children first == otherone.

   421 	self assert: repetition children second == othertwo

   422 !

   423 

   424 testTransformIdentityGrammarC

   425 	| orig tran |

   426 	orig := self grammarC.

   427 	tran := orig transform: [ :each | each ].

   428 	self deny: orig == tran.

   429 	self deny: orig children first == tran children first.

   430 	self deny: orig children first children first == tran children first children first.

   431 	self deny: orig children first children last == tran children first children last.

   432 	self deny: orig children last == tran children last.

   433 	

   434 	self assert: orig class == PPChoiceParser.

   435 	self assert: orig children first class == PPSequenceParser.

   436 	self assert: orig children first children first == orig.

   437 	self assert: orig children first children last == orig.

   438 	self assert: orig children last class == PPLiteralObjectParser.

   439 

   440 	self assert: tran class == PPChoiceParser.

   441 	self assert: tran children first class == PPSequenceParser.

   442 	self assert: tran children first children first == tran.

   443 	self assert: tran children first children last == tran.

   444 	self assert: tran children last class == PPLiteralObjectParser

   445 !

   446 

   447 testTransformIdentityGrammarE

   448 	| orig tran |

   449 	orig := self grammarE.

   450 	tran := orig transform: [ :each | each ].

   451 	self deny: orig == tran.

   452 	self deny: orig children first = tran children first.

   453 	

   454 	self assert: orig class == PPDelegateParser.

   455 	self assert: orig children first == orig.

   456 	

   457 	self assert: tran class == PPDelegateParser.

   458 	self assert: tran children first == tran

   459 !

   460 

   461 testTransformWrapGrammarC

   462 	| orig tran |

   463 	orig := self grammarC.

   464 	tran := orig transform: [ :each | each memoized ].

   465 

   466 	self assert: orig class == PPChoiceParser.

   467 	self assert: orig children first class == PPSequenceParser.

   468 	self assert: orig children first children first == orig.

   469 	self assert: orig children first children last == orig.

   470 	self assert: orig children last class == PPLiteralObjectParser.

   471 	

   472 	self assert: tran class == PPMemoizedParser.

   473 	self assert: tran children first class == PPChoiceParser.

   474 	self assert: tran children first children first class == PPMemoizedParser.

   475 	self assert: tran children first children first children first class == PPSequenceParser.

   476 	self assert: tran children first children first children first children first == tran.

   477 	self assert: tran children first children first children first children last == tran.

   478 	self assert: tran children first children last class == PPMemoizedParser.

   479 	self assert: tran children first children last children first class == PPLiteralObjectParser

   480 !

   481 

   482 testTransformWrapGrammarE

   483 	| orig tran |

   484 	orig := self grammarE.

   485 	tran := orig transform: [ :each | each memoized ].

   486 	

   487 	self assert: orig class == PPDelegateParser.

   488 	self assert: orig children first == orig.

   489 	

   490 	self assert: tran class == PPMemoizedParser.

   491 	self assert: tran children first class == PPDelegateParser.

   492 	self assert: tran children first children first == tran

   493 ! !

   494 

   495 !PPAnalyzerTest methodsFor:'utilities'!

   496 

   497 assert: aCollection includes: aString epsilon: aBoolean

   498 	| parsers checker stream |

   499 	parsers := aCollection

   500 		collect: [ :each | each end ].

   501 	checker := [ :string |

   502 		parsers anySatisfy: [ :parser |

   503 			(parser parse: string asPetitStream)

   504 				isPetitFailure not ] ].

   505 	stream := WriteStream on: String new.

   506 	32 to: 127 do: [ :index |

   507 		(checker value: (String with: (Character value: index)))

   508 			ifTrue: [ stream nextPut: (Character value: index) ] ].

   509 	self

   510 		assert: stream contents = aString

   511 		description: 'Expected ' , aString printString , ', but got ' , stream contents printString.

   512 	self

   513 		assert: (checker value: '') = aBoolean

   514 		description: 'Expected epsilon to ' , (aBoolean ifTrue: [ 'be' ] ifFalse: [ 'not be' ]) , '  included'

   515 ! !

   516 

   517 !PPAnalyzerTest class methodsFor:'documentation'!

   518 

   519 version

   520     ^ '$Header: /cvs/stx/stx/goodies/petitparser/analyzer/tests/PPAnalyzerTest.st,v 1.1 2014-03-04 15:42:53 cg Exp $'

   521 !

   522 

   523 version_CVS

   524     ^ '$Header: /cvs/stx/stx/goodies/petitparser/analyzer/tests/PPAnalyzerTest.st,v 1.1 2014-03-04 15:42:53 cg Exp $'

   525 ! !

   526