Miguel A. Alonso
COMPAS (COMpiler for PArsing Schemata) is a system that can be used to automatically compile formal specifications of parsing algorithms (in the form of parsing schemata) to efficient Java implementations of the corresponding parsers.
COMPAS allows compiling arbitrary user-defined parsing schemata into efficient implementations.
The distribution provided the following predefined parsing schemata for context-free grammars and tree-adjoining grammars:
- CYKRecognizer: A simple CYK context-free grammar recognizer.
- CYKVariant: A different way of expressing CYK, by expressing rules as items.
- CYKAnyGrammarRecognizer: The same as CYKRecognizer, but featuring a grammar class option so that if the input grammar is not in Chomsky Normal Form (CNF), the parser automatically transforms it to CNF when read.
- CYKWithTree: Simple CYK parser generating parse trees.
- SimpleEarleyRecognizer: An Earley recognizer, as it appears in the Parsing Schemata book by Sikkel (97).
- OptimizedEarleyRecognizer: An “unrolled” version of the Earley recognizer so that indexing is a bit faster.
- OptimizedEarleyWithTree: A simple Earley parser which generates parse trees.
- LCStandard.sch: A Left-Corner recognizer, this is the “LC” schema described by Sikkel (97). In this implementation, items are used to represent left-corner relationships.
- LCSimplifiedItems.sch: An optimized Left-Corner recognizer, this is the “sLC” schema described by Sikkel (97).
- LCWithPredicates.sch: An alternative implementation of Left-Corner where predicates, instead of items, are used to represent left-corner relationships.
- TopDown.sch: A simple, inefficient top-down parser.
- EarleyNVPforXTAG.sch: A tree-adjoining grammar parser for use with the XTAG English Grammar, including feature structure unification and several XTAG-specific features.
COMPAS can be used to compile error-repair parsing schemata. The following one is provided in the distribution:
- Lyon.sch: Lyon’s error-correcting parser, using a priority queue as agenda.
The COMPAS system is written in Java
The COMPAS system is runnable in any system for which a Java Virtual Machine (JVM) is available, including Windows and Linux.
You need to have the following software installed in order to use the system::
- A Java Runtime Environment (JRE), version 1.4 or higher. Download it here.
- The Apache Ant Build System is not strictly necessary, but highly recommended in order to be able to easily compile the code generated by the system.
The first compiler for arbitrary parsing schemata.
It defined the notion of error-repair parsing schemata and provided a mechanism for efficnet compilation of these kind of schemata.