Elamur Research⌕
☰
home / papers / 2013 / On the Relation between Context-Free Grammars and Parsing Expression Grammars

On the Relation between Context-Free Grammars and Parsing Expression Grammars

Summary

The authors examine how two formalisms for describing syntax relate to each other: context-free grammars (CFG) and Parsing Expression Grammars (PEG). They are usually described in such different ways that comparing them is difficult. The authors therefore give a new definition of CFG, which they call PE-CFG. It is based on natural semantics and borrows the syntax of parsing expressions from PEG. Here a grammar does not generate strings; instead, it recognizes a prefix of the input string. The ambiguity of CFG is concentrated in the nondeterministic choice operator. Replacing it with ordered choice with explicit failure and adding the not predicate yields the semantics of PEG. The authors prove that this semantics is equivalent to Ford's classical definition. Hence, the key difference between the formalisms lies precisely in ordered choice. On this basis, the authors formally prove that an LL(1) grammar defines the same language both as a CFG and as a PEG. For strong-LL(k), right-linear and LL-regular grammars, they propose simple transformations into equivalent PEGs that preserve the structure of the grammar. As a result, classical top-down grammars, including those written for ANTLR, can be used in PEG-based tools.

Key points

  • An illustrative example: the grammar S → (aba | a) b on the input abac recognizes the prefix ab as a CFG, but fails as a PEG.
  • LL(1): if no alternative derives the empty string, the language coincides without changes. Otherwise, it suffices to reorder the alternatives appropriately.
  • Strong-LL(k): even reordering the alternatives does not yield a direct correspondence. However, it suffices to add a syntactic predicate at the beginning or at the end of each alternative. Backtracking is then needed only to check the lookahead, so the resulting parser is efficient even without memoization.
  • Right-linear grammars with the prefix property define the same language under both interpretations. This result is used to build lookahead predicates for LL-regular grammars based on regular partitions.
  • Limitations: the transformations require an end-of-input marker, which makes it harder to embed the resulting PEGs into larger grammars. As the next step, the authors name the relationship between PEG and the bottom-up grammars LR(k) and SLR(k), where the key problem is left recursion.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Computing & GPUs

Topics Syntax & grammar formalisms

Cite

Cite as Fabio Mascarenhas, Sérgio Medeiros and Roberto Ierusalimschy. 2013. On the Relation between Context-Free Grammars and Parsing Expression Grammars. arXiv:1304.3177.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1016/j.scico.2014.01.012 · arXiv 1304.3177

@misc{mascarenhas2013relation,
  title = {{On the Relation between Context-Free Grammars and Parsing Expression Grammars}},
  author = {Fabio Mascarenhas, Sérgio Medeiros and Roberto Ierusalimschy},
  year = {2013},
  doi = {10.1016/j.scico.2014.01.012},
  eprint = {1304.3177},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1016/j.scico.2014.01.012}
}

References

