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