mooigraph 8ee3407a65 sparse update 4 lat temu
..
Documentation 8c87a7d591 initial 4 lat temu
compat 8c87a7d591 initial 4 lat temu
gvpr 8c87a7d591 initial 4 lat temu
validation 8c87a7d591 initial 4 lat temu
.gitignore 8c87a7d591 initial 4 lat temu
FAQ 8c87a7d591 initial 4 lat temu
LICENSE 8c87a7d591 initial 4 lat temu
Makefile 8c87a7d591 initial 4 lat temu
README 8c87a7d591 initial 4 lat temu
allocate.c 8c87a7d591 initial 4 lat temu
allocate.h 8c87a7d591 initial 4 lat temu
ast-inspect.c 8c87a7d591 initial 4 lat temu
ast-inspect.h 8c87a7d591 initial 4 lat temu
ast-model.c 8c87a7d591 initial 4 lat temu
ast-model.h 8c87a7d591 initial 4 lat temu
ast-view.c 8c87a7d591 initial 4 lat temu
ast-view.h 8c87a7d591 initial 4 lat temu
bitmap.h 8c87a7d591 initial 4 lat temu
bits.h 8c87a7d591 initial 4 lat temu
builtin.c 8c87a7d591 initial 4 lat temu
builtin.h 8c87a7d591 initial 4 lat temu
c2xml.c 8c87a7d591 initial 4 lat temu
cgcc 8c87a7d591 initial 4 lat temu
cgcc.1 8c87a7d591 initial 4 lat temu
char.c 8c87a7d591 initial 4 lat temu
char.h 8c87a7d591 initial 4 lat temu
compat-bsd.c 8c87a7d591 initial 4 lat temu
compat-cygwin.c 8c87a7d591 initial 4 lat temu
compat-linux.c 8c87a7d591 initial 4 lat temu
compat-mingw.c 8c87a7d591 initial 4 lat temu
compat-solaris.c 8c87a7d591 initial 4 lat temu
compat.h 8c87a7d591 initial 4 lat temu
compile-i386.c 8c87a7d591 initial 4 lat temu
compile.c 8c87a7d591 initial 4 lat temu
compile.h 8c87a7d591 initial 4 lat temu
cse.c 8c87a7d591 initial 4 lat temu
cse.h 8c87a7d591 initial 4 lat temu
ctags.c 8c87a7d591 initial 4 lat temu
dissect.c 8c87a7d591 initial 4 lat temu
dissect.h 8c87a7d591 initial 4 lat temu
dominate.c 8c87a7d591 initial 4 lat temu
dominate.h 8c87a7d591 initial 4 lat temu
evaluate.c 8c87a7d591 initial 4 lat temu
evaluate.h 8c87a7d591 initial 4 lat temu
example.c 8c87a7d591 initial 4 lat temu
expand.c 8c87a7d591 initial 4 lat temu
expand.h 8c87a7d591 initial 4 lat temu
expression.c 8c87a7d591 initial 4 lat temu
expression.h 8c87a7d591 initial 4 lat temu
flow.c 8c87a7d591 initial 4 lat temu
flow.h 8c87a7d591 initial 4 lat temu
flowgraph.c 8c87a7d591 initial 4 lat temu
flowgraph.h 8c87a7d591 initial 4 lat temu
gcc-attr-list.h 8c87a7d591 initial 4 lat temu
gdbhelpers 8c87a7d591 initial 4 lat temu
graph.c 8c87a7d591 initial 4 lat temu
ident-list.h 8c87a7d591 initial 4 lat temu
inline.c 8c87a7d591 initial 4 lat temu
ir.c 8c87a7d591 initial 4 lat temu
ir.h 8c87a7d591 initial 4 lat temu
lib.c 8c87a7d591 initial 4 lat temu
lib.h 8c87a7d591 initial 4 lat temu
linearize.c 0503fa5e33 sparse bug 4 lat temu
linearize.h 8c87a7d591 initial 4 lat temu
liveness.c 8c87a7d591 initial 4 lat temu
liveness.h 8c87a7d591 initial 4 lat temu
machine.h 8c87a7d591 initial 4 lat temu
memops.c 8c87a7d591 initial 4 lat temu
obfuscate.c 8c87a7d591 initial 4 lat temu
opcode.c 8c87a7d591 initial 4 lat temu
opcode.def 8c87a7d591 initial 4 lat temu
opcode.h 8c87a7d591 initial 4 lat temu
optimize.c 8c87a7d591 initial 4 lat temu
optimize.h 8c87a7d591 initial 4 lat temu
options.c 8c87a7d591 initial 4 lat temu
options.h 8c87a7d591 initial 4 lat temu
parse.c 8c87a7d591 initial 4 lat temu
parse.dtd 8c87a7d591 initial 4 lat temu
parse.h 8c87a7d591 initial 4 lat temu
pre-process.c 8c87a7d591 initial 4 lat temu
predefine.c 8c87a7d591 initial 4 lat temu
ptrlist.c 8c87a7d591 initial 4 lat temu
ptrlist.h 8c87a7d591 initial 4 lat temu
ptrmap.c 8c87a7d591 initial 4 lat temu
ptrmap.h 8c87a7d591 initial 4 lat temu
scope.c 8c87a7d591 initial 4 lat temu
scope.h 8c87a7d591 initial 4 lat temu
semind.1 8c87a7d591 initial 4 lat temu
semind.c 8c87a7d591 initial 4 lat temu
show-parse.c 8c87a7d591 initial 4 lat temu
simplify.c 8c87a7d591 initial 4 lat temu
sort.c 8c87a7d591 initial 4 lat temu
sparse-llvm-dis 8c87a7d591 initial 4 lat temu
sparse-llvm.c 8c87a7d591 initial 4 lat temu
sparse.1 8c87a7d591 initial 4 lat temu
sparse.c 8c87a7d591 initial 4 lat temu
sparsec 8c87a7d591 initial 4 lat temu
sparsei 8c87a7d591 initial 4 lat temu
ssa.c 8c87a7d591 initial 4 lat temu
ssa.h 8c87a7d591 initial 4 lat temu
sset.c 8c87a7d591 initial 4 lat temu
sset.h 8c87a7d591 initial 4 lat temu
stats.c 8c87a7d591 initial 4 lat temu
storage.c 8c87a7d591 initial 4 lat temu
storage.h 8c87a7d591 initial 4 lat temu
symbol.c 8c87a7d591 initial 4 lat temu
symbol.h 8ee3407a65 sparse update 4 lat temu
target-alpha.c 8c87a7d591 initial 4 lat temu
target-arm.c 8c87a7d591 initial 4 lat temu
target-arm64.c 8c87a7d591 initial 4 lat temu
target-bfin.c 8c87a7d591 initial 4 lat temu
target-default.c 8c87a7d591 initial 4 lat temu
target-h8300.c 8c87a7d591 initial 4 lat temu
target-m68k.c 8c87a7d591 initial 4 lat temu
target-microblaze.c 8c87a7d591 initial 4 lat temu
target-mips.c 8c87a7d591 initial 4 lat temu
target-nds32.c 8c87a7d591 initial 4 lat temu
target-nios2.c 8c87a7d591 initial 4 lat temu
target-openrisc.c 8c87a7d591 initial 4 lat temu
target-ppc.c 8c87a7d591 initial 4 lat temu
target-riscv.c 8c87a7d591 initial 4 lat temu
target-s390.c 8c87a7d591 initial 4 lat temu
target-sh.c 8c87a7d591 initial 4 lat temu
target-sparc.c 8c87a7d591 initial 4 lat temu
target-x86.c 8c87a7d591 initial 4 lat temu
target-xtensa.c 8c87a7d591 initial 4 lat temu
target.c 8c87a7d591 initial 4 lat temu
target.h 8c87a7d591 initial 4 lat temu
test-dissect.c 8c87a7d591 initial 4 lat temu
test-inspect.c 8c87a7d591 initial 4 lat temu
test-lexing.c 8c87a7d591 initial 4 lat temu
test-linearize.c 8c87a7d591 initial 4 lat temu
test-parsing.c 8c87a7d591 initial 4 lat temu
test-show-type.c 8c87a7d591 initial 4 lat temu
test-sort.c 8c87a7d591 initial 4 lat temu
test-unssa.c 8c87a7d591 initial 4 lat temu
token.h 8c87a7d591 initial 4 lat temu
tokenize.c 8c87a7d591 initial 4 lat temu
unssa.c 8c87a7d591 initial 4 lat temu
utils.c 8c87a7d591 initial 4 lat temu
utils.h 8c87a7d591 initial 4 lat temu

