9 May 91 14:11:41 GMT

Related articles |
---|

Generating LR parsers from EBNF? dexter314159@qwest.net (Gary F. Goodman) (2006-04-03) |

Re: Generating LR parsers from EBNF? gene@abhost.us (Gene Wirchenko) (2006-04-17) |

Generating LR parsers from EBNF? S.R.Adams@ecs.southampton.ac.uk (Stephen Adams) (1991-05-07) |

Re: Generating LR parsers from EBNF? grass@ulysses.att.com (1991-05-09) |

Re: Generating LR parsers from EBNF? KARSTEN@tfl.dk (Karsten Nyblad, TFL, Denmark) (1991-05-10) |

Newsgroups: | comp.compilers |

From: | grass@ulysses.att.com (Judith Grass) |

Keywords: | LR(0), parse, bibliography, EBNF |

Organization: | AT&T Bell Labs |

References: | <29305.9105072033@pessoa.ecs.soton.ac.uk> |

Date: | 9 May 91 14:11:41 GMT |

This is a longish response containing a bibtex list of references...

*>> I have looked in several books and a couple of conference proceedings but*

*>> I have failed to find any references on generating LR parse tables*

*>> directly from an EBNF grammar. What I would like to know is:*

Research on this goes back to the mid-70's, but you'll find it mainly in

Canadian and European sources. It seems right now that there isn't a lot

being published about parser generators and parser theory, as supposedly

there isn't anything interesting to say anymore.

In general, a lot of theoretical work has been done on the direct

generation of elalr parsers from regular-right part grammars (EBNF), but

there are very few finished, working examples of them. Two I know of: my

own "Ryacc" parser generator (a prototype) and Compiler Resource, Inc.'s

Yacc++ (a product).

*>> 1. Are there any references?*

Tons. Try these:

@article {LA77,

author = "W. R. {LaLonde}",

title = "Regular Right part Grammars and Their Parsers",

journal = "CACM",

volume = 20,

number = 10,

pages = "731--741",

month = oct,

year = 1977}

@article {LA79,

author = "W. R. {LaLonde}",

title = "Constructing {LR} Parsers for Regular Right part Grammars",

journal = AI,

volume = 11,

pages = "177--193",

year = 1979}

@article {PB,

author = "P. W. {Purdom, Jr.} and C. A. Brown",

title = "Parsing Extended {LR}(k) Grammars",

journal = AI,

volume = 15,

pages = "115--127",

year = 1981}

@article {CH,

author = "N. P. Chapman",

title = "{LALR}(1,1) Parser Generation for Regular Right Part Grammars",

journal = AI,

volume = 21,

pages = "29--45",

year = 1984}

@article {HEI,

author = "S. Heilbrunner",

title = "On the Definition of {ELR}(k) and {ELL}(k) Grammars",

journal = AI,

volume = 11,

pages = "169--176",

year = 1979}

@article {HEC,

author = "R. Heckmann",

title = "An Efficient {ELL}(1) Parser Generator",

journal = AI,

volume = 23,

pages = "127--148",

year = 1986}

@article {NS86,

author = "I. Nakata and M. Sassa",

title = "Generation of Efficient {LALR} Parsers for Regular Right

Part Grammars",

journal = AI,

volume = 23,

pages = "149--162",

year = 1986}

@article {NS87,

author = "I. Nakata and M. Sassa",

title = "A Simple Realization of {LR}-Parsers for Regular Right Part

Grammars",

journal = IPL,

volume = 24,

pages = "113--120",

year = 1987}

@inproceedings {GrKiSe,

author = "J. E. Grass, Chandra Kintala and Ravi Sethi",

title = "Object-oriented Redesign using {C++}",

booktitle = "Usenix {C++} Conference Proceedings",

pages = "75--86",

address= "San Francisco, CA",

month = "April",

year = 1990}

@unpublished {GR90.pub,

author = "J. E. Grass",

title = "A User's Guide to {Ryacc} (version 0.0):

A Parser Generator for Regular Right Part Grammars",

institution = BLTM,

note = "Available from author",

year = 1990}

*>> 2. Is the EBNF approach equivalent to the CFG one? Is*

*>> the difference in the tables always a due to small set*

*>> of `optimizations'?*

Since you can always rewrite an EBNF grammar as a BNF grammar, the

languages described are the same set. Not all EBNF grammars will directly

yield an ELALR parser (or ELR or ELL) because of some kinds of

non-determinism possible in the description. I am not sure that this is

the answer to the question you are asking, but...

*>> 3. Which is faster? The EBNF item sets are smaller but*

*>> more complex to handle. Using the EBNF approach seems*

*>> to reduce the need for `optimizing' the generated*

*>> table.*

*>From my experience, for the same language, the ELALR parser tends to be*

about 1/3 faster, simply because there are fewer states in the parser and

fewer "artificial" productions. The tables also are much smaller. The

tables still can be packed and optimized, but the techniques for doing so

have to be a bit different.

*>> 4. I only generated the LR(0) automaton by hand. I have*

*>> not thought about `higher' grammar categories like*

*>> LALR(1), LR(2), regular-LR etc. Are these kinds*

*>> easily generated using the EBNF method?*

ELALR(1), ELR(1), LL(1) are all known techniques. My guess is that doing

longer lookaheads is no problem, although I am not aware of anyone that

has actually tried it. The techniques should be about the same as is done

for LR(2) and such.

-- Judy Grass, AT&T Bell Labs, Murray Hill

grass@ulysses.att.com

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.