The Alto parser

Welcome to Alto, the Algebraic Language Toolkit.

Alto is a parser and decoder for Interpreted Regular Tree Grammars (IRTGs). It is being developed at Saarland University in the Computational Linguistics group, led by Alexander Koller. Its main features are:

• Represents grammars from a wide variety of popular grammar formalisms as IRTGs, including:
  • Context-free grammars
  • Tree-adjoining grammars (TAG), including TAG with feature structures (FTAG)
  • Tree automata and bottom-up tree transducers
  • Synchronous context-free grammars, TAG, etc.
  • Tree-to-string and string-to-tree transducers
  • Synchronous Hyperedge Replacement Grammars (HRG): Alto is the fastest published HRG parser in the world
  • and many more
• Implements chart-based algorithms for
  • parsing
  • synchronous parsing (with inputs from multiple sides of a synchronous grammar)
  • decoding (to another side of a synchronous grammar)
  • computing 1-best (Viterbi) and k-best derivations
  • maximum likelihood and expectation maximization (EM) training
  • binarization
• Supports PCFG-style and log-linear probability models for all of these grammar formalisms.
• Built for easy extensibility: implement your own grammar formalism by adding an Algebra class, and use any of the Alto algorithms directly.
• Comes with a GUI that provides access to most of these algorithms and visualizes parsing results.

Alto is published under a Apache 2.0 license. More license information can be found in the file license-info.md.

The basic theory of IRTGs is explained in Koller & Kuhlmann, IWPT 2011. You can find more details on the Literature page.

Running and using Alto

Alto requires at least Java 8 and can be downloaded here. To build Alto from source, clone this repository and run ./gradlew build (or ./gradlew.bat build if you use Windows).

To use Alto as a library in your project, include it via jitpack:

repositories {
    [...]
    mavenCentral()
    maven {url 'http://akci.coli.uni-saarland.de/artifactory/external'}
    maven {url 'https://jitpack.io'}
}
dependencies {
    [...]
    compile group: "com.github.coli-saar", name:"alto", version:"2.3.0"
}

Replace "2.3.0" with the release you want to use; see the releases page for details. If you want to build against the latest version, use master-SNAPSHOT or a specific git commit hash as version.

See the Wiki for more details on how to use Alto. The tutorials are a good way to get started. For advanced usage, you can check out the JavaDoc (see below).

If you run into trouble, please feel free to submit an issue.

JavaDoc

You can read the JavaDoc API documentation for the current stable version or the JavaDoc API documentation for the master branch.

Screenshots

Here are some screenshots of the Alto GUI. Here's an IRTG with one string and one graph interpretation (equivalent to a synchronous HRG):

Here's the result of parsing "the boy wants to go" with this grammar:

Version History

See the releases page for versions after 2.3.0.

Version 2.3.0, April 2019

• Move to GitHub and switch build system to gradle.
• fix deprecation warnings in the build process
• use more generics instead of raw classes

Version 2.1, April 2017

• Improved intersection and invhom algorithms (condensed, sibling-finder) for much faster PCFG, TAG, and HRG parsing (Groschwitz et al., ACL 2016).
• Added pruning techniques, including beam search and coarse-to-fine parsing.
• Added adaptive importance sampler for grammar induction (Teichmann et al., ACL 2016 Workshop on Statistical NLP and Weighted Automata).
• Added "inside" binarization strategy (Klein & Manning 2003).
• Added command-line scripts for parsing and grammar/corpus conversion.
• Initial support for running reproducible experiments using Alto Lab.
• Many small bugfixes and performance improvements.

Version 2.0, July 2015

• Initial Bitbucket release.

Contributors

• Danilo Baumgarten (BSc University of Potsdam, 2013)
• Johannes Gontrum (BSc University of Potsdam, 2015)
• Jonas Groschwitz
• Arne Köhn
• Alexander Koller
• Christoph Teichmann