---------------------------------------------------------------------------

                 CFG - Manipulation of Context-Free Grammars

---------------------------------------------------------------------------

                               Prerequisites

             YOU WILL NEED GNU-MAKE TO COMPILE THE SYSTEM WITH
                         THE DISTRIBUTED MAKEFILES

---------------------------------------------------------------------------

                       Contents of this distribution

Changes             - History of code changes.

LICENSE             - A copy of the "GNU LESSER GENERAL PUBLIC LICENSE"

Makefile            - Top Makefile

OcamlMakefile       - Makefile for easy handling of compilation of not
                      so easy OCaml-projects.  It generates dependencies
                      of Ocaml-files automatically, is able to handle
                      "ocamllex"-, "ocamlyacc"-, IDL- and C-files and
                      generates native- or byte-code, as executable or
                      as library - with thread-support if you want!

README.txt          - this file

lib/                - Implementation of the CFG-library

examples/bnf/       - A simple demonstration of analysing CFGs in BNF-form.

---------------------------------------------------------------------------

                                What is it?

This OCaml-library consists of a set of modules which implement functions
for manipulating context-free grammars (CFGs) in a purely functional way.

The core-module (cfg_impl.ml) contains a functor which allows the
parameterization of the main transformation functions with arbitrary grammar
entities that fill the demanded specification (see the interface in
"cfg_intf.mli" and the BNF-example).

Thus, you may use this module for any kind of symbol system and any kind of
representation which can be treated like a CFG.

What it can do:

  Besides building up grammars with the single function "add_prod",
  some powerful functions allow you to construct new grammars from old
  ones: "union", "diff", "inter".  These functions behave similarly as
  with sets.  E.g. "inter" will generate the intersection of all grammar
  entities (common nonterminals and their common productions).

  Further manipulation functions exist for:

    * Pruning unproductive productions and nonterminals: they contain
      references to nonexistent symbols.

    * Pruning nonlive entities: such symbols and productions only exist
      in cyclic derivations from which there is no escape.

    * Pruning unreachable entities: such symbols and productions cannot be
      reached from the start symbol.

    * Generating a "sane" grammar: combines the above steps. In such
      grammars each entity is useful.

  Functions for getting information on grammars:

    * Calculating the minimum number of derivations necessary to derive
      nonterminals and productions. This step is done during pruning of
      nonlive symbols, because this process allows the easy collection
      of this information.

    * Because the implementation is purely functional, the library can
      safely export its internal representation without copying. All this
      internal data adheres to interfaces of standard libraries and is
      therefore easy to use (see the example) and does not break easily.

Due to the applicative nature of the library, which allows a lot of sharing
in memory (persistency), it should be useful for handling very large
grammars efficiently.

---------------------------------------------------------------------------

                                BNF-Example

The example uses CFGs in traditional BNF-notation, which represents
terminals and nonterminals as plain strings.

You cannot have several productions that contain the same terminals
and nonterminals in the same order. The BNF-example uses the unit-type
for tagging productions, which does not allow differences other than of
syntactical nature.

Thus, if you want to make a difference between two productions which are
otherwise structurally equivalent, just parameterize the CFG-module so
that productions get an additional tag, which makes them unequal.

This allows you, for example, to use the library for doing transformations
on grammars for abstract syntax, where productions carry additional
information concerning static semantics (e.g. attributes). Two
syntactically identical productions may have different semantics then
and will not be treated the same.

---------------------------------------------------------------------------

                         Documentation of Functions

For details see the comments in "cfg_intf.mli".

---------------------------------------------------------------------------

Up-to-date information (newest release of distribution) can always be
found at:

  http://www.ocaml.info

---------------------------------------------------------------------------

Enjoy!

Vienna, 2003-04-08
Markus Mottl

e-mail: markus.mottl@gmail.com
WWW:    http://www.ocaml.info