Re: DFA Lexer Generation From BNF

"Paul B Mann" <pbm@oct.net> writes:


> Does anyone know of a lexer generator whose input is a BNF grammar
> instead of regular expressions ?
>
> Paul Mann
>
> [DFA's aren't adequate to recognize BNF, which is why parser
> generators use a DFA and a stack or other more powerful machines. I
> suppose you could limit it to a BNF subset equivalent to regexps, but
> what would be the point? -John]


Perhaps, let me explain. Yacc++ allows one to write lexers in [E]BNF
grammars, i.e. yacc notation extended by regular expression operators.
In Yacc++, you can mix LR matching with regular expressions at either
the lexing or parsing level. However, if you are asking if it will
also collapse left-linear or right-linear grammars down to regular
expressions, it doesn't do that. If you use a recursive production,
Yacc++ uses a stack to resolve it. Now, it wouldn't be hard to
reconize the linear cases and transform them. However, I'm not aware
of any advantage to doing so, so yacc++ doesn't do it. In fact,
because of the difference in memory performance (one can use a fixed
sized memory (but one needs to "cons" the output list when desired
immediately) if one has no right recursion), I would be cautious and
make it an optional feature even if it were to be done.


Are you thinking of using BNF based lexers?


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

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