[DGD] parse_string efficiency

[Par Winzell]

Keith,

> I was wondering how efficient parse string is?  How
> well does it scale with more rules, more possible
> interpretations of rules.  I'm wondering because I'm
> writting a psuedo-natural language parser using
> parse_string(), and was wondering when I should start
> worrying about efficiency.

As Nino has already said, the single thing to really worry about is 
ambiguity. I suspect a grammar can be vast and still efficient if it is 
not ambiguous.

Once you go down the road of ambiguity though, things can get very 
scary. I believe you can get away with a few carefully constructed ones 
-- e.g. where there are two or three full parse trees, when all's said 
and done.

What can sink your process is when there's two or more ways for the 
parser to go in 'internal' nodes, i.e. where the number of possible 
parse trees take on the flavour of exponential growth. I've had this 
happen several times when doing (what seemed to me) fairly innocent 
modifications to my grammars.

I believe there are fairly straight-forward tools out of any standard 
computer science book on this subject that can be used to automatically 
check for ambiguity -- somebody should implement one.

Zell

_________________________________________________________________
List config page:  http://list.imaginary.com/mailman/listinfo/dgd