# Parsing of Lexicalised Linear Context-Free Rewriting Systems via Supertagging

From International Center for Computational Logic

# Parsing of Lexicalised Linear Context-Free Rewriting Systems via Supertagging

##### Alex IvlievAlex Ivliev

Alex Ivliev

Project Thesis, TU Dresden, May 2020

**Parsing of Lexicalised Linear Context-Free Rewriting Systems via Supertagging**Project Thesis, TU Dresden, May 2020

**Kurzfassung****Abstract**

Many natural language processing tasks require a syntactic representation of the input sentence. This can be achieved via dependency trees, which describe grammatical relations between words as directed edges. Non-projective trees, i.e. dependency trees with "crossing" edges, cannot be expressed by context-free grammars. Using context-sensitive grammars, however, is not feasable especially in real-time applications since parsing them is PSPACE-complete. Therefore, a number of grammar formalisms were proposed that can represent non-projective structures occuring in natural languages while still allowing the sentence to be parsed in polynomial time. These formalisms are summarized under the term mildly-context-sensitive grammars which includes for example head grammars, tree-adjoining and linear indexed grammars. Linear context-free rewriting systems (LCFRS) were introduced to represent this class of grammars in a uniform way. To further optimize the parsing of such grammars, a method called Supertagging has been developed in the context of tree-adjoining grammars. This method aims to reduce the number of rules considered during parsing by pre-selecting a small number of so-called elementary trees. In this work, we adapt this approach to lexicalised LCFRS grammars. As a way to pre-select rules during parsing we use BERT, which is a pre-trained neural network developed by Google AI. To train the network, we apply an embedding algorithm that assigns each rule to a small-dimensional vector of real numbers based on syntactic similarities between the rules. We further measure the impact of this method on the time and accuracy of parsing using established corpura.**Bemerkung:****Note:**Supervised by Heiko Vogler and Richard Mörbitz**Forschungsgruppe:****Research Group:**Wissensbasierte Systeme

```
@misc{I2020,
author = {Alex Ivliev},
title = {Parsing of Lexicalised Linear Context-Free Rewriting Systems via
Supertagging},
year = {2020},
month = {May}
}
```