[antlr-interest] CommonTree & Tree grammar versus DIY
Gerald Rosenberg
gerald at certiv.net
Sat Aug 16 00:56:51 PDT 2008
At 06:33 PM 8/15/2008, Szczepan =?iso-8859-2?q?Ho=B3yszewski?= wrote:
>Andy Tripp wrote:
>
> > Right. Whoever writes the doSomething() method shown above is going to
> > have to know what the AST looks like, regardless of whether the
> > doSomething() call is embedded in a treewalker.g file or plain old code.
>
>That's exactly the problem. Whoever writes the doSomething() for a processing
>pass that is only interested in 3% of the language constructs, will have not
>only to know, but also to painstakingly express with tree rules, what the AST
>can possibly look like from the start symbol to wherever the relevant
>constructs can appear in the grammar. This essentially duplicates a large
>chunk of the parser grammar. There is no simple way to tell ANTLR to
>doSomething() e.g. for each type definition, regardless of whether it occurs
>at top level, in a class, in a function, in an anonymous code block buried
>deep in a lambda expression, or in that fifth possible place where the draft
>0.0.2 specification will allow type definitions to occur.
>
>Szczepan Holyszewski
Exactly correct. Except ... almost all of the machinery needed to
implement "doSomething()" as an operation on an AST already exists in Antlr!
Most any "doSomething()" can be composed from a well-defined API set
of AST node-oriented operations, such as create, copy, insert,
delete, and find.
Some if not most of the needed atomic AST operations already exist
in the org.antlr.runtime.tree.TreeWizard hierarchy (create(Token),
dupNode(Object), dupTree(Object), index, getParent, setParent,
getChild, setChild, addChild, replaceChildren, etc).
What is missing is a code generation step that would generate the
bodies of the create, copy, insert, delete, and find methods specific
to a particular AST node structure. This is basically the same
operation used in the generation of a tree-walker.
Tree-walker code is generated using ASTTreeParser.stg using a custom
tree grammar to define static AST rewrites. The implementing code
for AST node create, copy, insert, delete, and find methods would be
generated based on an analogous "access grammar" and corresponding
ASTAccessParser.stg. As with the tree grammar, the access grammar
would identify the nodes of interest and their relevant structure.
Even with so much existing, this is not a trivial extension to
Antlr. Theoretically, the end result of any "doSomething()" AST
manipulation could be done with a well-planned set of
tree-walkers. It is just that a random access approach, supported by
the equivalent of findFirst, findNext, findPrev, findLast operations,
is distinctly better than a purely top-down (only getNext allowed)
approach for non-trivial bi-directionally context-dependent AST
rewrite problems.
Unfortunately, does not sound like AntlrMorph addresses this
particular problem.
Ter, do you have another graduate student looking for a project? Or,
if I finish my implementation, can I get Ph.D. credits? ;)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20080816/f7ccb22a/attachment.html
More information about the antlr-interest
mailing list