Re: Parsing wars

dww@inf.fu-berlin.de writes:


>jar@cheops.HQ.Ileaf.COM (Jim Roskind x5570) writes [about "strange parsing"]


>>The conseqeunces of this extension are quite significant, and the
>>resulting parser engine provides a much larger class of parsers than LR
>>parsers. ...


>Oh yes, with backing up it seems you could parse a lot more languages
>like a^n b^n c^n ...


You can't quite get a^n b^n c^n with the straightforward 2-stack technique
that is suggested here. It *is* possible to get a proper subset of the
non-deterministic cfl's. For example, it is quite easy to obtain {a^n
b^n} U {a^n b^2n c}. Non-canonical techniques for parsing such languages
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
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
Universiy, echnical 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
--

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