---
title: "On the Relation between Context-Free Grammars and Parsing Expression Grammars — Mascarenhas 2013"
description: "On this basis, the authors formally prove that an LL(1) grammar defines the same language both as a CFG and as a… 28 references, cited by 2 papers here."
authors: ["Fabio Mascarenhas", "Sérgio Medeiros", "Roberto Ierusalimschy"]
year: 2013
venue: "arXiv:1304.3177"
source: "https://arxiv.org/abs/1304.3177"
doi: "10.1016/j.scico.2014.01.012"
arxiv: "1304.3177"
licence: "arXiv — non-exclusive licence to distribute"
licence_url: "http://arxiv.org/licenses/nonexclusive-distrib/1.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/mascarenhas-2013-relation-between-context-free-grammars/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/mascarenhas-2013-relation-between-context-free-grammars/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2013](https://md.research.elamur.ai/free/en/papers/2013/page/2/) / On the Relation between Context-Free Grammars and Parsing Expression Grammars

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

**Authors:** Fabio Mascarenhas, Sérgio Medeiros and Roberto Ierusalimschy · **Year:** 2013 · **Venue:** arXiv:1304.3177 · **Licence:** [arXiv — non-exclusive licence to distribute](http://arxiv.org/licenses/nonexclusive-distrib/1.0/)

**Links:** [Publisher's page](https://arxiv.org/abs/1304.3177) · [PDF](https://arxiv.org/pdf/1304.3177) · [DOI 10.1016/j.scico.2014.01.012](https://doi.org/10.1016/j.scico.2014.01.012) · [arXiv 1304.3177](https://arxiv.org/abs/1304.3177)

**Citations:** 2 in our library, of the 140,884 papers whose bibliographies we read

## 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](https://md.research.elamur.ai/free/en/shelves/computing/)

Topics: [📐 Syntax & grammar formalisms](https://md.research.elamur.ai/free/en/topics/syntax-grammar/)

## 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.

```bibtex
@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}
}
```

- [← previous An Empirical Study of Differences between Conversion Schemes and Annotation Guidelines](https://md.research.elamur.ai/free/en/papers/sogaard-2013-empirical-study-differences-between-conversion/)
- [next → Ranking Translations using Error Analysis and Quality Estimation](https://md.research.elamur.ai/free/en/papers/fishel-2013-ranking-translations-error-analysis-quality/)
- [↑ back to papers of 2013](https://md.research.elamur.ai/free/en/papers/2013/page/2/)

## 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](https://scholar.google.com/scholar?q=B%2E+Ford%2C+Parsing+Expression+Grammars%3A+a+recognition%2Dbased+syntactic+foundation%2C+in%3A+Proceedings+of+the+31st+ACM+SIGPLAN%2DSIGACT+Symposium+on+Principles+of+Programming+Languages%2C+POPL+%E2%80%9904%2C+ACM%2C+New+York)
2. A. Birman, J. D. Ullman, Parsing algorithms with backtrack, Information and Control 23 (1) (1973) 1 – 34. [find](https://scholar.google.com/scholar?q=A%2E+Birman%2C+J%2E+D%2E+Ullman%2C+Parsing+algorithms+with+backtrack%2C+Information+and+Control+23+%281%29+%281973%29+1+%E2%80%93+34%2E)
3. A. V. Aho, J. D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1972. [find](https://scholar.google.com/scholar?q=A%2E+V%2E+Aho%2C+J%2E+D%2E+Ullman%2C+The+Theory+of+Parsing%2C+Translation%2C+and+Compiling%2C+Prentice%2DHall%2C+Inc%2E%2C+Upper+Saddle+River%2C+NJ%2C+USA%2C+1972%2E)
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](https://scholar.google.com/scholar?q=T%2E+J%2E+Parr%2C+R%2E+W%2E+Quong%2C+Antlr%3A+a+predicated%2Dll%28k%29+parser+generator%2C+Softw%2E+Pract%2E+Exper%2E+25+%287%29+%281995%29+789%E2%80%93810%2E+doi%3A10%2E1002%2Fspe%2E4380250705%2E+%E2%80%94+%5Bdoi%3A10%2E1002%2Fspe%2E4380250705%5D%28https%3A%2F%2Fdoi%2Eorg%2F10%2E1002%2Fspe%2E)
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](https://scholar.google.com/scholar?q=G%2E+Kahn%2C+Natural+semantics%2C+in%3A+Proceedings+of+the+4th+Annual+Symposium+on+Theoretical+Aspects+of+Computer+Science%2C+STACS+%E2%80%9987%2C+Springer%2DVerlag%2C+London%2C+UK%2C+1987%2C+pp%2E+22%E2%80%9339%2E)
6. G. Winskel, The Formal Semantics of Programming Languages: An Introduction, Foundations of Computing, MIT Press, 1993. [find](https://scholar.google.com/scholar?q=G%2E+Winskel%2C+The+Formal+Semantics+of+Programming+Languages%3A+An+Introduction%2C+Foundations+of+Computing%2C+MIT+Press%2C+1993%2E)
7. C. F. Clark, Message to comp.compilers reference 05-08-115, [http://compilers.iecc.com/comparch/article/05-09-009](http://compilers.iecc.com/comparch/article/05-09-009) (2005). [↗](http://compilers.iecc.com/comparch/article/05-09-009)
8. D. Grune, C. J. Jacobs, Parsing Techniques – A Practical Guide, Ellis Horwood, 1991. [find](https://scholar.google.com/scholar?q=D%2E+Grune%2C+C%2E+J%2E+Jacobs%2C+Parsing+Techniques+%E2%80%93+A+Practical+Guide%2C+Ellis+Horwood%2C+1991%2E)
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) [↗](http://dx.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](https://scholar.google.com/scholar?q=J%2E+E%2E+Hopcroft%2C+J%2E+D%2E+Ullman%2C+Introduction+to+Automata+Theory%2C+Languages%2C+and+Computation%2C+1st+Edition%2C+Addison%2DWesley+Longman+Publishing+Co%2E%2C+Inc%2E%2C+Boston%2C+MA%2C+USA%2C+1979%2E)
11. A. Nijholt, LL-regular grammars, International Journal of Computer Mathematics 8 (1980) 303–318. [find](https://scholar.google.com/scholar?q=A%2E+Nijholt%2C+LL%2Dregular+grammars%2C+International+Journal+of+Computer+Mathematics+8+%281980%29+303%E2%80%93318%2E)
12. S. Jarzabek, T. Krawczyk, LL-regular grammars, Information Processing Letters 4 (2) (1975) 31–37. [find](https://scholar.google.com/scholar?q=S%2E+Jarzabek%2C+T%2E+Krawczyk%2C+LL%2Dregular+grammars%2C+Information+Processing+Letters+4+%282%29+%281975%29+31%E2%80%9337%2E)
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](https://scholar.google.com/scholar?q=A%2E+Nijholt%2C+From+LL%2Dregular+to+LL%281%29+grammars%3A+Transformations%2C+covers+and+parsing%2C+RAIRO+Informatique+The%CC%81orique+et+Applications+16+%281982%29+387%E2%80%93406%2E)
14. S. Q. de Medeiros, Correspondência entre PEGs e classes de gramáticas livres de contexto, Ph.D. thesis, PUC-Rio (2010). [find](https://scholar.google.com/scholar?q=S%2E+Q%2E+de+Medeiros%2C+Corresponde%CC%82ncia+entre+PEGs+e+classes+de+grama%CC%81ticas+livres+de+contexto%2C+Ph%2ED%2E+thesis%2C+PUC%2DRio+%282010%29%2E)
15. R. R. Redziejowski, Applying classical concepts to parsing expression grammar, Fundamenta Informaticae 93 (2009) 325–336. [find](https://scholar.google.com/scholar?q=R%2E+R%2E+Redziejowski%2C+Applying+classical+concepts+to+parsing+expression+grammar%2C+Fundamenta+Informaticae+93+%282009%29+325%E2%80%93336%2E)
16. R. R. Redziejowski, Some aspects of parsing expression grammar, Fundamenta Informaticae 85 (2008) 441–451. [find](https://scholar.google.com/scholar?q=R%2E+R%2E+Redziejowski%2C+Some+aspects+of+parsing+expression+grammar%2C+Fundamenta+Informaticae+85+%282008%29+441%E2%80%93451%2E)
17. R. R. Redziejowski, From EBNF to PEG, Fundamenta Informaticae 128 (2013) 177–191. [find](https://scholar.google.com/scholar?q=R%2E+R%2E+Redziejowski%2C+From+EBNF+to+PEG%2C+Fundamenta+Informaticae+128+%282013%29+177%E2%80%93191%2E)
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](https://scholar.google.com/scholar?q=S%2E+Schmitz%2C+Modular+syntax+demands+verification%2C+Tech%2E+Rep%2E+I3S%2FRR%2D2006%2D32%2DFR%2C+Laboratoire+I3S%2C+Universite%CC%81+de+Nice%2DSophia+Antipolis%2C+France+%28Oct%2E+2006%29%2E)
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](https://scholar.google.com/scholar?q=T%2E+J%2E+Parr%2C+R%2E+W%2E+Quong%2C+Adding+semantic+and+syntactic+predicates+to+LL%28k%29%3A+pred%2DLL%28k%29%2C+in%3A+Proceedings+of+the+5th+International+Conference+on+Compiler+Construction%2C+CC+%E2%80%9994%2C+Springer%2DVerlag%2C+London%2C+U)
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](https://scholar.google.com/scholar?q=T%2E+Parr%2C+K%2E+Fisher%2C+LL%28%2A%29%3A+the+foundation+of+the+ANTLR+parser+generator%2C+in%3A+Proceedings+of+the+32nd+ACM+SIGPLAN+conference+on+Programming+language+design+and+implementation%2C+PLDI+%E2%80%9911%2C+ACM%2C+New+York%2C+)
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](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) [↗](http://www.sciencedirect.com/science/article/pii/S0167642312000627)
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) [↗](http://dx.doi.org/10.1007/978-3-64…)
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…](http://www.aclweb.org/anth…) [↗](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](http://dblp.uni-trier.de/db/journals/entcs/entcs253.html\#ScottJ10) [↗](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) [↗](http://dx.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](https://scholar.google.com/scholar?q=D%2E+E%2E+Knuth%2C+On+the+translation+of+languages+from+left+to+right%2C+Information+and+Control+8+%286%29+%281965%29+607+%E2%80%93+639%2E+doi%3Ahttp%3A%2F%2Fdx%2Edoi%2Eorg%2F10%2E1016%2FS0019%2D9958%2865%2990426%2D2%2E)
27. F. L. DeRemer, Simple LR(k) grammars, Commun. ACM 14 (7) (1971) 453–460. doi:10.1145/362619.362625. [find](https://scholar.google.com/scholar?q=F%2E+L%2E+DeRemer%2C+Simple+LR%28k%29+grammars%2C+Commun%2E+ACM+14+%287%29+%281971%29+453%E2%80%93460%2E+doi%3A10%2E1145%2F362619%2E362625%2E)
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](https://scholar.google.com/scholar?q=S%2E+Medeiros%2C+F%2E+Mascarenhas%2C+R%2E+Ierusalimschy%2C+Left+recursion+in+parsing+expression+grammars%2C+in%3A+Proceedings+of+the+16th+Brazilian+conference+on+Programming+Languages%2C+SBLP%E2%80%9912%2C+Springer%2DVerlag%2C+Berli)