Re: Help constructing tiny expression grammar

[Randy W. Sims]

Laurence Finston wrote:
> On Tue, 19 Oct 2004, Randy W. Sims wrote:
>
>
> > I'm trying to figure out how to write a grammar for a tiny expression
> > language that checks for complicated module dependencies for Perl.
>
>
> Languages have a way of becoming non-tiny.
>
>
> > The def statements define macros that are to be substituted into the
> > main expression.
>
>
> If your macro expansion can be implemented as simple text
> replacement, as in the C preprocessor, I think you might
> find that it will be easier to read the macro definitions
> into `strings', if you're using C++, or an array of `chars',
> if you're using C, perform all of the expansion in an
> action, store the resulting string somewhere, and then let
> `yylex()' read it in for parsing when you call the macro.
> This technique can also be used for macros that take
> arguments.  The macro call will have to be parsed and
> special substrings in the macro string will have to be
> replaced with strings representing the arguments for a given
> call to that macro.
>
> This is how I plan to implement macros in GNU 3DLDF, but I
> haven't tried it out yet.  However, I do use the technique
> of reading input into strings for loops and conditionals, so
> I know that that works.

That sounds like a good approach.

I'm actually implementing this twice. The primary goal is to provide a 
Perl implementation for the Module::Build project[1] which is a to 
eventually replace ExtUtils::MakeMaker[2] as the primary tool for 
building and installing Perl modules. This, as may be obvious, is to 
provide a better way of expressing and managing complex requirements.

Anyway, in my perl implementation I was thinking that macros would be 
parsed into syntax trees and stored in the symbol table. Then, anywhere 
the macro is invoked, a copy of the already parsed tree would just be 
inserted into the main expression tree.

My second implementation is just an exercise for me to play with Bison 
and try to learn something new; to learn more about Bison its self and 
to learn more about parsing.

I wrote a naive prototype at <http://thepierianspring.org/perl/expr.pl>. 
This was just to give a starting point for discussion and design. It 
doesn't include macros; just parsing of simple logical expressions. The 
parser is extremely simplistic. One of the main reasons for my trying to 
write out the formal grammar at this point is to aid me in crafting a 
state transition table for the parser. I'm finding it extremely 
difficult to do by hand. Probably, mostly due to ignorance on my part.

I think crafting the table is the biggest hurdle for me in getting a 
workable perl implementation. I've got written what I think is a 
workable lexer <http://thepierianspring.org/perl/lex.pl>. (Note: in my 
perl lexer, I'm treating ranges as an object instead of breaking it down 
further; It seemed simpler.)

Lexing/Parsing is extremely cool. I've been scouring the net for 
resources, reading everything I can. Like I've said, I've also got an 
order in to Amazon, and I'm expecting arrival this week. As much as I've 
learned, I still feel like I'm stumbling through the dark.

Thanks for the feedback,

Randy.

1. <http://search.cpan.org/dist/Module-Build/>
2. <http://search.cpan.org/dist/ExtUtils-MakeMaker/>