// precedence parser
// stevan apter, 11.01
// thomas niemann's parsing paper:  http://epaperpress.com

/ operator table:

Z:_ci 255					/ end-of-string
S:":"						/ assignment
G:"()"						/ grouping
L:";"						/ list

O:(,S						/ assignment
   ("&";"and";"|";"or")				/ and, or
   ("in";"~";"=";"<";">";"<>";"<=";">=")	/ relations
   "+-"						/ plus, minus
   "*/"						/ times, divide
   ,"^"						/ power
   ,","						/ join
   ("LIST";"list";"NEG";"neg";"NOT";"not")	/ enlist, negate, not
   ,"if"					/ ternary functions
   ("min";"max")				/ binary functions
   ("sum";"avg")				/ unary functions
   ,L						/ arg separator
   ,G 0						/ left paren
   ,G 1						/ right paren
   ,Z)						/ end of string

/ type table:

R:+((,S					;,/(0 1 0;0 2 0;0 4 0;0 6 0)+\:/:(1 0 1;2 0 2;4 0 4))
    (("~";"in")				;(1 1 1;1 1 2;1 1 4;1 2 1;1 2 2;1 2 4;1 4 1;1 4 2;1 4 4))
    (,","				;(1 1 1;2 1 2;2 2 1;2 2 2;4 4 4))
    (("+";"-";"*";"min";"max")		;(1 1 1;2 2 1;2 1 2;2 2 2))
    ("/^"				;(2 1 1;2 2 1;2 1 2;2 2 2))
    (,"="				;(1 1 1;1 2 1;1 1 2;1 2 2;1 4 4))
    (("LIST";"list")			;(1 1;2 2;4 4))
    (("NEG";"neg")			;(1 1;2 2))
    (("NOT";"not")			;,1 1)
    (("&";"and";"|";"or")		;,1 1 1)
    (("<";">";"<>";"<=";">=")		;(1 1 1;1 1 2;1 2 1;1 2 2))
    (,"sum"				;(1 1;2 2))
    (,"avg"				;(2 1;2 2))
    (,"if"				;(1 1 1 1;2 1 2 2;4 1 4 4)))

/ shift-reduce table:

V:2 2 2 2 2 2 2 1 3 2 1 -1 0 -2 0 0	/ valence

/   S&=+*^,U321L()Zc 			/ s -> right assoc, r -> left assoc

P:("rssssssssssrsrrc"   / S
   "rrsssssssssrsrrc"	/ & |
   "rrrssssssssrsrrc"	/ = < > <> <= >=
   "rrrrsssssssrsrrc"   / + -
   "rrrrrssssssrsrrc"	/ * /
   "rrrrrrsssssrsrrc"	/ ^
   "rrrrrrrssssrsrrc"   / ,
   "rrrrrrrssssrsrrc"	/ U
   "rrrrrrrrrssrsrrc"	/ 3
   "rrrrrrrrrrsrsrrc"	/ 2
   "rrrrrrrrrrrrsrrc"	/ 1
   "rrrrrrrrrrrrrrrc"	/ L
   "ssssssssssssssRc"	/ (
   "rrrrrrrrrrrrOrrc"	/ )
   "sssssssssssssLac") 	/ Z

/ L -> K translation:

trans:{(K[1],,x)K[0]?x}			/ translate to K

K:+(("<>";"(~=)")			/ L -> K
    ("<=";"(~>)")
    (">=";"(~<)")
    ("/";"%")
    ("in";"IN")
    ("LIST";"(,:)")
    ("NOT";"(~:)")
    ("NEG";"(-:)")
    ("list";"(,:)")
    ("not";"(~:)")
    ("neg";"(-:)")
    ("and";"&")
    ("or";"|")
    ("min";"&")
    ("max";"|")
    ("if";"IF")
    ("sum";"SUM")
    ("avg";"AVG")
    (S;"SET"))

/ tokenizing parameters:

W:("<>";"<=";">=")						/ 2 character operators
U:(("-";"NEG");("~";"NOT");(",";"LIST"))			/ ambivalent unaries

