ANTLR2PEG: A tool to convert ANTLR grammars into PEG grammars
Resumo
Context-Free Grammars (CFGs) and Parsing Expression Grammars (PEGs) are formalisms for describing the syntax of languages, where the visual description of a CFG for a language is similar to the corresponding PEG one. Due to this similarity and the fact that CFGs predate PEGs by several decades, it is common practice to derive a PEG from a BNF-like description of a CFG, intended for parser generators like ANTLR, rather than writing the PEG parser from scratch. However, the distinct semantics of PEGs may make this manual translation error-prone. We describe several automatically transformations that help to produce, from an ANTLR grammar, a PEG parser that recognizes the same language.We present ANTLR2PEG, a tool that implements these transformations, and we evaluated it against a corpus of more than 200 community-made ANTLR grammars, comparing the result of the ANTLR parser with the PEG one. Each translatable grammar is evaluated against 100 automatic generated inputs and against the examples that accompany the grammar in the ANTLR repository. From the 262 grammars used from the ANTLR/grammars-v4 repository, ANTLR2PEG can generate a PEG parser for 146 of them. Considering the examples, the PEG parser and the ANTLR one agree perfectly for 42.5% of these 146 grammars. On generated tests, we have a percentage of 35.8% on parsers agreement. We also perform a more in-depth analysis for 10 ANTLR grammars, evaluating how ANTLR2PEG’s output can help to manually fix PEG parsers.
Palavras-chave:
Parsing, Parser Generators, ANTLR, Parsing Expression Grammars, Context-Free Grammars
Referências
Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. 1986. Compilers: Principles, Techniques, and Tools. Addison-Wesley.
Sérgio Queiroz de Medeiros and Fabio Mascarenhas. 2018. Towards automatic error recovery in parsing expression grammars. In Proceedings of the XXII Brazilian Symposium on Programming Languages (Sao Carlos, Brazil) (SBLP ’18). Association for Computing Machinery, New York, NY, USA, 3–10. DOI: 10.1145/3264637.3264638
Bryan Ford. 2004. 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, Venice, Italy, 111–122. DOI: 10.1145/964001.964011
Grammarinator 2017. ANTLRv4 grammar-based test generator. Retrieved June 07, 2022 from [link]
Robert Grimm. 2006. Ambiguity. PEG mailing list. Available at [link].
Renáta Hodován, Ákos Kiss, and Tibor Gyimóthy. 2018. Grammarinator: A Grammar-Based Open Source Fuzzer. Association for Computing Machinery, New York, NY, USA, 45–48. DOI: 10.1145/3278186.3278193
Renáta Hodován, Ákos Kiss, and Tibor Gyimóthy. 2018. Grammarinator: A Grammar-Based Open Source Fuzzer. In Proceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation (Lake Buena Vista FL USA, 2018-11-05). ACM, 45–48. DOI: 10.1145/3278186.3278193
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2007. Introduction to Automata Theory, Languages, and Computation (3 ed.). Pearson Education.
Roberto Ierusalimschy. 2009. A text pattern-matching tool based on Parsing Expression Grammars. Softw. Pract. Exper. 39, 3 (March 2009), 221–258.
Roberto Ierusalimschy. 2009. A Text Pattern-Matching Tool Based on Parsing Expression Grammars. In Proceedings of the 2009 ACM Symposium on Applied Computing. ACM, 687–694.
JavaCC Contributors. 2025. JavaCC: The Java Compiler Compiler. GitHub. [link] Accessed: 2025-12-30.
Stephen C. Johnson. 1975. Yacc: Yet Another Compiler-Compiler. Computing Science Technical Report 32. Bell Laboratories, Murray Hill, NJ.
Fabio Mascarenhas, Sérgio Medeiros, and Roberto Ierusalimschy. 2014. On the Relation between Context-Free Grammars and Parsing Expression Grammars. 89 (2014), 235–250. DOI: 10.1016/j.scico.2014.01.012
Sérgio Medeiros, Fabio Mascarenhas, and Roberto Ierusalimschy. 2014. From regexes to parsing expression grammars. Science of Computer Programming 93 (2014), 3–18. DOI: 10.1016/j.scico.2012.11.006, Special Issue with Selected Papers from the Brazilian Symposium on Programming Languages (SBLP 2011).
Sérgio Medeiros, Fabio Mascarenhas, and Roberto Ierusalimschy. 2014. Left recursion in Parsing Expression Grammars. Science of Computer Programming 96 (2014), 177–190. DOI: 10.1016/j.scico.2014.01.013, Selected and extended papers of the Brazilian Symposium on Programming Languages 2012 (SBLP 2012).
Marcelo Oikawa, Roberto Ierusalimschy, and Ana Moura. 2010. Converting regexes to Parsing Expression Grammars. In SBLP ’10: Proceedings of the 14th Brazilian Symposium on Programming Languages (Salvador, Brazil).
Terence Parr. 2013. The Definitive ANTLR 4 Reference (2nd ed.). Pragmatic Bookshelf.
Terence John Parr, Sam Harwell, and Kathleen Fisher. 2014. Adaptive LL(*) Parsing: The Power of Dynamic Analysis. In Proceedings of the 2014 ACM International Conference on Object-Oriented Programming Systems, Languages & Applications (OOPSLA 2014), part of SPLASH 2014. ACM, 579–598. DOI: 10.1145/2660193.2660202
Roman R Redziejowski. 2010. Mouse sampe grammars for Java and C. [link]. Accessed 11 June 2022.
Roman R Redziejowski. 2013. From ebnf to peg. Fundamenta Informaticae 128, 1-2 (2013), 177–191.
Roman R Redziejowski. 2014. More about converting BNF to PEG. Fundamenta Informaticae 133, 2-3 (2014), 257–270.
Roman R. Redziejowski. 2018. Trying to Understand PEG. Fundam. Inf. 157, 4 (jan 2018), 463–475. DOI: 10.3233/FI-2018-1638
Roman R Redziejowski. 2021. Left recursion by recursive ascent. In Proceedings of the International Workshop on Concurrency, Specification and Programming CS&P’2021. 72–82. [link]
Sylvain Schmitz. 2006. Modular syntax demands verification. Technical Report. LABORATOIRE I3S, UNIVERSITÉ DE NICE-SOPHIA ANTIPOLIS.
Phillip van Heerden, Moeketsi Raselimo, Konstantinos Sagonas, and Bernd Fischer. 2020. Grammar-Based Testing for Little Languages: An Experience Report with Student Compilers. In Proceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering (Virtual, USA) (SLE 2020). Association for Computing Machinery, New York, NY, USA, 253–269. DOI: 10.1145/3426425.3426946
Alessandro Warth, James R. Douglass, and Todd Millstein. 2008. Packrat Parsers Can Support Left Recursion. In Proceedings of the 2008 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (San Francisco, California, USA) (PEPM ’08). Association for Computing Machinery, New York, NY, USA, 103–110. DOI: 10.1145/1328408.1328424
Sérgio Queiroz de Medeiros and Fabio Mascarenhas. 2018. Towards automatic error recovery in parsing expression grammars. In Proceedings of the XXII Brazilian Symposium on Programming Languages (Sao Carlos, Brazil) (SBLP ’18). Association for Computing Machinery, New York, NY, USA, 3–10. DOI: 10.1145/3264637.3264638
Bryan Ford. 2004. 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, Venice, Italy, 111–122. DOI: 10.1145/964001.964011
Grammarinator 2017. ANTLRv4 grammar-based test generator. Retrieved June 07, 2022 from [link]
Robert Grimm. 2006. Ambiguity. PEG mailing list. Available at [link].
Renáta Hodován, Ákos Kiss, and Tibor Gyimóthy. 2018. Grammarinator: A Grammar-Based Open Source Fuzzer. Association for Computing Machinery, New York, NY, USA, 45–48. DOI: 10.1145/3278186.3278193
Renáta Hodován, Ákos Kiss, and Tibor Gyimóthy. 2018. Grammarinator: A Grammar-Based Open Source Fuzzer. In Proceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation (Lake Buena Vista FL USA, 2018-11-05). ACM, 45–48. DOI: 10.1145/3278186.3278193
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2007. Introduction to Automata Theory, Languages, and Computation (3 ed.). Pearson Education.
Roberto Ierusalimschy. 2009. A text pattern-matching tool based on Parsing Expression Grammars. Softw. Pract. Exper. 39, 3 (March 2009), 221–258.
Roberto Ierusalimschy. 2009. A Text Pattern-Matching Tool Based on Parsing Expression Grammars. In Proceedings of the 2009 ACM Symposium on Applied Computing. ACM, 687–694.
JavaCC Contributors. 2025. JavaCC: The Java Compiler Compiler. GitHub. [link] Accessed: 2025-12-30.
Stephen C. Johnson. 1975. Yacc: Yet Another Compiler-Compiler. Computing Science Technical Report 32. Bell Laboratories, Murray Hill, NJ.
Fabio Mascarenhas, Sérgio Medeiros, and Roberto Ierusalimschy. 2014. On the Relation between Context-Free Grammars and Parsing Expression Grammars. 89 (2014), 235–250. DOI: 10.1016/j.scico.2014.01.012
Sérgio Medeiros, Fabio Mascarenhas, and Roberto Ierusalimschy. 2014. From regexes to parsing expression grammars. Science of Computer Programming 93 (2014), 3–18. DOI: 10.1016/j.scico.2012.11.006, Special Issue with Selected Papers from the Brazilian Symposium on Programming Languages (SBLP 2011).
Sérgio Medeiros, Fabio Mascarenhas, and Roberto Ierusalimschy. 2014. Left recursion in Parsing Expression Grammars. Science of Computer Programming 96 (2014), 177–190. DOI: 10.1016/j.scico.2014.01.013, Selected and extended papers of the Brazilian Symposium on Programming Languages 2012 (SBLP 2012).
Marcelo Oikawa, Roberto Ierusalimschy, and Ana Moura. 2010. Converting regexes to Parsing Expression Grammars. In SBLP ’10: Proceedings of the 14th Brazilian Symposium on Programming Languages (Salvador, Brazil).
Terence Parr. 2013. The Definitive ANTLR 4 Reference (2nd ed.). Pragmatic Bookshelf.
Terence John Parr, Sam Harwell, and Kathleen Fisher. 2014. Adaptive LL(*) Parsing: The Power of Dynamic Analysis. In Proceedings of the 2014 ACM International Conference on Object-Oriented Programming Systems, Languages & Applications (OOPSLA 2014), part of SPLASH 2014. ACM, 579–598. DOI: 10.1145/2660193.2660202
Roman R Redziejowski. 2010. Mouse sampe grammars for Java and C. [link]. Accessed 11 June 2022.
Roman R Redziejowski. 2013. From ebnf to peg. Fundamenta Informaticae 128, 1-2 (2013), 177–191.
Roman R Redziejowski. 2014. More about converting BNF to PEG. Fundamenta Informaticae 133, 2-3 (2014), 257–270.
Roman R. Redziejowski. 2018. Trying to Understand PEG. Fundam. Inf. 157, 4 (jan 2018), 463–475. DOI: 10.3233/FI-2018-1638
Roman R Redziejowski. 2021. Left recursion by recursive ascent. In Proceedings of the International Workshop on Concurrency, Specification and Programming CS&P’2021. 72–82. [link]
Sylvain Schmitz. 2006. Modular syntax demands verification. Technical Report. LABORATOIRE I3S, UNIVERSITÉ DE NICE-SOPHIA ANTIPOLIS.
Phillip van Heerden, Moeketsi Raselimo, Konstantinos Sagonas, and Bernd Fischer. 2020. Grammar-Based Testing for Little Languages: An Experience Report with Student Compilers. In Proceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering (Virtual, USA) (SLE 2020). Association for Computing Machinery, New York, NY, USA, 253–269. DOI: 10.1145/3426425.3426946
Alessandro Warth, James R. Douglass, and Todd Millstein. 2008. Packrat Parsers Can Support Left Recursion. In Proceedings of the 2008 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (San Francisco, California, USA) (PEPM ’08). Association for Computing Machinery, New York, NY, USA, 103–110. DOI: 10.1145/1328408.1328424
Publicado
08/09/2026
Como Citar
SANTOS, José Eduardo; MEDEIROS, Sérgio Queiroz de.
ANTLR2PEG: A tool to convert ANTLR grammars into PEG grammars. In: SIMPÓSIO BRASILEIRO DE LINGUAGENS DE PROGRAMAÇÃO (SBLP), 30. , 2026, São Paulo/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 88-97.
DOI: https://doi.org/10.5753/sblp.2026.28552.
