[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Fast deterministic parsers for transition networks

  • Original Article
  • Published:
Acta Informatica Aims and scope Submit manuscript

Abstract

Extended BNF grammars (EBNF) allow regular expressions in the right parts of their rules. They are widely used to define languages, and can be represented by recursive Transition Networks (TN) consisting of a set of finite-state machines. We present a novel direct construction of efficient shift-reduce ELR(1) parsers for TNs. We show that such a parser works deterministically if the TN is free from the classical shift-reduce and reduce–reduce conflicts of the LR(1) parsers, and from a new conflict type called convergence conflict. Such a novel condition for determinism is proved correct and is more general than those proposed in the past for EBNF grammars or TNs. Such ELR(1) parsers perform fewer shift moves than the equivalent LR(1) parsers. A simple optimization of the reduction moves is described.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Notes

  1. We reserve the term “automata” to the push-down machines of the parsers.

  2. This function is analogous to the “GOTO” component of the canonical parsing table described in the classical textbooks on compilers such as [1].

  3. When applying the function \(\mu \) to a stack p-state, if two items have identical (machine) states, then they are coalesced as said in Definitions 7 and 10.

  4. It would be interesting to supplement the above analysis with experimental measurements for realistic grammars. A few results are mentioned in [3], which point to a greater compactness of the ELR(1) graphs. Just an example: for the Oracle EBNF grammar of the Java language, the TN has 532 machine states and 599 machine transitions. The ELR(1) graph has 1937 p-states and 25,231 transitions, while the standard LR(1) graph has 2946 p-states and 25,837 transitions.

  5. It is well known that the terminal and nonterminal symbols, typically represented in the stack when the LR(1) techniques are taught, are unnecessary.

References

  1. Aho, A., Lam, M., Sethi, R., Ullman, J.: Compilers: Principles, Techniques and Tools. Prentice-Hall, Englewoof Cliffs (2006)

    MATH  Google Scholar 

  2. Beatty, J.: On the relationship between the LL(1) and LR(1) grammars. JACM 29(4), 1007–1022 (1982)

    Article  MathSciNet  Google Scholar 

  3. Borsotti, A., Breveglieri, L., Crespi Reghizzi, S., Morzenti, A.: Complexity of extended vs classic LR parsers. In: Descriptional Complexity of Formal Systems (DCFS), LNCS, vol. 8614, pp. 77–89. Springer (2014)

  4. Breveglieri, L., Crespi Reghizzi, S., Morzenti, A.: Shift-reduce parsers for transition networks. In: Language and Automata Theory and Applications (LATA), LNCS, vol. 8370, pp. 222–235. Springer (2014)

  5. Celentano, A.: LR parsing technique for extended context-free grammars. Comput. Lang. 6(2), 95–107 (1981)

    Article  Google Scholar 

  6. Chapman, N.: LALR(1,1) parser generation for regular right part grammars. Acta Inform. 21, 29–45 (1984). https://doi.org/10.1007/BF00289138

    Article  MathSciNet  MATH  Google Scholar 

  7. Conway, M.: Design of a separable transition-diagram compiler. Commun. ACM 6(7), 396–408 (1963)

    Article  Google Scholar 

  8. Crespi Reghizzi, S., Breveglieri, L., Morzenti, A.: Formal Languages and Compilation, 2nd edn. Springer, London (2013)

    Book  Google Scholar 

  9. Engelfriet, J.: Iterating iterated substitution. Theor. Comput. Sci. 5(1), 85–100 (1977). https://doi.org/10.1016/0304-3975(77)90043-3

    Article  MathSciNet  MATH  Google Scholar 

  10. Gálvez, J.: A note on a proposed LALR parser for extended context-free grammars. Inf. Process. Lett. 50(6), 303–305 (1994). https://doi.org/10.1016/0020-0190(94)00051-4

    Article  MATH  Google Scholar 

  11. Grune, D., Jacobs, C.: Parsing Techniques: A Practical Guide, 2nd edn. Springer, London (2009)

    Google Scholar 

  12. Gruska, J.: On a classification of context-free languages. Kybernetika 3(1), 22–29 (1967). http://www.kybernetika.cz/content/1967/1/22

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

    Article  MathSciNet  Google Scholar 

  14. Hemerik, K.: Towards a taxonomy for ECFG and RRPG parsing. In: Language and Automata Theory and Applications (LATA), LNCS, vol. 5457, pp. 410–421. Springer (2009). https://doi.org/10.1007/978-3-642-00982-2

    Google Scholar 

  15. Jensen, K., Wirth, N.: Pascal User Manual and Report. LNCS, vol. 18, 2nd edn. Springer, Berlin (1975). https://doi.org/10.1007/3-540-06950-X

    Book  MATH  Google Scholar 

  16. Kannapinn, S.: Reconstructing LR theory to eliminate redundance, with an application to the construction of ELR parsers. Ph.D. thesis, Technical University of Berlin (2001). (in German)

  17. Knuth, D.: On the translation of languages from left to right. Inform. Control 8, 607–639 (1965)

    Article  MathSciNet  Google Scholar 

  18. Knuth, D.: Top-down syntax analysis. Acta Inform. 1, 79–110 (1971)

    Article  Google Scholar 

  19. LaLonde, W.: Constructing LR parsers for regular right part grammars. Acta Inform. 11, 177–193 (1979). https://doi.org/10.1007/BF00264024

    Article  MathSciNet  MATH  Google Scholar 

  20. Lee, G., Kim, D.: Characterization of extended LR(k) grammars. Inf. Process. Lett. 64(2), 75–82 (1997). https://doi.org/10.1016/S0020-0190(97)00152-X

    Article  MathSciNet  MATH  Google Scholar 

  21. Lewi, J., De Vlaminck, K., Huens, J., Huybrechts, M.: A Programming Methodology in Compiler Construction: Part I and II. North-Holland, Amsterdam (1979)

    MATH  Google Scholar 

  22. Morimoto, S., Sassa, M.: Yet another generation of LALR parsers for regular right part grammars. Acta Inform. 37, 671–697 (2001)

    Article  MathSciNet  Google Scholar 

  23. Rosenkrantz, D., Stearns, R.: Properties of deterministic top-down grammars. Inform. Control 17(3), 226–256 (1970)

    Article  MathSciNet  Google Scholar 

  24. Sassa, M., Nakata, I.: A simple realization of LR-parsers for regular right part grammars. Inf. Process. Lett. 24(2), 113–120 (1987). https://doi.org/10.1016/0020-0190(87)90104-9

    Article  MATH  Google Scholar 

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

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. DEIB - Politecnico di Milano, Milan, Italy

    Angelo Borsotti, Luca Breveglieri, Stefano Crespi Reghizzi & Angelo Morzenti

  2. CNR-IEIIT, Bologna, Italy

    Stefano Crespi Reghizzi

Authors
  1. Angelo Borsotti
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Luca Breveglieri
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Stefano Crespi Reghizzi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Angelo Morzenti
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Luca Breveglieri.

Additional information

A preliminary account of this research is in [4].

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Borsotti, A., Breveglieri, L., Crespi Reghizzi, S. et al. Fast deterministic parsers for transition networks. Acta Informatica 55, 547–574 (2018). https://doi.org/10.1007/s00236-017-0308-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00236-017-0308-3

Search

Navigation