Navigation

NatsWiki

System

The CDG Reference Manual

0.95

Author:: Michael Daum, Ingo Schröder, Kilian A. Foth

Purpose of this document

This document is a thorough description of all data structures and functions used in the CDG system and serves as a technical documentation of the parser.

Most of the core functionality is exported by the modules in the directory libcdg, which can be viewed as yet another C library, although a very specialized one. Application-specific functionality must be implemented by the application that uses the libcdg library. Thus, the command-line parser cdgp includes code to parse its command-line options and to do I/O on a terminal, and the graphical parser xcdg defines extensive routines to display input structures graphically. This document will eventually cover all data structures and functions of the constraint parsing library libcdg and the text-based parser cdgp.

CDG is written entirely in C (and automatically generated C in some cases). It relies on several non-ANSI extensions to the C programming language (such as local functions and dynamic arrays). The GNU C compiler can compile all of these features; others may or may not.

Overview

The CDG library is organized into several modules each of which offers a specialized service to the environment. The set of all modules can be further divided into those offering the basic infrastructure for CDG parsing whereas others are build on top and offer the different parsing flavours that are available.

Basic Modules

Cdg - The Root Module: This the root layer of the CDG library.
Chunker - Interface to a Chunking Parser: This module offers an interface for an external chunker.
Cdgdb - Get lexical entries out of a berkeley database: This module provides access to a berkeley database for retrieving lexical entries.
Command - The CDG Scripting Language: This module implements the CDG scripting interface.
Compiler - compile a constraint grammar: This module implements a compiler in order to translate constraints into C code.
Constraintnet - maintainance of constraint nets: Herein the basic and most central datastructure of CDG is implemented, the ConstraintNet.
Eval - routines to evaluate constraint formulas: The Eval module actually implements the constraint interpreter
ref Functions: Implementation of all function calls
Hook - A callback system: The Hook module connects the core of the library to its outside world by a callback mechanism.
ref Input:This module defines the data structures and access functions for constraint grammar.
ref Interpreter: This module implements the constraint grammar language it consists of the following submodules
ref Levelvalue
Lexemgraph - maintainance of lexem graphs
ref Parse
ref Predicates: Implementation of all predicates
Scache - Cache structures for binary LV scores
Scorematrix - The matrix of scores appearing in each ConstraintEdge: This module implements the score matrix for a constraint edge.
ref Set: This module provides a uniform interface for all user-visible variables.
ref Statistics
ref Tagger
ref Testing
Timer - timekeeping functions
ref Variables: This module provides a generic interface for variable encapsulation, and is exclusively used by the set module.
ref Write

Parsing Flavours

ref Arcconsistency
ref Frobbing
ref MGLS
ref Increment
ref Incrementalcompletion
ref Netsearch
ref Nodeconsistency
ref Search

General guidelines

File structure

Every module consists of a declaration part <moduleName>.h and an implementation part <moduleName>.c . Another module can use the exported services of this modules by including its declarations in <moduleName>.h . Note that many of the functions covered in this manual are not exported and therefore cannot be used from other modules at all. The files skel.c and skel.h provide a skeleton for a new module.

Terms used in this document

While some of the functions in the libcdg library explicitly use variable-length argument lists, other have a prototype like the following:

 int no, char **args

In this case it is always assumed that args is an array of valid zero-terminated strings, and that no specifies the number of these strings. This is an alternate way of passing a varying number of additional arguments. The strings contained in the array are called command words in this document to distinguish them from the actual function arguments.

Coding style

Most identifiers of data structures and algorithms are complete English phrases such as `ConstraintNet' or `printLexiconItem'. When a module deals primarily with one data structure, it is common practice to abbreviate the name of this structure and use it as a prefix to all exported identifiers, as in `lvNew', `lvPrint', and `lvDelete' (rather than `newLevelValue', `printLevelValue', and `deleteLevelValue').

To avoid the explicit use of pointer variables, most modules export typedef 'd aliases for all pointer types. These aliases have meaningful names, while the underlying struct types have names ending in Struct:

typedef struct {
   String id;
   Boolean active;
   int counter;
} SectionStruct;
typedef SectionStruct *Section;

Although ANSI C allows the programmer to collapse these two typedef statements into one, this construct cannot be parsed by the interface generator SWIG, used for building xcdg. Therefore it is important to use exactly this way of defining pointers to structures.

One consequence of this definition style is that although very few pointer symbols are used in the code, most libcdg data types obey reference semantics: A function called on a variable s can usually change the underlying structure, even though C function calls actually use value semantics.

A more practical demonstration of the coding style is given in Skel - A Skeleton Module.

CDG 0.95 (28 Oct 2004)

A printable manual his here: libcdg-refman.pdf:

r1.2 - 28 Oct 2004 - 16:20 GMT - MichaelDaum

Navigation

Constraint Dependency Grammar