machine.ebnf (2757B)
1 // %machine: regular languages over an abstract token alphabet. 2 // Compiled codegen-only to a steppable verifier (fsm_*) + an AST-directed 3 // sampler (gen_*). Token-mode is C-generator-only, so this file is excluded 4 // from the C<->Python parity set. 5 6 // conn — the design example: SYN SYNACK ACK (SEND|RECV)* FIN FINACK. 7 %machine conn { 8 %def data = [ SEND RECV ] ; 9 %def opened = data* ; 10 session = SYN SYNACK ACK opened FIN FINACK ; 11 } 12 13 // kinds — multiple rules: distinct accept kinds, plus source-order priority on a 14 // same-length tie (greet and greet2 share a language; greet, declared first, 15 // wins the `which` report). 16 %machine kinds { 17 greet = HELLO WORLD ; 18 greet2 = HELLO WORLD ; 19 bye = BYE ; 20 } 21 22 // shapes — alternation, + and ?, counted {n,m}, complement [^...], and `.`. 23 %machine shapes { 24 %def vowel = [ A E I O U ] ; 25 word = START ( vowel | CONS )+ STOP ; // one or more vowels/consonants 26 pair = L . R ; // any single symbol between L and R 27 notv = N [^ vowel ] ; // a non-vowel symbol (set ref in [^]) 28 reps = X{2,3} ; // two or three X 29 maybe = P Q? Z ; // optional Q 30 } 31 32 // sets — set algebra inside [ ], mirroring the UTF-8 character classes. A %def 33 // whose body is a set doubles as a named symbol set; inside `[ … ]` a member may 34 // be an UPPERCASE symbol or a lowercase set name, juxtaposition is union, `&&` is 35 // intersection, `--` is difference, and `^` complements. (Set names are scoped 36 // to their %machine block, so `shapes` could reuse `vowel` without colliding.) 37 %machine sets { 38 %def vow = [ A E I O U ] ; 39 %def con = [ B C ] ; 40 %def both = vow | con ; // union of two sets 41 %def vowy = [ vow Y ] ; // a set reference + a symbol inside a bracket 42 %def notvw = [^ vow ] ; // a complement set (legal in a definition) 43 anyv = V [ vow ] ; // a vowel, named by set reference 44 notv = N [^ vow ] ; // complement of a set 45 inboth = P [ both ] ; // a member of a union set 46 outb = M [^ both ] ; // complement of a union set 47 vy = W [ vowy ] ; // a member of a set-ref-plus-symbol set 48 inter = I [ both && con ] ; // intersection -> con 49 diff = D [ both -- vow ] ; // difference -> con 50 cnv = K [ notvw && both ] ; // (¬vow) ∩ both -> con 51 } 52 53 // overlap — overlapping alternatives, resolved by the subset construction. 54 %machine overlap { 55 r = A B | A C | A B D ; 56 } 57 58 // epsilon — ε-accepting is allowed in %machine (unlike the byte lexer, which 59 // rejects a nullable recognizer): the empty trace is valid when the start state 60 // is accepting. 61 %machine epsilon { 62 opt = HEAD? TAIL? ; 63 }