basis/peg/ebnf/ebnf-tests.factor

   1 ! Copyright (C) 2007 Chris Double.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 !
   4 USING: kernel tools.test peg peg.ebnf peg.ebnf.private words
   5 math math.parser sequences accessors peg.parsers parser
   6 namespaces arrays strings eval unicode.data multiline ;
   7 IN: peg.ebnf.tests
   8
   9 { T{ ebnf-non-terminal f "abc" } } [
  10   "abc" 'non-terminal' parse
  11 ] unit-test
  12
  13 { T{ ebnf-terminal f "55" } } [
  14   "'55'" 'terminal' parse
  15 ] unit-test
  16
  17 {
  18   T{ ebnf-rule f
  19      "digit"
  20      T{ ebnf-choice f
  21         V{ T{ ebnf-terminal f "1" } T{ ebnf-terminal f "2" } }
  22      }
  23   }
  24 } [
  25   "digit = '1' | '2'" 'rule' parse
  26 ] unit-test
  27
  28 {
  29   T{ ebnf-rule f
  30      "digit"
  31      T{ ebnf-sequence f
  32         V{ T{ ebnf-terminal f "1" } T{ ebnf-terminal f "2" } }
  33      }
  34   }
  35 } [
  36   "digit = '1' '2'" 'rule' parse
  37 ] unit-test
  38
  39 {
  40   T{ ebnf-choice f
  41      V{
  42        T{ ebnf-sequence f
  43           V{ T{ ebnf-non-terminal f "one" } T{ ebnf-non-terminal f "two" } }
  44        }
  45        T{ ebnf-non-terminal f "three" }
  46      }
  47   }
  48 } [
  49   "one two | three" 'choice' parse
  50 ] unit-test
  51
  52 {
  53   T{ ebnf-sequence f
  54      V{
  55        T{ ebnf-non-terminal f "one" }
  56        T{ ebnf-whitespace f
  57          T{ ebnf-choice f
  58             V{ T{ ebnf-non-terminal f "two" } T{ ebnf-non-terminal f "three" } }
  59          }
  60        }
  61      }
  62   }
  63 } [
  64   "one {two | three}" 'choice' parse
  65 ] unit-test
  66
  67 {
  68   T{ ebnf-sequence f
  69      V{
  70        T{ ebnf-non-terminal f "one" }
  71        T{ ebnf-repeat0 f
  72           T{ ebnf-sequence f
  73              V{
  74                 T{ ebnf-choice f
  75                    V{ T{ ebnf-non-terminal f "two" } T{ ebnf-non-terminal f "three" } }
  76                 }
  77                 T{ ebnf-non-terminal f "four" }
  78              }
  79           }
  80         }
  81      }
  82   }
  83 } [
  84   "one ((two | three) four)*" 'choice' parse
  85 ] unit-test
  86
  87 {
  88   T{ ebnf-sequence f
  89      V{
  90        T{ ebnf-non-terminal f "one" }
  91        T{ ebnf-ignore f
  92           T{ ebnf-sequence f
  93              V{
  94                 T{ ebnf-choice f
  95                    V{ T{ ebnf-non-terminal f "two" } T{ ebnf-non-terminal f "three" } }
  96                 }
  97                 T{ ebnf-non-terminal f "four" }
  98              }
  99           }
 100         }
 101      }
 102   }
 103 } [
 104   "one ((two | three) four)~" 'choice' parse
 105 ] unit-test
 106
 107 {
 108   T{ ebnf-sequence f
 109      V{
 110          T{ ebnf-non-terminal f "one" }
 111          T{ ebnf-optional f T{ ebnf-non-terminal f "two" } }
 112          T{ ebnf-non-terminal f "three" }
 113      }
 114   }
 115 } [
 116   "one ( two )? three" 'choice' parse
 117 ] unit-test
 118
 119 { "foo" } [
 120   "\"foo\"" 'identifier' parse
 121 ] unit-test
 122
 123 { "foo" } [
 124   "'foo'" 'identifier' parse
 125 ] unit-test
 126
 127 { "foo" } [
 128   "foo" 'non-terminal' parse symbol>>
 129 ] unit-test
 130
 131 { "foo" } [
 132   "foo]" 'non-terminal' parse symbol>>
 133 ] unit-test
 134
 135 { V{ "a" "b" } } [
 136   "ab" [EBNF foo='a' 'b' EBNF]
 137 ] unit-test
 138
 139 { V{ 1 "b" } } [
 140   "ab" [EBNF foo=('a')[[ drop 1 ]] 'b' EBNF]
 141 ] unit-test
 142
 143 { V{ 1 2 } } [
 144   "ab" [EBNF foo=('a') [[ drop 1 ]] ('b') [[ drop 2 ]] EBNF]
 145 ] unit-test
 146
 147 { CHAR: A } [
 148   "A" [EBNF foo=[A-Z] EBNF]
 149 ] unit-test
 150
 151 { CHAR: Z } [
 152   "Z" [EBNF foo=[A-Z] EBNF]
 153 ] unit-test
 154
 155 [
 156   "0" [EBNF foo=[A-Z] EBNF]
 157 ] must-fail
 158
 159 { CHAR: 0 } [
 160   "0" [EBNF foo=[^A-Z] EBNF]
 161 ] unit-test
 162
 163 [
 164   "A" [EBNF foo=[^A-Z] EBNF]
 165 ] must-fail
 166
 167 [
 168   "Z" [EBNF foo=[^A-Z] EBNF]
 169 ] must-fail
 170
 171 { V{ "1" "+" "foo" } } [
 172   "1+1" [EBNF foo='1' '+' '1' [[ drop "foo" ]] EBNF]
 173 ] unit-test
 174
 175 { "foo" } [
 176   "1+1" [EBNF foo='1' '+' '1' => [[ drop "foo" ]] EBNF]
 177 ] unit-test
 178
 179 { "foo" } [
 180   "1+1" [EBNF foo='1' '+' '1' => [[ drop "foo" ]] | '1' '-' '1' => [[ drop "bar" ]] EBNF]
 181 ] unit-test
 182
 183 { "bar" } [
 184   "1-1" [EBNF foo='1' '+' '1' => [[ drop "foo" ]] | '1' '-' '1' => [[ drop "bar" ]] EBNF]
 185 ] unit-test
 186
 187 { 6 } [
 188   "4+2" [EBNF num=[0-9] => [[ digit> ]] foo=num:x '+' num:y => [[ x y + ]] EBNF]
 189 ] unit-test
 190
 191 { 6 } [
 192   "4+2" [EBNF foo=[0-9]:x '+' [0-9]:y => [[ x digit> y digit> + ]] EBNF]
 193 ] unit-test
 194
 195 { 10 } [
 196   { 1 2 3 4 } [EBNF num=. ?[ number? ]? list=list:x num:y => [[ x y + ]] | num EBNF]
 197 ] unit-test
 198
 199 [
 200   { "a" 2 3 4 } [EBNF num=. ?[ number? ]? list=list:x num:y => [[ x y + ]] | num EBNF]
 201 ] must-fail
 202
 203 { 3 } [
 204   { 1 2 "a" 4 } [EBNF num=. ?[ number? ]? list=list:x num:y => [[ x y + ]] | num EBNF]
 205 ] unit-test
 206
 207 [
 208   "ab" [EBNF -=" " | "\t" | "\n" foo="a" - "b" EBNF]
 209 ] must-fail
 210
 211 { V{ "a" " " "b" } } [
 212   "a b" [EBNF -=" " | "\t" | "\n" foo="a" - "b" EBNF]
 213 ] unit-test
 214
 215 { V{ "a" "\t" "b" } } [
 216   "a\tb" [EBNF -=" " | "\t" | "\n" foo="a" - "b" EBNF]
 217 ] unit-test
 218
 219 { V{ "a" "\n" "b" } } [
 220   "a\nb" [EBNF -=" " | "\t" | "\n" foo="a" - "b" EBNF]
 221 ] unit-test
 222
 223 { V{ "a" f "b" } } [
 224   "ab" [EBNF -=" " | "\t" | "\n" foo="a" (-)? "b" EBNF]
 225 ] unit-test
 226
 227 { V{ "a" " " "b" } } [
 228   "a b" [EBNF -=" " | "\t" | "\n" foo="a" (-)? "b" EBNF]
 229 ] unit-test
 230
 231
 232 { V{ "a" "\t" "b" } } [
 233   "a\tb" [EBNF -=" " | "\t" | "\n" foo="a" (-)? "b" EBNF]
 234 ] unit-test
 235
 236 { V{ "a" "\n" "b" } } [
 237   "a\nb" [EBNF -=" " | "\t" | "\n" foo="a" (-)? "b" EBNF]
 238 ] unit-test
 239
 240 { V{ "a" "b" } } [
 241   "ab" [EBNF -=(" " | "\t" | "\n")? => [[ drop ignore ]] foo="a" - "b" EBNF]
 242 ] unit-test
 243
 244 { V{ "a" "b" } } [
 245   "a\tb" [EBNF -=(" " | "\t" | "\n")? => [[ drop ignore ]] foo="a" - "b" EBNF]
 246 ] unit-test
 247
 248 { V{ "a" "b" } } [
 249   "a\nb" [EBNF -=(" " | "\t" | "\n")? => [[ drop ignore ]] foo="a" - "b" EBNF]
 250 ] unit-test
 251
 252 [
 253   "axb" [EBNF -=(" " | "\t" | "\n")? => [[ drop ignore ]] foo="a" - "b" EBNF]
 254 ] must-fail
 255
 256 { V{ V{ 49 } "+" V{ 49 } } } [
 257   #! Test direct left recursion.
 258   #! Using packrat, so first part of expr fails, causing 2nd choice to be used
 259   "1+1" [EBNF num=([0-9])+ expr=expr "+" num | num EBNF]
 260 ] unit-test
 261
 262 { V{ V{ V{ 49 } "+" V{ 49 } } "+" V{ 49 } } } [
 263   #! Test direct left recursion.
 264   #! Using packrat, so first part of expr fails, causing 2nd choice to be used
 265   "1+1+1" [EBNF num=([0-9])+ expr=expr "+" num | num EBNF]
 266 ] unit-test
 267
 268 { V{ V{ V{ 49 } "+" V{ 49 } } "+" V{ 49 } } } [
 269   #! Test indirect left recursion.
 270   #! Using packrat, so first part of expr fails, causing 2nd choice to be used
 271   "1+1+1" [EBNF num=([0-9])+ x=expr expr=x "+" num | num EBNF]
 272 ] unit-test
 273
 274 { t } [
 275   "abcd='9' | ('8'):x => [[ x ]]" 'ebnf' (parse) remaining>> empty?
 276 ] unit-test
 277
 278 EBNF: primary
 279 Primary = PrimaryNoNewArray
 280 PrimaryNoNewArray =  ClassInstanceCreationExpression
 281                    | MethodInvocation
 282                    | FieldAccess
 283                    | ArrayAccess
 284                    | "this"
 285 ClassInstanceCreationExpression =  "new" ClassOrInterfaceType "(" ")"
 286                                  | Primary "." "new" Identifier "(" ")"
 287 MethodInvocation =  Primary "." MethodName "(" ")"
 288                   | MethodName "(" ")"
 289 FieldAccess =  Primary "." Identifier
 290              | "super" "." Identifier
 291 ArrayAccess =  Primary "[" Expression "]"
 292              | ExpressionName "[" Expression "]"
 293 ClassOrInterfaceType = ClassName | InterfaceTypeName
 294 ClassName = "C" | "D"
 295 InterfaceTypeName = "I" | "J"
 296 Identifier = "x" | "y" | ClassOrInterfaceType
 297 MethodName = "m" | "n"
 298 ExpressionName = Identifier
 299 Expression = "i" | "j"
 300 main = Primary
 301 ;EBNF
 302
 303 { "this" } [
 304   "this" primary
 305 ] unit-test
 306
 307 { V{ "this" "." "x" } } [
 308   "this.x" primary
 309 ] unit-test
 310
 311 { V{ V{ "this" "." "x" } "." "y" } } [
 312   "this.x.y" primary
 313 ] unit-test
 314
 315 { V{ V{ "this" "." "x" } "." "m" "(" ")" } } [
 316   "this.x.m()" primary
 317 ] unit-test
 318
 319 { V{ V{ V{ "x" "[" "i" "]" } "[" "j" "]" } "." "y" } } [
 320   "x[i][j].y" primary
 321 ] unit-test
 322
 323 { V{ V{ "a" "b" } "c" } } [
 324   "abc" [EBNF a="a" "b" foo=(a "c") EBNF]
 325 ] unit-test
 326
 327 { V{ "a" "c" } } [
 328   "abc" [EBNF a="a" "b"~ foo=(a "c") EBNF]
 329 ] unit-test
 330
 331 { V{ V{ "a" V{ "b" "b" } } "c" } } [
 332   "abbc" [EBNF a=("a" "b"*) foo=(a "c") EBNF]
 333 ] unit-test
 334
 335 { V{ "a" "c" } } [
 336   "abc" [EBNF a=("a" ("b")~) foo=(a "c") EBNF]
 337 ] unit-test
 338
 339 { V{ "a" "c" } } [
 340   "abc" [EBNF a=("a" "b"~) foo=(a "c") EBNF]
 341 ] unit-test
 342
 343 { "c" } [
 344   "abc" [EBNF a=("a" "b")~ foo=(a "c") EBNF]
 345 ] unit-test
 346
 347 { V{ V{ "a" "b" } "c" } } [
 348   "abc" [EBNF a="a" "b" foo={a "c"} EBNF]
 349 ] unit-test
 350
 351 { V{ V{ "a" "b" } "c" } } [
 352   "abc" [EBNF a="a" "b" foo=a "c" EBNF]
 353 ] unit-test
 354
 355 [
 356   "a bc" [EBNF a="a" "b" foo=(a "c") EBNF]
 357 ] must-fail
 358
 359 [
 360   "a bc" [EBNF a="a" "b" foo=a "c" EBNF]
 361 ] must-fail
 362
 363 [
 364   "a bc" [EBNF a="a" "b" foo={a "c"} EBNF]
 365 ] must-fail
 366
 367 [
 368   "ab c" [EBNF a="a" "b" foo=a "c" EBNF]
 369 ] must-fail
 370
 371 { V{ V{ "a" "b" } "c" } } [
 372   "ab c" [EBNF a="a" "b" foo={a "c"} EBNF]
 373 ] unit-test
 374
 375 [
 376   "ab c" [EBNF a="a" "b" foo=(a "c") EBNF]
 377 ] must-fail
 378
 379 [
 380   "a b c" [EBNF a="a" "b" foo=a "c" EBNF]
 381 ] must-fail
 382
 383 [
 384   "a b c" [EBNF a="a" "b" foo=(a "c") EBNF]
 385 ] must-fail
 386
 387 [
 388   "a b c" [EBNF a="a" "b" foo={a "c"} EBNF]
 389 ] must-fail
 390
 391 { V{ V{ V{ "a" "b" } "c" } V{ V{ "a" "b" } "c" } } } [
 392   "ab cab c" [EBNF a="a" "b" foo={a "c"}* EBNF]
 393 ] unit-test
 394
 395 { V{ } } [
 396   "ab cab c" [EBNF a="a" "b" foo=(a "c")* EBNF]
 397 ] unit-test
 398
 399 { V{ V{ V{ "a" "b" } "c" } V{ V{ "a" "b" } "c" } } } [
 400   "ab c ab c" [EBNF a="a" "b" foo={a "c"}* EBNF]
 401 ] unit-test
 402
 403 { V{ V{ "a" "c" } V{ "a" "c" } } } [
 404   "ab c ab c" [EBNF a="a" "b"~ foo={a "c"}* EBNF]
 405 ] unit-test
 406
 407 { V{ } } [
 408   "ab c ab c" [EBNF a="a" "b" foo=(a "c")* EBNF]
 409 ] unit-test
 410
 411 { V{ } } [
 412   "ab c ab c" [EBNF a="a" "b" foo=(a "c")* EBNF]
 413 ] unit-test
 414
 415 { V{ "a" "a" "a" } } [
 416   "aaa" [EBNF a=('a')* b=!('b') a:x => [[ x ]] EBNF]
 417 ] unit-test
 418
 419 { t } [
 420   "aaa" [EBNF a=('a')* b=!('b') a:x => [[ x ]] EBNF]
 421   "aaa" [EBNF a=('a')* b=!('b') (a):x => [[ x ]] EBNF] =
 422 ] unit-test
 423
 424 { V{ "a" "a" "a" } } [
 425   "aaa" [EBNF a=('a')* b=a:x => [[ x ]] EBNF]
 426 ] unit-test
 427
 428 { t } [
 429   "aaa" [EBNF a=('a')* b=a:x => [[ x ]] EBNF]
 430   "aaa" [EBNF a=('a')* b=(a):x => [[ x ]] EBNF] =
 431 ] unit-test
 432
 433 { t } [
 434   "number=(digit)+:n 'a'" 'ebnf' (parse) remaining>> length zero?
 435 ] unit-test
 436
 437 { t } [
 438   "number=(digit)+ 'a'" 'ebnf' (parse) remaining>> length zero?
 439 ] unit-test
 440
 441 { t } [
 442   "number=digit+ 'a'" 'ebnf' (parse) remaining>> length zero?
 443 ] unit-test
 444
 445 { t } [
 446   "number=digit+:n 'a'" 'ebnf' (parse) remaining>> length zero?
 447 ] unit-test
 448
 449 { t } [
 450   "foo=(name):n !(keyword) => [[ n ]]" 'rule' parse
 451   "foo=name:n !(keyword) => [[ n ]]" 'rule' parse =
 452 ] unit-test
 453
 454 { t } [
 455   "foo=!(keyword) (name):n => [[ n ]]" 'rule' parse
 456   "foo=!(keyword) name:n => [[ n ]]" 'rule' parse =
 457 ] unit-test
 458
 459 <<
 460 EBNF: parser1
 461 foo='a'
 462 ;EBNF
 463 >>
 464
 465 EBNF: parser2
 466 foo=<foreign parser1 foo> 'b'
 467 ;EBNF
 468
 469 EBNF: parser3
 470 foo=<foreign parser1> 'c'
 471 ;EBNF
 472
 473 EBNF: parser4
 474 foo=<foreign any-char> 'd'
 475 ;EBNF
 476
 477 { "a" } [
 478   "a" parser1
 479 ] unit-test
 480
 481 { V{ "a" "b" } } [
 482   "ab" parser2
 483 ] unit-test
 484
 485 { V{ "a" "c" } } [
 486   "ac" parser3
 487 ] unit-test
 488
 489 { V{ CHAR: a "d" } } [
 490   "ad" parser4
 491 ] unit-test
 492
 493 { } [
 494  "USING: kernel peg.ebnf ; \"a\\n\" [EBNF foo='a' '\n'  => [[ drop \"\n\" ]] EBNF] drop" eval( -- )
 495 ] unit-test
 496
 497 [
 498   "USING: peg.ebnf ; <EBNF foo='a' foo='b' EBNF>" eval( -- ) drop
 499 ] must-fail
 500
 501 { t } [
 502   #! Rule lookup occurs in a namespace. This causes an incorrect duplicate rule
 503   #! if a var in a namespace is set. This unit test is to remind me to fix this.
 504   [ "fail" "foo" set "foo='a'" 'ebnf' parse transform drop t ] with-scope
 505 ] unit-test
 506
 507 #! Tokenizer tests
 508 { V{ "a" CHAR: b } } [
 509   "ab" [EBNF tokenizer=default foo="a" . EBNF]
 510 ] unit-test
 511
 512 TUPLE: ast-number value ;
 513
 514 EBNF: a-tokenizer
 515 Letter            = [a-zA-Z]
 516 Digit             = [0-9]
 517 Digits            = Digit+
 518 SingleLineComment = "//" (!("\n") .)* "\n" => [[ ignore ]]
 519 MultiLineComment  = "/*" (!("*/") .)* "*/" => [[ ignore ]]
 520 Space             = " " | "\t" | "\r" | "\n" | SingleLineComment | MultiLineComment
 521 Spaces            = Space* => [[ ignore ]]
 522 Number            = Digits:ws '.' Digits:fs => [[ ws "." fs 3array concat >string string>number ast-number boa ]]
 523                     | Digits => [[ >string string>number ast-number boa ]]
 524 Special            =   "("   | ")"   | "{"   | "}"   | "["   | "]"   | ","   | ";"
 525                      | "?"   | ":"   | "!==" | "~="  | "===" | "=="  | "="   | ">="
 526                      | ">"   | "<="  | "<"   | "++"  | "+="  | "+"   | "--"  | "-="
 527                      | "-"   | "*="  | "*"   | "/="  | "/"   | "%="  | "%"   | "&&="
 528                      | "&&"  | "||=" | "||"  | "."   | "!"
 529 Tok                = Spaces (Number | Special )
 530 ;EBNF
 531
 532 { V{ CHAR: 1 T{ ast-number f 23 } ";" CHAR: x } } [
 533   "123;x" [EBNF bar = .
 534                 tokenizer = <foreign a-tokenizer Tok>  foo=.
 535                 tokenizer=default baz=.
 536                 main = bar foo foo baz
 537           EBNF]
 538 ] unit-test
 539
 540 { V{ CHAR: 5 "+" CHAR: 2 } } [
 541   "5+2" [EBNF
 542           space=(" " | "\n")
 543           number=[0-9]
 544           operator=("*" | "+")
 545           spaces=space* => [[ ignore ]]
 546           tokenizer=spaces (number | operator)
 547           main= . . .
 548         EBNF]
 549 ] unit-test
 550
 551 { V{ CHAR: 5 "+" CHAR: 2 } } [
 552   "5 + 2" [EBNF
 553           space=(" " | "\n")
 554           number=[0-9]
 555           operator=("*" | "+")
 556           spaces=space* => [[ ignore ]]
 557           tokenizer=spaces (number | operator)
 558           main= . . .
 559         EBNF]
 560 ] unit-test
 561
 562 { "++" } [
 563   "++--" [EBNF tokenizer=("++" | "--") main="++" EBNF]
 564 ] unit-test
 565
 566 { "\\" } [
 567   "\\" [EBNF foo="\\" EBNF]
 568 ] unit-test
 569
 570 [ "USE: peg.ebnf [EBNF EBNF]" eval( -- ) ] must-fail
 571
 572 [ """USE: peg.ebnf [EBNF
 573     lol = a
 574     lol = b
 575   EBNF]""" eval( -- )
 576 ] [
 577     error>> [ redefined-rule? ] [ name>> "lol" = ] bi and
 578 ] must-fail-with
 579
 580 [
 581     { "a" "a" }
 582 ] [
 583     EBNF: foo   Bar = "a":a1 "a":a2 => [[ a1 a2 2array ]] ;EBNF
 584     "aa" foo
 585 ] unit-test
 586
 587 [
 588     { "a" "a" }
 589 ] [
 590     EBNF: foo2   Bar = "a":a-1 "a":a-2 => [[ a-1 a-2 2array ]] ;EBNF
 591     "aa" foo2
 592 ] unit-test