19 Jun 1998 12:53:48 -0400

Related articles |
---|

A big easy subset of the CFGs mtimmerm@microstara.com (Matt Timmermans) (1998-06-18) |

Re: A big easy subset of the CFGs mickunas@cs.uiuc.edu (1998-06-19) |

Re: A big easy subset of the CFGs cfc@world.std.com (Chris F Clark) (1998-06-19) |

Re: A big easy subset of the CFGs mtimmerm@microstar.no-spam.com (Matt Timmermans) (1998-06-24) |

Re: A big easy subset of the CFGs scavadini@hotmail.com (Salvador Valerio Cavadini) (1998-06-24) |

Re: A big easy subset of the CFGs clark@quarry.zk3.dec.com (Chris Clark USG) (1998-07-01) |

From: | mickunas@cs.uiuc.edu (Dennis Mickunas,297D,3336351,0000000) |

Newsgroups: | comp.compilers |

Date: | 19 Jun 1998 12:53:48 -0400 |

Organization: | University of Illinois at Urbana-Champaign |

References: | 98-06-104 |

Keywords: | parse, bibliography, question |

"Matt Timmermans" <mtimmerm@microstara.com> writes:

*>What I need is this:*

*>A subset of CFGs bigger than LR(1). In particular, it should include most*

*>of what you can do with LR(1)+lex, using characters as terminals.*

...

*>The idea is like LR(1), but rather than looking ahead a single token,*

*>it looks ahead a single non-terminal or terminal, i.e., "It must be*

*>possible to recognize a production without looking past the following*

*>term (in the rules in which it appears)". This meets the criteria,*

*>but produces an unwelcome effect in naive implementations -- the*

*>parser might not be able to recognize anything until it gets to the*

*>end of the input, at which point the last/deepest non-terminal gets*

*>reduced and causes a huge reduction cascade back to the beginning.*

*>I'm willing to live with that, because small reduction cascades are*

*>necessary to do LR(1)+lex, and I think I can get rid almost all large*

*>ones with a sufficiently clever implementation.*

*>This LR(term) idea is too obvious to be new. Does anyone know what*

*>it's really called?*

Such non-canonical parsing techniques have been around for some time.

Virtually all of them can be cast in the form of a two-stack parser.

These non-canonical techniques include Colmerauer's total precedence

method [1], Williams' Bounded-Context Parsable (BCP) method [2], Culik

& Cohen's LR-Regular method [3], Szymanski's LR(k,infinity) and Finite

Phrase Finding Automaton Parsable (FPFAP(k)) methods [4], Fischer's

Synchronous Parsing Machines (SPM) method [5], Tai's Noncanonical SLR

(NSLR) and Leftmost Noncanonical SLR (LSLR) methods [6], and finally,

Schell's Generalized Piecewise LR (GPLR) method [7]. In particular,

Tai's TOPLAS paper provides a very readable presentation of the

technique.

[1] Colmerauer, A., "Total precedence relations," _JACM 17_, 1 (1970).

[2] Williams, J. H., "Bounded context parsable grammars," _Information

and Control_, 28 (1975).

[3] Culik, K. and R. Cohen, "LR - regular grammars - an extension of

LR(k) grammars," _JCSS 7_, 1 (1973).

[4] Szymanski, T. G., "Generalized bottom-up parsing," PhD Thesis,

Computer Science Department, Cornell University, Technical

Report TR 73-168, Ithaca, New York (1973).

[5] Fischer, C. N., "On parsing context-free languages in a parallel

environment," PhD Thesis, Computer Science Department, Cornell

University, Technical Report TR 75-237, Ithaca, New York (1975).

[6] Tai, K. C., "Noncanonical SLR(1) grammars," _TOPLAS 1_, 2 (1979).

[7] Schell, R. M., "Methods for constructing parallel compilers for use

in a multiprocessor environment," PhD Thesis, Department of

Computer Science, University of Illinois at Urbana-Champaign,

Technical Report UIUCDCS-79-958, Urbana, Illinois (1979).

--

M. Dennis Mickunas

Department of Computer Science 1304 W. Springfield Ave.

University of Illinois Urbana, Illinois 61801

mickunas@cs.uiuc.edu (217) 333-6351

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.