Open forum for discussing o:XML technology, language issues, implementations and applications

Cefn Hoile | 19 Apr 2007 01:53

Planning Project to use YAPP - confused on AST Tree Walker

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';

(Continue reading)

headers

Martin Klang | 22 Apr 2007 22:36

Re: Planning Project to use YAPP - confused on AST Tree Walker

Hello,

Interesting question, made me think about parsing issues again.
Using XML for intermediary or cross-language formats indeed has  
massive advantages, and I think we'll see much more of such formats  
in the future.

Antlr does have a strong treewalker component, though I've found it  
difficult to work with when generating XML (or xml-like) output.

The idea with YAPP is that you feed a grammar (in XML format) as the  
input and you get a parser (an xsl stylesheet) as output.
The example with the BNF parser is a bit like pulling oneself up by  
the straps of one's boots. The resulting BNF parser can parse text- 
based BNF grammars into the XML format that is used to drive the two  
main xsl's.
Note that YAPP is more a proof of concept than a production-grade  
tool - ultimately XSLT is not the best language for writing high- 
performance parsers in.

Another o:XML-related project you might want to check out is MLML  
[1], which aims to be an XML format for representing almost any  
programming language. It would work very well as the basis for a  
Javascript representation in XML. There are also some tools available  
for MLML already, for generating JavaDoc-style documentation in  
DocBook and HTML, and for producing XMI-format class diagrams.
Writing an XSLT stylesheet that can generate valid ECMA Script code  
from a decent XML-based format should not be too difficult.
There is also a framework for compiler construction based on MLML  
which was created for a commercial, production-grade compiler project

(Continue reading)

headers

Cefn Hoile | 25 Apr 2007 18:27

Re: YAPP+BNF Working Example?

WORKING EXAMPLE?

I've been trying to get a basic example of YAPP compiling a source  
file which conforms to a BNF spec.

I've been using the example of arithmetic directly from the YAPP  
page, and a text file containing '3 + 4' but I'm filling in a lot of  
blanks as there doesn't seem to be a worked example with verified  
code - how to run the full-fledged BNF+YAPP process, e.g.

* start with BNF and example source (plus a templates file for  
'compilation')
* generate lexer and parser (which itself imports both lexer and  
templates file)
* run the source through the parser to complete a compilation  
(triggering rules in the templates file)

I attach the files I'm currently using to test run the process,  
(which would be ideal supporting files for a worked example, if they  
worked :). They are as minimal as possible, really just a vehicle for  
the BNF right now.

The XSLT templating is being coordinated through ANT, and the full  
output is shown at the end of this mail. The early lines of output  
from ANT are just copying original files into a working directory  
where they can be safely operated on. ANT terminates with an unusual- 
looking error 'Content is not allowed in Prolog'.

Can you point me to an example which should actually work so I can  
complete this whole pipeline correctly at least once. I'm using Xalan

(Continue reading)

headers

Martin Klang | 28 Apr 2007 20:11

Re: YAPP+BNF Working Example?

On 25 Apr 2007, at 18:27, Cefn Hoile wrote:

> WORKING EXAMPLE?
>
> I've been trying to get a basic example of YAPP compiling a source  
> file which conforms to a BNF spec.

Cefn,

did you try running the examples that come in the download zip?  
There's an XPath grammar written in BNF (incomplete - XPath is quite  
a big expression language), toghether with the BNF grammar itself.  
There are some basic usage instructions in the readme.txt file.

You can run the examples using the Makefile with:
make test
(just edit the Xalan home directory first)

Though for some bizarre reason the left-recursion elimination doesn't  
work with Xalan 2.7.0 unless you enable XSLTC. The error message is  
not very helpful at all:
java.lang.RuntimeException: java.lang.RuntimeException: XSLT  
TransformerFactory Error
It works fine if you pass the -XSLTC flag to Xalan.

I've updated the readme file and made some changes to the Makefile so  
that it works out of the box with Xalan 2.7.0.
If you like you might want to simply download the new version [1], or  
get the updated files from CVS [2].

(Continue reading)

headers

Martin Klang | 26 Apr 2007 11:19

Re: YAPP+BNF Working Example?

Hi Cefn,

thanks for the files, I'll see what I can do to put a working example  
together in the next day or so.

As far as parsers are concerned, you generally get two varieties: top- 
down (aka recursive descent) and bottom-up.
YAPP XSLT is an example of a pure recursive descent parser, with no  
workarounds to fix any of the problems inherent with this type of  
parser (eg poor error detection and reporting).

For Java, the main free parser generators are Antlr as you've  
mentioned, JavaCC and JCup. I've used all of these in different  
projects, and can't say I've found any one particularly better or  
worse than any other. It's a case of horses for courses, and what  
syntax you feel most comfortable working with. JavaCC and Antlr are  
the two biggest contenders, JCup being a much smaller and less  
supported project.

JCup is used for the XPath expression parser in the current o:XML  
compiler/interpreter implementation. JavaCC is used for the various  
parsers in SML. In fact, if you are interested in examples of XML- 
oriented JavaCC parsers, check out SML [1] (source in CVS [2]).

If you're interested in parsers, compilers etc then I can recommend  
the book Modern Compiler Design [3]. It's a good read and a great  
resource, not exactly a beginners volume but it covers the whole  
compiler/interpreter realm very thoroughly. Otherwise the so-called  
Red Dragon Book [4] is supposed to be the classic in the genre.

(Continue reading)