perl -pe '
BEGIN { my $term = qr/(S|K|\((?-1)(?-1)\))/ }
1 while
    s/\(\(\(S($term)\)($term)\)($term)\)/(($1$3)($2$3))/
or  s/\(\(K($term)\)($term)\)/$2/;
'

##</code><code>##

perl -Mre=eval -nE <<CODE
chomp;
$_ = <<RULE . "---\n$_";
^111 0^11
^110 1^10
^11  1^1
^01  1^1
^10  1^0
^00  0^0
^1   1
^0
  1  1^1
  0  0^0
RULE

BEGIN {
    my $nc_rule = qr/^ *\S+ *\S* *$/m;
    my $c_rule = qr/^ *(\S+) *(\S*) *$/m;
}

/\^.*$/ or say( ( split /\n/ )[-1] ) while
    s/$c_rule(?:\n$nc_rule)*\n---\n.*?\K\1/$2/;
CODE

##</code><code>##

1
11
111
1011
11111
100011
1100111
11101011
101111111
1110000011
10110000111
111110001011
1000110011111
11001110100011
111010111100111
...

##</code><code>##

perl -Mre=eval -nE <<CODE
chomp;
$_ = <<RULE . "---\n$_";
+ ^'>'+ ^
+ ^> ^
. ^`>`.. ^
. ^S>S ^
. ^K>K ^
. ^x>x+ ^

- ^'>- ^
- ^> ^
! ^`>!! ^
! ^S> ^
! ^K> ^
! ^x>- ^

, ; ^'>', '; ^
, ; ^>  ^
@ * ^`>`@@ `** ^
@ * ^S>S S ^
@ * ^K>K K ^
@ * ^x>x, x; ^

^>

```S>``.@`.*^
``K>.!^
RULE

BEGIN {
    my $vs = qr/[^ >\n]*/;
    my $ss = qr/ *?/;
    my $c_rule = qr/(?>($vs)$ss($vs)$ss($vs)$ss>$ss($vs)$ss($vs)$ss($vs)$)/m;
    my $nc_rule = qr/(?>(?:$vs$ss){3}>(?:$ss$vs){3}$)/m;
}
1 while
    s/$c_rule(?:\n+$nc_rule)*\n---\n.*?\K\1(.*?)\2(.*?)\3/$4$7$5$8$6/;
say ( ( split /\n/ )[-1] );
CODE

##</code><code>##

t ::= S
t ::= K
t ::= xp
p ::= 'p
p ::=
t ::= `tt

##</code><code>##

`````S`KSKxx'x''             # B = S(KS)K
`x`x'x''                     # Bxyz = x(yz)
`````S``S`K``S`KSKS`KKxx'x'' # C = S(S(K(S(KS)K))S)(KK) = S(S(KB)S)(KK)
``xx''x'                     # Cxyz = xzy
````SS`K``SKKxx'             # W = SS(K(SKK))
``xx'x'                      # Wxy = xyy