peg-matching
peg-matching is a Haskell library for parsing, analyzing, matching, and
rewriting syntax trees using Parsing Expression Grammars (PEGs) and user-defined
patterns. It is designed for research and experimentation with syntax-driven
transformations and pattern matching in abstract syntax trees (ASTs).
Features
- PEG Parsing: Define grammars using PEGs and parse input strings into syntax
trees.
- Pattern Language: Express complex patterns over syntax trees, including
variables, choices, sequences, and repetitions.
- Pattern Matching: Match patterns against parsed trees and capture subtrees.
- Rewriting: Rewrite syntax trees by applying pattern-based transformations.
- Semantic Analysis: Validate grammars and patterns, detect left recursion,
duplicate rules, and other semantic errors.
- Pretty Printing: Human-readable output for grammars, patterns, and trees.
- Extensible: Modular design for easy extension and integration.
Project Structure
src/
Match/
Capture.hs -- Pattern matching and capture
Rewrite.hs -- Tree rewriting
Parser/
Base.hs -- Parser combinators and utilities
ParsedTree.hs -- PEG-based parser to AST
Pattern.hs -- Pattern parser
Peg.hs -- PEG grammar parser
Pipeline/
MatchPipeline.hs -- High-level pipeline for parsing, matching, and rewriting
Quote/
Base.hs -- Quasi-quoter base functions
Pattern.hs -- Pattern quasi-quoter
Peg.hs -- PEG quasi-quotter
Semantic/
Pattern.hs -- Semantic analysis for patterns
Peg.hs -- Semantic analysis for PEGs
Syntax/
Base.hs -- Core types (Terminal, NonTerminal, etc.)
ParsedTree.hs -- AST definition and utilities
Pattern.hs -- Pattern types
Peg.hs -- PEG types and utilities
input/
peg/ -- Example PEG grammars
pattern/ -- Example pattern files
file/ -- Example input files
test/
Main.hs -- Property and sanity tests
Getting Started
Installation
peg-matching is published on
Hackage. To use it in your
own project, add it to the build-depends of your .cabal file:
build-depends:
base >=4.17 && <5
, peg-matching >=0.1 && <0.2
Or install it directly:
cabal update
cabal install --lib peg-matching
The sections below are for building this repository from source, which you only
need if you intend to work on the library itself.
Prerequisites
You may build the project either locally or using Docker.
Local environment
Docker environment
Building
First, clone the repository:
git clone https://github.com/lives-group/peg-matching
cd peg-matching
After this, you may build using Cabal:
cabal update
cabal build
Or with Stack:
stack build
Alternatively, you also may use docker to setup.
After cloning the repository, run:
docker compose build
docker compose run ghci
This will already run cabal update inside the container for you.
Usage
You can use the library in your own Haskell projects or run the provided pipelines
for parsing, matching, and rewriting:
import Pipeline.MatchPipeline
-- Parse and validate a PEG grammar from a string
let grammarResult = parseValidGrammar "S <- \"a\" S / \"b\""
-- Parse and validate patterns
let patternsResult = parseValidPatterns grammarString patternString
-- Parse an input file and match patterns
let matchResult = parseMatch grammarString patternString inputString
QuasiQuoters
This library also exposes compile-time QuasiQuoters for PEG grammars and patterns.
Use Quote.Peg.grammar to embed a PEG definition directly in Haskell source, and
Quote.Pattern.patterns to embed pattern definitions.
Example:
import qualified Quote.Peg as QPeg
import qualified Quote.Pattern as QPattern
myGrammar :: Grammar
myGrammar = [QPeg.grammar|
S <- "a" S / "b"
|]
myPatterns :: [NamedSynPat]
myPatterns = [QPattern.patterns|
pattern example : S := "a" (S := "b")
|]
File-based Pipeline Functions
Most pipeline functions also have IO variants that accept file paths instead of raw
strings. These allow you to directly specify files containing PEG, patterns, and input data.
You can find several example PEG, pattern, and input files in the input/ directory
to experiment with. The file extension for PEG and pattern files are .peg and .pat
respectively, but they are simple text files.
Tests
The test/ directory contains property-based and sanity tests for the main algorithms
and is still in progress.
You can use these to check the correctness and robustness of the library.
See the Haddock documentation for detailed API usage and examples.
Running examples
After building the project, you may run some provived examples. First, run the REPL:
cabal repl
And then load the pipeline module:
:l Pipeline.MatchPipeline
Example 1 - Parsing a file:
Run
parseFileIO "input/peg/expression.peg" "input/file/expression.txt" True
The parseFileIO function takes as arguments two files and a boolean. The first is a
file that contains the PEG, while the second contains the input data. The boolean indicates
in which way you want the parsed content to be displayed: if True, it will flatten the content
and show it exactly as is in the file. Otherwise, it you show the generated tree.
The result should be:
(1+2)*3
If you ran with False:
NT E
╰╴Seq
├╴NT T
| ╰╴Seq
| ├╴NT F
| | ╰╴Right
| | ╰╴Seq
| | ├╴"("
| | ╰╴Seq
| | ├╴NT E
| | | ╰╴Seq
| | | ├╴NT T
| | | | ╰╴Seq
| | | | ├╴NT F
| | | | | ╰╴Left
| | | | | ╰╴NT n
| | | | | ╰╴"1"
| | | | ╰╴Star []
| | | ╰╴Star [
| | | ├╴Seq
| | | | ├╴"+"
| | | | ╰╴NT T
| | | | ╰╴Seq
| | | | ├╴NT F
| | | | | ╰╴Left
| | | | | ╰╴NT n
| | | | | ╰╴"2"
| | | | ╰╴Star []
| | | ╰╴]
| | ╰╴")"
| ╰╴Star [
| ├╴Seq
| | ├╴"*"
| | ╰╴NT F
| | ╰╴Left
| | ╰╴NT n
| | ╰╴"3"
| ╰╴]
╰╴Star []
Example 2 - Matching with patterns:
Run
parseMatch1IO "input/peg/python.peg" "input/pattern/factorial.pat" "input/file/fact_math.py" "factorial_call"
The parseMatch1IO function takes as arguments three files and one string. The files
are the PEG file, pattern file and input file, respectively. The string is an identifiers for
any pattern inside the pattern file. In this case, factorial_call is a pattern that
matches with calls to functions named math.factorial.
The output should be something like this:
factorial_call: match!
Indicating that the indicated pattern did match inside the file.
Running
parseMatch1IO "input/peg/python.peg" "input/pattern/factorial.pat" "input/file/fact_while.py" "factorial_call"
will produce something like this:
factorial_call: not match!
Indicating that the indicated pattern did not match inside the file.
Run
parseCallGraphIO "input/peg/python.peg" "input/pattern/call_graph.pat" "input/file/ex4.py" "definition" "call"
The parseCallGraphIO function takes as arguments three files and two strings. The files
are the PEG file, pattern file and input file, respectively. The strings are identifiers for
patterns inside the pattern file, where the first one is a pattern that matches with functions definitions and the second one a pattern that matches with function calls.
The output should be something like this:
bhaskara -> delta
bhaskara -> math.sqrt
Indicating that the function bhaskara calls both delta and math.sqrt.
Example 4 - rewriting based on patterns:
This is the content of input/file/if.py:
if not a:
print(b)
print(b1)
else:
print(c)
print(c1)
Run
parseRewriteIO "input/peg/python.peg" "input/pattern/subst_if.pat" "input/file/if.py" "if_def" "subst"
The parseRewriteIO function takes as arguments three files and two strings. The files
are the PEG file, pattern file and input file, respectively. The strings are identifiers for
patterns inside the pattern file, where the first one is a pattern that matches with some
desired data and the second one specifies how to rewrite the matched data.
The output should be something like this:
if a:print(c)
print(c1)else:print(b)
print(b1)
The printing is a bit broken, but it is possible to see that it swapped the if and
else body and removed the not from the condition.
You may change the input files (and their contents) for new tests, if you wish.
Documentation
All modules are documented with Haddock. To generate HTML documentation:
cabal haddock
or
stack haddock
The documentation covers:
- PEG and pattern syntax
- Pattern matching and rewriting
- Error handling and semantic checks
