[antlr-interest] Which approach for an Interpreter: Tree Grammar vs AST-Visitor

[bill punch]

Ultimately, generating byte code is one of the goals. However, given
that this is a class we are working our way up, climbing the ladder. My
approach has been to:

- first, just write some grammar rules (first project really just did
token counting). Basically expr grammar
- add control constructs (if, while, etc.) , and generate an AST (just
print it)
- now, walk the tree. I thought it would be good for them to manipulate
the tree by writing their own visitor. This was the question I asked,
whether to walk the AST directly (which I think is what I will do, easy
enough to implement) or to use a tree grammar.

The remaining steps are a good question. I was thinking:
- add scope ala the Pie example, with function definitions, stack of
scopes, etc.
- generate JVM byte code, probably use Jasmine.
- not sure for a last project. I was thinking about retargeting to a
different architecture, I'm working on that now.

I appreciate the feedback and, again think ANTLR and the book examples
make this a really great teaching tool. Also, this forum has been most
helpful. I've been following a number of the discussions and they have
been very helpful.

      >>>bill<<<


On 2/3/11 10:58 AM, Jim Idle wrote:
> I agree wholeheartedly with this. Trying you interpret the tree will tie
> everyone up in problems understanding the tree, but generating byte code
> by walking the tree in a grammar will help to visualize the tree and is
> easy to do (especially with a simple stack machine). Generating register
> based byte code will usually result in faster execution times but needs
> more thought. Also, these days I would consider using the asm framework to
> generate Java classes/byte code as this is easy to learn and shows a lot
> of things that will be practical in the real world. Knowing the visitor
> patterns for tree walking is obviously a base skill for this area and
> should be at least taught.
>
> Jim
>
>> -----Original Message-----
>> From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-
>> bounces at antlr.org] On Behalf Of Loring Craymer
>> Sent: Thursday, February 03, 2011 12:59 AM
>> To: bill punch; antlr-interest at antlr.org
>> Subject: Re: [antlr-interest] Which approach for an Interpreter: Tree
>> Grammar vs AST-Visitor
>>
>> The "best" way to implement an interpreter is to compile to byte code
>> and interpret the byte code--the interpreter is then a large case
>> statement surrounded by a loop which fetches the next byte to be
>> interpreted and that value is used as an index into the case statement.
>> That provides the code separation that you want and provides a good
>> lesson in designing a virtual machine.  As to the tree grammar or
>> visitor choice, consider doing both--possibly by dividing the class.
>> The tree grammar approach is superior in the general case, but an
>> important lesson for students to learn the value of tools as opposed to
>> automatically hand coding solutions--exposing students to alternatives
>> is good for them.
>>
>> --Loring
>>
>>
>> ----- Original Message ----
>>> From: bill punch <punch at cse.msu.edu>
>>> To: antlr-interest at antlr.org
>>> Sent: Wed, February 2, 2011 5:36:38 PM
>>> Subject: [antlr-interest] Which approach for an Interpreter: Tree
>> Grammar vs
>>> AST-Visitor
>>>
>>> I'm designing a project for my compiler class, and we are at the
>> stage
>>> of  building an interpreter for our grammar. Before going farther,
>> let me
>>> say  first that ANTLR is great and makes the whole process a lot
>> easier.
>>> However,  I'm converting the course and, being new to ANTLR, have a
>> few
>>> questions. Here  is one.
>>>
>>> I was using Pattern 25, the Pie language,  from LIP as a  guideline,
>> but
>>> I'm a little confused about the best approach. Pattern 25,  Pie,
>>> constructs an AST then uses hand-written code to do the visiting. I
>> like
>>> the approach, as more complex code can be embedded in the visitor
>> code.
>>> However, instead of writing my own visitor, I could have the
>> students
>>> write a tree grammar to visit the AST nodes. But it seems that I
>> would
>>> still be better off putting the exec type code in a separate  file.
>>>
>>> So would it be better to have an example like the Pie language use  a
>>> tree grammar or is the hand-written visitor code a better approach?
>> What
>>> are the pros and cons? Any help appreciated.
>>>
>>> --
>>>        >>>bill<<<
>>>
>>>
>>> List: http://www.antlr.org/mailman/listinfo/antlr-interest
>>> Unsubscribe:
>>> http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>>>
>>
>>
>>
>> List: http://www.antlr.org/mailman/listinfo/antlr-interest
>> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-
>> email-address
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address