Re: EBNF Parser generator information (RRPG reply)

I have followed the LL1 vs LALR vs EBNF debate waiting for someone to
mention that you do not have to convert your grammars to LL1 to do
recursive descent. You can construct a parser (automatically) directly
from EBNF. The best reference I have for doing it is Barrett, Bates,
Gustafson, and Couch "Compiler Construction - Theory and Practice, 2nd
Edition", pp. 167-173, with their description of grammar tree nodes
(gtns).


The basis is 1) you translate EBNF statements to gtns, 2) walk the gtns to
obtain first and follow sets, and 3) translate the augmented gtns to
procedures, one for each EBNF statement. You never see LL1. You can add
semantic actions naturally and by adding a four-tuple (attribute name, LHS
attached to, attribute data type, and an inherited/synthesized/local
indicator), you can automatically synthesize the formal and actual
procedure parameters.


With EBNF, you have ~3+ times fewer productions, the semantic actions are
clear and clean, and the resulting syntax-directed translator is readable.
Several translator classes and I have produced a TWS in Modula-2 based on
this style and it is elegant. Avoiding LL1 makes a recursive descent TWS
intuitive and enjoyable.
--

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