Re: A big easy subset of the CFGs

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

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