Re: Finding out when a token is consumed

[Hans Aberg]

At 02:26 +0200 2003/05/09, Frank Heckenbach wrote:
>> Unless you try integrate this somehow into the grammar, such things are
>> very difficult to handle with Bison as the generated parser (as you say)
>> may or may not make use of the lookahead. The problem here is that you say
>> that this stuff can be inserted anywhere, which is essentially saying that
>> you do not have a language ruled by a grammar.
>
>It is ruled by a grammar -- but this grammer is not nice (as shown
>in my first example), so I try to avoid doing it this way.

We still do not get to know say whether this is a language given to you, or
whether the examples you have are just your own experimenting with
designing a grammar.

>However, that's nothing unusual, I think. Many grammars bison is
>used for are not really context free (identifier names etc.). But
>that's no real obstacle -- one just checks these things in the
>semantic actions, i.e. outside of the parser.

The unusual is that we do not get to know if this language you are working
with has a given grammar or whether it just has the ability to throw in
directives anywhere, as you claim. In the latter case, the hope diminishes
rapidly.

In the case of context sensitives, often these pass with some tweaks, but
not always: It depends on the language.

>Even hairier things are possible with lexical tie-ins (as described
>in the Bison manual!). (BTW, the example given there could also be
>described by a grammar, by lexing `a1b' as a special token which is
>"an identifier or a hex number" and which is accepted in both
>contexts in the grammer, doing some trickery with the semantic
>value; maybe it will be necessary to duplicate all rules and
>nonterminals that are part of expressions; perhaps it will even
>create some conflicts. It's possible, sure, but whether it's nice to
>do in practice, doubtful ...)

The difference here is that these are some localize, well defined, features
which can be handled by special tricks. You are asking for something else,
fuzzy directives that can be thrown in anywhere.

>In a theoretical sense, it might be cleaner to put all such things
>in a proper grammar (even if it causes some conflicts and might even
>require a more general and less efficient parsing method). In
>practice, it's probably better to use an efficient LALR(1) parser
>for the most part, and do the ugly bits outside of the parser. My
>question was only about how to interface it to the parser in the
>least painful way ...

It is difficult to make such interfacing, especially when there is no way
to identify the interfacing segments. If you want to say implement
operators with dynamic precedents, then this can be done by writing Bison
rules that make the save the expression components in a stack, and then
write a special program that sorts out how they should be combined. So here
one is saving the semantics and sorts it out later. If you want to make use
of lexer context switches, you must make sure they do not clash with parser
lookaheads.

This your comment and the next...

>> You might experiment with grammars like:
>>
>> [...]
>
>Uhm, well, this is just what I tried in the examples I sent (t1.y
>and t2.y) and which had the problems I described.

...suggest that you are designing your own language where directives can be
thrown in just anywhere. This is a poor language design, because you do not
get semantics attached to parsing tree.

>I don't think this discussion is going anywhere since I seem to be
>repeating myself with the examples etc. Obviously, the answer to my
>initial question is no. Thanks for your time, anyway.

For general discussions on language design, you might try the newsgroup
comp.compilers.

  Hans Aberg