demo_output.txt

   1 Parsing non-context-free languages
   2
   3 EXAMPLE 1: L4 {aⁿbⁿcⁿdⁿ : n∈ℕ}
   4 see https://secure.wikimedia.org/wikipedia/en/wiki/Context-sensitive_grammar
   5   TreeAdjoiningGrammar with 2 productions
   6    (S )
   7    (S.N a (S b *S.N c) d)
   8
   9   parsing 'aaabbbcccddd':
  10     (S a (S a (S a (S b (S b (S b (S ) c) c) c) d) d) d)
  11   parsing 'aaaabbbbccccdddd':
  12     (S a (S a (S a (S a (S b (S b (S b (S b (S ) c) c) c) c) d) d) d) d)
  13
  14
  15 EXAMPLE 2: Cross serial dependencies
  16 see http://www.let.rug.nl/~vannoord/papers/acl94/node5.html
  17   TreeAdjoiningGrammar with 11 productions
  18    (NP Jan)
  19    (NP Marie)
  20    (NP Piet)
  21    (V helpen)
  22    (V zag)
  23    (S.N (S.O NP (VP (V ))) V)
  24    (V leren)
  25    (V zwemmen)
  26    (NP (D de) (N kinderen))
  27    (S.N NP (VP *S.N V))
  28    (S.N (S.O NP (VP *S.N (V ))) V)
  29
  30   parsing 'Jan Piet Marie de kinderen zag helpen leren zwemmen':
  31     (S (S (S (S (NP Jan) (VP (S (NP Piet) (VP (S (NP Marie) (VP (S (NP (D de) (N kinderen)) (VP (V ))) (V ))) (V ))) (V zag))) (V helpen)) (V leren)) (V zwemmen))
  32
  33
  34 Example 3: An ambiguous sentence
  35   TreeAdjoiningGrammar with 13 productions
  36    (D an)
  37    (N elephant)
  38    (N pajamas)
  39    (S NP VP)
  40    (D my)
  41    (NP D N)
  42    (PP P NP)
  43    (VP V NP)
  44    (NP I)
  45    (P in)
  46    (V shot)
  47    (NP *NP PP)
  48    (VP *VP PP)
  49
  50   parsing 'I shot an elephant in my pajamas':
  51     (S (NP I) (VP (VP (V shot) (NP (D an) (N elephant))) (PP (P in) (NP (D my) (N pajamas)))))
  52     (S (NP I) (VP (V shot) (NP (NP (D an) (N elephant)) (PP (P in) (NP (D my) (N pajamas))))))
  53
  54
  55 Performance testing results
  56 with a medium grammar: (104 productions, 16 nonterminals, 101 terminals
  57     tree depth  sentence length  NLTK's best  Prefix-Valid Earley  ratio    Standard Earley ratio
  58      4          3.08             1.00 ms      30.12 ms             29.98    25.19 ms        25.07
  59      5          3.65             1.24 ms      37.09 ms             29.79    31.50 ms        25.30
  60      6          4.34             1.54 ms      46.89 ms             30.45    39.39 ms        25.58
  61      7          4.76             1.80 ms      53.12 ms             29.52    44.63 ms        24.80
  62      8          5.26             2.19 ms      64.06 ms             29.28    53.65 ms        24.52
  63      9          5.44             2.48 ms      74.66 ms             30.15    63.10 ms        25.48
  64     10          5.97             2.84 ms      92.56 ms             32.55    76.28 ms        26.82
  65
  66 with a large grammar [ATIS] (5517 productions, 1473 terminals, 549 nonterminals):
  67     sentence length  NLTK's best  Prefix-Valid Earley  ratio   Standard Earley ratio
  68     11.4             1.37 s       515.7 s              376.05  459.9 s         335.32