Exercices 03

Consider the following grammar:

S' → S EOF

S → s

S → i c S

S → i c S e S

Parse the following string: “icicses” using Earley parsing (show the list of sets of items you get until the string is recognized).
How many parses did you get?

Solution:

$S(0)=\{(S'\rightarrow .SEOF,0),(S\rightarrow.s,0),(S\rightarrow.icS,0),(S\rightarrow.icSeS,0)\}$
$S(1)=\{(S\rightarrow i.cS,0),(S\rightarrowi.cSeS,0)\}$
$S(2)=\{(S\rightarrow ic.S,0),(S\rightarrow ic.SeS,0),(S\rightarrow .s,2),(S\rightarrow .icS,2),(S\rightarrow .icSeS,2)\}$
$S(3)=\{(S\rightarrow i.cS,2),(S\rightarrow i.cSeS,2)\}$
$S(4)=\{(S\rightarrow ic.S,2),(S\rightarrow ic.SeS,2),(S\rightarrow s.,4),(S\rightarrow .icS,4),(S\rightarrow .icSeS,4)\}$
$S(5)=\{(S\rightarrow s.,4),(S\rightarrow icS.,2),(S\rightarrow icS.eS,2),(S\rightarrow icS.es, 0)\}$
$S(6)=\{S\rightarrow icSe.S,0),(S\rightarrow icSe.S,2),(S\rightarrow s.,6),(S\rightarrow .icS,6),(S\rightarrow .icSeS,6)\}$
$S(7)=\{(S\rightarrow s.,6),(S\rightarrow icSeS.,0),(S\rightarrow icSeS.,2),(S\rightarrow icS.,0),(S\rightarrow icS.eS,0),$
$(S\rightarrow icS.,0),(S\rightarrow ic.SeS,0)\}$

We get 2 parse trees.