chart-parsers

This is a library of chart parsers for natural language processing using context-free grammars and unification-based grammars.

Supported algorithms

The following parsing algorithms are supported:

• Cocke Younger Kasama (CYK) Parser: an efficient purely bottom up chart parser for parsing with grammars in Chomsky Normal Form (CNF)
• Earley Parser: a basic chart parser based on Earley's algorithm for parsing with context-free grammars
• Left-Corner Parser: a chart parser for parsing with top-down predictions based on the left-corner of production rules.
• Head-Corner Parser: a chart parser for parsing with top-down predictions
  based on the head of production rules.

All four parsers are created and called in the same way and return the same type of result, that is a chart with recognised items. Both context-free grammars and unification grammars can be used. In the next section it will be explained how grammars and parsers are used in general. After that each parser will be discussed in more detail.

Installation

This module can be installed using npm as follows:

npm install chart-parsers

Usage

All four parser are used in the same way: load a grammar, create a parser and parse sentences.

var GrammarParser = require('GrammarParser');
var ParserFactory = require('ParserFactory');
var parserFactory = new ParserFactory();

var tagged_sentence = [['I', 'NP'], ['saw', 'V'], ['the', 'DET'], ['man', 'N'], 
                       ['with', 'P'], ['the', 'DET'], ['telescope', 'N']];
var grammar_text = "S -> NP *VP*\nNP -> DET *N*\nNP -> *NP* PP\nPP -> P *NP*\nVP -> *V* NP\nVP -> *VP* PP";

// Parse the grammar
var grammar = GrammarParser.parse(grammar_text);
// Create a parser; other parsing algorithms are 'Earley', 'LeftCorner', 'HeadCorner'
var parser = parserFactory.createParser({
  grammar: grammar, 
  type: 'CYK', 
  unification: false, 
  listOfCategories: true
});
// parse the sentence
var chart = parser.parse(tagged_sentence);

The resulting chart is an array of length N+1, and each entry contains items of the form [rule, dot, from, children] where:

• rule is the production rule; it has two members: lhs for the left-hand-side of the rule, and rhs for the right-hand-side of the rule.
• dot is the position in the right hand side of the rule up to which it has been recognised.
• from is the origin position pointing at the position in the sentence at which recognition of this rule began.
• children are the completed items that are used to recognise the current item

Based on the children of the completed items the parse(s) of a sentence can be reconstructed.

Context-Free Grammars

The grammar module reads context-free grammars from file, and offers some methods that are practical for parsing.

The syntax of production rules is as follows (in EBNF):

grammar =         { comment | production_rule }
production_rule = nonterminal, [ white_space ], "->", [ white_space ], [nonterminal_seq] , ["*" nonterminal "*" nonterminal_seq ]
nonterminal_seq = nonterminal, { whitespace, nonterminal }
nonterminal =     non_whitespace_char, { non_whitespace_char }
comment =         "//", { any_character }

Note the possibility of identifying one nonterminal as the head of the production rule. This information is used by the head-corner parser for predicting new partial parses. Terminals are not allowed in the grammar, because we assume these to be recognised by a lexer and tagged with (lexical) categories (or feature structures). In the grammar these lexical categories are seen as preterminals. The grammar parser also allows adding constraints to the production rules. Contraints may have two possible forms:

<nonterminal1 feature1 feature2> = type
<nonterminal2 feature3 feature3> = <nonterminal3 feature4>

where type is a type defined by a type lattice. See below for an explanation of type lattices.

CYK Chart Parser

The CYK algorithm works with context-free grammars in Chomsky Normal Form (CNF). Production rules are of the form:

A -> B C
A -> a

where A, B and C are nonterminals and a is a terminal.

##Algorithm The CYK algorithm is as follows:

function CYK-PARSE(sentence, grammar)
  let the input be a sentence consisting of n characters: a1 ... an.
  This grammar contains the subset Rs which is the set of start symbols.

  chart = INITIALISE-CHART(sentence, grammar)
  for each i = 2 to n do // Length of span
    for each j = 1 to n-i+1 do // Start of span
      for each k = 1 to i-1 do // Partition of span
        for each production A -> B C do
          if chart[j,k,B] and chart[j+k,i-k,C] then 
            chart[j,i,A] = true
          end
        end
      end
    end
  end
  return chart
end

function INITIALISE-CHART(sentence, grammar)
  let chart[n,n,r] be an array of booleans 
    where n is the length of the sentence and
    r the number of nonterminal symbols. 
  Initialize all elements of chart to false.
  for i = 1 to n do
    for each unit production A -> ai
      chart[i,1,A] = true
    end
  end
  return chart
end

