syntax-pattern 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).

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

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

You may build the project either locally or using Docker.

• GHC (>= 8.10)
• Cabal, or Stack

• Docker
• Docker Compose

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.

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

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")
|]

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.

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.

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

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 []

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.

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.

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