CykParse: Simple example 

Grammar (Chomsky normal form) 

1. S -> Noun VP   [1.0]
2. VP -> Verb Noun [0.5]
3. VP -> Modal Verb [0.5]
4. Modal -> can   [1]
5. Noun -> can    [0.3]
6. Noun -> fish   [0.3]
7. Noun -> people [0.4]
8. Verb -> can    [0.1]
9. Verb -> fish   [0.8]
8. Verb -> people [0.1]


Iterations of line 5
Create the following trees nodes (leaves)

i = 1
A. [Noun  | 1 | 1 | people | --- | --- | 0.4]
B. [Verb  | 1 | 1 | people | --- | --- | 0.1]

i = 2
C. [Modal | 2 | 2 | can    | --- | --- | 1 ]
D. [Noun  | 2 | 2 | can    | --- | --- | 0.3 ]
E. [Verb  | 2 | 2 | can    | --- | --- | 0.1 ]

i=3
F. [Noun  | 3 | 3 | fish   | --- | --- | 0.3 ]
G. [Verb  | 3 | 3 | fish   | --- | --- | 0.8 ]

Main loop (I show only iterations that create a node of non-zero probability)

length = 2
   i = 1
   j = 2
       M = VP
       Create node H. [VP | 1 | 2 | --- | --- | --- | 0.0]
          k = 1
              Rule = VP -> Verb Noun [0.5]
              Combination of B & D and prob. of rule has probability 0.015.
              Change H to be [VP | 1 | 2 | --- | B | D | 0.015]

   i = 2
   j = 3
       M = VP
       Create node I. [VP | 2 | 3 | --- | --- | --- | 0.0]
          k = 2
              Rule = VP -> Verb Noun [0.5]
              Combination of E & F and prob of rule has probability 0.015.
              Change I to be [VP | 2 | 3 | --- | E | F | 0.015]


              Rule = VP -> Modal Verb [0.5]
              Combination of C & G and prob of rule has probability 0.4.
              Change I to be [VP | 2 | 3 | --- | C | G | 0.4]

length = 3
   i = 1
   j = 3
       M=S
       Create node J. [S | 1 | 3 | --- | --- | --- | 0.0]
         k = 1.
            Rule = S -> Noun VP [1.0]
            Combination of A & I and prob. of rule has probability 0.16
            Change J to be [S | 1 | 3 | --- | A | I | 0.16]

Done.



Final Tree:

S 
   Noun people
   VP
      Modal can
      Verb  fish