[DGD] Re: Parse String and Virtual Objects

[Par Winzell]

S. Foley writes:

 > This function really isn't too hard to figure out, though the effort 
 > required is something north of 'none'.  I have no formal training in the 
 > computer sciences or any programming language and through a combination of 
 > the list archives, web searches on grammars, and trial and error use of the 
 > actual function, I was able to figure it out (and as bulbs go, I'm not 
 > particularly bright ;) ).

I agree that you can get a pretty good idea of what it does by just
staring at examples long enough. The problem comes when you exceed a
certain level of complexity in your grammars. If there are many ways
to correctly parse a given string with a grammar, parsing takes more
and more time. It takes some real work to keep this from happening to
a complex grammar. It also gets real bad real fast for a lot of cases
that look very innocent.

The C language has a classic case of fairly simple ambiguity --

	if (E1) if (E2) S1; else S2;

has two legitimate parsings:

	if (E1) {
		if (E2) {
			S1;
		} else {
			S2;
		}
	}

OR

	if (E1) {
		if (E2) {
			S1;
		}
	} else {
		S2;
	}


A parser like YACC/BISON just picks one (the former, I think),
but parse_string() gives you the option of collecting them all.

The if if else ambiguity isn't so bad, but there are examples
that get very bad very fast...

... and now after writing all this, I don't remember if DGD does
or does not suffer a slow-down from an ambiguius grammar if it
is called without its third argument (which specifies how many
ambigously valid parse trees to return at each branch point).

Felix?




 > After making that kind of effort, you should be 
 > in a position to ask more specific questions about parse_string.  And, in 
 > general, the list is more responsive to specific questions, since they 
 > indicate that you've at least made some effort to understand things on your 
 > own, and beyond that, they don't require a veritable textbook to answer.

This is very true in general. In this case the question was a
plea for examples and reference material, which is understandable.

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