Re: Non-greedy wildcard possible? (Long)

[Laurence Finston]

On Mon, 17 May 2004, Frank Heckenbach wrote:

> Laurence Finston wrote:
>
> > > Sure, that's not a problem. What it means semantically isn't fixed,
> > > though. (Just think of binary vs. unary minus, for example.)
> >
> > Binary vs. unary plus and minus are context-dependencies.  In order to make
> > them work in Bison, it's necessary to use the `%prec' feature, as described 
> > in
> > the manual.
>
> No, it's not:
>

I stand corrected.

>

> > I've found that it doesn't really pay to use Flex when one is using Bison,
> > since in this case, the scanner mostly just returns tokens to yyparse().
>
> Uhm, well, that's the purpose of a scanner, isn't it?
>

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. In
addition, I believe it would have
been harder to implement certain features using Flex that I've
now implemented in my scanner.

> To me the main advantage of (f)lex is the ability to match several
> regexes in parallel. If done one-by-one using a simple regex
> facility, it would be much slower. Of course, if R1, R2 ... Rn are
> your token regexes, you could match `(R1)|(R2)|...|(Rn)' and check
> the parenthesized expressions (\1, \2, ...) to find out which one
> matched. That's roughly what (f)lex does internally.

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.

>
> > > The documents I'm trying to parse can certainly be described
> > > with context-free grammars (I've tried to explain how, but I guess I
> > > haven't been quite clear). The problem is either (1) analyzing the
> > > input-grammar in order to produce a wildcard that doesn't contain any
> > > relevant terminating tokens, or (2) making Bison handle an ambiguous
> > > grammar.
> >
> > An ambiguous context-free grammar is invalid.
>
> 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.

Laurence