|
From: | Randy W. Sims |
Subject: | Re: Help constructing tiny expression grammar |
Date: | Tue, 19 Oct 2004 07:16:47 -0400 |
User-agent: | Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8a4) Gecko/20040925 |
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/>
[Prev in Thread] | Current Thread | [Next in Thread] |