B:" "								/ blank
D:"."								/ decimal point
N:"0123456789"							/ numerics
A:"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_"	/ alphas
Q:"\""								/ quotation
F:?(,//O)_dvl Z,A,N						/ symbolics
C:(B;A;D;N;Q;F)							/ token classes

state:{{.[x;(;y);:;z]}/[((#x),256)#-1;y;+x]}			/ construct state table

/        B A D N Q O 		/ token classes
M:state[(1 2 2 4 7 9		/ 0 start
         1 2 2 4 7 9		/ 1 blank
         1 3 3 3 7 9		/ 2 name1
         1 3 3 3 7 9		/ 3 name2
         1 2 5 4 7 9		/ 4 num1
         1 2 2 6 7 9		/ 5 decimal
         1 2 2 6 7 9		/ 6 num2
         7 7 7 7 8 7		/ 7 open quote
         1 2 2 4 7 9		/ 8 close quote
         1 2 2 4 7 9)]_ic C	/ 9 operator

I:0 1 3 6 8			/ state endpoints

/ tokenize:

token:{((()lit/()one/fsm chr"",x)two/W)una/U}						/ tokenize
fsm:{bla cut[x;0 M\_ic x]}								/ scan input
bla:{x _di&B=*:'x}									/ eliminate blanks
cut:{{:[1=#x;*x;x]}'(&(~=)':I _binl y)_ x}						/ cut into vectors and atoms
one:{x,:[&/y _lin F;y;,y]}								/ operator strings -> atoms
lit:{x,,:[~@y;y;y _in A,D,N;,y;y]}							/ "a" -> ,"a"
two:{@[x;i;:[;y]]_di -1+i:&0{&/x~'(z;y)}[y]':x}						/ 2 char operators -> 1
una:{@[x;&{((z _in,/O)&~z~G 1)&y~x}[*y]':"(",x;:[;y 1]]}				/ e.g. - x -> NEG x (U)
chr:{:[~&/b:x _lin,/C;ERROR[(1+b?0)#x;"character error"];x]}				/ character error

/ parse:

parse:{:[#x;*tree[x]5;x]}								/ parse
type:{:[#x;*tree[x]3]}									/ type
tree:{act/("";x,,Z;!0;!0;,Z;"")}							/ construct tree
act:{t:P . class'x[4 1;0];trace[t]. 2#x;H[`$t]. x}					/ action step
T:0;trace:{[t;j;i]if[T;`0:,t,(T$j)," | ",(-T)$1_,/B,'i]}				/ trace, e.g. T:15
class:{(|/'x _in/:O)?1}									/ syntax class
H.a:{[j;i;p;w;o;v]:[1=#v;(j;i;p;w;o;v);ERROR[j;"syntax error"]]}			/ accept
H.c:{[j;i;p;w;o;v](j,B,*i;1_ i;p;tcons[*c],w;o;c:cons[i 0],v)}				/ constant -> v-stack
cons:{,:[&/x _lin D,N;(),x;Q~*x;"`",x;("GET";"`\"",x,"\"")]}				/ construct constant
tcons:{:[~4:x;TYPE@. x 1;"`"=*x;4;D _in x;2;1]}						/ type constant
H.s:{[j;i;p;w;o;v](j,B,*i;1_ i;topr[i 0],p;w;i[,0],o;v)}				/ shift operator -> o-stack
topr:{,(R[1],-1)(x _in/:*R)?1}								/ type operator
H.r:{[j;i;p;w;o;v]:[0<n;rp;rn][j;i;p;w;o;v;n:V class o 0]}				/ reduce v-stack by *o
H.O:{[j;i;p;w;o;v]ERROR[j;"missing operator"]}						/ missing operator
H.L:{[j;i;p;w;o;v]ERROR[j;"missing ("]}							/ missing (
H.R:{[j;i;p;w;o;v]ERROR[j;"missing )"]}							/ missing )
rn:{[j;i;p;w;o;v;n](j;i;(-n)_ p;w;(-n)_ o;v)}						/ reduce without result
rp:{[j;i;p;w;o;v;n]val[j;v;n];(j;i;1_ p;texp[j;p;w;n],n _ w;1_ o;exp[o;v;n],n _ v)}	/ reduce with result
val:{[j;v;n]if[n>#v;ERROR[j;"missing argument(s)"]]}					/ missing argument
exp:{[o;v;n],(,o),:[("GET"~**v:|n#v)&S~o*:;.[v;0 0;:;"RET"];v]}				/ construct expression
texp:{[j;p;w;n]:[6 _in w:|n#w;6;|/b:(1_'p*:)~\:w;*p b?1;ERROR[j;"type"]]}		/ type expression

/ errors:

ERROR:{`0:,x;'((-1+#x)#""),"^ ",y}							/ signal error

/ evaluate:

eval:{:[~#x;x;~4:x;_f[trans x 0]._f'1_ x;"GET"~x;GET;"SET"~x;SET;. x]}			/ simple evaluation
/ SET:{y}										/ comment
/ SET:{`0:,$x;y}									/ trace
SET:{.[x;();:;y];y}									/ set value
RET:{x}											/ return value
GET:{. x}										/ get value
TYPE:{__abs 4:. x}									/ type variable
SUM:+/;AVG:{(+/x)%#x}									/ aggregation
IF:{:[x;y;z]}										/ conditional
IN:{|/((),x)_lin(),y}									/ tolerant membership

/ references:

refs:{:[4:y;();~x~*y;?,/_f[x]'1_ y;. y 1]}						/ unique list of refs
gets:refs["GET"]									/ unique list of gets
sets:refs["SET"]									/ unique list of sets

/ miscellaneous:

string:{:[~#x;"";4:x;x;trans[*x],1!"][",1_,/(";",_f@)'1_ x]}				/ construct k-executable
run:eval parse token@									/ evaluate
cmd:{if["\\"~*x;. 1_ x;:""];x}								/ command
int:{while[~"\\\\"~a:{`0:"> ";0:`}[];a:cmd a;`0:,:[*r:.[run;a;:];r 1;5:r 1]]}		/ mini-interpreter - \\ to exit