|right context in scanner generators (was Re: LEX and YACC) email@example.com (1989-11-12)|
|Re: right context in scanner generators (was Re: LEX and YACC) firstname.lastname@example.org (1989-11-12)|
|Re: right context in scanner generators (was Re: LEX and YACC) email@example.com (1989-11-13)|
|Re: right context in scanner generators (was Re: LEX and YACC) firstname.lastname@example.org (1989-11-13)|
|Date:||Mon, 13 Nov 89 12:02:25 EST|
|From:||email@example.com (Vern Paxson)|
|Organization:||Cornell Univ. CS Dept, Ithaca NY|
In article <1989Nov12.firstname.lastname@example.org> email@example.com (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:
>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 Paxson firstname.lastname@example.org
Computer Science Dept. decvax!cornell!vern
Cornell University vern@LBL (bitnet)
[Vern is the author of flex. -John]
Return to the
Search the comp.compilers archives again.