Re: Non-greedy wildcard possible? (Long)

[Frank Heckenbach]

Laurence Finston wrote:

> I've found that it's worthwhile to use Flex when the actions perform
> more complicated processing and when there's no need to perform the
> kind of parsing Bison does.  I also found that simply putting together
> tokens and returning them doesn't require the power of Flex.

Depends on what tokens are. If they are simply sequences of
characters from some class, flex might be overkill. If the length of
the sequence depends on the content (say, `=', `>' and `>=') or
tokens have a more complicated structure (say, floating point
notation), regexes can be handy. OTOH, there are cases (such as
Magnus' perhaps) where regexes are not even sufficient ...

> The main reason I stopped using it was that it swallowed look-ahead
> tokens.  I don't know why, and it seemed like too much trouble to find
> out, so I'm not claiming that it's a bug in Flex.

I'm not sure exactly what you mean. flex has no concept of
look-ahead tokens -- it just delivers tokens one by one. Do you mean
look-ahead characters? Or do you mean that the contents of yytext
get overwritten if you don't strdup() them? (A common problem, but
not a bug.)

> > Not at all. General CFGs can be vastly ambiguous. In LALR parsing
> > you have to deal with ambiguities. GLR parsing, OTOH, can deal with
> > arbitrary CFGs, though at the cost of possibly exponential time and
> > space if the ambiguities are not localized.
> 
> Again, I stand corrected.  I meant "invalid" in the sense that Bison
> wouldn't be able to generate a parser that functions and produces
> correct results. To my way of thinking, "dealing with ambiguities"
> implies resolving them, i.e., making the grammar unambiguous, for
> example, by resolving shift/reduce conflicts by always shifting.
> I also think that an ambiguous set of parsing rules might represent
> a _class_ of grammars but not a single grammer.
> However, I haven't studied this subject, so perhaps I'm using the
> terminology incorrectly.

The grammar, and also the language, are still well-defined, but the
set of possible parsings for some inputs may be ambiguous -- which
matters, of course, for semantic values. In GLR, such cases can be
resolved using `dprec'. (But that's not always necessary when using
GLR. Sometimes GLR in effect just provides for larger look-ahead, so
grammars that are unambiguous, but not LALR(k) can be parsed.)

Frank

-- 
Frank Heckenbach, address@hidden
http://fjf.gnu.de/
GnuPG and PGP keys: http://fjf.gnu.de/plan (7977168E)