Re: EBNF Parser generator information (RRPG reply)

reid@cherry.iss.nus.sg (Thomas Reid)
Tue, 2 Feb 1993 08:53:47 GMT

          From comp.compilers

Related articles
parser-generators for RRPGs dyck@cs.sfu.ca (Michael Dyck) (1993-01-28)
EBNF Parser generator information (RRPG reply) thutt@MAIL.CASI.NASA.GOV (thutt) (1993-01-29)
Re: EBNF Parser generator information (RRPG reply) reid@cherry.iss.nus.sg (1993-02-02)
| List of all articles for this month |

Newsgroups: comp.compilers
From: reid@cherry.iss.nus.sg (Thomas Reid)
Keywords: parse, tools
Organization: Institute of Systems Science, NUS, Singapore
References: 93-01-206 93-02-005
Date: Tue, 2 Feb 1993 08:53:47 GMT

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.
--


Post a followup to this message

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