The script parse.k is a tool for implementing languages with precedence relations. (a k4 version is here).

Assignment v:e Logic p&q, p and q, p|q, p or q, ~p, not p relations a in b, a~b, a=b, ab, a<=b, a>=b arithmetic a+b, a-b, a*b, a/b, a^b, -a, neg a lists a,b, ,a, list a comparison a min b, a max b aggregation sum a, avg a conditional if(a;b;c), integer = type(a), type(b)=type(c) function f(a), g(a;b), h(a;b;c) types 12 (int), 12.2 (float), "12.2" (symbol)

The type of an operator o of valence n is a list of type-vectors. Each type-vector t specifies the type of the result t[0] as a function of the types of its arguments 1_ t. The parser recognizes three primitive types: 1 (integer), 2 (float), and 4 (symbol). All character vectors are treated as symbolic atoms. When you add a new operator, you need to add type information for it to R.

Note that four of the syntax classes have special valence: ',' (argument separator) has valence -1, '(' has 0, ')' has -2, and Z (end of string) has 0. When one of these is detected (because valence is <= 0), a routine is invoked which reduces the operator-stack (see below) without affecting the value-stack. when ',' is detected, we throw it away; when '(', we throw nothing away; when ')' is detected, we throw it and '(' away; and when Z is detected (we're done) we throw nothing away. ',' and Z are no-ops. '(' and ')' have no semantic effect. c (constant) also has valence 0, but that's just a place-holder to keep V in sync with the columns of P. It's never used.

The basic parsing operation is to find and execute the appropriate operation given an operator of class c and an input token of class d. That operation is given by P[c;d] -- a simple lookup given the classes. In the course of parsing, there are two lists: the input parsed so far j and the input yet to be parsed i, and two stacks: the operator-stack o and the value-stack v. The parser moves tokens from i to j, and uses the two stacks to hold the current state. Parsing is therefore programmed in K as a 'converge': keep parsing until the result matches the input -- then the result tree is in v:

**|act/(i;j;o;v) /first of the last of final stepThere are four atomic operations:

c shift the constant to the value-stack s shift the operator to the operator-stack> r construct a tree from the top of the operator-stack and n values from the value-stack and shift the result to the value-stack a accept the result (you're done).There are also several error conditions, including a general "syntax error" if the result is not a tree. There are one or two oddities:

2+3 +(2;3) +2 3 +(2 3)are equivalent, but

a+b +(a;b)while equivalent to each other, are not in general equivalent to

+a b +(a b)

Thanks to Thomas Niemann and Wayne Miraglia for comments and corrections.