[antlr-interest] how do you make Antlr work with a recursively changing input stream

Wed Jun 30 12:40:44 PDT 2010

Thanks Mark.  I appreciate the response.  However, I'm not sure if I've made myself quite clear in what I'm trying to do.  I read the links you gave me, and I think I understand at least the basics of using a symbol table.  I implemented a rudimentary C compiler in college using flex/bison, but that was 12 years ago.  Plenty long enough for me to forget the details. 

However, unless I can either call Antlr recursively (is this possible?), or change the stream that Antlr is parsing as I find substitutions, then I don't see how a symbol table will help me.  I get the feeling that I'm missing something completely obvious.  I'm sure I'm not the only person who has ever tried to do what I'm trying to do.

My problem isn't forward references in this case.  My problem is that the data stream is discovered dynamically by following a table of substitutions.  The tables are similar to a relational database.

I have a hand-coded parser using regular expressions that I've written that handles all of this, but it's somewhat hard to maintain (even for me the person who wrote it).

I would like Antlr to both tell me whether or not I need to substitute at any given node based on a grammar and then recurse over the substituted data and finally parse the leaf nodes using the grammar.

Here's a slightly more complex example than I gave before:

xml = Parse(Person);  /* I pass in the table to start with - that's it.  The original stream only contains the Person table representation.  The rest is determined dynamically. */       

/* Here's how the tables might be layed out. */

Person (table name)
_Identifier_       {Name}        {Address}
Person1          15555            15555       
Person2          14444            14444

Name (table name)
_Identifier_      Salutation    FirstName    LastName
15555               Mr             Joe         Blow
14444               Mrs            Jane        Doe

Address (table name)
_Identifier_     Street      City        State      {Neighborhood}
15555            Main      Bozeman        MT           Stirling
14444           Second    Los Angeles     CA           Brentwood

Neighborhood (table name)
_Identifier_           Name                 YearlyDues
Stirling            Stirling Meadows          400
Brentwood           Brentwood Estates         4000

Here's what the XML would look like - remember I only passed in the Person table representation as the original stream, the rest was determined dynamically as I look at each node and decide whether or not to perform a substitution.  Currently these substitutions are designated with the {} around the table's column header.

<Person1>
  <Name>
    <Salutation>Mr</Salutation>
    <FirstName>Joe</FirstName>
    <LastName>Blow</LastName>
  </Name>
  <Address>
    <Street>Main</Street>
    <City>Bozeman</City>
    <State>MT</State>
    <Neighborhood>
      <Name>Stirling Meadows</Name>
      <YearlyDues>400</YearlyDues>
    </Neighborhood>
  </Address>
</Person1>
<Person2>
  <Name>
    <Salutation>Mrs</Salutation>
    <FirstName>Jane</FirstName>
    <LastName>Doe</LastName>
  </Name>
  <Address>
    <Street>Second</Street>
    <City>Los Angeles</City>
    <State>CA</State>
    <Neighborhood>
      <Name>Brentwood Estates</Name>
      <YearlyDues>4000</YearlyDues>
    </Neighborhood>
  </Address>
</Person2>

I'm sorry if this is too long.  Maybe there is something obvious I am missing here.  If you still think a symbol table is warranted, could you please write me some psuedocode that shows how I can get Antlr to parse the dynamic data recursively.

Thanks!

         -- alex

--- On Tue, 6/29/10, Mark Wright <markwright at internode.on.net> wrote:

From: Mark Wright <markwright at internode.on.net>
Subject: Re: [antlr-interest] how do you make Antlr work with a recursively changing input stream
To: antlr-interest at antlr.org
Date: Tuesday, June 29, 2010, 5:29 PM

On Tue, Jun 29, 2010 at 03:18:55PM -0700, Alex McMains wrote:
> Hi all,
> 
> I'm new to Antlr.  I've bought and read portions of the Antlr book,
> and I've read dozens of postings and tutorials, but I still can't
> see how to do deal with a recursively changing input stream in
> Antlr.  Do I somehow use TokenRewriteStream, or am I missing
> something?

Hi Alex,

Yes, you are missing something, the Antlr book does not say much about
symbol tables or type systems.

For simple type systems, it is probably easier to just use the
approach which is called a "symbol table" in old school books
on compiler construction.  A really good description of this
approach is in chapter 7 of the book Language Implementation Patterns
by Terence Parr.  An introduction to this approach is at:

http://www.antlr.org/wiki/display/CS652/Symbol+tables

You obviously need to implement forward references scopes.

Mainly for the mailing list archive, I would just like to say that I
find this symbol table approach seems difficult to use for
complex type systems.  For complex type systems the approach I
recommend is described in the book "Types and Programming Languages"
by Benjamin Pierce, the online book "Software Foundations", see the
course:

http://www.seas.upenn.edu/~cis500/current/index.html

and the book "Certified Programming with Dependent Types" by
Adam Chlipala:

http://adam.chlipala.net/cpdt/

Regards, Mark

> Here's the situation:
> 
> I start with an input stream.  As I move through the input I will
> either encounter something that can be parsed directly, or I will
> encounter something that tells me to go to a table and substitute an
> entire row of the table at the node where I currently am.  This can
> continue to happen recursively since each field from the substituted
> row can again call for a substitution. 
>  
> Here's an example:
>  
> Person table:
>  Identifier     Name   {Address}
> Person1        Jon       Jon's Address
>  
> Address table:
>  Identifier      HouseNumber  StreetName
> Jon's Address   3477               Blue Lane
>  
> The {} around Address says to name the current node "Address" and
> substitute the current value for whatever is at "Jon's Address" in
> the Address table.
>  
> Eventually this will become XML that would look like:
>  
> <Person>
>     <Name>Jon</Name>
>     <Address>
>          <HouseNumber>3477</HouseNumber>
>          <StreetName>Blue Lane</StreetName>
>      </Address>
> </Person>
>  
> Any ideas would be appreciated.
>  
> Thanks.
>  
>        -- alex
> 
> 
>       
> 
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
> 

-----Inline Attachment Follows-----

List: http://www.antlr.org/mailman/listinfo/antlr-interest
Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address