Groups | Search | Server Info | Login | Register

Groups > comp.compilers > #120

Re: Maintaining scope while parsing C with a YACC grammar

Show all headers | View raw

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
> No, sorry.  I'd be interested to hear if anybody built a C parser that
> didn't use any feedback into the parser from a symbol table to deal
> with the typedef issue.

Our DMS Software Reengineering Toolkit does exactly this.
(www.semanticdesigns.com/Products/DMS/DMSToolkit.html).

We use GLR parsing machinery, which means we can decouple parsing from
semantic hackery.  The grammar for this is just as you'd expect, with
productions for expression statements and declarations.  The GLR
parser builds an ambiguous tree with maximal sharing of the subtrees.
At the end of the parse, you have a parse DAG with ambiguity nodes.

Name resolution is handled by an attribute grammar evaluator with some
special effects.  The AGE is pretty general and we use it for lots of
tree-structured analyses; this is pretty nice for nested scopes,
building control flow graphs, etc.  For name and type resolution, the
attributes passed up and down the tree are, as you might expect,
reference to symbol scopes and/or type declarations.  The special
effects of interest here are the ability to declare an aborted
attribute evaluation at any tree node; this will kill off any
dependent attribute computation and delete the offending tree node and
its otherwise-unreferenced children (remember, there may be sharing,
so a node may have more than one reference).  What we do to handle the
T* x issue is check for consistency of the types; if T is a type, then
T*x as an expression makes no sense and that part of the AGE dies off.
If T is numeric type, then T* x makes no sense as a declartion, and
that part of the AGE dies off.  Destroying the "bad" subtree removes
the incorrect parse from the tree, and thus the final tree has no
ambiguity nodes and a completed name/type resoultion with symbol
tables that is correct.  The C parser is question has been used in
anger to carry out static analysis of software systems with usome
19,000 compilation units.  We think it is quite robust.

This scheme works really nicely for C, C++, COBOL and other languages,
and it means we can build grammars without worrying about semantic
constraints.  The grammars are thus nice and clean, and the AGEs are
pretty clean too because of the separation of concerns.

You can do this by mixing symbol lookup and parsing, but then it
generally gets a lot messier to build both.

--
Ira Baxter, CTO
www.semanticdesigns.com

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Maintaining scope while parsing C with a YACC grammar eliben <eliben@gmail.com> - 2011-04-25 05:14 -0700
  Re: Maintaining scope while parsing C with a YACC grammar Robert A Duff <bobduff@shell01.TheWorld.com> - 2011-04-26 12:22 -0400
    Re: Maintaining scope while parsing C with a YACC grammar Robert A Duff <bobduff@shell01.TheWorld.com> - 2011-04-26 14:08 -0400
    Re: Maintaining scope while parsing C with a YACC grammar eliben <eliben@gmail.com> - 2011-04-28 23:20 -0700
      Re: Maintaining scope while parsing C with a YACC grammar Robert A Duff <bobduff@shell01.TheWorld.com> - 2011-05-02 20:19 -0400
        Re: Maintaining scope while parsing C with a YACC grammar "Ira Baxter" <idbaxter@semdesigns.com> - 2011-05-13 17:46 -0500
        Maintaining scope while parsing C with a Yacc grammar Chris F Clark <cfc@shell01.TheWorld.com> - 2011-06-12 20:43 -0400
      Re: Maintaining scope while parsing C with a YACC grammar torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-05-03 09:51 +0200
  Re: Maintaining scope while parsing C with a YACC grammar Paul B Mann <paul@paulbmann.com> - 2011-05-06 10:43 -0700

csiph-web