Re: Parsers for Programming Languages.

[Matthew Estes <address@hidden>]

At 11:35 AM 9/17/2003 -0400, Michael St . Hippolyte wrote:
>On 2003.09.17 00:35 Matthew Estes wrote:
> >          I'm also curious if there's still useful work(for programming
> > languages application in particular) in the field of parsing. I would
> > assume so, and that this would be a good direction(hint, I'm a graduate
> > student looking at thesis topics) to work in.
>
>This has probably already been done, but one idea I'd love to see
>someone research is analyzing arbitrary programs as grammars.  If you
>take a functional program which generates structured output, you can
>think of the functions in the program as productions, and the output
>statements as terminals for the language defined by all possible outputs
>of the program.  Assuming some reasonable constraints on such a program
>and its output, how practical is it to generate a parser for the program's
>output by analyzing the program as a grammar?   I think some work along
>these lines has been done specifically on compilers (grammar recovery),
>but the more general case is interesting too -- there are an awful lot of
>files out there in formats whose only grammatical representation are the
>programs which generated them...
         This sounds like the book "Grammars for Programming Languages" by 
Cleaveland. In it, they use a van Wijngaarden grammar to COMPLETELY specify 
all the semantics of a programming language. The act of "parsing" the 
language performs the computation. Unfortunately, I'm quite sure that it 
takes the FULL power of a 2 level grammar, and so while it is possible to 
specify ALL aspects of computation via the grammar, at that point, many 
aspects would probably be undecidable, and a parser that could completely 
accept every program would be able to solve the Halting Problem.
         I actually really enjoyed the book though, its really neat as they 
start with a context-free description of a language along with English 
"Semantics" and then go through about 4 stages to consume everything into 
the grammar. Its pretty old(1977), but my school's library had it, so it 
can't be too hard to find.
         Maybe I misunderstood your question though. As someone has pointed 
out to me, it may not be best to "consume" some of the static 
semantics(like typing) into the formal grammar. I still would like to think 
a decent parser for context-sensitive 2-level grammars would be a good 
thing to have, and it seems to me like very few have attempted it. I guess 
I'm trying to decide if I'm wasting my time.

                                                 Matt Estes