Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > C parser yielding syntax tree data structure?

Reply
Thread Tools

C parser yielding syntax tree data structure?

 
 
(Jamie Andrews)
Guest
Posts: n/a
 
      04-08-2006
For a research project, we're looking for a reliable parser for C
that will take an ANSI C program and yield a tree representation of
the program (as a Java or C++ object). Of course a grammar e.g. in
jflex/jbison that will yield the same thing is fine too. We have been
able to find some grammars and parsers, of unknown reliability, that
don't yield a syntax tree; we want to avoid starting with a flaky
parser and/or adding the syntax tree code.

Preferably the tokens in the tree will contain information
on the line number and character number of the token, but if it
is sufficiently easy to add that code, then we can do that too.

Thanks for any info you can give.

--Jamie. (efil4dreN)
 
Reply With Quote
 
 
 
 
Rod Pemberton
Guest
Posts: n/a
 
      04-09-2006
"Jamie Andrews" <(E-Mail Removed)> wrote in message
> For a research project, we're looking for a reliable parser for C
> that will take an ANSI C program and yield a tree representation of
> the program (as a Java or C++ object). Of course a grammar e.g. in
> jflex/jbison that will yield the same thing is fine too. We have been
> able to find some grammars and parsers, of unknown reliability, that
> don't yield a syntax tree; we want to avoid starting with a flaky
> parser and/or adding the syntax tree code.
>
> Preferably the tokens in the tree will contain information
> on the line number and character number of the token, but if it
> is sufficiently easy to add that code, then we can do that too.


(Since this is cross-posted, for those on comp.lang.c: yes, I've
posted most of these links previously...)

I don't know which if any of these may fulfill your needs, but they may be
worth a look. I also noticed some of the links are bad as I posted, but
they may still help you to track them down.

CIL - C Intermediate Language - C to C transformation
http://manju.cs.berkeley.edu/cil/

WCC - A C Subset Compiler (DECUS ftp links now appear to be dead...sorry)
http://www.decus.org/libcatalog/desc...ml/v00281.html
ftp://ftp.encompassus.org/lib/

npath - C Source Complexity Measures
http://www.geonius.com/software/tools/npath.html

Check: A unit test framework for C
http://check.sourceforge.net/

CTool Library (call-graph generator, source transformations)
http://ctool.sourceforge.net/

Cproto automatically generates C function prototypes
http://cproto.sourceforge.net/

JSCPP - a C preprocessor + parser with special modes
http://www.die-schoens.de/prg/

CXREF C language cross referencing program
in volume1 of comp.sources.unix:
http://ftp.sunet.se/pub/usenet/ftp.u....sources.unix/

CSur Le projet Csur (in French)
An analyzer of code C to detect common program execution errors
http://www.lsv.ens-cachan.fr/~goubault/Csur/csur.html

Chico State Mini-C Compiler (CSMCC) is a student training load-and-go
compiler (incomplete, teaching tool)
http://www.ecst.csuchico.edu/~sameerg/compproj.html
http://www.ecst.csuchico.edu/~hilzer/csci250/proj/

Edward Willink's C++ grammars:
http://www.computing.surrey.ac.uk/research/dsrg/fog/
(some of the links have an extra text '/v' in them, just delete)

ISO C/C++ grammars version 1.2 (c-c++-grammars-1.2.tar.gz)
http://www.sigala.it/sandro/download.php

A C99 Parser, a recursive decent parser
http://www.mazumdar.demon.co.uk/c_parser.html

Ctags generates an index (or tag) file of language objects
http://ctags.sourceforge.net/

Cdecl English<->C translator for C declarations
cdecl in volume6 of comp.sources.unix:
cdecl2 in volume14 of comp.sources.unix:
http://ftp.sunet.se/pub/usenet/ftp.u....sources.unix/


Rod Pemberton
 
Reply With Quote
 
 
 
 
tmp123
Guest
Posts: n/a
 
      04-09-2006
(Jamie Andrews) wrote:
> For a research project, we're looking for a reliable parser for C
> that will take an ANSI C program and yield a tree representation of
> the program (as a Java or C++ object). ...