(Adapted from: Wikipedia, http://en.wikipedia.org/wiki/CYK_algorithm)

Below is a simple toy grammar that is in CNF:

S -> NP VP
NP -> DET N
NP -> NP PP
PP -> P NP
VP -> V NP
VP -> VP PP
DET -> the
NP -> I
N -> man
N -> telescope
P -> with
V -> saw
N -> cat
N -> dog
N -> pig
N -> hill
N -> park
N -> roof
P -> from
P -> on
P -> in

The language generated by this grammar contains a.o. "I saw the man with the telescope". Clearly, this grammar contains the lexicon as well. In our parser the lexicon is separated from the grammar. The parser expects a tokenized and tagged sentence as input. In this way we feed the output of a tagger into the parser.

Earley Chart Parser

The Earley Chart Parser can parse all context-free languages and uses arbitrary context-free grammars.

##Algorithm The algorithm in pseudo code:

function EARLEY-PARSE(words, grammar)
  ENQUEUE((γ → •S, 0), chart[0])
  for i ← from 0 to LENGTH(words) do
      for each state in chart[i] do
        if INCOMPLETE?(state) then
          PREDICTOR(state, i, grammar)
        else
          COMPLETER(state, i)
        end
      end
  end
  return chart
end
 
procedure PREDICTOR((A → α•B, i), j, grammar)
    for each (B → γ) in GRAMMAR-RULES-FOR(B, grammar) do
        ADD-TO-SET((B → •γ, j), chart[j])
    end
end
 
procedure COMPLETER((B → γ•, j), k)
  for each (A → α•Bβ, i) in chart[j] do
    ADD-TO-SET((A → αB•β, i), chart[k])
  end
end

(Adapted from: Wikipedia, http://en.wikipedia.org/wiki/Earley_parser)

Left-Corner Chart Parser

The left-corner algorithm is parses the sentence from left to right just like the Earley algorithm. The only difference is in the prediction of new items. The left-corner relation is used to optimise predictions top down. Therefore, the left-corner algorithm is called an bottom-up with top-down filtering. The left-corner relation is based on the left-corner of production rules. Consider the following production rule

S -> NP VP

NP is called the left-corner of S, written as S >_lc NP. The transitive reflexive closure, written as >_lc*, is used for filtering.

Algorithm

function LEFT-CORNER-PARSE(sentence)
  chart = INITIALISE-CHART(sentence)
  agenda = INITIALISE-AGENDA(sentence)
  for i = 0 to n do
    for items [A → α•β, i] do
      LC-PREDICTOR(item, chart, grammar)
      COMPLETER(item, chart, grammar)
    end
  end
  return chart
end

The deduction rules that is applied by LC-PREDICTOR is:

D_lc = {[X → γ•, k, j], [A → α.Cβ,i,k] |- [B → X.δ, k, j] | B → Xδ, C >_lc* B}

Head-Corner Chart Parser

The algorithm of head corner parsing is based on the idea that the right-hand side of a production rule contains a head, a word or constituent that determines the syntactic type of the complete phrase. To make the algorithm work in each production rule the right hand-side must a symbol that is decorated as head, like this:

NP -> DET *N*

This means that N is head-corner of NP, or NP >_hc N. The parser uses these the head-corner relation to predict new partial parses. In fact, it uses the reflexive transitive closure of the head-corner relation to create new goal items and head-corner items. The closure is written as >_hc*

Algorithm

Head-corner parsing involves a complex administrative bookkeeping. It uses a chart and an agenda. As long as items are available on the agenda, it takes an item from the agenda and tries to combine it with items on the chart. New items are added to the agenda. Algorithm in pseudo-code:

function HEAD-CORNER-PARSE(sentence)
  chart = INITIALISE-CHART(sentence)
  agenda = INITIALISE-AGENDA(sentence)
  while not IS-EMPTY(agenda) do
    current = GET-ITEM-FROM-AGENDA(agenda)
      if not IS-ON-CHART(current) then
        ADD-TO-CHART(chart, current)
        COMBINE-WITH-CHART(chart, current)
      end
  end
  return chart
end

The following types of items are used:

• CYK items are of the form [A, i, j] which means that nonterminal A can produce the sentence from position i to position j.
• Goal items are of the form [l, r, A] which means that the nonterminal is expected to be recognised somewhere between position l and r.
• Head-corner items are of the form [S -> NP VP, i, j, l, r] where the right hand side of the production rule has been recognised from position i to j, and the recognised part of the production can generate the sentence from position l to r.

Given a sentence a1, a2, .. , an, the following set is used to initialise the agenda; it adds goal items to the agenda for the start symbol.

D_init_agenda = {[i, j, S]|0 <= i <= j <= n}

The following set is used to initialise the chart; for each word of the sentence appropriate CYK items are added to the chart.

D_init_chart = {[A, i, i+1]| A -> a_i, 0 <= i <= n}

These deduction rules are used for creating new items in the combine step:

(1) D_HC = {[i, j, A], [X, i, j] |- [B -> α•X•β, i, j] | A >_hc* B}
(2) D_HC_epsilon = {[j, j, A] |- [B -> ••, j, j] | A >_hc* B}
(3) D_left_predict = {[l, r, A], [B -> αC•β•γ, k, r] |- [i, j, C] | A >_hc* B, l <= i <= j <= k}
(4) D_right_predict = {[l, r, A], [B -> α•β•Cγ, l, i] |- [j, k, C] | A >_hc* B, i <= j <= k <= r}
(5) D_pre_complete = {[A -> •β•, i, j] |- [A, i, j]}
(6) D_left_complete = {[i, k, A], [X, i, j], [B -> αX•β•γ, j, k] |- [B -> α•Xβ•γ, i, k] | A >_hc* B}
(7) D_right_complete = {[i, k, A], [B -> α•β•Xγ, i, j], [X, j, k] |- [B -> α•βX•γ, i, k] | A >_hc* B}

Deduction rules (1) and (2) introduce head-corner items from goal items. Rules (3) and (4) introduce goal items from partially recognised head-corner items. Rule (5) creates CYK items for head-corner items that are completely recognised. Rules (6) and (7) recognise parts of head-corner items based on CYK items.

Usage

The head-corner parser is created and applied as usual; there is one difference: the production rules of the grammar must be decorated with heads as follows:

S -> NP *VP*
NP -> DET *N*
NP -> *NP* PP
PP -> P *NP*
VP -> *V* NP
VP -> *VP* PP

Specification of a type lattice

A type lattice is specified as follows:

Type type1 ()
Type type2 ()
Type type3 (type1 type2)
Type type4 (type1)
Type type5 (type 4)

Each type specification if started with keyword Type followed by the type name and the super types between braces. If no super types are supplied, BOTTOM (the most general type) is assumed to be the sole super type.

Once a type lattice has been created the least upper bound of two types can be determined:

var LUB = type1.LUB(type2, type_lattice);

Checking if one type subsumes another type is done as follows:

if (type1.subsumes(type2, type_lattice)) {
  console.log(type1.prettyPrint() + ' subsumes ' + type2.prettyPrint());
}

A type may be appropriate for a feature with a value type. These appropriate features are specified in the form of a feature structure:

Type type1 ()
Type type2 ()
Type type3 (type1 type2) ->
[type3
 FEATURE1: type1
 FEATURE2: [type2
            FEATURE3: type1
           ]
]

When a new type with a feature structure is defined:

• The feature structure of the type is unified with the feature structures of its super types.
• The types used in the feature structure are unified with the respective feature structures belonging to these types.

As a result the feature structure inherits all appropriate features and types from super types and used types.

Built-in types are (types are case sensitive):

• BOTTOM: least specific type
• TOP: most specific type
• LIST: a list of coreferences and/or feature structures
• CONCATLIST: concatenation of lists referred to
• STRING: a lexical string
• RULE: type used for the feature structures of production rules
• CONSTITUENT: type used for the feature structures of a RHS nonterminal

Typed feature structures

Feature structures are specified using a specification language that largely follows PATRII. The LexiconParser reads lexicons that assign feature structures to words. Multiple alternative feature structures may be assigned to the same word by specifying multiple entries of the word. Each node of a feature
structure has a type assigned that is specified in a type lattice.

[home] ->
[sign
 CATEGORY: noun
 AGREEMENT: [agreement
             NUMBER: singular
             GENDER: neutrum
            ]
]

In this example the root node of the feature structure is of type sign and category is of type noun.

Feature structures can be unified as follows:

var result = fs1.unify(fs2, typeLattice);

Features may have several different values: Type: feature: type

PERSON: first

Feature structure: f1: [t1 f2: t2]

AGREEMENT: [agreement
            PERSON: first
            GENDER: masculin
           ]

A coreference to a feature structures: FEATURE: [1]

AGREEMENT: [1][agreement
               PERSON: first
               GENDER: masculin
              ]
SAME: [1]

A list of coreferences to other feature structures: <[1], [2], .. .>; A list may contain embedded feature structures.

NP: [1]: [...]
PP: [2]: [...]
CAT: [cat
      COMPS: <[1], [2], [BOTTOM f: type]>
     ]

A concatenated list of coreferences: [1] + [2]

CAT: [cat
      SUBJ: [1]: <>
      SPR: [2]: <>
      COMPS: [3]: <NP>
      ARG-STR: <[1] + [2] + [3]>
     ]

References

• An Introduction to Unification-Based Approaches to Grammar, Stuart M. Shieber, 2003, URL: https://dash.harvard.edu/handle/1/11576719
• Head-Driven Phrase Structure Grammar, Pollard, Carl, and Ivan A. Sag. 1994. Chicago: University of Chicago Press and Stanford: CSLI Publications. Chapters 1, 3 and 4 are online available: http://hpsg.stanford.edu/LSA07/
• Introduction to Head-driven Phrase Structure Grammar, Steve Harlow, 2009, URL: http://www-users.york.ac.uk/~sjh1/hpsgcourse.pdf