<jupyter_start><jupyter_text>Python Parsing with NLTK **(C) 2017-2021 by [<NAME>](http://damir.cavar.me/)** **Download:** This and various other Jupyter notebooks are available from my [GitHub repo](https://github.com/dcavar/python-tutorial-notebooks). **License:** [Creative Commons Attribution-ShareAlike 4.0 International License](https://creativecommons.org/licenses/by-sa/4.0/) ([CA BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/)) This is a tutorial related to the discussion of grammar engineering and parsing in the class *Alternative Syntactic Theories* and *Advanced Natural Language Processing* taught at Indiana University in Spring 2017, Fall 2018 and 2020.  Working with Grammars The following examples are taken from the NLTK [parsing HOWTO](http://www.nltk.org/howto/parse.html) page.<jupyter_code>from nltk import Nonterminal, nonterminals, Production, CFG
nt1 = Nonterminal('NP')
nt2 = Nonterminal('VP')
nt1.symbol()
nt1 == Nonterminal('NP')
nt1 == nt2
S, NP, VP, PP = nonterminals('S, NP, VP, PP')
print(S.symbol())
N, V, P, DT = nonterminals('N, V, P, DT')
prod1 = Production(S, [NP, VP])
prod2 = Production(NP, [DT, NP])
prod1.lhs()
prod1.rhs()
prod1 == Production(S, [NP, VP])
prod1 == prod2
grammar = CFG.fromstring("""
 S -> NP VP
 PP -> P NP
 PP -> P NP
 NP -> 'the' N | N PP | 'the' N PP
 NP -> D N
 D -> 'a'
 VP -> V NP | V PP | V NP PP
 N -> 'cat'
 N -> 'fish'
 N -> 'aligator'
 N -> 'dog'
 N -> 'rug'
 N -> 'mouse'
 V -> 'chased'
 V -> 'sat'
 P -> 'in'
 P -> 'on'
""")
print(grammar)<jupyter_output>Grammar with 21 productions (start state = S)
    S -> NP VP
    PP -> P NP
    PP -> P NP
    NP -> 'the' N
    NP -> N PP
    NP -> 'the' N PP
    NP -> D N
    D -> 'a'
    VP -> V NP
    VP -> V PP
    VP -> V NP PP
    N -> 'cat'
    N -> 'fish'
    N -> 'aligator'
    N -> 'dog'
    N -> 'rug'
    N -> 'mouse'
    V -> 'chased'
    V -> 'sat'
    P -> 'in'
    P -> 'on'<jupyter_text>Feature Structures One can build complex feature structures using the following strategies:<jupyter_code>import nltk

fstr = nltk.FeatStruct("[POS='N', AGR=[PER=3, NUM='pl', GND='fem']]")
print(fstr)<jupyter_output>[       [ GND = 'fem' ] ]
[ AGR = [ NUM = 'pl'  ] ]
[       [ PER = 3     ] ]
[                       ]
[ POS = 'N'             ]<jupyter_text>Creating shared paths is also possible:<jupyter_code>fstr2 = nltk.FeatStruct("""[NAME='Lee', ADDRESS=(1)[NUMBER=74, STREET='rue Pascal'],
                          SPOUSE=[NAME='Kim', ADDRESS->(1)]]""")
print(fstr2)<jupyter_output>[ ADDRESS = (1) [ NUMBER = 74           ] ]
[               [ STREET = 'rue Pascal' ] ]
[                                         ]
[ NAME    = 'Lee'                         ]
[                                         ]
[ SPOUSE  = [ ADDRESS -> (1)  ]           ]
[           [ NAME    = 'Kim' ]           ]<jupyter_text>Let us create feature structures and try out unification:<jupyter_code>fs1 = nltk.FeatStruct("[AGR=[PER=3, NUM='pl', GND='fem'], POS='N']")
fs2 = nltk.FeatStruct("[POS='N', AGR=[PER=3, GND='fem']]")

print(fs1.unify(fs2))<jupyter_output>[       [ GND = 'fem' ] ]
[ AGR = [ NUM = 'pl'  ] ]
[       [ PER = 3     ] ]
[                       ]
[ POS = 'N'             ]<jupyter_text>Chart Parser The following examples are taken from the NLTK [parsing HOWTO](http://www.nltk.org/howto/parse.html) page.<jupyter_code>import nltk
nltk.parse.chart.demo(2, print_times=False, trace=1,
                       sent='I saw a dog', numparses=1)<jupyter_output>* Sentence:
I saw a dog
['I', 'saw', 'a', 'dog']

* Strategy: Bottom-up

|.    I    .   saw   .    a    .   dog   .|
|[---------]         .         .         .| [0:1] 'I'
|.         [---------]         .         .| [1:2] 'saw'
|.         .         [---------]         .| [2:3] 'a'
|.         .         .         [---------]| [3:4] 'dog'
|>         .         .         .         .| [0:0] NP -> * 'I'
|[---------]         .         .         .| [0:1] NP -> 'I' *
|>         .         .         .         .| [0:0] S  -> * NP VP
|>         .         .         .         .| [0:0] NP -> * NP PP
|[--------->         .         .         .| [0:1] S  -> NP * VP
|[--------->         .         .         .| [0:1] NP -> NP * PP
|.         >         .         .         .| [1:1] Verb -> * 'saw'
|.         [---------]         .         .| [1:2] Verb -> 'saw' *
|.         >         .         .         .| [1:1] VP -> * Verb NP
|.         >         .         .         .| [1:1] VP -> * Verb
|.         [--------->[...]<jupyter_text>This is an example how to apply top-down parsing:<jupyter_code>nltk.parse.chart.demo(1, print_times=True, trace=0,
                       sent='she killed the man with the tie', numparses=2)<jupyter_output>* Sentence:
she killed the man with the tie
['she', 'killed', 'the', 'man', 'with', 'the', 'tie']

* Strategy: Top-down<jupyter_text>This is how to apply bottom-up parsing:<jupyter_code>nltk.parse.chart.demo(2, print_times=False, trace=0,
                       sent='I saw John on the roof', numparses=2)
nltk.parse.featurechart.demo(print_times=False,
                              print_grammar=True,
                              parser=nltk.parse.featurechart.FeatureChartParser,
                              sent='I saw John with a dog')<jupyter_output>Grammar with 18 productions (start state = S[])
    S[] -> NP[] VP[]
    PP[] -> Prep[] NP[]
    NP[] -> NP[] PP[]
    VP[] -> VP[] PP[]
    VP[] -> Verb[] NP[]
    VP[] -> Verb[]
    NP[] -> Det[pl=?x] Noun[pl=?x]
    NP[] -> 'John'
    NP[] -> 'I'
    Det[] -> 'the'
    Det[] -> 'my'
    Det[-pl] -> 'a'
    Noun[-pl] -> 'dog'
    Noun[-pl] -> 'cookie'
    Verb[] -> 'ate'
    Verb[] -> 'saw'
    Prep[] -> 'with'
    Prep[] -> 'under'

* FeatureChartParser
Sentence: I saw John with a dog
|.I.s.J.w.a.d.|
|[-] . . . . .| [0:1] 'I'
|. [-] . . . .| [1:2] 'saw'
|. . [-] . . .| [2:3] 'John'
|. . . [-] . .| [3:4] 'with'
|. . . . [-] .| [4:5] 'a'
|. . . . . [-]| [5:6] 'dog'
|[-] . . . . .| [0:1] NP[] -> 'I' *
|[-> . . . . .| [0:1] S[] -> NP[] * VP[] {}
|[-> . . . . .| [0:1] NP[] -> NP[] * PP[] {}
|. [-] . . . .| [1:2] Verb[] -> 'saw' *
|. [-> . . . .| [1:2] VP[] -> Verb[] * NP[] {}
|. [-] . . . .| [1:2] VP[] -> Verb[] *
|. [-> . . . .| [1:2] VP[] -> VP[] * PP[] {}
|[---] . . . .| [0:2] S[] ->[...]<jupyter_text>Loading grammars from files and editing them We will need the following NLTK modules in this section:<jupyter_code>import nltk
from nltk import CFG
from nltk.grammar import FeatureGrammar as FCFG<jupyter_output><empty_output><jupyter_text>We can load a *grammar* from a file, that is located in the same folder as the current Jupyter notebook, in the following way:<jupyter_code>cfg = nltk.data.load('spanish1.cfg')
print(cfg)<jupyter_output>Grammar with 31 productions (start state = S)
    S -> SN SV
    SV -> v SN
    SV -> v
    SN -> det GN
    GN -> nom_com
    GN -> nom_prop
    det -> 'el'
    det -> 'la'
    det -> 'los'
    det -> 'las'
    det -> 'un'
    det -> 'una'
    det -> 'unos'
    det -> 'unas'
    nom_com -> 'vecino'
    nom_com -> 'ladrones'
    nom_com -> 'mujeres'
    nom_com -> 'bosques'
    nom_com -> 'noche'
    nom_com -> 'flauta'
    nom_com -> 'ventana'
    nom_prop -> 'Jose'
    nom_prop -> 'Lucas'
    nom_prop -> 'Pedro'
    nom_prop -> 'Marta'
    v -> 'toca'
    v -> 'moja'
    v -> 'adoran'
    v -> 'robaron'
    v -> 'escondieron'
    v -> 'rompió'<jupyter_text>We instantiate a ChartParser object with this grammar:<jupyter_code>cp1 = nltk.parse.ChartParser(cfg)<jupyter_output><empty_output><jupyter_text>The *ChartParser* object has a parse-function that takes a list of tokens as a parameter. The token list can be generated using a language specific tokenizer. In this case we simply tokenize using the Python-function *split* on strings. The output of the parse function is a list of trees. We loop through the list of parse trees and print them out:<jupyter_code>"los mujeres adoran la Lucas".split()
for x in cp1.parse("los mujeres adoran la Lucas".split()):
    print(x)<jupyter_output>(S
  (SN (det los) (GN (nom_com mujeres)))
  (SV (v adoran) (SN (det la) (GN (nom_prop Lucas)))))<jupyter_text>We can also edit a grammar directly:<jupyter_code>cfg2 = CFG.fromstring("""
 S -> NP VP
 PP -> P NP
 NP -> 'the' N | N PP | 'the' N PP
 VP -> V NP | V PP | V NP PP
 N -> 'cat'
 N -> 'dog'
 N -> 'bird'
 N -> 'rug'
 N -> 'woman'
 N -> 'man'
 N -> 'tie'
 V -> 'chased'
 V -> 'killed'
 V -> 'sat'
 V -> 'bit'
 P -> 'in'
 P -> 'on'
 P -> 'with'
""")<jupyter_output><empty_output><jupyter_text>We parse our example sentences using the same approach as above:<jupyter_code>cp2 = nltk.parse.ChartParser(cfg2)
for x in cp2.parse("the cat chased the dog".split()):
    print(x)<jupyter_output>(S (NP the (N cat)) (VP (V chased) (NP the (N dog))))<jupyter_text>The previous example included a Context-free grammar. In the following example we load a Context-free Grammar with Features, instantiate a *FeatureChartParser*, and loop through the parse trees that are generated by our grammar to print them out:<jupyter_code>fcfg = nltk.data.load('spanish1.fcfg')
fcp1 = nltk.parse.FeatureChartParser(fcfg)
for x in fcp1.parse(u"Miguel adoró el gato".split()):
    print(x)<jupyter_output>(S[]
  (SN[+PROP, gen=?g, num='singular'] (NP[num='singular'] Miguel))
  (SV[num='singular', tiempo='pasado']
    (VT[num='singular', tiempo='pasado'] adoró)
    (SN[-PROP, gen='masculino', num='singular']
      (DET[gen='masculino', num='singular'] el)
      (NC[gen='masculino', num='singular'] gato))))<jupyter_text>We can edit a Feature CFG in the same way directly in this notebook and then parse with it:<jupyter_code>fcfg2 = FCFG.fromstring("""
% start CP
# ############################
# Grammar Rules
# ############################
CP -> Cbar[stype=decl]
Cbar[stype=decl] -> IP[+TNS]
IP[+TNS] -> DP[num=?n,pers=?p,case=nom] VP[num=?n,pers=?p]
DP[num=?n,pers=?p,case=?k] ->  Dbar[num=?n,pers=?p,case=?k]
Dbar[num=?n,pers=?p] -> D[num=?n,DEF=?d,COUNT=?c] NP[num=?n,pers=?p,DEF=?d,COUNT=?c]
Dbar[num=?n,pers=?p] -> NP[num=?n,pers=?p,DEF=?d,COUNT=?c]
Dbar[num=?n,pers=?p,case=?k] -> D[num=?n,pers=?p,+DEF,type=pron,case=?k]
NP[num=?n,pers=?p,COUNT=?c] -> N[num=?n,pers=?p,type=prop,COUNT=?c]
VP[num=?n,pers=?p] -> V[num=?n,pers=?p,val=1]
VP[num=?n,pers=?p] -> V[num=?n,pers=?p,val=2] DP[case=acc]
PP -> P DP[num=?n,pers=?p,case=acc]
#PP -> P DP[num=?n,pers=?p,case=dat]
#
# ############################
# Lexical Rules
# ############################
D[-DEF,+COUNT,num=sg] -> 'a'
D[-DEF,+COUNT,num=sg] -> 'an'
D[+DEF] -> 'the'
D[+DEF,gen=f,num=sg,case=nom,type=pron] -> 'she'
D[+DEF,gen=m,num=sg,case=nom,type=pron] -> 'he'
D[+DEF,gen=n,num=sg,type=pron] -> 'it'
D[+DEF,gen=f,num=sg,case=acc,type=pron] -> 'her'
D[+DEF,gen=m,num=sg,case=acc,type=pron] -> 'him'
N[num=sg,pers=3,type=prop] -> 'John' | 'Sara' | 'Mary'
V[tns=pres,num=sg,pers=3,val=2] -> 'loves' | 'calls' | 'sees' | 'buys'
N[num=sg,pers=3,-COUNT] -> 'furniture' | 'air' | 'justice'
N[num=sg,pers=3] -> 'cat' | 'dog' | 'mouse'
N[num=pl,pers=3] -> 'cats' | 'dogs' | 'mice'
V[tns=pres,num=sg,pers=3,val=1] -> 'sleeps' | 'snores'
V[tns=pres,num=sg,pers=1,val=1] -> 'sleep' | 'snore'
V[tns=pres,num=sg,pers=2,val=1] -> 'sleep' | 'snore'
V[tns=pres,num=pl,val=1] -> 'sleep' | 'snore'
V[tns=past,val=1] -> 'slept' | 'snored'
V[tns=pres,num=sg,pers=3,val=2] -> 'calls' | 'sees' | 'loves'
V[tns=pres,num=sg,pers=1,val=2] -> 'call' | 'see' | 'love'
V[tns=pres,num=sg,pers=2,val=2] -> 'call' | 'see' | 'love'
V[tns=pres,num=pl,val=2] -> 'call' | 'see' | 'love'
V[tns=past,val=2] -> 'called' | 'saw' | 'loved'
""")<jupyter_output><empty_output><jupyter_text>We can now create a parser instance and parse with this grammar:<jupyter_code>fcp2 = nltk.parse.FeatureChartParser(fcfg2, trace=1)
sentence = "John buys a furniture"
result = list(fcp2.parse(sentence.split()))
if result:
    for x in result:
        print(x)
else:
    print("*", sentence)<jupyter_output>|.Joh.buy. a .fur.|
|[---]   .   .   .| [0:1] 'John'
|.   [---]   .   .| [1:2] 'buys'
|.   .   [---]   .| [2:3] 'a'
|.   .   .   [---]| [3:4] 'furniture'
|[---]   .   .   .| [0:1] N[num='sg', pers=3, type='prop'] -> 'John' *
|[---]   .   .   .| [0:1] NP[COUNT=?c, num='sg', pers=3] -> N[COUNT=?c, num='sg', pers=3, type='prop'] *
|[---]   .   .   .| [0:1] Dbar[num='sg', pers=3] -> NP[COUNT=?c, DEF=?d, num='sg', pers=3] *
|[---]   .   .   .| [0:1] DP[case=?k, num='sg', pers=3] -> Dbar[case=?k, num='sg', pers=3] *
|[--->   .   .   .| [0:1] IP[+TNS] -> DP[case='nom', num=?n, pers=?p] * VP[num=?n, pers=?p] {?k2: 'nom', ?n: 'sg', ?p: 3}
|.   [---]   .   .| [1:2] V[num='sg', pers=3, tns='pres', val=2] -> 'buys' *
|.   [--->   .   .| [1:2] VP[num=?n, pers=?p] -> V[num=?n, pers=?p, val=2] * DP[case='acc'] {?n: 'sg', ?p: 3}
|.   .   [---]   .| [2:3] D[+COUNT, -DEF, num='sg'] -> 'a' *
|.   .   [--->   .| [2:3] Dbar[num=?n, pers=?p] -> D[COUNT=?c, DEF=?d, num=?n] * NP[COUNT=?c, DEF=?d, num=?n, pers[...]
{'fraction_non_alphanumeric': 0.2332174584781769, 'fraction_numerical': 0.016145229818462725, 'mean_word_length': 2.5458778416872088, 'pattern_counts': {'":': 0, '<': 54, '<?xml version=': 0, '>': 239, 'https://': 3, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '16', 'dir': 'jupyter-structured-clean-dedup', 'id': '75445', 'license': 'MIT', 'n_tokens_mistral': 5565, 'n_tokens_neox': 5309, 'n_words': 1172, 'path': 'Data Science and Machine Learning/Thorough Python Data Science Topics/Python Parsing with NLTK.ipynb', 'repo_name': 'okara83/Becoming-a-Data-Scientist', 'size': '12950'}