28 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. B. Ford, Parsing Expression Grammars: a recognition-based syntactic foundation, in: Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’04, ACM, New York, NY, USA, 2004, pp. 111–122. find
  2. A. Birman, J. D. Ullman, Parsing algorithms with backtrack, Information and Control 23 (1) (1973) 1 – 34. find
  3. A. V. Aho, J. D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1972. find
  4. T. J. Parr, R. W. Quong, Antlr: a predicated-ll(k) parser generator, Softw. Pract. Exper. 25 (7) (1995) 789–810. doi:10.1002/spe.4380250705. — [doi:10.1002/spe.4380250705](https://doi.org/10.1002/spe.4380250705) find
  5. G. Kahn, Natural semantics, in: Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, STACS ’87, Springer-Verlag, London, UK, 1987, pp. 22–39. find
  6. G. Winskel, The Formal Semantics of Programming Languages: An Introduction, Foundations of Computing, MIT Press, 1993. find
  7. C. F. Clark, Message to comp.compilers reference 05-08-115, http://compilers.iecc.com/comparch/article/05-09-009 (2005). ↗
  8. D. Grune, C. J. Jacobs, Parsing Techniques – A Practical Guide, Ellis Horwood, 1991. find
  9. D. E. Knuth, Top-down syntax analysis, Acta Informatica 1 (2) (1971) 79– 110. doi:10.1007/BF00289517. URL http://dx.doi.org/10.1007/BF00289517 — [doi:10.1007/bf00289517](https://doi.org/10.1007/bf00289517) ↗
  10. J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 1st Edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1979. find
  11. A. Nijholt, LL-regular grammars, International Journal of Computer Mathematics 8 (1980) 303–318. find
  12. S. Jarzabek, T. Krawczyk, LL-regular grammars, Information Processing Letters 4 (2) (1975) 31–37. find
  13. A. Nijholt, From LL-regular to LL(1) grammars: Transformations, covers and parsing, RAIRO Informatique Théorique et Applications 16 (1982) 387–406. find
  14. S. Q. de Medeiros, Correspondência entre PEGs e classes de gramáticas livres de contexto, Ph.D. thesis, PUC-Rio (2010). find
  15. R. R. Redziejowski, Applying classical concepts to parsing expression grammar, Fundamenta Informaticae 93 (2009) 325–336. find
  16. R. R. Redziejowski, Some aspects of parsing expression grammar, Fundamenta Informaticae 85 (2008) 441–451. find
  17. R. R. Redziejowski, From EBNF to PEG, Fundamenta Informaticae 128 (2013) 177–191. find
  18. S. Schmitz, Modular syntax demands verification, Tech. Rep. I3S/RR-2006-32-FR, Laboratoire I3S, Université de Nice-Sophia Antipolis, France (Oct. 2006). find
  19. T. J. Parr, R. W. Quong, Adding semantic and syntactic predicates to LL(k): pred-LL(k), in: Proceedings of the 5th International Conference on Compiler Construction, CC ’94, Springer-Verlag, London, UK, 1994, pp. 263–277. find
  20. T. Parr, K. Fisher, LL(*): the foundation of the ANTLR parser generator, in: Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation, PLDI ’11, ACM, New York, NY, USA, 2011, pp. 425–436. find
  21. E. Scott, A. Johnstone, GLL parse-tree generation, Science of Computer Programming 78 (10) (2013) 1828 – 1844. doi:http://dx.doi.org/10.1016/j.scico.2012.03.005. URL http://www.sciencedirect.com/science/article/pii/S0167642312000627 — [doi:10.1016/j.scico.2012.03.005](https://doi.org/10.1016/j.scico.2012.03.005) ↗
  22. A. Johnstone, E. Scott, Modelling GLL parser implementations, in: B. Malloy, S. Staab, M. Brand (Eds.), Software Language Engineering, Vol. 6563 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2011, pp. 42–61. doi:10.1007/978-3-642-19440-5\\_4. URL http://dx.doi.org/10.1007/978-3-64… — [doi:10.1007/978-3-642-19440-5\\_4](https://doi.org/10.1007/978-3-642-19440-5_4) ↗
  23. M. Tomita, Graph-structured stack and natural language parsing, in: Proceedings of the 26th Annual Meeting of the Association for Computational Linguistics, Association for Computational Linguistics, Buffalo, New York, USA, 1988, pp. 249–257. doi:10.3115/982023.982054. URL http://www.aclweb.org/anth… ↗
  24. E. Scott, A. Johnstone, Gll parsing., Electronic Notes on Theoretical Computer Science 253 (7) (2010) 177–189. URL http://dblp.uni-trier.de/db/journals/entcs/entcs253.html\#ScottJ10 ↗
  25. E. Scott, A. Johnstone, R. Economopoulos, BRNGLR: a cubic Tomita-style GLR parsing algorithm, Acta Informatica 44 (6) (2007) 427–461. doi:10.1007/s00236-007-0054-z. URL http://dx.doi.org/10.1007/s00236-007-0054-z — [doi:10.1007/s00236-007-0054-z](https://doi.org/10.1007/s00236-007-0054-z) ↗
  26. D. E. Knuth, On the translation of languages from left to right, Information and Control 8 (6) (1965) 607 – 639. doi:http://dx.doi.org/10.1016/S0019-9958(65)90426-2. find
  27. F. L. DeRemer, Simple LR(k) grammars, Commun. ACM 14 (7) (1971) 453–460. doi:10.1145/362619.362625. find
  28. S. Medeiros, F. Mascarenhas, R. Ierusalimschy, Left recursion in parsing expression grammars, in: Proceedings of the 16th Brazilian conference on Programming Languages, SBLP’12, Springer-Verlag, Berlin, Heidelberg, 2012, pp. 27–41. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/mascarenhas-2013-relation-between-context-free-grammars/