Re: right context in scanner generators (was Re: LEX and YACC)

In article <1989Nov12.041025.12451@esegue.segue.boston.ma.us> boehm@flora.rice.edu (Hans Boehm) writes:
>A number of scanner generators, including lex, make the claim that
>they can handle regular expressions specifying right context.
>However, as was pointed out to me by a student in a compiler class
>I was teaching, the implementation that lex uses (namely that described
>in the Aho and Ullman text) is wrong. (I believe the same bug exists
>in Aho, Sethi, and Ullman, but I don't have a copy handy at the moment.)
>An example is:
>
>(a|ab)/ba
>
>on input "aba". Lex will consider "ab" to be the first token instead of "a".
>...
>Are there any scanner generators that actually
>do this right?


Note that flex kind of does this correctly--it allows x/y whenever it can
get it right, i.e., if either x or y have fixed length or if both are
variable length and the end of x will be unambiguous. It will correctly
match the above example. If the example is changed to "(a|ab)/ba*" then
it warns "Dangerous trailing context in rule at line <whatever>".


Vern


Vern Paxson vern@cs.cornell.edu
Computer Science Dept. decvax!cornell!vern
Cornell University vern@LBL (bitnet)
[Vern is the author of flex. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.