1 testcase "pathological O(n^2) behavior" {
2 input "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
14 testcase "another O(n^2) example, tickles different epsilon behaviors" {
16 output "x:{x:{x:{x}}}";
31 output "1:{{a b} {c}}";
34 ids = "1":: id (" " ids &~ id ("":: ~[]*))
35 | "2":: id ( ids &~ id ("":: ~[]*))
43 output "2:{{a} 1:{{b} {c}}}";
44 output "1:{{a b} {c}}";
47 ids = "1":: id " " ids
80 output "xbx:{{a} abab:{a b} {b}}";
83 s = xbx:: ("":: x*) b ("":: x*)
90 output "bam:{a bam:{a bam:{a x}}}";
100 output "s2:{b0 a:{a:{epsilon}}}";
101 output "b:{a:{a:{epsilon}} epsilon}";
122 output "s1:{a2:{a2:{a0 b0} b0}}";
130 testcase "epsilon forests" {
133 output "s3:{s3:{epsilon a0 epsilon epsilon} epsilon epsilon epsilon}";
134 output "s3:{s3:{epsilon epsilon epsilon epsilon} a0 epsilon epsilon}";
135 output "s3:{s3:{epsilon epsilon a0 epsilon} epsilon epsilon epsilon}";
136 output "s3:{s3:{epsilon epsilon epsilon a0} epsilon epsilon epsilon}";
137 output "s3:{epsilon epsilon a0 a0}";
138 output "s3:{s3:{s3:{epsilon epsilon epsilon epsilon} epsilon epsilon epsilon} epsilon epsilon epsilon}";
139 output "s3:{s3:{epsilon epsilon epsilon epsilon} epsilon epsilon a0}";
140 output "s3:{s3:{epsilon epsilon epsilon epsilon} epsilon a0 epsilon}";
141 output "s3:{epsilon a0 epsilon a0}";
142 output "s3:{epsilon a0 a0 epsilon}";
152 output "poo:{poo:{poox poox} poox}";
153 output "poo:{poox poo:{poox poox}}";
160 output "s:{aa:{aa:{a b} b}}";
169 output "sx:{b aa:{aa:{b b} b}}";
180 output "+:{{a} *:{{b} {c}}}";
192 output "times:{plus:{stringify:{a} minus:{stringify:{b} stringify:{d}}} stringify:{c}}";
193 output "plus:{stringify:{a} times:{minus:{stringify:{b} stringify:{d}} stringify:{c}}}";
194 output "minus:{plus:{stringify:{a} stringify:{b}} times:{stringify:{d} stringify:{c}}}";
195 output "plus:{stringify:{a} minus:{stringify:{b} times:{stringify:{d} stringify:{c}}}}";
196 output "times:{minus:{plus:{stringify:{a} stringify:{b}} stringify:{d}} stringify:{c}}";
207 id = stringify:: idl++
211 testcase "priority" {
213 output "plus:{stringify:{a} times:{stringify:{b} stringify:{c}}}";
224 id = stringify:: idl++
228 testcase "associativity" {
230 output "times:{stringify:{a} times:{stringify:{b} stringify:{c}}}";
241 id = stringify:: idl++
247 output "{q:{a a} q:{b b}}";
254 testcase "indentation" {
274 output "smt:{while:{>:{{x} {0}} while:{>:{{y} {0}} sbb:{{f o o} {b a r}}}} while:{>:{{x} {0}} sbb:{while:{>:{{y} {0}} {f o o}} {b a r}}}}";
277 outdent = " " outdent " "
278 | " " ("":: (~[])*) "\n"
280 w = " " | "\n" | "\r"
286 s = smt:: ws! statement ws! statement ws!
288 block = "\n" indent! blockBody
289 &~ "\n" (" " outdent! " ") ~[\ ]! ("":: ~[]*)!
291 blockBody = statement
292 > sbb:: statement ws blockBody
295 | ^"while" expr block /ws
306 ident = "":: [a-z]++ &~ keyword
307 keyword = "if" | "then" | "else" | "while"
318 q = a3:: [a-z] [a-z] [a-z]
319 &~ ("":: ~[])! "b" ("":: ~[]*)!
326 s = s:: [a-z] [a-z] [a-z] " "*
332 output "Plus:{left:{Foo} right:{{2}}}";
336 | Plus:: (left::Expra) "+" (right::Expr)
337 Expra = Foo:: ("a" | "b")
343 output "top:{a q a}";
345 s = top:: z (q::"a"*) z
349 testcase "dangling else" {
350 input "if (x) if (y) z else q";
351 output "if:{ident:{x} else:{if:{ident:{y} then:{ident:{z}}} ident:{q}}}";
354 Expr = if:: "if" "(" Expr ")" IfBody /ws
356 IfBody = else:: Expr "else" Expr /ws
357 | then:: Expr &~ (("":: (~[])*) "else" Expr! /ws)
364 output "ac:{{2 1 2 1}}";
373 b = "":: ("b":: x "2")*
374 c = "":: ("c":: x "2" x "1")*
378 testcase "follow restrictions on empty string" {
380 s = x:: "x" A "x" C "x"
390 output "q:{a {x x x x x} c}";
391 s = q:: A ws (B|()) ws C
399 input "aaaaaaaaaaaaaaaaaaaa";
406 testcase "question mark" {
409 s = s:: X " " X " " X
416 testcase "operator: ... " {
417 input "aaabbbaaa abababababa";
418 output "s:{C:{a a a b b b a a a} B:{a b a b a b a b a b a}}";
421 B:: = [ab]* &~ (... "bbb" ...)
425 testcase "operator: ~~" {
426 input "aaabbbaaa abababababa";
427 output "s:{C:{a a a b b b a a a} B:{a b a b a b a b a b a}}";
430 B:: = ~~(... "bbb" ...)
436 output "+:{a *:{id:{b} c}}";
446 testcase "epsilon as a positive conjunct" {
449 X:: = "a" ("b"+ & ())
452 testcase "epsilon as a negative conjunct" {
455 X:: = "a" ("b"* &~ ())