I've not done it, but, if I should solve the same problem, my first
step will be see if a C compiler can "dump" the tree in a readable
format. By example, gcc allows the options -fdump-tree-xxxx

It could work, ... or not.

 
Reply With Quote
 
Arndt Muehlenfeld
Guest
Posts: n/a
 
      04-13-2006
(Jamie Andrews) wrote:

> For a research project, we're looking for a reliable parser for C
> that will take an ANSI C program and yield a tree representation of
> the program (as a Java or C++ object). Of course a grammar e.g. in
> jflex/jbison that will yield the same thing is fine too. We have been
> able to find some grammars and parsers, of unknown reliability, that
> don't yield a syntax tree; we want to avoid starting with a flaky
> parser and/or adding the syntax tree code.


On my search for a C++ Parser that yields an AST, I tried two
parsers, that look fine for C, while not being able to parse all C++
constructs.

- C or C++ grammar for ANTLR (http://www.antlr.org/grammar/list)

- ELSA/Elkhound (http://www.cs.berkeley.edu/~smcpeak/elkhound/)

I am currently using ELSA, hoping the few remaining bugs
(resp. C++) are fixed some time.

Cheers,
Arndt
 
Reply With Quote
 
Ira Baxter
Guest
Posts: n/a
 
      04-13-2006
"Jamie Andrews" <(E-Mail Removed)> wrote in message
> For a research project, we're looking for a reliable parser for C
> that will take an ANSI C program and yield a tree representation of
> the program (as a Java or C++ object). ...


The DMS Software Reengineering Toolkit provides a full ANSI C front
end, with preprocessor, builds ASTs and symbol table information, and
provides facilities for constructing custom analyzers and
source-to-source transformations. See
http://www.semdesigns.com/Products/F...CFrontEnd.html



--
Ira Baxter, CTO
www.semanticdesigns.com

 
Reply With Quote
 
Paul E. Black
Guest
Posts: n/a
 
      04-14-2006
On Wednesday 12 April 2006 22:48, Arndt Muehlenfeld wrote:

> (Jamie Andrews) wrote:
>> For a research project, we're looking for a reliable parser for C
>> that will take an ANSI C program and yield a tree representation of
>> the program (as a Java or C++ object). Of course a grammar e.g. in
>> jflex/jbison that will yield the same thing is fine too. We have been
>> able to find some grammars and parsers, of unknown reliability, that
>> don't yield a syntax tree; we want to avoid starting with a flaky
>> parser and/or adding the syntax tree code.


Consider ROSE
http://www.llnl.gov/CASC/rose/

I understand that another version is due within a month or two.

-paul-
--
Paul E. Black ((E-Mail Removed))

 
Reply With Quote
 
Rod Pemberton
Guest
Posts: n/a
 
      04-16-2006
> > For a research project, we're looking for a reliable parser for C
> > that will take an ANSI C program and yield a tree representation of
> > the program (as a Java or C++ object). ...


> I don't know which if any of these may fulfill your needs, but they may be
> worth a look. I also noticed some of the links are bad as I posted, but
> they may still help you to track them down.
>
> CIL - C Intermediate Language - C to C transformation
> http://manju.cs.berkeley.edu/cil/
>
> WCC - A C Subset Compiler (DECUS ftp links now appear to be dead...sorry)
> http://www.decus.org/libcatalog/desc...ml/v00281.html
> ftp://ftp.encompassus.org/lib/
>
> npath - C Source Complexity Measures
> http://www.geonius.com/software/tools/npath.html
>
> Check: A unit test framework for C
> http://check.sourceforge.net/
>
> CTool Library (call-graph generator, source transformations)
> http://ctool.sourceforge.net/
>
> Cproto automatically generates C function prototypes
> http://cproto.sourceforge.net/
>
> JSCPP - a C preprocessor + parser with special modes
> http://www.die-schoens.de/prg/
>
> CXREF C language cross referencing program
> in volume1 of comp.sources.unix:
> http://ftp.sunet.se/pub/usenet/ftp.u....sources.unix/
>
> CSur Le projet Csur (in French)
> An analyzer of code C to detect common program execution errors
> http://www.lsv.ens-cachan.fr/~goubault/Csur/csur.html
>
> Chico State Mini-C Compiler (CSMCC) is a student training load-and-go
> compiler (incomplete, teaching tool)
> http://www.ecst.csuchico.edu/~sameerg/compproj.html
> http://www.ecst.csuchico.edu/~hilzer/csci250/proj/
>
> Edward Willink's C++ grammars:
> http://www.computing.surrey.ac.uk/research/dsrg/fog/
> (some of the links have an extra text '/v' in them, just delete)
>
> ISO C/C++ grammars version 1.2 (c-c++-grammars-1.2.tar.gz)
> http://www.sigala.it/sandro/download.php
>
> A C99 Parser, a recursive decent parser
> http://www.mazumdar.demon.co.uk/c_parser.html
>
> Ctags generates an index (or tag) file of language objects
> http://ctags.sourceforge.net/
>
> Cdecl English<->C translator for C declarations
> cdecl in volume6 of comp.sources.unix:
> cdecl2 in volume14 of comp.sources.unix:
> http://ftp.sunet.se/pub/usenet/ftp.u....sources.unix/


These additional links may be of some use. ASTRÉE appears to be great
but I don't see any code release...

CCURED memory safe C transformations (for CIL)
http://manju.cs.berkeley.edu/ccured/

C Code Checker (for CIL)
http://www.drugphish.ch/~jonny/cca.html

PScan Scan C files for format string overflows
http://www.striker.ottawa.on.ca/~aland/pscan/

CQUAL C checking through extended type qualifiers
http://www.cs.umd.edu/~jfoster/cqual/

Smatch - Source Matcher, C source checker for Linux Kernel
http://smatch.sourceforge.net/

SPLint Secure Programming Lint error detection
http://www.splint.org

BOON Buffer Overrun detectiON
http://www.cs.berkeley.edu/~daw/boon/

CZECH, project pedantic error detection
http://pedantic.sourceforge.net/

Flawfinder for C (in Python)
http://www.dwheeler.com/flawfinder/

ASTRÉE determines absence of runtime errors (in OCAML)
http://www.astree.ens.fr/
"In Nov. 2003, ASTRÉE was able to prove completely automatically the absence
of any RTE in the primary flight control software of the Airbus A340
fly-by-wire system, a program of 132,000 lines of C"


Rod Pemberton

 
Reply With Quote
 
robert.thorpe@antenova.com
Guest
Posts: n/a
 
      04-22-2006
(Jamie Andrews) wrote:
> For a research project, we're looking for a reliable parser for C
> that will take an ANSI C program and yield a tree representation of
> the program (as a Java or C++ object). Of course a grammar e.g. in
> jflex/jbison that will yield the same thing is fine too. We have been
> able to find some grammars and parsers, of unknown reliability, that
> don't yield a syntax tree; we want to avoid starting with a flaky
> parser and/or adding the syntax tree code.
>
> Preferably the tokens in the tree will contain information
> on the line number and character number of the token, but if it
> is sufficiently easy to add that code, then we can do that too.
>
> Thanks for any info you can give.


Linus Torvalds of Linux fame once wrote one of these called "sparse".
See http://freshmeat.net/projects/sparse/

I think the latest version is in
http://www.kernel.org/pub/scm/devel/sparse/ you need to use the "git"
version control system to download it unfortunately.

It doesn't give C++ or Java objects as an output. But, as you'll find
there is not much gained by treating a whole tree as an object, the
important thing is that it has a single root.

I have no idea how good this parser is, you'll have to find that out
for yourself. It's hard to tell how good any C parser is that doesn't
get heavy use, and hard enough to tell if a parser does get heavy use.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Execute block in context of yielding method's module Trans Ruby 6 11-13-2005 05:13 PM
Yielding a chain of values Talin Python 18 09-10-2005 04:46 AM
Idiomatic conversion of yielding block to array David Brady Ruby 22 09-04-2005 07:51 PM
Ideas for yielding and exception raising Calvin Spealman Python 3 06-08-2004 10:59 AM
B tree, B+ tree and B* tree Stub C Programming 3 11-12-2003 01:51 PM



Advertisments