Parsing Fortran

[Joe Krahn]

Steven Bosscher wrote:
 > On Friday 14 July 2006 22:52, Joe Krahn wrote:
 >
 >>Parsing Fortran is difficult. A hand-made parser, like the one developed
 >>by Andy V. can be fairly ugly.
 >
 >
 > Can be.  But generally Fortran parsers are hand-made parsers.
...
...
 > This sounds like just the normal lexing/parsing separation that one
 > would usually use for a language that can be tokenized at the lexical
 > level, and described with a context-free grammar.
 >
 > Fortran can't be tokenized without parser feedback.  Think for example
 > about "MODULE PROCEDURE".  This could be the declaration of a module
 > called "procedure", or it could be the keyword MODULEPROCEDURE, or it
 > could be the identifier "MODULEPROCEDURE".  There is no way to tell
 > without parser feedback.  Likewise, "DO I = 1,2" could be "DOI=1" or
 > "DO I=1" and there is no way to tell what it should be until you see
 > the comma.  The typical algorithm to work around this mess is Sale's
 > algorithm.
The ugnliness of space-insensitive parsing is limited to fixed format 
code. Fortunately, an algorithm like Sale's can do this with good 
success. So, I keep that as a separate pre-pass.

As for knowing whether an identifier is a keyword, that is were two 
layers of LALR parsing can help. Instead of a lot of hacking while 
parsing, you can do some entity-typing between the first and second pass.

 >
 > Context-free LALR(1) grammars for Fortran also do not exist, so you
 > can never write a complete Fortran parser with YACC.  The only parser
 > generator I know of that can _almost_ handle Fortran is Eli, which has
 > a Fortran grammar developed by Bill Clodius.  But this grammar is also
 > not complete, and it's got tricks too to couple the scanner and parser
 > so that feedback can be passed from one to the other.
 >
 > Your tool can probably handle all sane Fortran input, but not every
 > ugly little detail that the standard allows.  But for most jobs, being
 > able to handle e.g. only free form source with sanely named identifiers
 > is good enough.
 >
 > A "good" setup for parsing Fortran would be:
 > * some kind of pre-lexing with Sale's algorithm
 > * tokenizer
 > * recursive-descent parser with backtracking.
I was considering recursive-descent, but that approach gives a lot of 
wasted efforts, with the complexity of having to save entire parser 
states. It seems more complex than a bit of hand-made token hinting 
between two levels of LALR.

Maybe I'll just have to get it working better, and share the code to 
illustrate the idea.

Joe Krahn