Re: Re: new experimental C++ parser (branch)

David Abrahams wrote:

> Not being an expert with viewsvn (it looks like you can't diff a
> branch with the trunk?) I am having a hard time seeng exactly what
> you've been changing.  

Actually the parser code itself is really mostly a rewrite, so there
isn't much use in 'diff' to compare to the original code.

> From
> http://synopsis.fresco.org/viewsvn/synopsis-Synopsis/branches/CxxParserRewrite/src/Synopsis/Parser.cc?rev=1593&r1=1593&view=log
> it looks like you might be hand-coding an LR(2) recursive-descent
> parser.  I wonder if you considered generating your parser with
> something like bison?  It seems like there's a great deal of code
> involved in lookahead, etc., that could be handled by a parser
> generator, leaving you to tackle the really hard problems (name
> lookup, overload resolution, etc.)

Indeed, and there are a number of projects following this route
(elsa: http://www.cs.berkeley.edu/~smcpeak/elkhound/ and
  keystone: http://www.cs.clemson.edu/~malloy/projects/keystone/keystone.html,
  notably).

The problem with bison is that it assumes a context-free grammar,
which C++ clearly isn't (the problem with semantic predicates Gilles
mentions).

There were long discussions on the gcc mailing list when Mark Mitchell
started to rewrite the gcc parser to replace the original bison-based
parser: http://gcc.gnu.org/ml/gcc/2000-10/msg00573.html

>>The changes incure a number of modifications to the parse
>>tree structure, so at the moment there is probably not much that
>>will work in the new branch, beside the some simple developer tools
>>such as the display-ptree, display-symbols, and display-types applets.
>>
>>Obviously, any help to move this project forward would be more than
>>welcome.
> 
> 
> I might be interested, but I'd need to know more about your approach
> and its rationale first.

The internal representations which the parser generates are a parse tree,
a symbol table, and a type repository. The parse tree is an evolution of
the original OpenC++ code, where the nodes are lisp-like cons cells that
encode parts of the C++ syntax in terms of C++ types as well as topology
of child nodes. Terminal nodes ('atoms') refer to tokens in a source code
buffer, which is kept in memory during the parsing. It is thus possible
to make local modifications to the parse tree, and then rewrite the buffer
with local replacements to a file, making this whole process non-lossy.

Some (sparse) documentation of the internal representation can be found
in synopsis' developer's guide at http://synopsis.fresco.org/docs/DevGuide/cxx.html.

The original parser didn't have a symbol table (at least not during the parse
stage), and so couldn't distinguish class-name, template-name, etc.
Thus it used some heuristics to guess the correct production for a given
syntax. (It had a greedy 'name' production that interpreted e.g. 'Foo<A < B, C...'
as a template-id with 'A<B, C...' as a type argument, when 'A<B' was actually
a compile-time (boolean) non-type argument.)

The new parser constructs (and uses) a symbol table, so it can use real
'class-name', 'template-name', and 'type-name' productions with the corresponding
semantic predicats, based on this symbol table.
Like the gcc C++ parser, it uses tentative parsing to try a production,
rolling back and retrying an alternative one if it failed.

Regards,
		Stefan