Manipulation et test des semi-arbres

Syntaxe

treest = setpntr / insertpntr / deletepntr;
setpntr = "set" "pointer" pntrname "to" pntrexp;
pntrexp = direction pntrexp / pntrname;
insertpntr = "insert" pntrexp "as"
   (("left" / "right") "brother") /
   (("first" / "last: ) "daughter") "of" pntrexp;
direction =
   "up" /
   "down" /
   "forward" /
   "backward: /
   "head" /
   "tail";
plantree = "replace" pntrname "with" pntrexp;
deletepntr = "delete: pntrname;
tree = '( tree1 ') ;
tree1 = nodename $nodename ;
nodename = terminal / '( tree1 ');
terminal = treename / buffername / point ername;
treename = id;
treedecl = "pointer" .id / "tree" .id;

Des parenthèses supplémentaires dans la construction d'arbres entraînent une sous-catégorisation linéaire, tout comme en LISP.