[antlr-interest] Parsing Lisp into C++

[Richard Lewis]

This is not  an intellectual exercise or a homework assignment. The Lisp in question is a peculiar dialect of CLOS developed for our clients to be able to embed scripting behavior in our application suite. The interpreter has been tweaked to the point of which we can no longer squeeze out any more performance gains. There are 10's of thousands of lines of code distributed amongst many clients so changing the language in any way is not an option. 

So the next step is to have it compiled natively. 

The requirements  are:

1. Lexical analyser and parser needs to support our dialect of lisp
2. The runtime library needs to be multithreaded and flexible (thinking native LLVM or OpenCL)
3. Has to be compiled into native machine code (i.e. can't run in a virtual machine)

My question was one of style with using Antlr... Is it better to muddy the parser grammar with a single pass or split the AST creation into 2 passes?

-Richard

-----Original Message-----
From: Loring Craymer [mailto:lgcraymer at yahoo.com]
Sent: Mon 9/28/2009 3:49 PM
To: Richard Lewis; antlr-interest at antlr.org
Subject: Re: [antlr-interest] Parsing Lisp into C++
 
This is a case where I have to ask "why".  The typical Lisp compiler (not interpreter) is a Lisp to C translator with some additional glue.  You can probably even find support for translating CLOS to C++ if you look around.

--Loring



>
>From: Richard Lewis <Richard.Lewis at razor-risk.com>
>To: antlr-interest at antlr.org
>Sent: Sunday, September 27, 2009 6:32:19 PM
>Subject: [antlr-interest] Parsing Lisp into C++
>
> >
>
>
>>
>I've started looking into translating a large amount of
>legacy Lisp code into C++ using Antlr. I put together a simple grammar that
>generates an AST. My question is: Where is the best place to attach semantic  information?
>It seems to me that I should have a 2 pass parser, starting with the AST as
>shown below and then making  an additional pass to generate another AST
>that contains semantics. Unfortunately I'm not that familiar with Lisp but it
>seems to be difficult to parse in a single pass without resorting to an ugly
>grammar definition since everything in Lisp seems to be an expression of some
>sort.  This is ironic since Lisp already seems to be "parsed". 
> 
>Input:
> 
>(defun foo (x y) (progn (+ x 1) (+ y 1)))
> 
>Grammar:
> 
>program: (sexpr)* -> ^(PROGRAM sexpr*);
>sexpr: QT?(list|atom) ;
>list:      '(' ')'   |
>'(' members ')'  -> ^(LIST members);
>members: (sexpr)+;
>atom: OPERATOR | ID | num | STRING ;
>num       : (n=INT|n=FLOAT)
>-> ^(NUM $n);
> 
>AST Output:
> 
>PROGRAM
>     LIST
>           defun
>           foo
>           LIST
>                x
>                y
>           LIST
>                progn
>                LIST
>                     +
>                     x
>                     1
>                LIST
>                     +
>                     y
>                     1
> 
>Desired Output:
> 
>PROGRAM
>     FUNCTION
>           foo
>           ARGS
>                x
>                y
>           BLOCK
>                +
>                     x
>                     1
>                +
>
>                     y
>                     1
>