krl/spec/grammar.ebnf at main · hyperpolymath/krl · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
(* SPDX-License-Identifier: MPL-2.0 *)
(* KRL — Knot Resolution Language *)
(* Grammar v0.1.0 (2026-04-05) — DRAFT *)
(* Pronounced "curl" *)

(* =================================================================== *)
(*  Top-level program                                                  *)
(* =================================================================== *)

program           = { statement } ;

statement         = binding
                  | expression_stmt
                  | query ;

binding           = "let" , identifier , "=" , expression , ";" ;
expression_stmt   = expression , ";" ;

(* =================================================================== *)
(*  Expressions — the four KRL operation families                      *)
(* =================================================================== *)

expression        = compose_expr ;

compose_expr      = tensor_expr , { ";" , tensor_expr } ;           (* sequential composition *)
tensor_expr       = unary_expr , { "|" , unary_expr } ;             (* tensor / juxtaposition *)

unary_expr        = prefix_op , unary_expr
                  | atom ;

prefix_op         = "close"                                         (* RESOLVE: closure *)
                  | "mirror"                                        (* TRANSFORM: reflection *)
                  | "simplify"                                      (* TRANSFORM: Reidemeister *)
                  | "normalise"                                     (* TRANSFORM: canonicalise *)
                  | "classify" ;                                    (* RESOLVE: equivalence class *)

atom              = generator                                       (* CONSTRUCT *)
                  | identifier
                  | "(" , expression , ")" ;

(* =================================================================== *)
(*  Generators (CONSTRUCT)                                             *)
(* =================================================================== *)

generator         = crossing_gen
                  | cup_cap_gen ;

crossing_gen      = "sigma" , integer                               (* positive crossing on strands i, i+1 *)
                  | "sigma_inv" , integer ;                         (* negative crossing *)

cup_cap_gen       = "cup" , integer                                 (* cup on strands i, i+1 *)
                  | "cap" , integer ;                               (* cap on strands i, i+1 *)

(* =================================================================== *)
(*  Queries (RETRIEVE)                                                 *)
(* =================================================================== *)

query             = "find" , "where" , filter_list , ";" ;

filter_list       = filter , { "and" , filter } ;

filter            = identifier , comparison , value ;

comparison        = "=" | "<" | ">" | "<=" | ">=" | "!=" ;

value             = integer
                  | string_literal
                  | identifier ;                                    (* reference to a let-bound expression *)

(* =================================================================== *)
(*  Equivalence predicates (RESOLVE)                                   *)
(* =================================================================== *)

(* These are recognised at the expression level as prefix queries:     *)
(*   equivalent? <expr> <expr>                                         *)
(*   near <expr>                                                       *)
(* For v0.1 grammar, model these as "call-shaped" atoms:               *)

(* Not in this grammar yet — placeholder for v0.2:                     *)
(*   resolve_query ::= "equivalent?" expression expression             *)
(*                   | "near" expression                               *)
(* =================================================================== *)

(* =================================================================== *)
(*  Terminals                                                          *)
(* =================================================================== *)

identifier        = letter , { letter | digit | "_" } ;
integer           = digit , { digit } ;
string_literal    = '"' , { string_char } , '"' ;
string_char       = ? any character except unescaped quote ? ;

letter            = "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J"
                  | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T"
                  | "U" | "V" | "W" | "X" | "Y" | "Z"
                  | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j"
                  | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t"
                  | "u" | "v" | "w" | "x" | "y" | "z" ;

digit             = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

(* =================================================================== *)
(*  Whitespace and comments                                            *)
(* =================================================================== *)

(* Whitespace (space, tab, newline) is ignored between tokens. *)
(* Line comments: "--" to end of line.                          *)

(* =================================================================== *)
(*  Reserved words                                                     *)
(* =================================================================== *)

(* let in close mirror simplify normalise classify find where and *)
(* sigma sigma_inv cup cap                                         *)