Skip to main content
SpringerLink
Log in
SpringerLink
Log in

Towards a Taxonomy for ECFG and RRPG Parsing

  • Conference paper
Language and Automata Theory and Applications (LATA 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5457))

Abstract

Extended Context-Free Grammars (ECFGs) and Regular Right-Part Grammars (RRPGs) have many applications, but they are sparsely covered in the vast literature on parsing and grammars. This paper presents first steps towards a taxonomy of parsers for ECFGs and RRPGs, in order to make this subject more accessible.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Wirth, N.: What can we do about the unnecessary diversity of notation for syntactic definitions? CACM 20, 822–823 (1977)

    Article  Google Scholar 

  2. ISO/IEC: International Standard EBNF Syntax Notation. 14977 edn. (1996), http://www.iso.ch/cate/d26153.html

  3. Conway, M.E.: Design of a separable transition-diagram compiler. CACM 6, 396–408 (1963)

    Article  MATH  Google Scholar 

  4. Lomet, D.B.: A formalization of transition diagram systems. JACM 20, 235–257 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  5. Perlin, M.: LR recursive transition networks for Earley and Tomita parsing. In: Procs. 29th Annual Meeting on Association for Computational Linguistics (ACL), Berkeley, California, pp. 98–105 (1991)

    Google Scholar 

  6. Woods, W.A.: Transition network grammars for natural language analysis. CACM 13, 591–606 (1970)

    Article  MATH  Google Scholar 

  7. Broy, M.: Program construction by transformations: a family tree of sorting programs. In: Biermann, A.W., Guiho, G. (eds.) Computer Program Synthesis Methodologies, pp. 1–49. Reidel (1983)

    Google Scholar 

  8. Darlington, J.: A synthesis of several sorting algorithms. Acta Inf. 11, 1–30 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  9. Jonkers, H.: Abstraction, specification and implementation techniques, with an application to garbage collection. PhD thesis, Technische Univ. Eindhoven (1983)

    Google Scholar 

  10. Watson, B.W.: Taxonomies and Toolkits of Regular Language Algorithms. PhD thesis, Technische Universiteit Eindhoven (1995)

    Google Scholar 

  11. Watson, B.W.: Implementing and using finite automata toolkits. In: Kornai, A. (ed.) Procs. 12th European Conference on Artificial Intelligence, Budapest, Hungary, pp. 97–100 (1996)

    Google Scholar 

  12. Cleophas, L.: Tree Algorithms - Two Taxonomies and a Toolkit. PhD thesis, Technische Universiteit Eindhoven (2008)

    Google Scholar 

  13. Cleophas, L.: Forest FIRE and FIRE Wood - tools for tree automata and tree algorithms. In: FSMNLP (2008)

    Google Scholar 

  14. Wilhelm, R., Maurer, D.: Compiler Design. Addison-Wesley, Reading (1995)

    MATH  Google Scholar 

  15. Lewi, J., de Vlaminck, K., Steegmans, E., Horebeek, I.V.: Software Development by LL(1) Syntax Description. Wiley, Chichester (1992)

    MATH  Google Scholar 

  16. Heilbrunner, S.: On the definition of ELR(k) and ELL(k) grammars. Acta Informatica 11, 169–176 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  17. Lucas, P.: The structure of formula-translators. ALGOL Bulletin 16 (1961)

    Google Scholar 

  18. Wirth, N.: Algorithms + Data Structures = Programs. Prentice-Hall, Englewood Cliffs (1975)

    MATH  Google Scholar 

  19. Lewi, J., Vlaminck, K.D., Huens, J., Huybrechts, M.: The ELL(l) parser generator and the error recovery mechanism. Acta Informatica 10, 209–228 (1978)

    Article  MATH  Google Scholar 

  20. Keim, E.: Theory and implementation of a family of parser components. Master’s thesis, Dept. of Math. and Comp.Sci., Technische Universiteit Eindhoven (2007)

    Google Scholar 

  21. Ssanyu, J., Hemerik, K.: Algorithms for recursive descent parsing of ECFGs. (in preparation, 2008)

    Google Scholar 

  22. Brüggemann-Klein, A., Wood, D.: On predictive parsing and extended context-free grammars. In: Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2002. LNCS, vol. 2608, pp. 239–247. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  23. Brüggemann-Klein, A., Wood, D.: The parsing of extended context-free grammars. HKUST Theoretical Computer Science Center Research Report HKUST-TCSC-2002-08, Hong Kong University (2002)

    Google Scholar 

  24. Celentano, A.: An LR parsing technique for extended context-free grammars. Computer Languages 6, 95–107 (1981)

    Article  Google Scholar 

  25. Madsen, O.L., Kristensen, B.B.: LR-parsing of extended context free grammars. Acta Informatica 7, 61–73 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  26. Chapman, N.P.: LALR(1,1) parser generation for regular right part grammars. Acta Informatica 21, 29–45 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  27. Chapman, N.P.: LR Parsing - Theory and Practice. Cambridge Univ. Press, Cambridge (1987)

    MATH  Google Scholar 

  28. LaLonde, W.R.: Regular right part grammars and their parsers. CACM 20, 731–741 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  29. LaLonde, W.R.: Lalonde: Constructing LR parsers for regular right part grammars. Acta Informatica 11, 177–193 (1979)

    Article  MATH  Google Scholar 

  30. Morimito, S.I., Sassa, M.: Yet another generation of LALR parsers for regular right part grammars. Acta Informatica 37, 671–697 (2001)

    Article  MathSciNet  Google Scholar 

  31. Nakata, I., Sassa, M.: Generation of efficient LALR parsers for regular right part grammars. Acta Informatica 23, 149–162 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  32. Purdom, P.W., Brown, C.A.: Parsing extended LR(k) grammars. Acta Informatica 15, 115–127 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  33. Sassa, M., Nakata, I.: A simple realization of LR-parsers for regular right part grammars. Information Processing Letters 24, 113–120 (1987)

    Article  MATH  Google Scholar 

  34. Shin, H.C., Choe, K.M.: An improved LALR(k) parser generation for regular right part grammars. Inf. Proc. Lett. 47, 123–129 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  35. Zhang, Y., Nakata, I.: Generation of path directed LALR(k) parsers for regular right part grammars. J. Inf. Process. 14, 325–334 (1991)

    MATH  Google Scholar 

  36. Colby, J.E., Bermudez, M.E.: Lookahead LR parsing with regular right part grammars. Intern. J. Computer Math. 64, 1–15 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  37. Kannapinn, S.: Eine Rekonstruktion der LR-Theorie zur Elimination von Redundanz mit Anwendung auf den Bau von ELR-Parsern. PhD thesis, Technische Universität Berlin (2001) (in German)

    Google Scholar 

  38. Fortes Gálvez, J.: A note on a proposed LALR parser for extended context-free grammars. Inf. Proc. Lett. 50, 303–305 (1994)

    Article  MATH  Google Scholar 

  39. Earley, J.C.: An efficient context-free parsing algorithm. CACM 13, 94–102 (1970)

    Article  MATH  Google Scholar 

  40. Leermakers, R.: How to cover a grammar. In: Procs. 27th Ann. Meeting of Association for Computational Linguistics, Vancouver, Canada, pp. 135–142 (1989)

    Google Scholar 

  41. Schneider, K.M.: Parsing schemata for grammars with variable number and order of constituents. In: Procs. 18th Conf. on Comp. Linguistics, vol. 2, pp. 733–739 (2000)

    Google Scholar 

  42. Spanbroek, M.: Towards a unification of regular and context-free recognition. Master’s thesis, Dept. of Math. and Comp. Sci., Technische Universiteit Eindhoven (2005)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands

    Kees Hemerik

Authors
  1. Kees Hemerik
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Research Group on Mathematical Linguistics, Rovira i Virgili University, Av. Catalunya, 35, 43002, Tarragona, Spain

    Adrian Horia Dediu

  2. Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, Spain

    Armand Mihai Ionescu

  3. European Research Council Executive Agency, 16 Place Rogier, 1210, Brussels, Belgium

    Carlos Martín-Vide

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hemerik, K. (2009). Towards a Taxonomy for ECFG and RRPG Parsing. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds) Language and Automata Theory and Applications. LATA 2009. Lecture Notes in Computer Science, vol 5457. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00982-2_35

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-00982-2_35

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-00981-5

  • Online ISBN: 978-3-642-00982-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation