<commit_before>Partage
==========

**Partage** is a Haskell library and a tool dedicated to parsing *tree
adjoining grammars* (TAGs).  It supports both adjunction and sister-adjunction.

It implements two kinds of parsers -- an Earley-style, bottom-up parser [1]
with special focus on structure (and, hence, computation) sharing [2], and an
A\* parser [3,4,5].
    
[![Build Status](https://travis-ci.org/kawu/partage.svg?branch=master)](https://travis-ci.org/kawu/partage)

#### Earley-style parser

The Earley-style parser implements two flavors of grammar compression:

  * Subtrees common to different elementary trees are shared.  The input TAG is
    in fact transformed into an equivalent directed acyclic graph (DAG).
  * Flat production grammar rules representing the individual parts of the DAG
    are compressed into an FSA.  The default choice is a prefix-tree
    compression, although other forms of compression are also possible (e.g.,
    minimal FSA).

#### A\* parser

The A\* parser works best on the results of dependency-aware supertagging in
which:

  * To each position in the input sentence a distribution of TAG elementary
    trees (supertags) which can be anchored at this position is assigned.  This
    comes from classic statistical supertagging.
  * To each position in the sentence the distribution of the possible heads is
    also assigned.  This can result from statistical dependency parsing.

The probability of a TAG derivation in this setting is defined as the product
of the probabilities of the participating supertags multiplied by the product
of the probabilities of the entailed dependency arcs.  The A\* parser then
gurantees to find a most probable derivation without searching the entire space
of the possible derivations.

Some correctness-related properties (notably, monotonicity) of the A\* parser
are verified using the [Coq][coq] proof assisatnt.  See the [proofs](proofs#proofs)
subfolder for more details.

Grammar compression is also used in the A\* parser, but to a very limited
extent.


Installation
------------

First you will need to download and install the [Haskell Tool Stack][stack].
Then run the following commands:

    git clone https://github.com/kawu/partage.git
    cd partage
    stack install

The last command builds the `partage` command-line tool and (on Linux) places
it in the `~/.local/bin/` directory by default. Installation on Windows, even
though not tested, should be also possible.

You can also run the following command in the local repository to make sure
that all the tests succeed:<commit_msg>Amend some typos in the README<commit_after>Partage
==========

**Partage** is a Haskell library and a tool dedicated to parsing *tree
adjoining grammars* (TAGs).  It supports both adjunction and sister-adjunction.

It implements two kinds of parsers -- an Earley-style, bottom-up parser [1]
with special focus on structure (and, hence, computation) sharing [2], and an
A\* parser [3,4,5].
    
[![Build Status](https://travis-ci.org/kawu/partage.svg?branch=master)](https://travis-ci.org/kawu/partage)

#### Earley-style parser

The Earley-style parser implements two flavors of grammar compression:

  * Subtrees common to different elementary trees are shared.  The input TAG is
    in fact transformed into an equivalent directed acyclic graph (DAG).
  * Flat production grammar rules representing the individual parts of the DAG
    are compressed into an FSA.  The default choice is a prefix-tree
    compression, although other forms of compression are also possible (e.g.,
    minimal FSA).

#### A\* parser

The A\* parser works best on the results of dependency-aware supertagging in
which:

  * To each position in the input sentence a distribution of TAG elementary
    trees (supertags) which can be anchored at this position is assigned.  This
    comes from classic statistical supertagging.
  * To each position in the sentence the distribution of the possible heads is
    also assigned.  This can result from statistical dependency parsing.

The probability of a TAG derivation in this setting is defined as the product
of the probabilities of the participating supertags multiplied by the product
of the probabilities of the entailed dependency arcs.  The A\* parser then
guarantees to find a most probable derivation without searching the entire
space of the possible derivations.

Some correctness-related properties (notably, monotonicity) of the A\* parser
are verified using the [Coq][coq] proof assistant.  See the
[proofs](proofs#proofs) subfolder for more details.

Grammar compression is also used in the A\* parser, but to a very limited
extent.


Installation
------------

First you will need to download and install the [Haskell Tool Stack][stack].
Then run the following commands:

    git clone https://github.com/kawu/partage.git
    cd partage
    stack install

The last command builds the `partage` command-line tool and (on Linux) places
it in the `~/.local/bin/` directory by default. Installation on Windows, even
though not tested, should be also possible.

You can also run the following command in the local repository to make sure
that all the tests succeed:
{'fraction_non_alphanumeric': 0.06861989205859677, 'fraction_numerical': 0.0019275250578257518, 'mean_word_length': 4.097249508840864, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 6, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7260231', 'n_tokens_mistral': 1393, 'n_tokens_neox': 1320, 'n_words': 700}