README


sparse (spärs), adj,., spars-er, spars-est.
1. thinly scattered or distributed; "a sparse population"
2. thin; not thick or dense: "sparse hair"
3. scanty; meager.
4. semantic parse
[ from Latin: spars(us) scattered, past participle of
spargere 'to sparge' ]

Antonym: abundant

Sparse is a semantic parser of source files: it's neither a compiler
(although it could be used as a front-end for one) nor is it a
preprocessor (although it contains as a part of it a preprocessing
phase).

It is meant to be a small - and simple - library. Scanty and meager,
and partly because of that easy to use. It has one mission in life:
create a semantic parse tree for some arbitrary user for further
analysis. It's not a tokenizer, nor is it some generic context-free
parser. In fact, context (semantics) is what it's all about - figuring
out not just what the grouping of tokens are, but what the _types_ are
that the grouping implies.

And no, it doesn't use lex and yacc (or flex and bison). In my personal
opinion, the result of using lex/yacc tends to end up just having to
fight the assumptions the tools make.

The parsing is done in five phases:

- full-file tokenization
- pre-processing (which can cause another tokenization phase of another
file)
- semantic parsing.
- lazy type evaluation
- inline function expansion and tree simplification

Note the "full file" part. Partly for efficiency, but mostly for ease of
use, there are no "partial results". The library completely parses one
whole source file, and builds up the _complete_ parse tree in memory.

Also note the "lazy" in the type evaluation. The semantic parsing
itself will know which symbols are typedefines (required for parsing C
correctly), but it will not have calculated what the details of the
different types are. That will be done only on demand, as the back-end
requires the information.

This means that a user of the library will literally just need to do

struct string_list *filelist = NULL;
char *file;

action(sparse_initialize(argc, argv, filelist));

FOR_EACH_PTR(filelist, file) {
action(sparse(file));
} END_FOR_EACH_PTR(file);

and he is now done - having a full C parse of the file he opened. The
library doesn't need any more setup, and once done does not impose any
more requirements. The user is free to do whatever he wants with the
parse tree that got built up, and needs not worry about the library ever
again. There is no extra state, there are no parser callbacks, there is
only the parse tree that is described by the header files. The action
funtion takes a pointer to a symbol_list and does whatever it likes with it.

The library also contains (as an example user) a few clients that do the
preprocessing, parsing and type evaluation and just print out the
results. These clients were done to verify and debug the library, and
also as trivial examples of what you can do with the parse tree once it
is formed, so that users can see how the tree is organized.