Planning Project to use YAPP - confused on AST Tree Walker
Cefn Hoile <[email protected]> Thu, 19 Apr 2007 00:53:00 +0100
| Newsgroups | gmane.text.xml.o-xml |
|---|---|
| Message-ID | <[email protected]> |
I've been seeking a suitable XML format and supporting toolset to
store both an abstract grammar and the mapping from an instance of
the grammar (abstract syntax tree) to executable programs in a target
language.
I'm aiming to learn the basics of compiler design by re-creating a
subset of ECMAScript, (control flow, arithmetic and boolean logic),
but where the javascript is written from an abstract syntax tree
(AST) stored in XML directly e.g.
<if>
<equals>
<sum>
<number>2</number>
<number>2</number>
</sum>
<number>4</number>
</equals>
<assign>
<property>world</property>
<string>consistent</string>
</assign>
</if>
The grammar (also represented in XML, as in the case of YAPP) should
ensure that the original tree is indeed a valid construct, and
traversing the tree should spit out ECMAscript, in this example...
if(2 + 2 == 4){
world = 'consistent';
}
...and then this should run in an ECMAscript interpreter as a proof
of concept.
I'm finding the YAPP introduction intriguing (I think I'm on the
right track looking at YAPP), but rather confusing because it's
essentially recursive - it uses it's own BNF grammar translator as
the main example.
Is there somewhere else where there's a nice simple YAPP example
(e.g. a language translator/compiler, not a grammar translator) which
would help me understand where the placeholders equivalent to this
kind of ANTLR file might go...
http://supportweb.cs.bham.ac.uk/docs/tutorials/docsystem/build/
tutorials/antlr/files/expression.g
I think I can see how the AST is constructed (or traversed), but not
so easy to make out if there's a convention for where the target
output code should be plugged in, e.g. I can provide this kind of
basic info in whatever format and whatever input file if I can only
find the right place...
'if(', [bool], '){',
[stmnt],
'}'
[number], '==', [number]
[property], '=', [number]
This is a clumsy blend of tokenizer's events with the required output
to my target language, but hopefully illustrates the point. Where
does this info on the final target output (the bits in quotes) get
put in the YAPP approach, in a way which reflects the relationship
between these strings and the production rules themselves, and hence
is used to traverse the AST?
ANTLR is capable of this, I think, and employs a number of variants
on BNF for the various defs (lexer, parser, tree walker).
However I'm really keen on getting this info into XML in the place of
BNF.
Once this data's in an XML format I hope to construct useful reports
on the grammar tree and in example abstract syntax trees using the
expressive power of XPath This is where the YAPP approach would be
very cool if I can get my head around it, as it would make pretty
well the whole toolset based on XML technologies.
Any assistance pointing me to examples would be useful.
Cefn