Sophie

Sophie

distrib > Mandriva > 2009.0 > i586 > by-pkgid > 8de1f55ea6a1a64d0f3f3ea116288458 > files > 61

happy-1.17-3mdv2009.0.i586.rpm


Example of a highly ambiguous grammar

It is a grammar taken from [1], although it is an example from the literature
(the draft paper didn't mention which source). 

There is an explosion of possibilities because many parse stacks need to be 
kept active. Inputs of sizes above 25 will get very expensive to parse, with
the current parser driver; but this seems no worse (if not better) than other 
implementations that produce a packed forest.


---

"make run" to run the test case.

For Hugs, load up Hugs.lhs - it doesn't produce graphs, and has easy entry 
point "test :: String -> IO ()

---

[1]   "Generalised LR Parsing in Haskell"
      Joao Fernandes, Joao Saraiva, and Joost Visser
      Universidade do Minho, Braga, Portugal
      submitted to AFP'04 summer school