cfg /

Filename Size Date modified Message
examples
lib
56 B
385 B
1.3 KB
873 B
26.8 KB
702 B
3.9 KB
881 B
648 B
364 B
17.2 KB
146.9 KB

CFG - Manipulation of Context-Free Grammars


What is CFG?

This OCaml-library consists of a set of modules which implement functions for analyzing and 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 (terminals, nonterminals, productions). See the interface in cfg_intf.ml and the BNF-example.

Thus, you may use this module for any kind of symbolic system that is equivalent to a context-free grammar. This includes, for example, specifications of algebraic datatypes, which are isomorphic.


Using CFG

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 somewhat like their set counterparts. 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 performed 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 and efficiently export its internal representation without copying.

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

Documentation of Functions

For details see the API documentation in cfg_intf.ml.


BNF-Example

The example in examples/bnf uses CFGs in traditional BNF-notation, which represents terminals and nonterminals as plain strings. It reads in a grammar specification from stdin and prints information about the grammar. Here is an example invocation (from top directory in the distribution after building):

:::sh bnf.native < examples/bnf/test.bnf

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

Thus, if you want to be able to distinguish between two productions which are otherwise structurally equivalent, just parameterize the CFG-module so that productions receive an additional tag to make 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.


Contact information and contributing

Up-to-date information should be available at: http://www.bitbucket.org/mmottl/cfg

Enjoy!

Markus Mottl in Rutherford, NJ on June 29, 2012

Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.