Re: DFA Lexer Generation From BNF

Chris F Clark <>
Sun, 11 Nov 2007 17:15:14 -0500

          From comp.compilers

Related articles
Code generation from AST (Lucas S. Silva) (2007-11-10)
DFA Lexer Generation From BNF (Paul B Mann) (2007-11-10)
Re: DFA Lexer Generation From BNF (Chris F Clark) (2007-11-11)
Re: DFA Lexer Generation From BNF gneuner2/@/ (George Neuner) (2007-11-12)
Re: DFA Lexer Generation From BNF (Paul B Mann) (2007-11-16)
Re: DFA Lexer Generation From BNF (Robert A Duff) (2007-11-16)
Re: DFA Lexer Generation From BNF (2007-11-17)
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers
Date: Sun, 11 Nov 2007 17:15:14 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 07-11-033 07-11-038
Keywords: lex, parse
Posted-Date: 15 Nov 2007 18:49:37 EST

"Paul B Mann" <> 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 Clark Internet :
Compiler Resources, Inc. Web Site :
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

Post a followup to this message

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