up: a general-purpose parser

Index
1. Overview
2. How To Use UP
3. Word Lattice and Extent
4. Edge
5. Chart
6. Link
7. Root Condition and Parse Tree
8. Disambiguation Module
9. Miscellaneous Items

1. Overview

The up is a parser that analyzes a sentence according to a unification-based grammar, e.g., HPSG. See this for further details about the grammar specifications.

The parser starts analyzing a sentence when users call parse/1 or parse_word_lattice. Users can give the target sentence as a string or a word latttice to the parser.

Parsing proceeds in the following steps.

1. preprocessing
2. lexicon lookup
3. kernel parsing

As seen in the figure, the parser has data structures called chart, edge manager, link manager and FOM manager. The details of them will be explained later.

2. How To Use UP

This tool loads LiLFeS modules specified with "-l" and executes a parser. If a lilfes command is specified, it is executed. If interactive mode is specified, it prints a command prompt of LiLFeS after executing the lilfes command.

It does nothing about loading of a lexicon and initialization of FOM models. For these, utilize the interfaces of "up" such as "parser_init".

3. Word Lattice and Extent

When parse/1 is evoked, the string in the argument will be converted to a word lattice by sentence_to_word_lattice/2, and then parse/1 does the same process as parse_word_lattice/1 does. The word lattice is defined as a list of extents, but the implementation of sentence_to_word_lattice/2 must be given in the grammar. The extent type is defined in parser.lil as follows. We call the data structure of extent type `extent.'

extent <- [bot] + [left_position\integer(0), right_position\integer(1)].

extent_bracket <- [extent].
extent_sign_constraint <- [extent] + [sign_constraint\bot(5)].
extent_word <- [extent] + [word\bot(5)].

The children of extent type are extent_bracket, extent_sign_constraint, extent_word, and they all have the feature left_position\ and right_position\.

The values of left_position\ and right_position\ are integer that represents the position in the target sentence. We call the integer `position,' and the sub-string designated by the left position and the right position `region.' When the target sentence is tokenized as a sequence of words w1,w2,w3,w4,w5,...,wn, the left position of w1 is 0, and the right position is 1. In general, the left position of wi is i-1, and the right position is i. Intuitively, the relation between words and positions are illustrated as follows.

extent_word is an extent that corresponds to a word. It has not only positions, but has the values relevant to the word, e.g., the spelling, POS, in the word\ feature. The value in the word\ feature is defined in each grammar module. When the lexicon lookup process, the lexical entry is retrieved by using the value in the word\ feature.

Users can explicitly specify the phrase boundary by specifying extent_bracket. That is, the parser never generates a parse tree that cross the region specified by the extent_bracket.

Users can add constraints to the feature structures in the region by specifying extent_sign_constraint.

4. Edge

There is no corresponding type to edge, but edge is a quintuple < left-position, right-position, sign, a list of links, FOM >, which represents a phrasal structure for the sub-string of the target sentence. Left-position and right-position are positions in the sentence. Sign is a phrasal structure represented as a feature structure. That is, an edge is a phrase structures that corresponds to a region. The edge also has an information to reconstruct the parse tree after parsing in the list of links, and also has an information about the score (FOM) for disambiguation of analysis.

5. Chart

The parser has a data structure generally called `chart.' The chart is a two dimensional table. Here, we call each cell in the table `CKY cell.' Let an input sentence s(= w1, w2, w3,...,wn), for example, w1 = "I", w2="saw", w3= "a", w4 = "girl", w5 = "with", w6 = "a", w7 = "telescope" for the sentence "I saw a girl with a telescope", the chart is arranged as follows.

The edges on the chart can be acquired by calling edge_id_list/3 and top_edge_id_list/1.

6. Link

During parsing, an edge (parent) is generated by applying the grammar rules to two edges (children). For example, the results of applying the grammar rules to an edge in S[0][3] and an edge in S[3][5] are stored to S[0][5]. When an edge is store to a CKY cell, signs are reduced, and if reduced signs are equivalent with any of reduced signs in the same CKY cell, reduced signs are packed into one sign. This process is called `factoring.' The information that are cut off during factoring is stored to another data structure called `link.' For example, the signs of children in the parent are cut off in Enju. Instead, the IDs of child edges are stored as links in the parent's edge. Because several reduced signs are packed into one, the edge has several links.

A link is represented as the link type defined in parser.lil as follows.

link <- [bot] + [SIGN_PLUS\bot (-100)].
terminal <- [link] + [LEX_NAME\bot (5)].
nonterminal <- [link] + [APPLIED_SCHEMA\bot (5)].
nonterminal_binary <- [nonterminal] + [L_DTR\integer(0), R_DTR\integer(1)].
nonterminal_unary <- [nonterminal] + [U_DTR\integer(0)].

terminal is a link that corresponds to a lexical entry. nonterminal_binary is a link that corresponds to a phrasal sign generated by a binary grammar rules. nonterminal_unairy is a link that corresponds to a phrasal sign generated by a unary grammar rule. The value of APPLIED_SCHEMA\ is an ID of the grammar rule used for generating the link. The value of SIGN_PLUS\ is a feature structure that is cut off during factoring. Namely, the original sign is restored by unifying reduced sign and the value in SIGN_PLUS\. The value of L_DTR\ is an edge ID of the left child, and the value of R_DTR\ is an edge ID of the right child. The value of U_DTR\ is an edge ID of the child for the construction by unary grammar rules.

The link of an edge can be retriebed by calling edge_link_id_list/2 and edge_link/2.

7. Root Condition and Parse Tree

All edges that contributes to the final result of parsing must satisfy the root condition of parse trees. It can be verified by calling root_sign/1 explained in How to use a grammar. root_edge_id_list returns only edge IDs which satisfy the root condition.

get_parse_tree/2 reconstruct a parse tree by following edge and link informations.

8. Disambiguation Module

If the disambiguation module is supported in the grammar, the score of each edge can be retrieved by calling edge_fom/2. We call the score FOM (Figure of Merit).

9. Miscellaneous Items