JavaScript parser API

Claus Reinke claus.reinke at
Wed Jul 6 10:02:03 PDT 2011

>> the AST API strawman ..
> It hasn't really been championed so far. I was concentrating on
> other proposals for

So it was just timing, not behind-the-scenes disagreements. Ok.

>>   - it does not support generic traversals, so it definitely needs a
>>       pre-implemented traversal, sorting out each type of Node
>>       (Array-based ASTs, like the es-lab version, make this slightly
>>       easier - Arrays elements are ordered, unlike Object properties);
> I designed it to be easily JSON-{de}serializable, so no special prototype.
> However, you can use the builder API to construct your own format:
> With a custom builder you can create objects with whatever methods
> you want, and builders for various formats can be shared in libraries.
>>       at that stage, simple applications (such as tag generation)
>>       may be better of working with hooks into the parser, rather
>>       than hooks into an AST traversal? also, there is the risk that
>>       one pre-implemented traversal might not cover all use cases,
>>       in which case the boilerplate tax would have to be paid again;
> I don't understand any of this.

Your builder API defines hooks into the parser (code the parser
calls on encountering certain pieces of syntax). The alternative is
to let the parser build its standard Node AST, then write traversals
for that AST, and have hooks in the traversal (code the traversal
calls on encountering certain Node types).

Parser hooks are tied to the parsing algorithm, but that can be
sufficient for tasks that can be handled in a single pass (generating
tags files, generating lint advice, ..). AST traversal hooks can build
on different traversal schemes (top-down is useful for some tasks,
bottom-up for others, a few tasks require combinations of both).

In both cases, having to write code for each Node type or for each
kind of syntax phrase is a pain. It also tends to be unnecessary, as
most AST-based tasks can be factored into default code (the same
scheme for most types of Node) and a few special cases.

Having to write out the default code (often a recursion scheme)
repeatedly, for each type of Node, is known as boilerplate code,
and people working with ASTs try to avoid that if they can. In
statically typed languages, this isn't trivial, but in dynamically
typed JS, it should be easy.

Take a couple of standard examples:

- extracting free variables:
    - by default, recurse into sub-ASTs, collecting sub-results;
    - for variable occurrences, record them;
    - for variable binders, recurse and collect, then remove
        the bound variables from the results.

- generating tags file:
    - by default, recurse into sub-ASTs
    - for variable/function definitions, write out source location

For less trivial tasks the number of special cases increases, but
the idea is the same: only write out the non-standard cases.

Starting from a Node AST, we'd have to write handlers for every
Node type. With an Array-based AST, we could write a generic
handler for the recursive traversal, then override it for the few
node types of interest. With the Builder API, we could omit
handlers, but the omitted handlers default to producing Nodes
(if we store information in non-local variables, this might suffice
for the two simple tasks above).

Things get more complex for realistic tasks, which mix top-down
with bottom-up traversals for program analysis and transformation.

One could write a Stratego[1]-style traversal library on top of the
Node AST, and then define traversals in terms of this library,
without the boilerplate code (which is what we did for the Haskell
Refactorer HaRe, and also what the Wrangler team did for Erlang).

That would also provide some isolation from AST details, as
traversal-based code would only mention the Node types it
needs to handle, not all the Node types it needs to traverse.

I'll stop here, to split my reply into smaller chunks, as requested.



    For an overview of the strategic rewriting approach to AST
    traversals and transformations, see this manual section:


More information about the es-discuss mailing list