Re: SUMMARY: BNF definition (EBNF acceptance)

  > Although they can significantly improve the readability of the
  > grammar, they complicate the matter when it comes to parser or
  > code generation, so EBNF is generally unpopular in compilers
  > theory.


"Nathan K. Inada" <nathan@stc.com> writes:
> is this true? ...
>
> is EBNF unpopular to the compiler theorist but not compiler
> practitioner, maybe?


EBNF is great if you generate recursive-descent parsers, but wouldn't
affect conventional LL or LALR automaton-based parsers because they simply
convert EBNF to BNF and do the usual FSM boogie. Russell Quong, Hank
Dietz (both at Purdue) and I once considered how you could build an
LR-based FSM that took advantage of EBNF constructs, but didn't end up
anywhere with it.


Anyhoo, EBNF makes a difference for recursive-descent as the following
illustrates:


a : A a | ;


generates


a()
{
if ( LA(1)==A ) {
MATCH(A);
a();
}
}


which uses evil tail-recursion. The equivalent EBNF construct is easier
to read/debug and can be used to generate better code (PCCTS does this).


a : (A)* ;


results in


a()
{
while ( LA(1)==A ) {
MATCH(A);
}
}


Regards,
Terence of ``Dr. T's Traveling Parsing Revival''
--

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