Re: Parsing wars (Dennis Mickunas)
Thu, 10 Sep 1992 20:40:14 GMT

          From comp.compilers

Related articles
[2 earlier articles]
Re: Parsing wars (1992-09-02)
Re: Parsing wars (1992-09-02)
Re: Parsing wars (1992-09-03)
Re: Parsing wars jar@cheops.HQ.Ileaf.COM (1992-09-05)
Re: Parsing wars (1992-09-08)
Re: Parsing wars (1992-09-09)
Re: Parsing wars (1992-09-10)
Re: Parsing wars (1992-09-13)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Dennis Mickunas)
Organization: University of Illinois, Dept. of Comp. Sci., Urbana, IL
Date: Thu, 10 Sep 1992 20:40:14 GMT
References: 92-09-006 92-09-051
Keywords: parse, LR(1), bibliography 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

Post a followup to this message

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