Re: Zebu and SableCC (was Re: Simple SableCC Example)

[Andrew Cooke <andrew@intertrader.com>]

Andrew Cooke wrote:
> "Etienne M. Gagnon" wrote:
> > Andrew Cooke wrote:
[...]
> > > (Using, these days, a similar program written in Lisp, called Zebu -
[...]
> > Do you have a short summary of the differences?
> - there is no tree-walking code provided in Zebu, but a separate
> package, called Zebu-RR  lets you define transforms as a
> collection of rules.  The rules are applied to the tree (either top-down
> or bottom-up) to modify the structure.
[...]

I've just done something in Zebu that I always found quite frustrating
in SableCC - because of the syntax of the language I was writing an
interpreter for I had to generate a tree for sequences, rather than a
list.  In other words, a frequent sub-tree was an object which included
both a token and a "next" object, which in turn carried a token and a
"next" object, which...

Now I have to do the same in Zebu, but I can transform the sub-tree into
a list using a Zebu-RR rewrite rule, and I thought you might be
interested in it as an example (feel free to ignore this - it's just
something I find neat that I'd like to share).

Okay, so my code to do the transform is:

(defrule tree-to-list                                             ; 1
  (tok-next-str (token tok)                                       ; 2
                (next nxt))                                       ; 3
  (list-str (list #'(lambda (top)                                 ; 4
                      (declare (ignore top))                      ; 5
                      (cond ((typep nxt 'list-str)                ; 6
                             (list tok (list-str-list nxt)))      ; 7
                            ((null nxt)                           ; 8
                             (list tok))                          ; 9
                            (t                                    ; 10
                             (list tok nxt)))))))                 ; 11

(zebu::postorder-transform tree '(tree-to-list))                  ; 12

Which is quite neat (I hope the brackets match!).  I'll explain the code
below, line by line (the line numbers are not part of Lisp code, they're
comments), but the important features can be seen without understanding
everything.

First, the rule consists of two halves.  The matching half (lines 2 and
3) which identifies which nodes in the tree should be processed, and the
replacement half (lines 4 to 11) which gives the replacement and a
function to calculate it.

In this case the rule replaces a tok-next-str structure (that has two
slots, token and next) by a list-str that contains the list.  The list
itself is calculated by the (lambda) function, which refers to "tok" and
"nxt", the values in the matched node's slots.

The rule is applied to the tree, bottom-up, as many times as possible,
in line 12.

As I said, I've no idea how this translates into Java for SableCC, I
just thought it was elegant.  Maybe it will give you some useful ideas.

Andrew


Line-by-line description:

lines 2 and 3: These define what the rule matches.  It should be applied
to any node of type tok-next-str, which has two slots, called token and
next, whose values (referred to in the code later) are tok and nxt.

line 4: This says what should replace the matched node.  In this case
it's a structure of type list-str which has a single slot (called list)
whose value will be given by the function defined in the next lines.

line 5: top is a pointer to the sub tree which is passed to the function
- we don't use it, so we tell the compiler to ignore it or it will issue
a warning.

line 6: cond is Lisp's general "if" statement.  The first branch (line
7) is executed if nxt (the contents of the next slot of the current
tok-next-str node) is a list-str, in which case we want this node to
include the contents of that node's list directly, removing any
reference to the node from the tree and extending the current node's
list.

line 7: If the node below is a list object, then we collect its
contents, put them in a list with the token for this node, and return
the list.  The returned value is used as the "list" slot value in the
replacement node.

lines 8 and 9: Alternatively, the node below may by null (a leaf node). 
In that case, return a list containging just the current token.

lines 10 and 11: Otherwise (t is always true), return a list containing
the two subnodes of this node.

line 12: Apply the rule to nodes, repeating as often as possible, moving
through the tree from top to bottom.

I can explain the code in more detail by email to anyone curious - Lisp
is not easy to read if you are not used to it.