Elsa: The Elkhound-based C/C++ Parser
Elsa is a C and C++ parser. It is based on the Elkhound parser generator. It lexes
and parses input C/C++ code into an abstract syntax tree. It does
some type checking, in the interest of elaborating the meaning of
constructs, but it does not (yet?) reject all invalid programs.
To download Elkhound and Elsa, see the
Elkhound distribution page.
- design.html: Document explaining various
aspects of the internal design of Elsa.
- tutorial.html: Introduction to using and
- cc.ast.html: The C/C++ abstract syntax tree
created by the parser.
- cc_type.html: The type representation
objects created by the type checker.
- cpp_er.html: C++ Entities and Relationships.
Provides an overview of C++ static semantics.
- serialization.txt: Explains the
XML serialization architecture, design decisions, how to use it, etc.
- declarator.html: Some details about how
declarators are parsed.
- convertibility.txt: A discussion
of the standard-convertibility relation, and its application to
operator overload resolution.
- lookup.txt: Documents some of my
interpretations of the lookup rules specified in the C++ standard,
and how they are implemented in Elsa.
- complex.txt: Brief overview of the
degree to which GNU/C99 complex/imaginary types are handled in Elsa.
- permissive.txt: Explanation of Elsa's
"permissive" mode, which is useful during automatic minimization.
- coloncolon.txt: Documents how an
ambiguity relating to the "::" operator is handled in cc.gr.
Elsa requires the following external software:
- elkhound, a GLR parser generator.
- ast, a system for making abstract syntax trees.
- smbase, a utility library.
a lexical analyzer generator.
$ make check
these options. You can also
look at the Makefile.
Parsing some sample (already preprocessed) input:
$ ./ccparse in/t0001.cc
The above command will parse and type check the given file. To
make it print the annotated, post-type-check AST, say
$ ./ccparse -tr printTypedAST in/t0001.cc
Additional -tr flags of interest:
The -tr flags can be passed separately, or strung together
separated by commas (e.g. "-tr env,disamb,printAST").
- printAST: Print the (possibly ambiguous) AST before type checking.
- printTypedAST: Print the AST after type checking.
- env: Print environment modifications as they happen.
- disamb: Print disambiguation activity.
- printHierarchies: Print inheritance hierarchies in
Interesting in that virtual inheritance is represented properly;
for example in/std/3.4.5.cc yields
- mustBeUnambiguous: After type checking, scan the AST to verify there
are no remaining ambiguities. If there are, abort.
- prettyPrint: Print out the AST as C++. This is still somewhat incomplete.
Some utilities for constructing fragments of the C++ AST.
Intermediate Lexer abstraction, built on top of yyFlexLexer and implementing
LexerInferface (thus fitting between flex and Elkhound), but not specific to
any set of tokens. Lexer (lexer.h) builds on top of this.
Representation of built-in operators, for use during operator
C/C++ Abstract Syntax Tree. This is the most important
file in the parser, since it defines the interface between
the parser and everything else that comes after it. It is
documented separately in cc.ast.html.
C/C++ parsing grammar. This is the second-most important file,
as it tells Elkhound how to parse the token stream. This grammar
is based on that in the C++ Standard document, but then modified
to remove unnecessary ambiguities and improve the grammar's ability
to extract structure.
Some auxilliary functions for cc.ast.
This module finds implicit function calls (like constructors) and creates
an explicit representation of them. An analysis can then ignore implicit
calls and just use the constructed explicit AST.
Env, the type checking environment. Fundamentally just a stack of
Scopes (cc_scope.h), plus some global
type checking state.
ErrorMsg, an object for representing type checking errors. For now
it's just an error string plus some metadata (like source location),
but I plan to evolve it to include more structured data like pointers
to (instead of just string representations of) the types involved in
This module defines a variety of enums relevant to parsing and
type checking C++, including enums for all the built-in types,
CCLang, a package of language dialect options. Setting flags in
this class tells the lexer, parser and type checker what language
options to support (e.g. C vs. C++).
cc_print is a module to pretty-print the AST using C++ syntax. It
extends the AST with entry points for printing.
A Scope is two maps: variables and types. The environment (cc_env.h) consists of a stack of them.
This is the type checker. It consists of an AST extension to
add type checking entry points and annotations, and an implementation
of all of those type checking functions. It's the most complicated
part of the parser.
This file lists all of the kinds of tokens the lexer recognizes. It's
designed to be extended simply by appending. The script
takes this as input, and generates
cc_tokens.ids. This last file is then
included into cc.gr (the others participate in
compilation in the obvious way).
This module defines the representation of types. They
form the core of the data manipulated by the type checker.
They are documented separately in
This module defines part of the parser context class, and assists
minimally with parsing.
This is type-checking extension that computes a statement-level
control flow graph for each function.
Constant-expression evaluator. Tries to predict the effect of
coercing data among different representation sizes, among other things.
This is the generic ambiguity resolution procedure. It typechecks
all of the alternatives, and selects the one that passes. Note that
there are other ambiguity resolution procedures in use, but this is
the one used in the absence of a specialized procedure.
Some routines for printing and modifying AST nodes that have
These files comprise the "gnu" extension module, though in truth this contains
extensions for both gcc and C99. See gnu.gr for a complete
list of the extensions implemented.
This module represents and computes implicit conversions, as defined
in sections 184.108.40.206 and 220.127.116.11 of the C++ standard.
Support routines, including ambiguity resolution, for the implicit-int
K&R extensions, in particular K&R function definitions and the
implicit-int rule. Daniel Wilkerson implemented most of this.
This module chops up a given C++ source file into tokens. It does
not do any preprocessing, so one must use an external preprocessor
Class to store the result set of a lookup.
This module contains the main() function of the parser. It's a simple
driver around the other modules. The nominal intent is that people who
want to use parts of Elsa in their own projects users will copy and modify
this file as necessary.
This is a very rudmentary name mangler. It is a somewhat arbitrary injective
map from Types to character strings, for use by the Oink linker imitator
(identifying declarations of the same entity from different translation units).
It does not implement any standard mangling scheme.
Type matching in the presence of type variables corresponding to template
parameters; sort of a generalized Type::equals.
Does overload resolution of a given candidate set.
This is a poorly-designed module intended to abstract some of the
functionality otherwise common to main()-providing modules. It
needs to die. alt.parssppt.die.die.die.
Sample application of Elsa, a "semantic grep". This is part
of the tutorial.
This is a simple module that can be used to attach object creation
serial numbers when an appropriate compile-time switch is used. This
is sometimes more convenient than working with virtual addresses,
"Structure printer"; work in progress.
Represents and computes standard conversions, as defined in section
4 of the C++ standard. See also
Hashtable-based map from StringRef to some pointer.
Data structures and algorithms for the template instantiation implementation.
Simple test driver program for the lexer.
Generic interface, plus a couple of implementations, for iterating
over sequences and examining their stored types.
Variable, a class for holding information about names in the
"variable" namespace. See
variable.h for a list of the kinds
of things that get represented with Variables. This module
is closely related to cc_type.
Module dependency diagram:
Or, in Postscript.
This script extracts pretty-printed C++ syntax from the other
debugging output produced by ccparse.
Build-time dependencies among auto-generated source files.
Script to verify that parsing then pretty-printing is idempotent.
Directory with testcases.
When preprocessing, add this directory to the preprocessor's
search path. It contains compiler-specific headers. Generally
I just use gcc's headers, but some of gcc's headers use syntax
that Elsa doesn't (yet?) understand, so this directory contains
Merge a base flex lexer with one or more extensions.
Used by the regression tester to test a given input file, plus
several variations obtained by un-commenting certain lines.
Minimize tmp.i exhibiting some specified error message.
Test for exhibition of a particular error; used by run-delta-loop.
Script to parse a file, making sure the parse is unambiguous.
This is a script that interprets the output of 'make' in order to
find C++ inputs to test with Elsa. I use it to make claims like
"Elsa can parse Mozilla".