pycfg

This repository contains a Python package, cfg, which implements
data structures and algorithms for carrying out sophisticated analysis and
parsing of arbitrary context-free grammars. The main vehicle used for CFG
parsing is the GLR (Generalized-LR) algorithm discovered by Masaru Tomita.
Several pedagogical parsing algorithms described by Alfred Aho and Jeffrey
Ullman are also included. A tool named pycfg provides a command-line
interface to CFG analysis algorithms.

Contents

The file pycfg is a command-line utility for analyzing CFGs. It can:

• Convert grammars to Chomsky Normal Form
• Compute a grammar’s first and follow sets
• Create a diagram of a grammar’s DFA of LR(0) items used for LR parsing
• Compute a grammar’s SLR(1) parse table
• Generate a report in HTML of the steps taken to build the parse table
• Make you a sandwich, as long as you have root privileges

Use the command

./pycfg

without arguments to see a full help message.

The src/ directory contains the Python packages cfg and util. Included
in cfg are:

• A class structure for context free grammars, symbols, parse trees, etc.
• Tomita’s GLR parsing algorithm, modified to handle empty production rules
  and cyclic grammars
• Algorithms for building first sets, follow sets, and multi-valued SLR parse
  tables
• Parsing algorithms described by Aho and Ullman and included for pedagogical
  purposes
• Other algorithms such as cycle and left-recursion detection

The test/ directory contains unit tests for most components in the
library. Use

./run_tests

to run all of the test cases included here, which should all pass.

The demos/ directory contains some standalone Python scripts demonstrating
the use of the library.

Demo

The demos/ directory has a number of driver programs demonstrating the use
of various parts of the library. For example, the command

cd src; python ../demos/glr_demo.py ../demos/grammars/gra.txt

will bring up a prompt for input symbols to be parsed with respect to the
ambiguous grammar described in demos/grammars/gra.txt, and then generate
and display images of the resulting parse trees. In this case the input
alphabet consists of the characters ‘n’ for noun, ‘d’ for determiner, ‘v’
for verb, and ‘p’ for preposition. To run the example
on an ambiguous sentence with six valid parse trees, enter the following
characters at the prompt and then press Ctrl-C, as shown below:

>> n
>> v
>> n
>> a
>> n
>> v
>> d
>> n
>> p
>> d
>> n
>> <Ctrl-C>

This corresponds to the sentence “I saw Jane and Jack hit the man with a
telescope.”

References

• Aho, Alfred V., and Ullman, Jeffrey D. The Theory of Parsing, Translation,
  and Compiling: Volume I: Parsing. Englewood Cliffs, NJ: Prentice-Hall,
  Inc. 1972.
• Tomita, Masaru (Ed.). Generalized LR Parsing. Boston, MA: Kluwer Academic
  Publishers. 1991.
• The Dragon Book.