A Parsing Expression Grammar-based Approach For Syntax Tree Pattern Matching
Resumo
We present a formal PEG-based approach to pattern matching on parse trees. Given an arbitrary Parsing Expression Grammar, we define a tree-producing semantics, a typing and subtyping relation for parse trees and patterns, and a pattern matching algorithm, all equipped with correctness proofs. The formalization is implemented as a Haskell library and we show some case studies like the design of simple static analysis tools.
Palavras-chave:
PEG, Pattern, Matching, Static analysis
Referências
Darren Atkinson and William Griswold. 2006. Effective pattern matching of source code using abstract syntax patterns. Softw., Pract. Exper. 36 (04 2006), 413–447. DOI: 10.1002/spe.704
Bryan Ford. 2004. Parsing expression grammars: a recognition-based syntactic foundation. SIGPLAN Not. 39, 1 (Jan. 2004), 111–122. DOI: 10.1145/982962.964011
Roberto Ierusalimschy. 2009. A text pattern-matching tool based on Parsing Expression Grammars. Softw. Pract. Exper. 39, 3 (March 2009), 221–258.
James Koppel, Varot Premtoon, and Armando Solar-Lezama. 2018. One tool, many languages: language-parametric transformation with incremental parametric syntax. Proc. ACM Program. Lang. 2, OOPSLA, Article 122 (Oct. 2018), 28 pages. DOI: 10.1145/3276492
Gabriel Matute, Wode Ni, Titus Barik, Alvin Cheung, and Sarah E. Chasins. 2024. Syntactic Code Search with Sequence-to-Tree Matching: Supporting Syntactic Search with Incomplete Code Fragments. Proc. ACM Program. Lang. 8, PLDI, Article 230 (June 2024), 22 pages. DOI: 10.1145/3656460
Varot Premtoon, James Koppel, and Armando Solar-Lezama. 2020. Semantic code search via equational reasoning. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (London, UK) (PLDI 2020). Association for Computing Machinery, NewYork, NY, USA, 1066–1082. DOI: 10.1145/3385412.3386001
Danilo Silva, João Paulo da Silva, Gustavo Santos, Ricardo Terra, and Marco Tulio Valente. 2021. RefDiff 2.0: A Multi-Language Refactoring Detection Tool. IEEE Transactions on Software Engineering 47, 12 (Dec 2021), 2786–2802. DOI: 10.1109/TSE.2020.2968072
Rijnard van Tonder and Claire Le Goues. 2019. Lightweight multi-language syntax transformation with parser parser combinators. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (Phoenix, AZ, USA) (PLDI 2019). Association for Computing Machinery, New York, NY, USA, 363–378. DOI: 10.1145/3314221.3314589
Daisuke Yamaguchi and Kimio Kuramitsu. 2019. CPEG: A Typed Tree Construction from Parsing Expression Grammars with Regex-Like Captures. In Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing (SAC ’19). Association for Computing Machinery, New York, NY, USA. DOI: 10.1145/3297280.3297433
Bryan Ford. 2004. Parsing expression grammars: a recognition-based syntactic foundation. SIGPLAN Not. 39, 1 (Jan. 2004), 111–122. DOI: 10.1145/982962.964011
Roberto Ierusalimschy. 2009. A text pattern-matching tool based on Parsing Expression Grammars. Softw. Pract. Exper. 39, 3 (March 2009), 221–258.
James Koppel, Varot Premtoon, and Armando Solar-Lezama. 2018. One tool, many languages: language-parametric transformation with incremental parametric syntax. Proc. ACM Program. Lang. 2, OOPSLA, Article 122 (Oct. 2018), 28 pages. DOI: 10.1145/3276492
Gabriel Matute, Wode Ni, Titus Barik, Alvin Cheung, and Sarah E. Chasins. 2024. Syntactic Code Search with Sequence-to-Tree Matching: Supporting Syntactic Search with Incomplete Code Fragments. Proc. ACM Program. Lang. 8, PLDI, Article 230 (June 2024), 22 pages. DOI: 10.1145/3656460
Varot Premtoon, James Koppel, and Armando Solar-Lezama. 2020. Semantic code search via equational reasoning. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (London, UK) (PLDI 2020). Association for Computing Machinery, NewYork, NY, USA, 1066–1082. DOI: 10.1145/3385412.3386001
Danilo Silva, João Paulo da Silva, Gustavo Santos, Ricardo Terra, and Marco Tulio Valente. 2021. RefDiff 2.0: A Multi-Language Refactoring Detection Tool. IEEE Transactions on Software Engineering 47, 12 (Dec 2021), 2786–2802. DOI: 10.1109/TSE.2020.2968072
Rijnard van Tonder and Claire Le Goues. 2019. Lightweight multi-language syntax transformation with parser parser combinators. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (Phoenix, AZ, USA) (PLDI 2019). Association for Computing Machinery, New York, NY, USA, 363–378. DOI: 10.1145/3314221.3314589
Daisuke Yamaguchi and Kimio Kuramitsu. 2019. CPEG: A Typed Tree Construction from Parsing Expression Grammars with Regex-Like Captures. In Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing (SAC ’19). Association for Computing Machinery, New York, NY, USA. DOI: 10.1145/3297280.3297433
Publicado
08/09/2026
Como Citar
NASCIMENTO, Guilherme Augusto Anício Drummond do; RIBEIRO, Rodrigo Geraldo.
A Parsing Expression Grammar-based Approach For Syntax Tree Pattern Matching. 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. 63-70.
DOI: https://doi.org/10.5753/sblp.2026.27725.
