|A big easy subset of the CFGs email@example.com (Matt Timmermans) (1998-06-18)|
|Re: A big easy subset of the CFGs firstname.lastname@example.org (1998-06-19)|
|Re: A big easy subset of the CFGs email@example.com (Chris F Clark) (1998-06-19)|
|Re: A big easy subset of the CFGs firstname.lastname@example.org (Matt Timmermans) (1998-06-24)|
|Re: A big easy subset of the CFGs email@example.com (Salvador Valerio Cavadini) (1998-06-24)|
|Re: A big easy subset of the CFGs firstname.lastname@example.org (Chris Clark USG) (1998-07-01)|
|From:||email@example.com (Dennis Mickunas,297D,3336351,0000000)|
|Date:||19 Jun 1998 12:53:48 -0400|
|Organization:||University of Illinois at Urbana-Champaign|
|Keywords:||parse, bibliography, question|
"Matt Timmermans" <firstname.lastname@example.org> 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 , Williams' Bounded-Context Parsable (BCP) method , Culik
& Cohen's LR-Regular method , Szymanski's LR(k,infinity) and Finite
Phrase Finding Automaton Parsable (FPFAP(k)) methods , Fischer's
Synchronous Parsing Machines (SPM) method , Tai's Noncanonical SLR
(NSLR) and Leftmost Noncanonical SLR (LSLR) methods , and finally,
Schell's Generalized Piecewise LR (GPLR) method . In particular,
Tai's TOPLAS paper provides a very readable presentation of the
 Colmerauer, A., "Total precedence relations," _JACM 17_, 1 (1970).
 Williams, J. H., "Bounded context parsable grammars," _Information
and Control_, 28 (1975).
 Culik, K. and R. Cohen, "LR - regular grammars - an extension of
LR(k) grammars," _JCSS 7_, 1 (1973).
 Szymanski, T. G., "Generalized bottom-up parsing," PhD Thesis,
Computer Science Department, Cornell University, Technical
Report TR 73-168, Ithaca, New York (1973).
 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).
 Tai, K. C., "Noncanonical SLR(1) grammars," _TOPLAS 1_, 2 (1979).
 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
email@example.com (217) 333-6351
Return to the
Search the comp.compilers archives again.