2

Say I have a string representing text in a natural language, for example:

She is an effective teacher. Most students have found her reasonably helpful.

Is there a programming library or command line program that will take this as input and return a tree stucture, the kind that is similar to syntax trees produced by parsers for formal/programming languages?

I know of POS taggers, but these taggers only seem to analyse the text at the word level. I need the constituents of all other levels..

Hence, the tree structure should reflect the structure of the text at all levels ie discourse, sentence, clause, phrase, group, word, even morpheme (both inflectional and derivational) and I should be able to traverse this tree from the bottom-most node to the "root" node... So traversing the whole tree of the above mentioned string sample should give something like:

  • Constituent/Element----Constituent/Element Type/Part Of Speech----Level
  • She----Pronoun----Word
  • Is----Verb----Word
  • An----Determiner----Word
  • Effective----Adjective----Word
  • teacher----Noun----Word
  • ...
  • She----Subject/Noun Phrase----Phrase
  • Is----Predicate/Verb Phrase----Phrase
  • An effective teacher----Object/Noun Phrase----Phrase
  • ...
  • She is an effective teacher.----Simple sentence----Sentence
  • Most students have found her reasonably helpful.----Simple sentence----Sentence

This sort of library and/or program should support the following languages at the very least: English Chinese Mandarin Korean

It would be good if it also supports: Cantonese Malay / Indonesian Russian Arabic ...and more!...

For languages that have inflectional morphology and particles, the parser should also recognise the elements below the level of the word, and the particles. Eg. In Korean, a word like 하모일어서 should be parsed as 하모일/NNG+이/VCP+어서/EC

Actually I have also thought of achieving the abovementioned by creating my own parser using a parser generator like ANTLR, which take in a BNF grammar as input, and produce a parser program/executable as output.. But I haven't been able to find BNFs for natural languages so far.. If one can provide BNF resources for natural languages that can be used with ANTLR, that can also be accepted..

System requirements:

PHP,Javascript,Java,Python (or any other language) (listed in order of preference from most preferred to least) AND/OR Command line program

For use on MacOS 10.13.6

Open source where possible

5
  • 1
    This is a question that I think has come up in different phrasings, over time - a very good question, but (thinking aloud here), I wonder if we should make a site-wiki type post, to direct people to.
    – Julius H.
    Jun 12, 2023 at 11:32
  • 1
    @hmltn 2nd that, but I dunno how to Jun 12, 2023 at 12:14
  • Thanks. We can look into it. I’ll dig up some URL on that. Or someone else can.
    – Julius H.
    Jun 12, 2023 at 12:23
  • 1
    There are parsers, but they don't do all you want them to. And they really only work on tagged input, so you hafta control that, too.
    – jlawler
    Jun 12, 2023 at 15:42
  • A BNF grammar for parser generators is not nearly powerful enough to analyse natural language. Jun 13, 2023 at 8:11

1 Answer 1

3

Parsers and syntax trees for natural languages

Say I have a string representing text in a natural language, for example:

She is an effective teacher. Most students have found her reasonably helpful.

Introduction

Is there a programming library or command line program that will take this as input and return a tree stucture, the kind that is similar to syntax trees produced by parsers for formal/programming languages?

There either already is, or the capability to make precisely what you want is manageable and feasible to put together.

POS taggers

I know of POS taggers, but these taggers only seem to analyse the text at the word level.

Possibly, but it depends which one / which technique is being used. Maybe someone can find a research review article on the state-of-the-art on this. My idea for classifying approaches would be, how much ‘knowledge’ or structure the program starts out with. Maybe it comes with a whole dictionary of tokens and their parts-of-speech - in which case, it’s a simple string matching algorithm. Maybe it’s a rule-based lemmatizer, in which case, the program comes with a lot of initial information about morphology and lemmatization rules based on different word forms. A syntax parser seems like a good approach, because one of the strongest relationships part of speech is commonly take to have, is to syntax rules dictating how POS elements (word kinds, or word classes) get arranged with one another. Or maybe semantics has a relationship to POS, and someone could think of a technique leveraging that. On the lowest level, there are algorithms that come without any strong relationship to the structures presumed to be in language, and can still identify patterns - for example, here is one highly cited paper from the 1980’s, which has been followed by more new techniques:

Schmidt, Helmut. “Probabilistic part-of-speech tagging using decision trees.” (1994).

Syntax parsing in research

I need the constituents of all other levels..

Then you’re looking for a complete syntax parse - another alive-and-well technique in modern NLP. Just try keyword-perusing Semantic Scholar or Google Scholar:

https://www.semanticscholar.org/search?q=Constituency%20parse&sort=relevance


Revisiting the Practical Effectiveness of Constituency Parse Extraction from Pre-trained Language Models
Taeuk Kim
Computer Science
International Conference on Computational…
15 September 2022

CPTAM: Constituency Parse Tree Aggregation Method
Adithya Kulkarni, Nasim Sabetpour, A. Markin, O. Eulenstein, Qi Li
Computer Science
SDM
19 January 2022

…

Syntax parsing code libraries

  • Hence, the tree structure should reflect the structure of the text at all levels

  • ie discourse, sentence, clause, phrase, group, word, even morpheme (both inflectional and derivational)

  • and I should be able to traverse this tree from the bottom-most node to the "root" node...

  • So traversing the whole tree of the above mentioned string sample should give something like:

    Constituent/Element----Constituent/Element Type/Part Of Speech----Level She----Pronoun----Word Is----Verb----Word An----Determiner----Word Effective----Adjective----Word teacher----Noun----Word ... She----Subject/Noun Phrase----Phrase Is----Predicate/Verb Phrase----Phrase An effective teacher----Object/Noun Phrase----Phrase ... She is an effective teacher.----Simple sentence----Sentence Most students have found her reasonably helpful.----Simple sentence----Sentence

I would say there are libraries that come close, like Spacy, but given a somewhat custom vision you have, you might want to Do-It-Yourself using more fundamental techniques & foundational approaches.

Spacy

Spacy is a library that offers a “pipeline” of natural language processing layers. All you would do is submit a text to Spacy’s core language object, and its constructor will perform virtually all standard processing tasks which could be desired, which are then accessible as attributes. Here’s a demo:

import spacy

nlp = spacy.load(‘en_core_web_sm’)

doc = nlp(some_text)

print(doc.sents)

for sent in doc.sents:

  for word in sent:

    print(word.POS)

and the like.

Using a computable grammar (for the language)

Using a parser generator like ANTLER + BNF

Actually I have also thought of achieving the abovementioned by creating my own parser using a parser generator like ANTLR, which take in a BNF grammar as input, and produce a parser program/executable as output.. But I haven't been able to find BNFs for natural languages so far.. If one can provide BNF resources for natural languages that can be used with ANTLR, that can also be accepted..

Grammatical Framework

The closest thing I know of is Grammatical Framework.

Custom, DIY solution (w.i.p.)

I can try to update this post with a custom or authentic DIY solution instead, which would be better. I think I would prefer non-probabilistic feature discovery if possible.

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .