TOC
- Basic Datatypes / Utilities: !UNames, Attributes, Position, Idents, Errors
- Monadic Parsing: StateTrans , StateBase, CIO, State
- C-specific Infrastructure: CAST, CTokens, CParserMonad, NameSpaces, CAttrs, CBuiltin
- Lexer/Parser/PP: CLexer, CParser, CPretty
- Other: CTrav
UNames
--- DESCRIPTION --------------------------------------------------------------- -- -- Generates unqiue names according to a method of L. Augustsson, M. Rittri -- & D. Synek ``Functional pearl: On generating unique names'', Journal of -- Functional Programming 4(1), pp 117-123, 1994. -- -- WARNING: DON'T tinker with the implementation! It uses UNSAFE low-level -- operations! -- --- DOCU ---------------------------------------------------------------------- -- -- language: Haskell 98 -- -- * This module provides an ordering relation on names (e.g., for using -- `FiniteMaps'), but no assumption maybe made on the order in which names -- are generated from the name space. Furthermore, names are instances of -- `Ix' to allow to use them as indicies. -- -- * A supply should be used *at most* once to *either* split it or extract a -- stream of names. A supply used repeatedly will always generate the same -- set of names (otherwise, the whole thing wouldn't be referential -- transparent). -- -- * If you ignored the warning below, looked at the implementation, and lost -- faith, consider that laziness means call-by-need *and* sharing, and that -- sharing is realized by updating evaluated thunks. -- -- * ATTENTION: No clever CSE or unnecessary argument elimination may be -- applied to the function `names'!
Attributes
--- DESCRIPTION --------------------------------------------------------------- -- -- This module provides an abstract notion of attributes (in the sense of -- compiler construction). The collection of attributes that is attached to a -- single node of the structure tree is referenced via an attributes -- identifier. This is basically a reference into so-called attribute tables, -- which manage attributes of one type and may use different representations. -- There is also a position attribute managed via the attribute identifier -- without needing a further table (it is already fixed on construction of -- the structure tree). -- -- The `Attributed' class is based on a suggestion from Roman Lechtchinsky. -- --- DOCU ---------------------------------------------------------------------- -- -- language: Haskell 98 -- -- * Attribute identifiers are generated during parsing and whenever new -- structure tree elements, possibly due to transformations, are generated. -- -- * New attributes can be added by simply providing a new attribute table -- indexed by the attribute identifiers. Thus, adding or discarding an -- attribute does not involve any change in the structure tree. -- -- * Consecutive sequences of names are used as attribute identifiers to -- facilitate the use of arrays for attributes that are fixed; speeds up -- read access. (See also TODO.) -- -- * Each attribute table can simultaneously provide melted (updatable) and -- frozen (non-updatable) attributes. It also allows to dynamically grow the -- table, i.e., cover a wider range of attribute identifiers. -- -- * There is a variant merely providing a position, which is used for -- internal identifiers and such. -- -- * `StdAttr' provides standard undefined and don't care variants for -- attribute values. -- --- TODO ---------------------------------------------------------------------- -- -- * When there are sparse attribute tables that we want to freeze (and they -- will occur sooner or later), then introduce a third variant of tables -- realized via hash table---depending on the type of attribute table, we -- may even allow them to be soft. -- -- NOTE: Currently, if assertions are switched on, on freezing a table, its -- density is calculate and, if it is below 33%, an internal error is -- raised (only if there are more than 1000 entries in the table). -- -- * check whether it would increase the performance significantly if we use -- a mixed finite map/array representation for soft tables (all attributes -- defined before the last `soften' could be held in the array, changing -- an attribute just means to update it in the FM; i.e., the FM entries take -- precedence over the array entries) --
Position
--- DESCRIPTION --------------------------------------------------------------- -- -- This module provides some definitions used throughout all modules of a -- compiler. -- --- DOCU ---------------------------------------------------------------------- -- -- language: Haskell 98 -- -- * May not import anything apart from `Config'.
Idents
--- DESCRIPTION --------------------------------------------------------------- -- -- This module provides an abstract notion of identifiers. -- --- DOCU ---------------------------------------------------------------------- -- -- language: Haskell 98 -- -- * We speed up the equality test between identifiers by keeping a hash -- -- * The ordering relation on identifiers is also based on the hash and, -- hence, does *not* follow the alphanumerical ordering of the lexemes of -- the identifiers. Instead, it provides a fast ordering when identifiers -- are used as keys in a `FiniteMap'. -- -- * Attributes may be associated to identifiers, except with `OnlyPos' -- identifiers, which have a position as their only attribute (they do not -- carry an attribute identifier, which can be used to index attribute -- tables). -- --- TODO ---------------------------------------------------------------------- -- -- * Hashing is not 8bit clean. --
Errors
--- DESCRIPTION --------------------------------------------------------------- -- -- This modules exports some auxilliary routines for error handling. -- --- DOCU ---------------------------------------------------------------------- -- -- language: Haskell 98 -- -- * the single lines of error messages shouldn't be to long as file name -- and position are prepended at each line -- --- TODO ---------------------------------------------------------------------- --
StateTrans
--- DESCRIPTION --------------------------------------------------------------- -- -- This module provides basic support for the use of state transformers. -- The state transformer is build around the `IO' monad to allow the -- manipulation of external state. It encapsulated two separate states with -- the intention to use the first one for the omnipresent compiler state -- consisting of the accumulated error messages etc. and to use the second as -- a generic component that can be used in different ways by the different -- phases of the compiler. -- -- The module also supports the use of exceptions and fatal errors. -- --- DOCU ---------------------------------------------------------------------- -- -- language: Haskell 98 -- -- * We explicitly do not use any names for the monad types and functions -- that are used by either Haskell's `IO' monad or GHC's `ST' monad. Since -- Haskell 1.4, `STB' is an instance of the `Monad' constructor class. -- -- * To integrate the Haskell prelude `IO' monad into our `STB' monad we use -- the technique from ``Composing monads'' by Mark P. Jones and Luc -- Duponcheel (Report YALEU/DCS/RR-1004) from 1993, Section 8. -- -- * The use of GHC's inplace-update goodies within monads of kind `STB' is -- possible, bacause `IO' is based on `ST' in the GHC. -- -- * In the following, we call the two kinds of state managed by the `STB' the -- base state (the omnipresent state of the compiler) and generic state. -- -- * `STB' is a newtype, which requires careful wrapping and unwrapping of its -- values in the following definitions. -- --- TODO ---------------------------------------------------------------------- -- -- * with constructor classes, the state transformer business can be made -- more elegant (they weren't around when this module was initially written) -- -- * it would be possible to maintain the already applied changes to the base -- and generic state even in the case of a fatal error, when in `listIO' -- every IO operation is encapsulated into a handler that transforms IO -- errors into exceptions --
StateBase
--- DESCRIPTION --------------------------------------------------------------- -- -- This module provides basic types and services used to realize the state -- management of the compiler. -- --- DOCU ---------------------------------------------------------------------- -- -- language: Haskell 98 -- -- * The monad `PreCST' is an instance of `STB' where the base state is fixed. -- However, the base state itself is parametrized by an extra state -- component that can be instantiated by the compiler that uses the toolkit -- (to store information like compiler switches) -- this is the reason for -- adding the prefix `Pre'. -- -- * The module exports the details of the `BaseState' etc as they have to be -- know by `State'. The latter ensures the necessary abstraction for -- modules that do not belong to the state management. -- -- * Due to this module, the state management modules can share internal -- information about the data types hidden to the rest of the system. -- -- * The following state components are maintained: -- -- + errorsBS (type `ErrorState') -- keeps track of raised errors -- + namesBS (type `NameSupply') -- provides unique names -- + extraBS (generic type) -- extra compiler-dependent state -- information, e.g., for compiler -- switches --
CIO
--- DESCRIPTION --------------------------------------------------------------- -- -- This module lifts the Haskell I/O facilities into `STB' and provides some -- useful extensions. -- --- DOCU ---------------------------------------------------------------------- -- -- language: Haskell 98 -- -- * the usage of the `...CIO' functions is exactly as that of the -- corresponding `...' functions from the Haskell 98 prelude and library -- -- * error handling can be found in the module `StateTrans' and `State' -- -- * Also reexports constants, such as `stderr', and data types of `IO' to -- avoid explicit imports of `IO' in the rest of the compiler. --
State
--- DESCRIPTION --------------------------------------------------------------- -- -- This module forms the interface to the state base of the compiler. It is -- used by all modules that are not directly involved in implementing the -- state base. It provides a state transformer that is capable of doing I/O -- and provides facilities such as error handling and compiler switch -- management. -- --- DOCU ---------------------------------------------------------------------- -- -- language: Haskell 98 -- -- * The monad `PreCST' is reexported abstractly. -- -- * Errors are dumped to `stdout' to facilitate communication with other -- processes (see `Interact').
CAST
--- DESCRIPTION --------------------------------------------------------------- -- -- Abstract syntax of C header files. -- --- DOCU ---------------------------------------------------------------------- -- -- language: Haskell 98 -- -- The tree structure corresponds to the grammar in Appendix A of K&R. This -- abstract syntax simplifies the concrete syntax by merging similar concrete -- constructs into a single type of abstract tree structure: declarations are -- merged with structure declarations, parameter declarations and type names, -- and declarators are merged with abstract declarators. -- -- With K&R we refer to ``The C Programming Language'', second edition, Brain -- W. Kernighan and Dennis M. Ritchie, Prentice Hall, 1988. This module -- supports the C99 `restrict' extension -- <http://www.lysator.liu.se/c/restrict.html>, `inline' functions, and also -- the GNU C `alignof' extension.
CTokens
--- DESCRIPTION --------------------------------------------------------------- -- -- C Tokens for the C lexer. --
CParserMonad
--- DESCRIPTION --------------------------------------------------------------- -- -- Monad for the C lexer and parser -- --- DOCU ---------------------------------------------------------------------- -- -- language: Haskell 98 -- -- This monad has to be usable with Alex and Happy. Some things in it are -- dictated by that, eg having to be able to remember the last token. -- -- The monad also provides a unique name supply (via the Names module) -- -- For parsing C we have to maintain a set of identifiers that we know to be -- typedef'ed type identifiers. We also must deal correctly with scope so we -- keep a list of sets of identifiers so we can save the outer scope when we -- enter an inner scope. -- --- TODO ---------------------------------------------------------------------- --
NameSpaces
--- DESCRIPTION --------------------------------------------------------------- -- -- This module manages name spaces. -- --- DOCU ---------------------------------------------------------------------- -- -- language: Haskell 98 -- -- * A name space associates identifiers with their definition. -- -- * Each name space is organized in a hierarchical way using the notion of -- ranges. A name space, at any moment, always has a global range and may -- have several local ranges. Definitions in inner ranges hide definitions -- of the same identifiert in outer ranges. -- --- TODO ---------------------------------------------------------------------- -- -- * evaluate the performance gain that a hashtable would bring --
CAttrs
--- DESCRIPTION --------------------------------------------------------------- -- -- This module provides the attributed version of the C structure tree. -- -- * C has several name spaces of which two are represented in this module: -- - `CObj' in `defObjsAC': The name space of objects, functions, typedef -- names, and enum constants. -- - `CTag' in `defTagsAC': The name space of tags of structures, unions, -- and enumerations. -- -- * The final state of the names spaces are preserved in the attributed -- structure tree. This allows further fast lookups for globally defined -- identifiers after the name anaysis is over. -- -- * In addition to the name spaces, the attribute structure tree contains -- a ident-definition table, which for attribute handles of identifiers -- refers to the identifiers definition. These are only used in usage -- occurences, except for one exception: The tag identifiers in forward -- definitions of structures or enums get a reference to the corresponding -- full definition - see `CTrav' for full details. -- -- * We maintain a shadow definition table, it can be populated with aliases -- to other objects and maps identifiers to identifiers. It is populated by -- using the `applyPrefix' function. When looksup performed via the shadow -- variant of a lookup function, shadow aliases are also considered, but -- they are used only if no normal entry for the identifiers is present. -- -- * Only ranges delimited by a block open a new range for tags (see -- `enterNewObjRangeC' and `leaveObjRangeC'). -- --- DOCU ---------------------------------------------------------------------- -- -- language: Haskell 98
CBuiltin
--- DESCRIPTION --------------------------------------------------------------- -- -- This module provides information about builtin entities. -- --- DOCU ---------------------------------------------------------------------- -- -- language: Haskell 98 -- -- Currently, only builtin type names are supported. The only builtin type -- name is `__builtin_va_list', which is a builtin of GNU C.
