Parsing

GLRParser as Natural Language Parser

Consider the sentence:

I saw the man in the house with the telescope

This sentence has five interpretations, hence five different parse trees:

1. saw(in the house) saw(with the telescope) 
2. man(in the house) saw(with the telescope)
3. saw(in the house) house(with the telescope)
4. man(in the house) man(with the telescope)
5. man(in the house) house(with the telescope)

Instead of generating 5 distinct parse trees, GLRParser generates a parse forest: a single tree with some alternative sub-trees, similar to and/or trees. This representation isolates local ambiguities, prevents exponential growth of number of alternative parse trees.

To be able to parse above sentence we need a simple grammar (see simple.grm):

S -> NP VP 
S -> S PP
NP -> i 
NP -> the man
NP -> the telescope 
NP -> the house 
NP -> NP PP 
PP -> in NP 
PP -> with NP
VP -> saw NP

And we write the following short program to load the grammar and parse the sentence:

from GLRParser import Parser, ParseError, GrammarError
parser = Parser()
try:
    parser.parse_grammar("GLRParser/grm/simple.grm")
    sent = "i saw the man in the house with the telescope"

    parser.compile()
    parser.parse(sent)
    tree = parser.make_tree()
    
    print(tree.pformat())
except ParseError as pe:
    print(pe)
except GrammarError as ge:
    print(ge)

it produces the following parse forest:

S(
    S(
        S(
            NP(i)
            VP(
                saw
                NP(the man)
            )
        )
        PP(
            in
            NP(the house)
        )
    |
        NP(i)
        VP(
            saw
            NP(
                NP(the man)
                PP(
                    in
                    NP(the house)
                )
            )
        )
    )
    PP(
        with
        NP(the telescope)
    )
|
    S(
        NP(i)
        VP(
            saw
            NP(the man)
        )
    )
    PP(
        in
        NP(
            NP(the house)
            PP(
                with
                NP(the telescope)
            )
        )
    )
|
    NP(i)
    VP(
        saw
        NP(
            NP(
                NP(the man)
                PP(
                    in
                    NP(the house)
                )
            )
            PP(
                with
                NP(the telescope)
            )
        |
            NP(the man)
            PP(
                in
                NP(
                    NP(the house)
                    PP(
                        with
                        NP(the telescope)
                    )
                )
            )
        )
    )
)