Right nulled GLR parsers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Right nulled GLR parsers

Full text

Pdf (734 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 28 , Issue 4 (July 2006) table of contents

Pages: 577 - 618

Year of Publication: 2006

ISSN:0164-0925

Authors

Elizabeth Scott	Royal Holloway, University of London, United Kingdom
Adrian Johnstone	Royal Holloway, University of London, United Kingdom

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 93, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1146809.1146810 What is a DOI?

ABSTRACT

The right nulled generalized LR parsing algorithm is a new generalization of LR parsing which provides an elegant correction to, and extension of, Tomita's GLR methods whereby we extend the notion of a reduction in a shift-reduce parser to include right nulled items. The result is a parsing technique which runs in linear time on LR(1) grammars and whose performance degrades gracefully to a polynomial bound in the presence of nonLR(1) rules. Compared to other GLR-based techniques, our algorithm is simpler and faster.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. V. Aho , S. C. Johnson , J. D. Ullman, Deterministic parsing of ambiguous grammars, Communications of the ACM, v.18 n.8, p.441-452, Aug. 1975 [doi>10.1145/360933.360969]
	2	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	3	Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
	4	John Aycock , R. Nigel Horspool, Faster Generalized LR Parsing, Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, p.32-46, March 22-28, 1999
	5	Sylvie Billot , Bernard Lang, The structure of shared forests in ambiguous parsing, Proceedings of the 27th annual meeting on Association for Computational Linguistics, p.143-151, June 26-29, 1989, Vancouver, British Columbia, Canada [doi>10.3115/981623.981641]
	6	Peter T. Breuer , Jonathan P. Bowen, A PREttier compiler-compiler: generating higher-order parsers in C, Software—Practice & Experience, v.25 n.11, p.1263-1297, Nov. 1995 [doi>10.1002/spe.4380251106]
	7	Masaru Tomita , Harry C. Bunt, Recent Advances in Parsing Technology, Kluwer Academic Publishers, Norwell, MA, 1996
	8	DeRemer, F. L. 1969. Practical translators for LR(k) languages. Ph.D. thesis, Massachussetts Institute of Technology.
	9	Franklin L. DeRemer, Simple LR(k) grammars, Communications of the ACM, v.14 n.7, p.453-460, July 1971 [doi>10.1145/362619.362625]
	10	Dodd, C. and Maslov, V. 1995. http://compilers.iecc.com/comparch/article/95-03-044.
	11	Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
	12	Eggert, P. 2003. http://compilers.iecc.com/comparch/article/03-01-005.
	13	Graham, S. L. and Harrison, M. A. 1976. Parsing of general context-free languages. Adv. Comput. 14, 77--185.
	14	Dick Grune , Ceriel J. H. Jacobs, Parsing techniques: a practical guide, Ellis Horwood, Upper Saddle River, NJ, 1990
	15	Hanson, D. R. and Proebsting, T. A. 2003. A research C# compiler. Tech. Rep. MSR-TR-2003-32, Microsoft Research, Redmond, WA.
	16	Hays, D. 1967. Introductions to Computational Linguistics. Elsevier, New York.
	17	Edgar T. Irons, A syntax directed compiler for ALGOL 60, Communications of the ACM, v.4 n.1, p.51-55, Jan. 1961 [doi>10.1145/366062.366083]
	18	Adrian Johnstone , Elizabeth Scott, Generalised Recursive Descent parsing and Fellow-Determinism, Proceedings of the 7th International Conference on Compiler Construction, p.16-30, March 28-April 04, 1998
	19	A. Johnstone , E. Scott, Generalised Reduction Modified LR Parsing for Domain Specific Language Prototyping, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 9, p.282, January 07-10, 2002
	20	Johnstone, A. and Scott, E. 2003. Generalized regular parsers. In Proceedings of the Compiler Construction, 12th International Conference, CC'03, G. Hedin, ed. LNCS, vol. 2622. Springer Berlin, 232--246.
	21	Johnstone, A., Scott, E., and Economopoulos, G. 2004a. Generalized parsing: Some costs. In Proceedings of the Compiler Construction, 13th International Conference, CC'04, E. Duesterwald, ed. LNCS, vol. 2985. Springer Berlin, 89--103.
	22	Johnstone, A., Scott, E., and Economopoulos, G. 2004b. The grammar tool box: A case study comparing GLR parsing algorithms. In Proceedings of the 4th Workshop on Language Descriptions, Tools and Applications LDTA2004, G. Hedin and E. V. Wick, eds. Also in Electronic Notes in Theoretical Computer Science. Elsevier, New York.
	23	Kasami, T. 1965. An efficient recognition and syntax analysis algorithm for context-free languages. Tech. Rep. AFCRL-65-758, Air Force Cambridge Research Laboratory, Bedford, Mass.
	24	Knuth, D. E. 1965. On the translation of languages from left to right. Inf. Control 8, 6, 607--639.
	25	Bernard Lang, Deterministic Techniques for Efficient Non-Deterministic Parsers, Proceedings of the 2nd Colloquium on Automata, Languages and Programming, p.255-269, July 29-August 02, 1974
	26	P. M. Lewis, II , R. E. Stearns, Syntax-Directed Transduction, Journal of the ACM (JACM), v.15 n.3, p.465-488, July 1968 [doi>10.1145/321466.321477]
	27	McPeak, S. and Necula, G. 2004. Elkhound: A fast, practical GLR parser generator. In Proceedings of the Compiler Construction, 13th Internationl. Conference CC'04, E. Duesterwald, ed. LNCS. Springer, Berlin.
	28	Mark-Jan Nederhof, An optimal tabular parsing algorithm, Proceedings of the 32nd annual meeting on Association for Computational Linguistics, p.117-124, June 27-30, 1994, Las Cruces, New Mexico [doi>10.3115/981732.981749]
	29	Nederhof, M.-J. and Sarbo, J. J. 1996. Increasing the applicability of LR parsing. In Recent Advances in Parsing Technology, H.Bunt and M. Tomita, eds. Kluwer Academic, Amsterdam, the Netherlands, 35--57.
	30	Mark-Jan Nederhof , Giorgio Satta, Efficient tabular LR parsing, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.239-246, June 24-27, 1996, Santa Cruz, California [doi>10.3115/981863.981895]
	31	Nederhof, M.-J. and Satta, G. 2004. Tabular parsing. In Formal Languages and Applications, Studies in Fuzziness and Soft Computing 148, G. C.Martin-Vide, V.Mitrana, eds. Springer, New York, 529--549.
	32	Nozohoor-Farshi, R. 1991. GLR parsing for ε-grammars. In Generalized LR Parsing, M. Tomita, ed. Kluwer Academic, Amsterdam, the Netherlands, 60--75.
	33	Parr, T. J. 1996. Language Translation Using PCCTS and C++. Automata Publishing.
	34	Rekers, J. G. 1992. Parser generation for interactive environments. Ph.D. thesis, Universty of Amsterdam.
	35	Sakai, I. 1962. Syntax in universal translation. In Proceedings of the 1961 International Conference on Machine Translation of Languages and Applied Language Analysis. 593--608.
	36	Elizabeth Scott , Adrian Johnstone, Reducing non-determinism in right nulled GLR parsers, Acta Informatica, v.40 n.6, p.459-489, May 2004 [doi>10.1007/s00236-004-0137-z]
	37	Scott, E., Johnstone, A., and Hussain, S. S. 2000. Tomita-Style generalized LR parsers. Updated version. Tech. Rep. TR-00-12, Royal Holloway, University of London Dec.
	38	Sheil, B. 1976. Observations on context-free parsing. In Statistical Methods in Linguistics. 71--109.
	39	Bjarne Stroustrup, The design and evolution of C++, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
	40	Masaru Tomita, Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems, Kluwer Academic Publishers, Norwell, MA, 1985
	41	Stephen H. Unger, A global parser for context-free phrase structure grammars, Communications of the ACM, v.11 n.4, p.240-247, April 1968 [doi>10.1145/362991.363001]
	42	Valiant, L. 1975. General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10, 308--315.
	43	Mark G. J. van den Brand , J. Heering , P. Klint , P. A. Olivier, Compiling language definitions: the ASF+SDF compiler, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.4, p.334-368, July 2002 [doi>10.1145/567097.567099]
	44	Visser, E. 1997. Syntax definition for langauge prototyping. Ph.D. thesis, Universty of Amsterdam.
	45	Visser, E. 2004. Program transformation with Stratego/XT: Rules, strategies, tools, and systems in StrategoXT-0.9. In Domain-Specific Program Generation, C. et al, ed. LNCS, vol. 3016. Springer, Berlin, 216--238.
	46	Younger, D. H. 1967. Recognition of context-free languages in time n3. Inform. Control 10, 2 (Feb.), 189--208.

CITED BY 4

	Martin Bravenboer , Éric Tanter , Eelco Visser, Declarative, formal, and extensible syntax definition for aspectJ, ACM SIGPLAN Notices, v.41 n.10, October 2006
	E. Bertsch , M. -J. Nederhof, Some observations on LR-like parsing with delayed reduction, Information Processing Letters, v.104 n.6, p.195-199, December, 2007
	Adrian Johnstone , Elizabeth Scott, Proofs and pedagogy; science and systems: The grammar tool box, Science of Computer Programming, v.69 n.1-3, p.76-85, December, 2007
	Sylvain Schmitz, An Experimental Ambiguity Detection Tool, Electronic Notes in Theoretical Computer Science (ENTCS), v.203 n.2, p.69-84, April, 2008