packages feed

peg-matching (empty) → 0.1.0.0

raw patch · 56 files changed

+7218/−0 lines, 56 filesdep +algebraic-graphsdep +basedep +megaparsecsetup-changed

Dependencies added: algebraic-graphs, base, megaparsec, parser-combinators, peg-matching, pretty, syb, tasty, tasty-hunit, template-haskell

Files

+ CHANGELOG.md view
@@ -0,0 +1,13 @@+# Changelog for `peg-matching`++All notable changes to this project will be documented in this file.++The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/),+and this project adheres to the+[Haskell Package Versioning Policy](https://pvp.haskell.org/).++## Unreleased++## 0.1.0.0 - 2026-09-01++Initial release.
+ LICENSE view
@@ -0,0 +1,26 @@+Copyright 2025 Guilherme Drummond, Rodrigo Ribeiro++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++1.  Redistributions of source code must retain the above copyright notice, this+    list of conditions and the following disclaimer.++2.  Redistributions in binary form must reproduce the above copyright notice,+    this list of conditions and the following disclaimer in the documentation+    and/or other materials provided with the distribution.++3.  Neither the name of the copyright holder nor the names of its contributors+    may be used to endorse or promote products derived from this software+    without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR+ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON+ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,347 @@+# 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++```haskell+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](https://hackage.haskell.org/package/peg-matching). To use it in your+own project, add it to the `build-depends` of your `.cabal` file:++```cabal+build-depends:+    base >=4.17 && <5+  , peg-matching >=0.1 && <0.2+```++Or install it directly:++```bash+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++- [GHC](https://www.haskell.org/ghc/) (>= 9.4)+- [Cabal](https://www.haskell.org/cabal/), or [Stack](https://docs.haskellstack.org/en/stable/)++#### Docker environment++- [Docker](https://www.docker.com/)+- Docker Compose++### Building++First, clone the repository:++```bash+git clone https://github.com/lives-group/peg-matching+cd peg-matching+```++After this, you may build using Cabal:++```bash+cabal update+cabal build+```++Or with Stack:++```bash+stack build+```++Alternatively, you also may use docker to setup. +After cloning the repository, run:++```bash+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:++```haskell+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:++```haskell+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](#documentation) for detailed API usage and examples.++### Running examples++After building the project, you may run some provived examples. First, run the REPL:++```bash+cabal repl+```++And then load the pipeline module:+```bash+:l Pipeline.MatchPipeline+```++#### Example 1 - Parsing a file: +Run+```bash+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:+```bash+(1+2)*3+```++If you ran with ```False```:+```bash+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+```bash+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:+```bash+factorial_call: match!+```+Indicating that the indicated pattern did match inside the file.++Running+```bash+parseMatch1IO "input/peg/python.peg" "input/pattern/factorial.pat" "input/file/fact_while.py" "factorial_call"+```+will produce something like this:+```bash+factorial_call: not match!+```+Indicating that the indicated pattern did not match inside the file.++#### Example 3 - extracting call graph from a Python file: +Run+```bash+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:+```bash+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```:+```python+if not a:+    print(b)+    print(b1)+else:+    print(c)+    print(c1)+```++Run+```bash+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:+```bash+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:++```bash+cabal haddock+```++or++```bash+stack haddock+```++The documentation covers:+- PEG and pattern syntax+- Pattern matching and rewriting+- Error handling and semantic checks
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ input/file/disallowed.py view
@@ -0,0 +1,24 @@+def inputVetor():+    entrada = input("Informe as metas dos estados: ")+    return list(map(int, entrada.split(',')))++def inputMatriz():+    entrada = input("Informe o plantio de arvores: ")+    linhas = entrada.split(';')+    matriz = [list(map(int, linha.split(','))) for linha in linhas]+    return matriz++def main():+    print("Ministerio do Meio Ambiente")+    metas = inputVetor()+    plantio = inputMatriz()++    num_estados = len(metas)+    totais_plantio = [sum(linha[i] for linha in plantio) for i in range(num_estados)]++    for i in range(num_estados):+        if totais_plantio[i] < metas[i]:+            print(f"Estado {i+1}, meta = {metas[i]}, plantio = {totais_plantio[i]}")++if __name__ == "__main__":+    main()
+ input/file/ex1.py view
@@ -0,0 +1,4 @@+C = float(input('Digite a temperatura em Celsius: '))
+F = C * 9 / 5
+F = F + 32
+print(f"A temperatura em Fahrenheit e {F:.1f}")
+ input/file/ex2.py view
@@ -0,0 +1,8 @@+S = float(input('Digite a distância percorrida em metros: '))
+T = float(input('Digite o tempo gasto em segundos: '))
+
+if S <= 0 or T <= 0:
+  print(f'ERRO: Entrada inválida.')
+else:
+  v = S / T
+  print(f'A velocidade média é {v:.2f}')
+ input/file/ex3.py view
@@ -0,0 +1,8 @@+T = float(input('Digite o período T: '))
+
+while T > 0:
+  f = 1 / T
+  print(f'A frequência é {f:.2f}')
+  T = float(input('Digite o período T: '))
+
+print("Fim")
+ input/file/ex4.py view
@@ -0,0 +1,20 @@+import math
+
+def delta(a, b, c):
+    return b**2 - 4*a*c
+
+def bhaskara(a, b, c):
+    d = delta(a, b, c)
+    x1 = (-b + math.sqrt(d)) / 2*a
+    x2 = (-b - math.sqrt(d)) / 2*a
+    return x1, x2
+
+a = float(input("Digite o valor de a: "))
+b = float(input("Digite o valor de b: "))
+c = float(input("Digite o valor de c: "))
+
+x1, x2 = bhaskara(a, b, c)
+
+print(f"{a}x^2 + {b}x + {c}")
+print(f"Raiz 1: {x1}")
+print(f"Raiz 2: {x2}")
+ input/file/expression.txt view
@@ -0,0 +1,1 @@+(1+2)*3
+ input/file/fact_math.py view
@@ -0,0 +1,6 @@+import math++n = int(input("Digite um numero: "))+fatorial = math.factorial(n)++print(fatorial)
+ input/file/fact_while.py view
@@ -0,0 +1,9 @@+n = int(input("Digite um numero: "))++i = 1+fatorial = 1+while i <= n:+    fatorial *= i+    i += 1++print(fatorial)
+ input/file/func1.py view
@@ -0,0 +1,2001 @@+def f1():
+    print("Funcao 1 chamada")
+    f2()
+    f3()
+
+def f2():
+    print("Funcao 2 chamada")
+    f4()
+    f5()
+
+def f3():
+    print("Funcao 3 chamada")
+    f6()
+
+def f4():
+    print("Funcao 4 chamada")
+    f7()
+    f8()
+
+def f5():
+    print("Funcao 5 chamada")
+    f9()
+
+def f6():
+    print("Funcao 6 chamada")
+    f10()
+
+def f7():
+    print("Funcao 7 chamada")
+    f11()
+
+def f8():
+    print("Funcao 8 chamada")
+    f12()
+
+def f9():
+    print("Funcao 9 chamada")
+    f13()
+
+def f10():
+    print("Funcao 10 chamada")
+    f14()
+
+def f11():
+    print("Funcao 11 chamada")
+    f15()
+
+def f12():
+    print("Funcao 12 chamada")
+    f16()
+
+def f13():
+    print("Funcao 13 chamada")
+    f17()
+
+def f14():
+    print("Funcao 14 chamada")
+    f18()
+
+def f15():
+    print("Funcao 15 chamada")
+    f19()
+
+def f16():
+    print("Funcao 16 chamada")
+    f20()
+
+def f17():
+    print("Funcao 17 chamada")
+    f21()
+
+def f18():
+    print("Funcao 18 chamada")
+    f22()
+
+def f19():
+    print("Funcao 19 chamada")
+    f23()
+
+def f20():
+    print("Funcao 20 chamada")
+    f24()
+
+def f21():
+    print("Funcao 21 chamada")
+    f25()
+
+def f22():
+    print("Funcao 22 chamada")
+    f26()
+
+def f23():
+    print("Funcao 23 chamada")
+    f27()
+
+def f24():
+    print("Funcao 24 chamada")
+    f28()
+
+def f25():
+    print("Funcao 25 chamada")
+    f29()
+
+def f26():
+    print("Funcao 26 chamada")
+    f30()
+
+def f27():
+    print("Funcao 27 chamada")
+    f31()
+
+def f28():
+    print("Funcao 28 chamada")
+    f32()
+
+def f29():
+    print("Funcao 29 chamada")
+    f33()
+
+def f30():
+    print("Funcao 30 chamada")
+    f34()
+
+def f31():
+    print("Funcao 31 chamada")
+    f35()
+
+def f32():
+    print("Funcao 32 chamada")
+    f36()
+
+def f33():
+    print("Funcao 33 chamada")
+    f37()
+
+def f34():
+    print("Funcao 34 chamada")
+    f38()
+
+def f35():
+    print("Funcao 35 chamada")
+    f39()
+
+def f36():
+    print("Funcao 36 chamada")
+    f40()
+
+def f37():
+    print("Funcao 37 chamada")
+    f41()
+
+def f38():
+    print("Funcao 38 chamada")
+    f42()
+
+def f39():
+    print("Funcao 39 chamada")
+    f43()
+
+def f40():
+    print("Funcao 40 chamada")
+    f44()
+
+def f41():
+    print("Funcao 41 chamada")
+    f45()
+
+def f42():
+    print("Funcao 42 chamada")
+    f46()
+
+def f43():
+    print("Funcao 43 chamada")
+    f47()
+
+def f44():
+    print("Funcao 44 chamada")
+    f48()
+
+def f45():
+    print("Funcao 45 chamada")
+    f49()
+
+def f46():
+    print("Funcao 46 chamada")
+    f50()
+
+def f47():
+    print("Funcao 47 chamada")
+    f51()
+
+def f48():
+    print("Funcao 48 chamada")
+    f52()
+
+def f49():
+    print("Funcao 49 chamada")
+    f53()
+
+def f50():
+    print("Funcao 50 chamada")
+    f54()
+
+def f51():
+    print("Funcao 51 chamada")
+    f55()
+
+def f52():
+    print("Funcao 52 chamada")
+    f56()
+
+def f53():
+    print("Funcao 53 chamada")
+    f57()
+
+def f54():
+    print("Funcao 54 chamada")
+    f58()
+
+def f55():
+    print("Funcao 55 chamada")
+    f59()
+
+def f56():
+    print("Funcao 56 chamada")
+    f60()
+
+def f57():
+    print("Funcao 57 chamada")
+    f61()
+
+def f58():
+    print("Funcao 58 chamada")
+    f62()
+
+def f59():
+    print("Funcao 59 chamada")
+    f63()
+
+def f60():
+    print("Funcao 60 chamada")
+    f64()
+
+def f61():
+    print("Funcao 61 chamada")
+    f65()
+
+def f62():
+    print("Funcao 62 chamada")
+    f66()
+
+def f63():
+    print("Funcao 63 chamada")
+    f67()
+
+def f64():
+    print("Funcao 64 chamada")
+    f68()
+
+def f65():
+    print("Funcao 65 chamada")
+    f69()
+
+def f66():
+    print("Funcao 66 chamada")
+    f70()
+
+def f67():
+    print("Funcao 67 chamada")
+    f71()
+
+def f68():
+    print("Funcao 68 chamada")
+    f72()
+
+def f69():
+    print("Funcao 69 chamada")
+    f73()
+
+def f70():
+    print("Funcao 70 chamada")
+    f74()
+
+def f71():
+    print("Funcao 71 chamada")
+    f75()
+
+def f72():
+    print("Funcao 72 chamada")
+    f76()
+
+def f73():
+    print("Funcao 73 chamada")
+    f77()
+
+def f74():
+    print("Funcao 74 chamada")
+    f78()
+
+def f75():
+    print("Funcao 75 chamada")
+    f79()
+
+def f76():
+    print("Funcao 76 chamada")
+    f80()
+
+def f77():
+    print("Funcao 77 chamada")
+    f81()
+
+def f78():
+    print("Funcao 78 chamada")
+    f82()
+
+def f79():
+    print("Funcao 79 chamada")
+    f83()
+
+def f80():
+    print("Funcao 80 chamada")
+    f84()
+
+def f81():
+    print("Funcao 81 chamada")
+    f85()
+
+def f82():
+    print("Funcao 82 chamada")
+    f86()
+
+def f83():
+    print("Funcao 83 chamada")
+    f87()
+
+def f84():
+    print("Funcao 84 chamada")
+    f88()
+
+def f85():
+    print("Funcao 85 chamada")
+    f89()
+
+def f86():
+    print("Funcao 86 chamada")
+    f90()
+
+def f87():
+    print("Funcao 87 chamada")
+    f91()
+
+def f88():
+    print("Funcao 88 chamada")
+    f92()
+
+def f89():
+    print("Funcao 89 chamada")
+    f93()
+
+def f90():
+    print("Funcao 90 chamada")
+    f94()
+
+def f91():
+    print("Funcao 91 chamada")
+    f95()
+
+def f92():
+    print("Funcao 92 chamada")
+    f96()
+
+def f93():
+    print("Funcao 93 chamada")
+    f97()
+
+def f94():
+    print("Funcao 94 chamada")
+    f98()
+
+def f95():
+    print("Funcao 95 chamada")
+    f99()
+
+def f96():
+    print("Funcao 96 chamada")
+    f100()
+
+def f97():
+    print("Funcao 97 chamada")
+    f101()
+
+def f98():
+    print("Funcao 98 chamada")
+    f102()
+
+def f99():
+    print("Funcao 99 chamada")
+    f103()
+
+def f100():
+    print("Funcao 100 chamada")
+    f104()
+
+def f101():
+    print("Funcao 101 chamada")
+    f105()
+
+def f102():
+    print("Funcao 102 chamada")
+    f106()
+
+def f103():
+    print("Funcao 103 chamada")
+    f107()
+
+def f104():
+    print("Funcao 104 chamada")
+    f108()
+
+def f105():
+    print("Funcao 105 chamada")
+    f109()
+
+def f106():
+    print("Funcao 106 chamada")
+    f110()
+
+def f107():
+    print("Funcao 107 chamada")
+    f111()
+
+def f108():
+    print("Funcao 108 chamada")
+    f112()
+
+def f109():
+    print("Funcao 109 chamada")
+    f113()
+
+def f110():
+    print("Funcao 110 chamada")
+    f114()
+
+def f111():
+    print("Funcao 111 chamada")
+    f115()
+
+def f112():
+    print("Funcao 112 chamada")
+    f116()
+
+def f113():
+    print("Funcao 113 chamada")
+    f117()
+
+def f114():
+    print("Funcao 114 chamada")
+    f118()
+
+def f115():
+    print("Funcao 115 chamada")
+    f119()
+
+def f116():
+    print("Funcao 116 chamada")
+    f120()
+
+def f117():
+    print("Funcao 117 chamada")
+    f121()
+
+def f118():
+    print("Funcao 118 chamada")
+    f122()
+
+def f119():
+    print("Funcao 119 chamada")
+    f123()
+
+def f120():
+    print("Funcao 120 chamada")
+    f124()
+
+def f121():
+    print("Funcao 121 chamada")
+    f125()
+
+def f122():
+    print("Funcao 122 chamada")
+    f126()
+
+def f123():
+    print("Funcao 123 chamada")
+    f127()
+
+def f124():
+    print("Funcao 124 chamada")
+    f128()
+
+def f125():
+    print("Funcao 125 chamada")
+    f129()
+
+def f126():
+    print("Funcao 126 chamada")
+    f130()
+
+def f127():
+    print("Funcao 127 chamada")
+    f131()
+
+def f128():
+    print("Funcao 128 chamada")
+    f132()
+
+def f129():
+    print("Funcao 129 chamada")
+    f133()
+
+def f130():
+    print("Funcao 130 chamada")
+    f134()
+
+def f131():
+    print("Funcao 131 chamada")
+    f135()
+
+def f132():
+    print("Funcao 132 chamada")
+    f136()
+
+def f133():
+    print("Funcao 133 chamada")
+    f137()
+
+def f134():
+    print("Funcao 134 chamada")
+    f138()
+
+def f135():
+    print("Funcao 135 chamada")
+    f139()
+
+def f136():
+    print("Funcao 136 chamada")
+    f140()
+
+def f137():
+    print("Funcao 137 chamada")
+    f141()
+
+def f138():
+    print("Funcao 138 chamada")
+    f142()
+
+def f139():
+    print("Funcao 139 chamada")
+    f143()
+
+def f140():
+    print("Funcao 140 chamada")
+    f144()
+
+def f141():
+    print("Funcao 141 chamada")
+    f145()
+
+def f142():
+    print("Funcao 142 chamada")
+    f146()
+
+def f143():
+    print("Funcao 143 chamada")
+    f147()
+
+def f144():
+    print("Funcao 144 chamada")
+    f148()
+
+def f145():
+    print("Funcao 145 chamada")
+    f149()
+
+def f146():
+    print("Funcao 146 chamada")
+    f150()
+
+def f147():
+    print("Funcao 147 chamada")
+    f151()
+
+def f148():
+    print("Funcao 148 chamada")
+    f152()
+
+def f149():
+    print("Funcao 149 chamada")
+    f153()
+
+def f150():
+    print("Funcao 150 chamada")
+    f154()
+
+def f151():
+    print("Funcao 151 chamada")
+    f155()
+
+def f152():
+    print("Funcao 152 chamada")
+    f156()
+
+def f153():
+    print("Funcao 153 chamada")
+    f157()
+
+def f154():
+    print("Funcao 154 chamada")
+    f158()
+
+def f155():
+    print("Funcao 155 chamada")
+    f159()
+
+def f156():
+    print("Funcao 156 chamada")
+    f160()
+
+def f157():
+    print("Funcao 157 chamada")
+    f161()
+
+def f158():
+    print("Funcao 158 chamada")
+    f162()
+
+def f159():
+    print("Funcao 159 chamada")
+    f163()
+
+def f160():
+    print("Funcao 160 chamada")
+    f164()
+
+def f161():
+    print("Funcao 161 chamada")
+    f165()
+
+def f162():
+    print("Funcao 162 chamada")
+    f166()
+
+def f163():
+    print("Funcao 163 chamada")
+    f167()
+
+def f164():
+    print("Funcao 164 chamada")
+    f168()
+
+def f165():
+    print("Funcao 165 chamada")
+    f169()
+
+def f166():
+    print("Funcao 166 chamada")
+    f170()
+
+def f167():
+    print("Funcao 167 chamada")
+    f171()
+
+def f168():
+    print("Funcao 168 chamada")
+    f172()
+
+def f169():
+    print("Funcao 169 chamada")
+    f173()
+
+def f170():
+    print("Funcao 170 chamada")
+    f174()
+
+def f171():
+    print("Funcao 171 chamada")
+    f175()
+
+def f172():
+    print("Funcao 172 chamada")
+    f176()
+
+def f173():
+    print("Funcao 173 chamada")
+    f177()
+
+def f174():
+    print("Funcao 174 chamada")
+    f178()
+
+def f175():
+    print("Funcao 175 chamada")
+    f179()
+
+def f176():
+    print("Funcao 176 chamada")
+    f180()
+
+def f177():
+    print("Funcao 177 chamada")
+    f181()
+
+def f178():
+    print("Funcao 178 chamada")
+    f182()
+
+def f179():
+    print("Funcao 179 chamada")
+    f183()
+
+def f180():
+    print("Funcao 180 chamada")
+    f184()
+
+def f181():
+    print("Funcao 181 chamada")
+    f185()
+
+def f182():
+    print("Funcao 182 chamada")
+    f186()
+
+def f183():
+    print("Funcao 183 chamada")
+    f187()
+
+def f184():
+    print("Funcao 184 chamada")
+    f188()
+
+def f185():
+    print("Funcao 185 chamada")
+    f189()
+
+def f186():
+    print("Funcao 186 chamada")
+    f190()
+
+def f187():
+    print("Funcao 187 chamada")
+    f191()
+
+def f188():
+    print("Funcao 188 chamada")
+    f192()
+
+def f189():
+    print("Funcao 189 chamada")
+    f193()
+
+def f190():
+    print("Funcao 190 chamada")
+    f194()
+
+def f191():
+    print("Funcao 191 chamada")
+    f195()
+
+def f192():
+    print("Funcao 192 chamada")
+    f196()
+
+def f193():
+    print("Funcao 193 chamada")
+    f197()
+
+def f194():
+    print("Funcao 194 chamada")
+    f198()
+
+def f195():
+    print("Funcao 195 chamada")
+    f199()
+
+def f196():
+    print("Funcao 196 chamada")
+    f200()
+
+def f197():
+    print("Funcao 197 chamada")
+    f201()
+
+def f198():
+    print("Funcao 198 chamada")
+    f202()
+
+def f199():
+    print("Funcao 199 chamada")
+    f203()
+
+def f200():
+    print("Funcao 200 chamada")
+    f204()
+
+def f201():
+    print("Funcao 201 chamada")
+    f205()
+
+def f202():
+    print("Funcao 202 chamada")
+    f206()
+
+def f203():
+    print("Funcao 203 chamada")
+    f207()
+
+def f204():
+    print("Funcao 204 chamada")
+    f208()
+
+def f205():
+    print("Funcao 205 chamada")
+    f209()
+
+def f206():
+    print("Funcao 206 chamada")
+    f210()
+
+def f207():
+    print("Funcao 207 chamada")
+    f211()
+
+def f208():
+    print("Funcao 208 chamada")
+    f212()
+
+def f209():
+    print("Funcao 209 chamada")
+    f213()
+
+def f210():
+    print("Funcao 210 chamada")
+    f214()
+
+def f211():
+    print("Funcao 211 chamada")
+    f215()
+
+def f212():
+    print("Funcao 212 chamada")
+    f216()
+
+def f213():
+    print("Funcao 213 chamada")
+    f217()
+
+def f214():
+    print("Funcao 214 chamada")
+    f218()
+
+def f215():
+    print("Funcao 215 chamada")
+    f219()
+
+def f216():
+    print("Funcao 216 chamada")
+    f220()
+
+def f217():
+    print("Funcao 217 chamada")
+    f221()
+
+def f218():
+    print("Funcao 218 chamada")
+    f222()
+
+def f219():
+    print("Funcao 219 chamada")
+    f223()
+
+def f220():
+    print("Funcao 220 chamada")
+    f224()
+
+def f221():
+    print("Funcao 221 chamada")
+    f225()
+
+def f222():
+    print("Funcao 222 chamada")
+    f226()
+
+def f223():
+    print("Funcao 223 chamada")
+    f227()
+
+def f224():
+    print("Funcao 224 chamada")
+    f228()
+
+def f225():
+    print("Funcao 225 chamada")
+    f229()
+
+def f226():
+    print("Funcao 226 chamada")
+    f230()
+
+def f227():
+    print("Funcao 227 chamada")
+    f231()
+
+def f228():
+    print("Funcao 228 chamada")
+    f232()
+
+def f229():
+    print("Funcao 229 chamada")
+    f233()
+
+def f230():
+    print("Funcao 230 chamada")
+    f234()
+
+def f231():
+    print("Funcao 231 chamada")
+    f235()
+
+def f232():
+    print("Funcao 232 chamada")
+    f236()
+
+def f233():
+    print("Funcao 233 chamada")
+    f237()
+
+def f234():
+    print("Funcao 234 chamada")
+    f238()
+
+def f235():
+    print("Funcao 235 chamada")
+    f239()
+
+def f236():
+    print("Funcao 236 chamada")
+    f240()
+
+def f237():
+    print("Funcao 237 chamada")
+    f241()
+
+def f238():
+    print("Funcao 238 chamada")
+    f242()
+
+def f239():
+    print("Funcao 239 chamada")
+    f243()
+
+def f240():
+    print("Funcao 240 chamada")
+    f244()
+
+def f241():
+    print("Funcao 241 chamada")
+    f245()
+
+def f242():
+    print("Funcao 242 chamada")
+    f246()
+
+def f243():
+    print("Funcao 243 chamada")
+    f247()
+
+def f244():
+    print("Funcao 244 chamada")
+    f248()
+
+def f245():
+    print("Funcao 245 chamada")
+    f249()
+
+def f246():
+    print("Funcao 246 chamada")
+    f250()
+
+def f247():
+    print("Funcao 247 chamada")
+    f251()
+
+def f248():
+    print("Funcao 248 chamada")
+    f252()
+
+def f249():
+    print("Funcao 249 chamada")
+    f253()
+
+def f250():
+    print("Funcao 250 chamada")
+    f254()
+
+def f251():
+    print("Funcao 251 chamada")
+    f255()
+
+def f252():
+    print("Funcao 252 chamada")
+    f256()
+
+def f253():
+    print("Funcao 253 chamada")
+    f257()
+
+def f254():
+    print("Funcao 254 chamada")
+    f258()
+
+def f255():
+    print("Funcao 255 chamada")
+    f259()
+
+def f256():
+    print("Funcao 256 chamada")
+    f260()
+
+def f257():
+    print("Funcao 257 chamada")
+    f261()
+
+def f258():
+    print("Funcao 258 chamada")
+    f262()
+
+def f259():
+    print("Funcao 259 chamada")
+    f263()
+
+def f260():
+    print("Funcao 260 chamada")
+    f264()
+
+def f261():
+    print("Funcao 261 chamada")
+    f265()
+
+def f262():
+    print("Funcao 262 chamada")
+    f266()
+
+def f263():
+    print("Funcao 263 chamada")
+    f267()
+
+def f264():
+    print("Funcao 264 chamada")
+    f268()
+
+def f265():
+    print("Funcao 265 chamada")
+    f269()
+
+def f266():
+    print("Funcao 266 chamada")
+    f270()
+
+def f267():
+    print("Funcao 267 chamada")
+    f271()
+
+def f268():
+    print("Funcao 268 chamada")
+    f272()
+
+def f269():
+    print("Funcao 269 chamada")
+    f273()
+
+def f270():
+    print("Funcao 270 chamada")
+    f274()
+
+def f271():
+    print("Funcao 271 chamada")
+    f275()
+
+def f272():
+    print("Funcao 272 chamada")
+    f276()
+
+def f273():
+    print("Funcao 273 chamada")
+    f277()
+
+def f274():
+    print("Funcao 274 chamada")
+    f278()
+
+def f275():
+    print("Funcao 275 chamada")
+    f279()
+
+def f276():
+    print("Funcao 276 chamada")
+    f280()
+
+def f277():
+    print("Funcao 277 chamada")
+    f281()
+
+def f278():
+    print("Funcao 278 chamada")
+    f282()
+
+def f279():
+    print("Funcao 279 chamada")
+    f283()
+
+def f280():
+    print("Funcao 280 chamada")
+    f284()
+
+def f281():
+    print("Funcao 281 chamada")
+    f285()
+
+def f282():
+    print("Funcao 282 chamada")
+    f286()
+
+def f283():
+    print("Funcao 283 chamada")
+    f287()
+
+def f284():
+    print("Funcao 284 chamada")
+    f288()
+
+def f285():
+    print("Funcao 285 chamada")
+    f289()
+
+def f286():
+    print("Funcao 286 chamada")
+    f290()
+
+def f287():
+    print("Funcao 287 chamada")
+    f291()
+
+def f288():
+    print("Funcao 288 chamada")
+    f292()
+
+def f289():
+    print("Funcao 289 chamada")
+    f293()
+
+def f290():
+    print("Funcao 290 chamada")
+    f294()
+
+def f291():
+    print("Funcao 291 chamada")
+    f295()
+
+def f292():
+    print("Funcao 292 chamada")
+    f296()
+
+def f293():
+    print("Funcao 293 chamada")
+    f297()
+
+def f294():
+    print("Funcao 294 chamada")
+    f298()
+
+def f295():
+    print("Funcao 295 chamada")
+    f299()
+
+def f296():
+    print("Funcao 296 chamada")
+    f300()
+
+def f297():
+    print("Funcao 297 chamada")
+    f301()
+
+def f298():
+    print("Funcao 298 chamada")
+    f302()
+
+def f299():
+    print("Funcao 299 chamada")
+    f303()
+
+def f300():
+    print("Funcao 300 chamada")
+    f304()
+
+def f301():
+    print("Funcao 301 chamada")
+    f305()
+
+def f302():
+    print("Funcao 302 chamada")
+    f306()
+
+def f303():
+    print("Funcao 303 chamada")
+    f307()
+
+def f304():
+    print("Funcao 304 chamada")
+    f308()
+
+def f305():
+    print("Funcao 305 chamada")
+    f309()
+
+def f306():
+    print("Funcao 306 chamada")
+    f310()
+
+def f307():
+    print("Funcao 307 chamada")
+    f311()
+
+def f308():
+    print("Funcao 308 chamada")
+    f312()
+
+def f309():
+    print("Funcao 309 chamada")
+    f313()
+
+def f310():
+    print("Funcao 310 chamada")
+    f314()
+
+def f311():
+    print("Funcao 311 chamada")
+    f315()
+
+def f312():
+    print("Funcao 312 chamada")
+    f316()
+
+def f313():
+    print("Funcao 313 chamada")
+    f317()
+
+def f314():
+    print("Funcao 314 chamada")
+    f318()
+
+def f315():
+    print("Funcao 315 chamada")
+    f319()
+
+def f316():
+    print("Funcao 316 chamada")
+    f320()
+
+def f317():
+    print("Funcao 317 chamada")
+    f321()
+
+def f318():
+    print("Funcao 318 chamada")
+    f322()
+
+def f319():
+    print("Funcao 319 chamada")
+    f323()
+
+def f320():
+    print("Funcao 320 chamada")
+    f324()
+
+def f321():
+    print("Funcao 321 chamada")
+    f325()
+
+def f322():
+    print("Funcao 322 chamada")
+    f326()
+
+def f323():
+    print("Funcao 323 chamada")
+    f327()
+
+def f324():
+    print("Funcao 324 chamada")
+    f328()
+
+def f325():
+    print("Funcao 325 chamada")
+    f329()
+
+def f326():
+    print("Funcao 326 chamada")
+    f330()
+
+def f327():
+    print("Funcao 327 chamada")
+    f331()
+
+def f328():
+    print("Funcao 328 chamada")
+    f332()
+
+def f329():
+    print("Funcao 329 chamada")
+    f333()
+
+def f330():
+    print("Funcao 330 chamada")
+    f334()
+
+def f331():
+    print("Funcao 331 chamada")
+    f335()
+
+def f332():
+    print("Funcao 332 chamada")
+    f336()
+
+def f333():
+    print("Funcao 333 chamada")
+    f337()
+
+def f334():
+    print("Funcao 334 chamada")
+    f338()
+
+def f335():
+    print("Funcao 335 chamada")
+    f339()
+
+def f336():
+    print("Funcao 336 chamada")
+    f340()
+
+def f337():
+    print("Funcao 337 chamada")
+    f341()
+
+def f338():
+    print("Funcao 338 chamada")
+    f342()
+
+def f339():
+    print("Funcao 339 chamada")
+    f343()
+
+def f340():
+    print("Funcao 340 chamada")
+    f344()
+
+def f341():
+    print("Funcao 341 chamada")
+    f345()
+
+def f342():
+    print("Funcao 342 chamada")
+    f346()
+
+def f343():
+    print("Funcao 343 chamada")
+    f347()
+
+def f344():
+    print("Funcao 344 chamada")
+    f348()
+
+def f345():
+    print("Funcao 345 chamada")
+    f349()
+
+def f346():
+    print("Funcao 346 chamada")
+    f350()
+
+def f347():
+    print("Funcao 347 chamada")
+    f351()
+
+def f348():
+    print("Funcao 348 chamada")
+    f352()
+
+def f349():
+    print("Funcao 349 chamada")
+    f353()
+
+def f350():
+    print("Funcao 350 chamada")
+    f354()
+
+def f351():
+    print("Funcao 351 chamada")
+    f355()
+
+def f352():
+    print("Funcao 352 chamada")
+    f356()
+
+def f353():
+    print("Funcao 353 chamada")
+    f357()
+
+def f354():
+    print("Funcao 354 chamada")
+    f358()
+
+def f355():
+    print("Funcao 355 chamada")
+    f359()
+
+def f356():
+    print("Funcao 356 chamada")
+    f360()
+
+def f357():
+    print("Funcao 357 chamada")
+    f361()
+
+def f358():
+    print("Funcao 358 chamada")
+    f362()
+
+def f359():
+    print("Funcao 359 chamada")
+    f363()
+
+def f360():
+    print("Funcao 360 chamada")
+    f364()
+
+def f361():
+    print("Funcao 361 chamada")
+    f365()
+
+def f362():
+    print("Funcao 362 chamada")
+    f366()
+
+def f363():
+    print("Funcao 363 chamada")
+    f367()
+
+def f364():
+    print("Funcao 364 chamada")
+    f368()
+
+def f365():
+    print("Funcao 365 chamada")
+    f369()
+
+def f366():
+    print("Funcao 366 chamada")
+    f370()
+
+def f367():
+    print("Funcao 367 chamada")
+    f371()
+
+def f368():
+    print("Funcao 368 chamada")
+    f372()
+
+def f369():
+    print("Funcao 369 chamada")
+    f373()
+
+def f370():
+    print("Funcao 370 chamada")
+    f374()
+
+def f371():
+    print("Funcao 371 chamada")
+    f375()
+
+def f372():
+    print("Funcao 372 chamada")
+    f376()
+
+def f373():
+    print("Funcao 373 chamada")
+    f377()
+
+def f374():
+    print("Funcao 374 chamada")
+    f378()
+
+def f375():
+    print("Funcao 375 chamada")
+    f379()
+
+def f376():
+    print("Funcao 376 chamada")
+    f380()
+
+def f377():
+    print("Funcao 377 chamada")
+    f381()
+
+def f378():
+    print("Funcao 378 chamada")
+    f382()
+
+def f379():
+    print("Funcao 379 chamada")
+    f383()
+
+def f380():
+    print("Funcao 380 chamada")
+    f384()
+
+def f381():
+    print("Funcao 381 chamada")
+    f385()
+
+def f382():
+    print("Funcao 382 chamada")
+    f386()
+
+def f383():
+    print("Funcao 383 chamada")
+    f387()
+
+def f384():
+    print("Funcao 384 chamada")
+    f388()
+
+def f385():
+    print("Funcao 385 chamada")
+    f389()
+
+def f386():
+    print("Funcao 386 chamada")
+    f390()
+
+def f387():
+    print("Funcao 387 chamada")
+    f391()
+
+def f388():
+    print("Funcao 388 chamada")
+    f392()
+
+def f389():
+    print("Funcao 389 chamada")
+    f393()
+
+def f390():
+    print("Funcao 390 chamada")
+    f394()
+
+def f391():
+    print("Funcao 391 chamada")
+    f395()
+
+def f392():
+    print("Funcao 392 chamada")
+    f396()
+
+def f393():
+    print("Funcao 393 chamada")
+    f397()
+
+def f394():
+    print("Funcao 394 chamada")
+    f398()
+
+def f395():
+    print("Funcao 395 chamada")
+    f399()
+
+def f396():
+    print("Funcao 396 chamada")
+    f400()
+
+def f397():
+    print("Funcao 397 chamada")
+    f401()
+
+def f398():
+    print("Funcao 398 chamada")
+    f402()
+
+def f399():
+    print("Funcao 399 chamada")
+    f403()
+
+def f400():
+    print("Funcao 400 chamada")
+    f404()
+
+def f401():
+    print("Funcao 401 chamada")
+    f405()
+
+def f402():
+    print("Funcao 402 chamada")
+    f406()
+
+def f403():
+    print("Funcao 403 chamada")
+    f407()
+
+def f404():
+    print("Funcao 404 chamada")
+    f408()
+
+def f405():
+    print("Funcao 405 chamada")
+    f409()
+
+def f406():
+    print("Funcao 406 chamada")
+    f410()
+
+def f407():
+    print("Funcao 407 chamada")
+    f411()
+
+def f408():
+    print("Funcao 408 chamada")
+    f412()
+
+def f409():
+    print("Funcao 409 chamada")
+    f413()
+
+def f410():
+    print("Funcao 410 chamada")
+    f414()
+
+def f411():
+    print("Funcao 411 chamada")
+    f415()
+
+def f412():
+    print("Funcao 412 chamada")
+    f416()
+
+def f413():
+    print("Funcao 413 chamada")
+    f417()
+
+def f414():
+    print("Funcao 414 chamada")
+    f418()
+
+def f415():
+    print("Funcao 415 chamada")
+    f419()
+
+def f416():
+    print("Funcao 416 chamada")
+    f420()
+
+def f417():
+    print("Funcao 417 chamada")
+    f421()
+
+def f418():
+    print("Funcao 418 chamada")
+    f422()
+
+def f419():
+    print("Funcao 419 chamada")
+    f423()
+
+def f420():
+    print("Funcao 420 chamada")
+    f424()
+
+def f421():
+    print("Funcao 421 chamada")
+    f425()
+
+def f422():
+    print("Funcao 422 chamada")
+    f426()
+
+def f423():
+    print("Funcao 423 chamada")
+    f427()
+
+def f424():
+    print("Funcao 424 chamada")
+    f428()
+
+def f425():
+    print("Funcao 425 chamada")
+    f429()
+
+def f426():
+    print("Funcao 426 chamada")
+    f430()
+
+def f427():
+    print("Funcao 427 chamada")
+    f431()
+
+def f428():
+    print("Funcao 428 chamada")
+    f432()
+
+def f429():
+    print("Funcao 429 chamada")
+    f433()
+
+def f430():
+    print("Funcao 430 chamada")
+    f434()
+
+def f431():
+    print("Funcao 431 chamada")
+    f435()
+
+def f432():
+    print("Funcao 432 chamada")
+    f436()
+
+def f433():
+    print("Funcao 433 chamada")
+    f437()
+
+def f434():
+    print("Funcao 434 chamada")
+    f438()
+
+def f435():
+    print("Funcao 435 chamada")
+    f439()
+
+def f436():
+    print("Funcao 436 chamada")
+    f440()
+
+def f437():
+    print("Funcao 437 chamada")
+    f441()
+
+def f438():
+    print("Funcao 438 chamada")
+    f442()
+
+def f439():
+    print("Funcao 439 chamada")
+    f443()
+
+def f440():
+    print("Funcao 440 chamada")
+    f444()
+
+def f441():
+    print("Funcao 441 chamada")
+    f445()
+
+def f442():
+    print("Funcao 442 chamada")
+    f446()
+
+def f443():
+    print("Funcao 443 chamada")
+    f447()
+
+def f444():
+    print("Funcao 444 chamada")
+    f448()
+
+def f445():
+    print("Funcao 445 chamada")
+    f449()
+
+def f446():
+    print("Funcao 446 chamada")
+    f450()
+
+def f447():
+    print("Funcao 447 chamada")
+    f451()
+
+def f448():
+    print("Funcao 448 chamada")
+    f452()
+
+def f449():
+    print("Funcao 449 chamada")
+    f453()
+
+def f450():
+    print("Funcao 450 chamada")
+    f454()
+
+def f451():
+    print("Funcao 451 chamada")
+    f455()
+
+def f452():
+    print("Funcao 452 chamada")
+    f456()
+
+def f453():
+    print("Funcao 453 chamada")
+    f457()
+
+def f454():
+    print("Funcao 454 chamada")
+    f458()
+
+def f455():
+    print("Funcao 455 chamada")
+    f459()
+
+def f456():
+    print("Funcao 456 chamada")
+    f460()
+
+def f457():
+    print("Funcao 457 chamada")
+    f461()
+
+def f458():
+    print("Funcao 458 chamada")
+    f462()
+
+def f459():
+    print("Funcao 459 chamada")
+    f463()
+
+def f460():
+    print("Funcao 460 chamada")
+    f464()
+
+def f461():
+    print("Funcao 461 chamada")
+    f465()
+
+def f462():
+    print("Funcao 462 chamada")
+    f466()
+
+def f463():
+    print("Funcao 463 chamada")
+    f467()
+
+def f464():
+    print("Funcao 464 chamada")
+    f468()
+
+def f465():
+    print("Funcao 465 chamada")
+    f469()
+
+def f466():
+    print("Funcao 466 chamada")
+    f470()
+
+def f467():
+    print("Funcao 467 chamada")
+    f471()
+
+def f468():
+    print("Funcao 468 chamada")
+    f472()
+
+def f469():
+    print("Funcao 469 chamada")
+    f473()
+
+def f470():
+    print("Funcao 470 chamada")
+    f474()
+
+def f471():
+    print("Funcao 471 chamada")
+    f475()
+
+def f472():
+    print("Funcao 472 chamada")
+    f476()
+
+def f473():
+    print("Funcao 473 chamada")
+    f477()
+
+def f474():
+    print("Funcao 474 chamada")
+    f478()
+
+def f475():
+    print("Funcao 475 chamada")
+    f479()
+
+def f476():
+    print("Funcao 476 chamada")
+    f480()
+
+def f477():
+    print("Funcao 477 chamada")
+    f481()
+
+def f478():
+    print("Funcao 478 chamada")
+    f482()
+
+def f479():
+    print("Funcao 479 chamada")
+    f483()
+
+def f480():
+    print("Funcao 480 chamada")
+    f484()
+
+def f481():
+    print("Funcao 481 chamada")
+    f485()
+
+def f482():
+    print("Funcao 482 chamada")
+    f486()
+
+def f483():
+    print("Funcao 483 chamada")
+    f487()
+
+def f484():
+    print("Funcao 484 chamada")
+    f488()
+
+def f485():
+    print("Funcao 485 chamada")
+    f489()
+
+def f486():
+    print("Funcao 486 chamada")
+    f490()
+
+def f487():
+    print("Funcao 487 chamada")
+    f491()
+
+def f488():
+    print("Funcao 488 chamada")
+    f492()
+
+def f489():
+    print("Funcao 489 chamada")
+    f493()
+
+def f490():
+    print("Funcao 490 chamada")
+    f494()
+
+def f491():
+    print("Funcao 491 chamada")
+    f495()
+
+def f492():
+    print("Funcao 492 chamada")
+    f496()
+
+def f493():
+    print("Funcao 493 chamada")
+    f497()
+
+def f494():
+    print("Funcao 494 chamada")
+    f498()
+
+def f495():
+    print("Funcao 495 chamada")
+    f499()
+
+def f496():
+    print("Funcao 496 chamada")
+    f500()
+
+def f497():
+    print("Funcao 497 chamada")
+    f500()
+
+def f498():
+    print("Funcao 498 chamada")
+    f500()
+
+def f499():
+    print("Funcao 499 chamada")
+    f500()
+
+def f500():
+    print("Funcao 500 chamada")
+ input/file/func2.py view
@@ -0,0 +1,468 @@+import random+import math+import itertools+import time++def f1():+    print("Funcao 1 chamada")+    f2()++def f2():+    print("Funcao 2 chamada")+    f3()++def f3():+    print("Funcao 3 chamada")+    f4()++def f4():+    print("Funcao 4 chamada")+    f5()++def f5():+    print("Funcao 5 chamada")+    f6()++def f6():+    print("Funcao 6 chamada")+    f7()++def f7():+    print("Funcao 7 chamada")+    f8()++def f8():+    print("Funcao 8 chamada")+    f9()++def f9():+    print("Funcao 9 chamada")+    f10()++def f10():+    print("Funcao 10 chamada")+    f11()++def f11():+    print("Funcao 11 chamada")+    f12()++def f12():+    print("Funcao 12 chamada")+    f13()++def f13():+    print("Funcao 13 chamada")+    f14()++def f14():+    print("Funcao 14 chamada")+    f15()++def f15():+    print("Funcao 15 chamada")+    f16()++def f16():+    print("Funcao 16 chamada")+    f17()++def f17():+    print("Funcao 17 chamada")+    f18()++def f18():+    print("Funcao 18 chamada")+    f19()++def f19():+    print("Funcao 19 chamada")+    f20()++def f20():+    print("Funcao 20 chamada")+    f21()++def f21():+    print("Funcao 21 chamada")+    f22()++def f22():+    print("Funcao 22 chamada")+    f23()++def f23():+    print("Funcao 23 chamada")+    f24()++def f24():+    print("Funcao 24 chamada")+    f25()++def f25():+    print("Funcao 25 chamada")+    f26()++def f26():+    print("Funcao 26 chamada")+    f27()++def f27():+    print("Funcao 27 chamada")+    f28()++def f28():+    print("Funcao 28 chamada")+    f29()++def f29():+    print("Funcao 29 chamada")+    f30()++def f30():+    print("Funcao 30 chamada")+    f31()++def f31():+    print("Funcao 31 chamada")+    f32()++def f32():+    print("Funcao 32 chamada")+    f33()++def f33():+    print("Funcao 33 chamada")+    f34()++def f34():+    print("Funcao 34 chamada")+    f35()++def f35():+    print("Funcao 35 chamada")+    f36()++def f36():+    print("Funcao 36 chamada")+    f37()++def f37():+    print("Funcao 37 chamada")+    f38()++def f38():+    print("Funcao 38 chamada")+    f39()++def f39():+    print("Funcao 39 chamada")+    f40()++def f40():+    print("Funcao 40 chamada")+    f41()++def f41():+    print("Funcao 41 chamada")+    f42()++def f42():+    print("Funcao 42 chamada")+    f43()++def f43():+    print("Funcao 43 chamada")+    f44()++def f44():+    print("Funcao 44 chamada")+    f45()++def f45():+    print("Funcao 45 chamada")+    f46()++def f46():+    print("Funcao 46 chamada")+    f47()++def f47():+    print("Funcao 47 chamada")+    f48()++def f48():+    print("Funcao 48 chamada")+    f49()++def f49():+    print("Funcao 49 chamada")+    f50()++def f50():+    print("Funcao 50 chamada")+    f51()++def f51():+    print("Funcao 51 chamada")+    f52()++def f52():+    print("Funcao 52 chamada")+    f53()++def f53():+    print("Funcao 53 chamada")+    f54()++def f54():+    print("Funcao 54 chamada")+    f55()++def f55():+    print("Funcao 55 chamada")+    f56()++def f56():+    print("Funcao 56 chamada")+    f57()++def f57():+    print("Funcao 57 chamada")+    f58()++def f58():+    print("Funcao 58 chamada")+    f59()++def f59():+    print("Funcao 59 chamada")+    f60()++def f60():+    print("Funcao 60 chamada")+    f61()++def f61():+    print("Funcao 61 chamada")+    f62()++def f62():+    print("Funcao 62 chamada")+    f63()++def f63():+    print("Funcao 63 chamada")+    f64()++def f64():+    print("Funcao 64 chamada")+    f65()++def f65():+    print("Funcao 65 chamada")+    f66()++def f66():+    print("Funcao 66 chamada")+    f67()++def f67():+    print("Funcao 67 chamada")+    f68()++def f68():+    print("Funcao 68 chamada")+    f69()++def f69():+    print("Funcao 69 chamada")+    f70()++def f70():+    print("Funcao 70 chamada")+    f71()++def f71():+    print("Funcao 71 chamada")+    f72()++def f72():+    print("Funcao 72 chamada")+    f73()++def f73():+    print("Funcao 73 chamada")+    f74()++def f74():+    print("Funcao 74 chamada")+    f75()++def f75():+    print("Funcao 75 chamada")+    f76()++def f76():+    print("Funcao 76 chamada")+    f77()++def f77():+    print("Funcao 77 chamada")+    f78()++def f78():+    print("Funcao 78 chamada")+    f79()++def f79():+    print("Funcao 79 chamada")+    f80()++def f80():+    print("Funcao 80 chamada")+    f81()++def f81():+    print("Funcao 81 chamada")+    f82()++def f82():+    print("Funcao 82 chamada")+    f83()++def f83():+    print("Funcao 83 chamada")+    f84()++def f84():+    print("Funcao 84 chamada")+    f85()++def f85():+    print("Funcao 85 chamada")+    f86()++def f86():+    print("Funcao 86 chamada")+    f87()++def f87():+    print("Funcao 87 chamada")+    f88()++def f88():+    print("Funcao 88 chamada")+    f89()++def f89():+    print("Funcao 89 chamada")+    f90()++def f90():+    print("Funcao 90 chamada")+    f91()++def f91():+    print("Funcao 91 chamada")+    f92()++def f92():+    print("Funcao 92 chamada")+    f93()++def f93():+    print("Funcao 93 chamada")+    f94()++def f94():+    print("Funcao 94 chamada")+    f95()++def f95():+    print("Funcao 95 chamada")+    f96()++def f96():+    print("Funcao 96 chamada")+    f97()++def f97():+    print("Funcao 97 chamada")+    f98()++def f98():+    print("Funcao 98 chamada")+    f99()++def f99():+    print("Funcao 99 chamada")+    f101()++def f101():+    num = random.randint(1, 100)+    print(f"Funcao 101 chamada - Raiz quadrada de {num}: {math.sqrt(num)}")+    f102()++def f102():+    num = random.randint(1, 100)+    print(f"Funcao 102 chamada - Raiz quadrada de {num}: {math.sqrt(num)}")+    f103()++def f103():+    nums = [1, 2, 3, 4]+    combinations = list(itertools.combinations(nums, 2))+    print(f"Funcao 103 chamada - Combinacoes de 2 elementos: {combinations}")+    f104()++def f104():+    nums = [1, 2, 3, 4]+    permutations = list(itertools.permutations(nums, 3))+    print(f"Funcao 104 chamada - Permutacoes de 3 elementos: {permutations}")+    f105()++def f105():+    nums = [1, 2, 3, 4]+    product = list(itertools.product(nums))+    print(f"Funcao 105 chamada - Produto cartesiano: {product}")+    f106()++def f106():+    start_time = time.time()+    time.sleep(1)+    end_time = time.time()+    print(f"Funcao 106 chamada - Tempo de execucao: {end_time - start_time} segundos")+    f107()++def f107():+    start_time = time.time()+    time.sleep(2)+    end_time = time.time()+    print(f"Funcao 107 chamada - Tempo de execucao: {end_time - start_time} segundos")+    f108()++def f108():+    num = random.randint(1, 100)+    print(f"Funcao 108 chamada - Numero aleatorio: {num}")+    f109()++def f109():+    num = random.randint(1, 100)+    print(f"Funcao 109 chamada - Numero aleatorio: {num}")+    f110()++def f110():+    num = random.randint(1, 100)+    if num % 2 == 0:+        print(f"Funcao 110 chamada - Numero par: {num}")+    f111()++def f111():+    num = random.randint(1, 100)+    if num % 2 == 0:+        print(f"Funcao 111 chamada - Numero par: {num}")+    f500()+++def f500():+    print("Funcao 500 chamada - Fim do codigo!")
+ input/file/func3.py view
@@ -0,0 +1,104 @@+import random+import math+from collections import deque++def calcular_fatorial(n):+    if n == 0 or n == 1:+        return 1+    else:+        return n * calcular_fatorial(n - 1)++def fibonacci(n):+    if n <= 1:+        return n+    else:+        return fibonacci(n - 1) + fibonacci(n - 2)++def busca_binaria(lista, alvo, baixo=0, alto=None):+    if alto is None:+        alto = len(lista) - 1+    +    if baixo > alto:+        return -1+    +    meio = (baixo + alto) // 2+    if lista[meio] == alvo:+        return meio+    elif lista[meio] > alvo:+        return busca_binaria(lista, alvo, baixo, meio - 1)+    else:+        return busca_binaria(lista, alvo, meio + 1, alto)++def quicksort(lista):+    if len(lista) <= 1:+        return lista+    pivo = lista[0]+    menores = [x for x in lista[1:] if x <= pivo]+    maiores = [x for x in lista[1:] if x > pivo]+    return quicksort(menores) + [pivo] + quicksort(maiores)++def calcular_raiz_quadrada(x):+    return math.sqrt(x)++def gerar_lista_aleatoria(tamanho, limite):+    return [random.randint(1, limite) for _ in range(tamanho)]++def somar_lista(lista):+    if not lista:+        return 0+    else:+        return lista[0] + somar_lista(lista[1:])++def largura_primeira(grafo, inicio):+    visitados = set()+    fila = deque([inicio])+    ordem_visita = []++    while fila:+        vertice = fila.popleft()+        if vertice not in visitados:+            visitados.add(vertice)+            ordem_visita.append(vertice)+            fila.extend(grafo[vertice])+    +    return ordem_visita++def profundidade_primeira(grafo, vertice, visitados=None):+    if visitados is None:+        visitados = set()++    visitados.add(vertice)+    ordem_visita = [vertice]++    for vizinho in grafo[vertice]:+        if vizinho not in visitados:+            ordem_visita += profundidade_primeira(grafo, vizinho, visitados)+    +    return ordem_visita++def funcao_principal():+    n = random.randint(1, 10)+    lista_aleatoria = gerar_lista_aleatoria(10, 100)+    lista_ordenada = quicksort(lista_aleatoria)+    +    print(f"Fatorial de {n}: {calcular_fatorial(n)}")+    print(f"Fibonacci de {n}: {fibonacci(n)}")+    print(f"Soma da lista {lista_aleatoria}: {somar_lista(lista_aleatoria)}")+    print(f"Raiz quadrada de {n}: {calcular_raiz_quadrada(n)}")+    print(f"Lista aleatória ordenada: {lista_ordenada}")+    +    alvo = random.choice(lista_ordenada)+    resultado_busca = busca_binaria(lista_ordenada, alvo)+    print(f"Resultado da busca binária pelo valor {alvo}: {resultado_busca}")+    +    grafo = {+        'A': ['B', 'C'],+        'B': ['A', 'D', 'E'],+        'C': ['A', 'F'],+        'D': ['B'],+        'E': ['B', 'F'],+        'F': ['C', 'E']+    }+    +    print(f"Ordem de visita em largura a partir de 'A': {largura_primeira(grafo, 'A')}")+    print(f"Ordem de visita em profundidade a partir de 'A': {profundidade_primeira(grafo, 'A')}")
+ input/file/if.py view
@@ -0,0 +1,6 @@+if not a:+    print(b)+    print(b1)+else:+    print(c)+    print(c1)
+ input/file/if2.py view
@@ -0,0 +1,5 @@+letra = input("Digite f ou F: ")+if (letra == 'f', letra == 'F'):+    print("OK")+else:+    print("ERRO")
+ input/file/language.txt view
@@ -0,0 +1,1 @@+f(g)
+ input/file/repeat_a.txt view
@@ -0,0 +1,1 @@+aaaaaaaaaaaaaa
+ input/file/wiki.txt view
@@ -0,0 +1,1 @@+xxxxxq
+ input/pattern/call_graph.pat view
@@ -0,0 +1,11 @@+pattern call : function_call := #name:identifier @space "(" @space #v:(expr_list?) ")" ε++-- pattern call2 : function_call := #name:identifier @space "(" @space @teste ")"+--pattern teste : expr_list := #v:expr1 @space (#s:sep #v2:expr1 @space)*+--pattern teste : expr_list := #v:expr1 @space (#s:sep #v1:expr1 @space) +-- pattern teste : expr_list := #v:expr1 @space (#s:sep #v1:expr1 @space) (#s:sep #v2:expr1 @space)+-- pattern teste : expr_list := #v:expr1 @space++pattern definition : function_def := ("def" @space #name:identifier "(" @space #p:(id_list?) ")" @space ":") #block:(statement*)++pattern space : space := " "*
+ input/pattern/expression.pat view
@@ -0,0 +1,7 @@+-- pattern sum : E := #e1:T #e2:A+-- pattern a : E := (T := (F := "(" #m:E ")") ("*" (F := "3" ε)) ) ε+pattern a : T := (F := "(" #X:E ")") ("*" #Y:F)+pattern e : T := #X:F ("*" #Y:F)+pattern b : E := #v:E+pattern c : n := "1"+pattern d : F := "(" #X:E ")"
+ input/pattern/factorial.pat view
@@ -0,0 +1,6 @@+pattern factorial_call : function_call := (identifier := "math.factorial") @space "(" @space #v2:(expr_list?) ")" ε+-- pattern factorial_call : function_call := (identifier := "math.factorial") @space "(" @space #v2:(expr_list?) ")" #v3:(("." primary)?)+pattern space : space := " "*++-- pattern factorial_call : function_call := (identifier := "math.factorial") "(" #v2:expr_list? ")"+-- Não vai casar se tiver dentro de uma f-string, se importar só a função ou se importar a math com outro nome
+ input/pattern/subst_if.pat view
@@ -0,0 +1,11 @@+pattern if_def : if_stmt := (("if" @space @expr ":") #ifBlock:(statement*)) @elseBlock+pattern elseBlock : else_block := ("else" @space ":") #elseBlock:(statement*)++pattern subst : if_stmt := (("if" @space #condition:expression ":") #elseBlock:(statement*)) @elseBlock2+pattern elseBlock2 : else_block := ("else" @space ":") #ifBlock:(statement*)++pattern expr    : expression := @orExpr ε+pattern orExpr  : or_expr    := @andExpr ε+pattern andExpr : and_expr   := "not" @space #condition:comparison++pattern space : space := " "*
+ input/peg/expression.peg view
@@ -0,0 +1,4 @@+E <- T ("+" T)*+T <- F ("*" F)* +F <- n / "(" E ")"+^n <- [0-9]+
+ input/peg/grammar.peg view
@@ -0,0 +1,5 @@+E <- (T "+")* T+T <- (F "*")* F+F <- Num / Var / "(" E ")"+Num <- [0-9]++Var <- [a-zA-Z] [a-zA-Z_0-9]*
+ input/peg/peg.peg view
@@ -0,0 +1,38 @@+-- Hierarchical syntax+Grammar     <- Spacing Definition+ EndOfFile+Definition  <- Identifier LEFTARROW Expression++Expression  <- Sequence (SLASH Sequence)*+Sequence    <- Prefix*+Prefix      <- (AND / NOT)? Suffix+Suffix      <- Primary (QUESTION / STAR / PLUS)?+Primary     <- Identifier !LEFTARROW / OPEN Expression CLOSE / Literal / Class / DOT++-- Lexical syntax+Identifier  <- IdentStart IdentCont* Spacing+IdentStart  <- [a-zA-Z_]+IdentCont   <- IdentStart / [0-9]++Literal     <- ["] (!["] Char)* ["] Spacing / ['] (!['] Char)* ['] Spacing+Class       <- "[" (!"]" Range)* "]" Spacing+Range       <- Char "-" Char / Char+Char        <- Escaped / "\\" [0-2][0-7][0-7] / "\\" [0-7][0-7]? / !"\\" .+Escaped     <- "\\" Escaped2+Escaped2    <- [nrt'"] / "[" / "]" / "\\"++LEFTARROW   <- "<-" Spacing+SLASH       <- "/" Spacing+AND         <- "&" Spacing+NOT         <- "!" Spacing+QUESTION    <- "?" Spacing+STAR        <- "*" Spacing+PLUS        <- "+" Spacing+OPEN        <- "(" Spacing+CLOSE       <- ")" Spacing+DOT         <- "." Spacing++Spacing     <- (Space / Comment)*+Comment     <- "--" (!EndOfLine .)* EndOfLine+Space       <- " " / "\t" / EndOfLine+EndOfLine   <- "\r\n" / "\n" / "\r"+EndOfFile   <- !.
+ input/peg/python.peg view
@@ -0,0 +1,65 @@+file <- (blank* newline)* statement+++-- TODO: Será que faz sentido isso? Um comentário ser uma declaração?+statement <- (compound / simple / comment) blank* newline*++compound <- function_def / if_stmt / while_stmt / for_stmt++function_def <- ("def" space identifier "(" space id_list? ")" space ":") > statement+if_stmt      <- (("if" space expression ":") > statement) (elif_block / else_block)?+elif_block   <- (("elif" space expression ":") > statement) (elif_block / else_block)?+else_block   <- ("else" space ":") > statement++while_stmt   <- ("while" space expression space ":") > statement+for_stmt     <- ("for" space identifier space "in" space expression ":") > statement++simple <- import_stmt / assignment / return_stmt / expression+return_stmt <- "return" space expr_list+import_stmt <- simple_import / from_import+simple_import <- "import" space identifier+from_import <- "from" space identifier space "import" space (id_list / "*")++assignment <- id_list space attr space expression+attr       <- "=" / "+=" / "-=" / "*=" / "/="++expression <- or_expr ("or" space or_expr)*+or_expr    <- and_expr ("and" space and_expr)*+and_expr   <- "not" space comparison / comparison+comparison <- sum (op_comp sum)*+sum        <- term (op_term term)* +term       <- factor (op_factor factor)*+factor     <- power (op_power power)*+power      <- "-" neg / neg+neg        <- primary space / "(" space expression ")" space++op_comp   <- ("==" / "!=" / "<=" / ">=" / "<" / ">") space+op_term   <- ("+" / "-") space+op_factor <- ("*" / "/" / "%") space+op_power  <- "**" space++primary <- function_call / array_access / "[" items? "]" / atom+function_call <- identifier space "(" space expr_list? ")" ("." primary)?+-- function_call <- identifier "(" expr_list? ")"+array_access <- identifier space "[" space expression "]" ("." primary)?++atom      <- "True" / "False" / "None" / number / strings / identifier+expr_list <- expr1 space (sep expr1 space)*+expr1     <- (single_id space "=" space)? expression+items     <- expression (sep expression space)*+id_list   <- identifier space (sep identifier space)*++sep <- "," space++^strings <- fstring / string+fstring <- "f" string+string  <- ['] (!['] char)* ['] / ["] (!["] char)* ["]+-- TODO: Fazer uma forma mais fácil+char    <- [a-zA-Z0-9 :{}.,;^+-*/%()_!?áéúçã] / "[" / "]"++^identifier <- single_id ("." single_id)*+single_id   <- [a-zA-Z] [a-zA-Z0-9_]*+^number     <- [0-9]++space       <- " "*+^blank       <- comment / " "+^comment    <- "#" char*+^newline    <- "\r\n" / "\r" / "\n"
+ input/peg/repeat_a.peg view
@@ -0,0 +1,1 @@+A <- "a"+ (!.)
+ input/peg/tarefa1.peg view
@@ -0,0 +1,46 @@+file <- line (newline line)*++line      <- statement blank comment? / comment / blank+statement <- simple++simple        <- import_stmt / assignment / expression+import_stmt   <- simple_import / from_import+simple_import <- "import" blank identifier+from_import   <- "from" blank identifier blank "import" blank (id_list / "*")++assignment <- id_list blank attr blank expression+attr       <- "=" / "+=" / "-=" / "*=" / "/="++expression <- term (blank op_term blank term)* +term       <- factor (blank op_factor blank factor)*+factor     <- power (blank op_power blank power)*+power      <- ("-" / "+") signed / signed+signed     <- primary / "(" blank expression blank ")"++op_term   <- ("+" / "-")+op_factor <- ("*" / "//" / "/" / "%")+op_power  <- "**"++primary       <- function_call / atom+function_call <- identifier blank "(" blank expr_list? blank ")"++atom      <- "True" / "False" / "None" / number / strings / identifier+expr_list <- expr1 (blank sep expr1)*+expr1     <- (single_id blank "=" blank)? expression+id_list   <- identifier (blank sep identifier)*++sep <- "," blank++^strings <- fstring / string+fstring  <- "f" string+string   <- ['] (!['] char)* ['] / ["] (!["] char)* ["]+-- TODO: Fazer uma forma mais fácil+char     <- [a-zA-Z0-9 :{}.,;=^~+-*/%$<>()_!?#\t\\áéíóúãõâêôàçÁÉÍÓÚÃÕÂÊÔÀÇ'"ẽĩũîûẼĨŨÎÛ] / "[" / "]"++^identifier <- single_id ("." single_id)*+single_id   <- [a-zA-Z] [a-zA-Z0-9_]*+^number     <- [0-9]+ ("." [0-9]+)?+^blank      <- space*+space       <- " " / "\t"+^comment    <- "#" char*+^newline    <- "\r\n" / "\r" / "\n"
+ input/peg/tarefa10.peg view
@@ -0,0 +1,62 @@+file <- line+++line      <- statement / comment newline / blank newline+statement <- compound / simple blank comment? newline?++compound <- if_stmt / while_stmt / for_stmt / function_def++function_def <- ("def" blank identifier blank "(" blank id_list? blank ")" blank ":" blank comment?) > line+if_stmt      <- (("if" blank expression blank ":" blank comment?) > line) (elif_stmt / else_stmt)?+elif_stmt    <- (("elif" blank expression blank ":" blank comment?) > line) (elif_stmt / else_stmt)?+else_stmt    <- ("else" blank ":" blank comment?) > line++while_stmt   <- ("while" blank expression blank ":" blank comment?) > line+for_stmt     <- ("for" blank identifier blank "in" blank expression blank ":" blank comment?) > line++simple        <- import_stmt / assignment / return_stmt / expression+import_stmt   <- simple_import / from_import+simple_import <- "import" blank identifier+from_import   <- "from" blank identifier blank "import" blank (id_list / "*")+return_stmt   <- "return" blank (expr_list / "(" blank expr_list blank ")")++assignment <- id_list blank attr blank expression+attr       <- "=" / "+=" / "-=" / "*=" / "/="++expression <- or_expr (blank "or" blank or_expr)*+or_expr    <- and_expr (blank "and" blank and_expr)*+and_expr   <- "not" blank comparison / comparison+comparison <- sum (blank op_comp blank sum)*+sum        <- term (blank op_term blank term)* +term       <- factor (blank op_factor blank factor)*+factor     <- power (blank op_power blank power)*+power      <- ("-" / "+") signed / signed+signed     <- primary / "(" blank expression blank ")"++op_comp   <- ("==" / "!=" / "<=" / ">=" / "<" / ">")+op_term   <- ("+" / "-")+op_factor <- ("*" / "//" / "/" / "%")+op_power  <- "**"++primary       <- function_call / atom+function_call <- identifier blank "(" blank expr_list? blank ")"++atom      <- "True" / "False" / "None" / number / strings / identifier+expr_list <- expr1 (blank sep expr1)*+expr1     <- (single_id blank "=" blank)? expression+id_list   <- identifier (blank sep identifier)*++sep <- "," blank++^strings <- fstring / string+fstring  <- "f" string+string   <- ['] (!['] char)* ['] / ["] (!["] char)* ["]+-- TODO: Fazer uma forma mais fácil+char     <- [a-zA-Z0-9 :{}.,;=^~+-*/%$<>()_!?#\t\\áéíóúãõâêôàçÁÉÍÓÚÃÕÂÊÔÀÇ'"ẽĩũîûẼĨŨÎÛ] / "[" / "]"++^identifier <- single_id ("." single_id)*+single_id   <- [a-zA-Z] [a-zA-Z0-9_]*+^number     <- [0-9]+ ("." [0-9]+)?+^blank      <- space*+space       <- " " / "\t"+^comment    <- "#" char*+^newline    <- "\r\n" / "\r" / "\n"
+ input/peg/tarefa12.peg view
@@ -0,0 +1,64 @@+file <- line+++line      <- statement / comment newline / blank newline+statement <- compound / simple blank comment? newline?++compound <- if_stmt / while_stmt / for_stmt / function_def++function_def <- ("def" blank identifier blank "(" blank id_list? blank ")" blank ":" blank comment?) > line+if_stmt      <- (("if" blank expression blank ":" blank comment?) > line) (elif_stmt / else_stmt)?+elif_stmt    <- (("elif" blank expression blank ":" blank comment?) > line) (elif_stmt / else_stmt)?+else_stmt    <- ("else" blank ":" blank comment?) > line++while_stmt   <- ("while" blank expression blank ":" blank comment?) > line+for_stmt     <- ("for" blank identifier blank "in" blank expression blank ":" blank comment?) > line++simple        <- import_stmt / assignment / return_stmt / expression+import_stmt   <- simple_import / from_import+simple_import <- "import" blank identifier+from_import   <- "from" blank identifier blank "import" blank (id_list / "*")+return_stmt   <- "return" blank (expr_list / "(" blank expr_list blank ")")++assignment <- id_list blank attr blank expression+attr       <- "=" / "+=" / "-=" / "*=" / "/="++expression <- or_expr (blank "or" blank or_expr)*+or_expr    <- and_expr (blank "and" blank and_expr)*+and_expr   <- "not" blank comparison / comparison+comparison <- sum (blank op_comp blank sum)*+sum        <- term (blank op_term blank term)* +term       <- factor (blank op_factor blank factor)*+factor     <- power (blank op_power blank power)*+power      <- ("-" / "+") signed / signed+signed     <- primary / "(" blank expression blank ")"++op_comp   <- ("==" / "!=" / "<=" / ">=" / "<" / ">")+op_term   <- ("+" / "-")+op_factor <- ("*" / "//" / "/" / "%")+op_power  <- "**"++primary       <- function_call / array_access / "[" blank items? blank "]" / atom+function_call <- identifier blank "(" blank expr_list? blank ")"+array_access  <- identifier (blank "[" blank expression blank "]")+++atom      <- "True" / "False" / "None" / number / strings / identifier+expr_list <- expr1 (blank sep expr1)*+expr1     <- (single_id blank "=" blank)? expression+id_list   <- identifier (blank sep identifier)*+items     <- expression (blank sep expression)*++sep <- "," blank++^strings <- fstring / string+fstring  <- "f" string+string   <- ['] (!['] char)* ['] / ["] (!["] char)* ["]+-- TODO: Fazer uma forma mais fácil+char     <- [a-zA-Z0-9 :{}.,;=^~+-*/%$<>()_!?#\t\\áéíóúãõâêôàçÁÉÍÓÚÃÕÂÊÔÀÇ'"ẽĩũîûẼĨŨÎÛ] / "[" / "]"++^identifier <- single_id ("." single_id)*+single_id   <- [a-zA-Z] [a-zA-Z0-9_]*+^number     <- [0-9]+ ("." [0-9]+)?+^blank      <- space*+space       <- " " / "\t"+^comment    <- "#" char*+^newline    <- "\r\n" / "\r" / "\n"
+ input/peg/tarefa17.peg view
@@ -0,0 +1,68 @@+file <- line+++line      <- statement / comment newline / blank newline+statement <- compound / simple blank comment? newline?++compound <- if_stmt / while_stmt / for_stmt / function_def++function_def <- ("def" blank identifier blank "(" blank id_list? blank ")" blank ":" blank comment?) > line+if_stmt      <- (("if" blank expression blank ":" blank comment?) > line) (elif_stmt / else_stmt)?+elif_stmt    <- (("elif" blank expression blank ":" blank comment?) > line) (elif_stmt / else_stmt)?+else_stmt    <- ("else" blank ":" blank comment?) > line++while_stmt   <- ("while" blank expression blank ":" blank comment?) > line+for_stmt     <- ("for" blank identifier blank "in" blank expression blank ":" blank comment?) > line++simple        <- import_stmt / assignment / return_stmt / expression+import_stmt   <- simple_import / from_import+simple_import <- "import" blank identifier+from_import   <- "from" blank identifier blank "import" blank (id_list / "*")+return_stmt   <- "return" blank (expr_list / "(" blank expr_list blank ")")++assignment <- id_list blank attr blank expression_list+attr       <- "=" / "+=" / "-=" / "*=" / "/="++expression_list <- expression (blank sep expression)*++expression <- or_expr (blank "or" blank or_expr)*+or_expr    <- and_expr (blank "and" blank and_expr)*+and_expr   <- "not" blank comparison / comparison+comparison <- sum (blank op_comp blank sum)*+sum        <- term (blank op_term blank term)* +term       <- factor (blank op_factor blank factor)*+factor     <- power (blank op_power blank power)*+power      <- ("-" / "+") signed / signed+signed     <- primary / "(" blank expression blank ")"++op_comp   <- ("==" / "!=" / "<=" / ">=" / "<" / ">")+op_term   <- ("+" / "-")+op_factor <- ("*" / "//" / "/" / "%")+op_power  <- "**"++primary       <- function_call / array_access / "[" blank items? blank "]" / "{" blank dict? blank "}" / atom+function_call <- identifier blank "(" blank expr_list? blank ")"+array_access  <- identifier (blank "[" blank expression blank "]")+++atom      <- "True" / "False" / "None" / number / strings / identifier+expr_list <- expr1 (blank sep expr1)*+expr1     <- (single_id blank "=" blank)? expression+id_list   <- identifier (blank sep identifier)*+items     <- expression (blank sep expression)*+dict      <- dict_item (blank sep dict_item)*+dict_item <- expression blank ":" blank expression++sep <- "," blank++^strings <- fstring / string+fstring  <- "f" string+string   <- ['] (!['] char)* ['] / ["] (!["] char)* ["]+-- TODO: Fazer uma forma mais fácil+char     <- [a-zA-Z0-9 :{}.,;=^~+-*/%$<>()_!?#\t\\áéíóúãõâêôàçÁÉÍÓÚÃÕÂÊÔÀÇ'"ẽĩũîûẼĨŨÎÛ] / "[" / "]"++^identifier <- single_id ("." single_id)*+single_id   <- [a-zA-Z] [a-zA-Z0-9_]*+^number     <- [0-9]+ ("." [0-9]+)?+^blank      <- space*+space       <- " " / "\t"+^comment    <- "#" char*+^newline    <- "\r\n" / "\r" / "\n"
+ input/peg/tarefa3.peg view
@@ -0,0 +1,56 @@+file <- line+++line      <- statement / comment newline / blank newline+statement <- compound / simple blank comment? newline?++compound <- if_stmt++if_stmt     <- (("if" blank expression blank ":" blank comment?) > line) else_stmt?+else_stmt   <- ("else" blank ":" blank comment?) > line++simple        <- import_stmt / assignment / expression+import_stmt   <- simple_import / from_import+simple_import <- "import" blank identifier+from_import   <- "from" blank identifier blank "import" blank (id_list / "*")++assignment <- id_list blank attr blank expression+attr       <- "=" / "+=" / "-=" / "*=" / "/="++expression <- or_expr (blank "or" blank or_expr)*+or_expr    <- and_expr (blank "and" blank and_expr)*+and_expr   <- "not" blank comparison / comparison+comparison <- sum (blank op_comp blank sum)*+sum        <- term (blank op_term blank term)* +term       <- factor (blank op_factor blank factor)*+factor     <- power (blank op_power blank power)*+power      <- ("-" / "+") signed / signed+signed     <- primary / "(" blank expression blank ")"++op_comp   <- ("==" / "!=" / "<=" / ">=" / "<" / ">")+op_term   <- ("+" / "-")+op_factor <- ("*" / "//" / "/" / "%")+op_power  <- "**"++primary       <- function_call / atom+function_call <- identifier blank "(" blank expr_list? blank ")"++atom      <- "True" / "False" / "None" / number / strings / identifier+expr_list <- expr1 (blank sep expr1)*+expr1     <- (single_id blank "=" blank)? expression+id_list   <- identifier (blank sep identifier)*++sep <- "," blank++^strings <- fstring / string+fstring  <- "f" string+string   <- ['] (!['] char)* ['] / ["] (!["] char)* ["]+-- TODO: Fazer uma forma mais fácil+char     <- [a-zA-Z0-9 :{}.,;=^~+-*/%$<>()_!?#\t\\áéíóúãõâêôàçÁÉÍÓÚÃÕÂÊÔÀÇ'"ẽĩũîûẼĨŨÎÛ] / "[" / "]"++^identifier <- single_id ("." single_id)*+single_id   <- [a-zA-Z] [a-zA-Z0-9_]*+^number     <- [0-9]+ ("." [0-9]+)?+^blank      <- space*+space       <- " " / "\t"+^comment    <- "#" char*+^newline    <- "\r\n" / "\r" / "\n"
+ input/peg/tarefa4.peg view
@@ -0,0 +1,57 @@+file <- line+++line      <- statement / comment newline / blank newline+statement <- compound / simple blank comment? newline?++compound <- if_stmt++if_stmt     <- (("if" blank expression blank ":" blank comment?) > line) (elif_stmt / else_stmt)?+elif_stmt   <- (("elif" blank expression blank ":" blank comment?) > line) (elif_stmt / else_stmt)?+else_stmt   <- ("else" blank ":" blank comment?) > line++simple        <- import_stmt / assignment / expression+import_stmt   <- simple_import / from_import+simple_import <- "import" blank identifier+from_import   <- "from" blank identifier blank "import" blank (id_list / "*")++assignment <- id_list blank attr blank expression+attr       <- "=" / "+=" / "-=" / "*=" / "/="++expression <- or_expr (blank "or" blank or_expr)*+or_expr    <- and_expr (blank "and" blank and_expr)*+and_expr   <- "not" blank comparison / comparison+comparison <- sum (blank op_comp blank sum)*+sum        <- term (blank op_term blank term)* +term       <- factor (blank op_factor blank factor)*+factor     <- power (blank op_power blank power)*+power      <- ("-" / "+") signed / signed+signed     <- primary / "(" blank expression blank ")"++op_comp   <- ("==" / "!=" / "<=" / ">=" / "<" / ">")+op_term   <- ("+" / "-")+op_factor <- ("*" / "//" / "/" / "%")+op_power  <- "**"++primary       <- function_call / atom+function_call <- identifier blank "(" blank expr_list? blank ")"++atom      <- "True" / "False" / "None" / number / strings / identifier+expr_list <- expr1 (blank sep expr1)*+expr1     <- (single_id blank "=" blank)? expression+id_list   <- identifier (blank sep identifier)*++sep <- "," blank++^strings <- fstring / string+fstring  <- "f" string+string   <- ['] (!['] char)* ['] / ["] (!["] char)* ["]+-- TODO: Fazer uma forma mais fácil+char     <- [a-zA-Z0-9 :{}.,;=^~+-*/%$<>()_!?#\t\\áéíóúãõâêôàçÁÉÍÓÚÃÕÂÊÔÀÇ'"ẽĩũîûẼĨŨÎÛ] / "[" / "]"++^identifier <- single_id ("." single_id)*+single_id   <- [a-zA-Z] [a-zA-Z0-9_]*+^number     <- [0-9]+ ("." [0-9]+)?+^blank      <- space*+space       <- " " / "\t"+^comment    <- "#" char*+^newline    <- "\r\n" / "\r" / "\n"
+ input/peg/tarefa6.peg view
@@ -0,0 +1,59 @@+file <- line+++line      <- statement / comment newline / blank newline+statement <- compound / simple blank comment? newline?++compound <- if_stmt / while_stmt++if_stmt     <- (("if" blank expression blank ":" blank comment?) > line) (elif_stmt / else_stmt)?+elif_stmt   <- (("elif" blank expression blank ":" blank comment?) > line) (elif_stmt / else_stmt)?+else_stmt   <- ("else" blank ":" blank comment?) > line++while_stmt  <- (("while" blank expression blank ":" blank comment?) > line)++simple        <- import_stmt / assignment / expression+import_stmt   <- simple_import / from_import+simple_import <- "import" blank identifier+from_import   <- "from" blank identifier blank "import" blank (id_list / "*")++assignment <- id_list blank attr blank expression+attr       <- "=" / "+=" / "-=" / "*=" / "/="++expression <- or_expr (blank "or" blank or_expr)*+or_expr    <- and_expr (blank "and" blank and_expr)*+and_expr   <- "not" blank comparison / comparison+comparison <- sum (blank op_comp blank sum)*+sum        <- term (blank op_term blank term)* +term       <- factor (blank op_factor blank factor)*+factor     <- power (blank op_power blank power)*+power      <- ("-" / "+") signed / signed+signed     <- primary / "(" blank expression blank ")"++op_comp   <- ("==" / "!=" / "<=" / ">=" / "<" / ">")+op_term   <- ("+" / "-")+op_factor <- ("*" / "//" / "/" / "%")+op_power  <- "**"++primary       <- function_call / atom+function_call <- identifier blank "(" blank expr_list? blank ")"++atom      <- "True" / "False" / "None" / number / strings / identifier+expr_list <- expr1 (blank sep expr1)*+expr1     <- (single_id blank "=" blank)? expression+id_list   <- identifier (blank sep identifier)*++sep <- "," blank++^strings <- fstring / string+fstring  <- "f" string+string   <- ['] (!['] char)* ['] / ["] (!["] char)* ["]+-- TODO: Fazer uma forma mais fácil+char     <- [a-zA-Z0-9 :{}.,;=^~+-*/%$<>()_!?#\t\\áéíóúãõâêôàçÁÉÍÓÚÃÕÂÊÔÀÇ'"ẽĩũîûẼĨŨÎÛ] / "[" / "]"++^identifier <- single_id ("." single_id)*+single_id   <- [a-zA-Z] [a-zA-Z0-9_]*+^number     <- [0-9]+ ("." [0-9]+)?+^blank      <- space*+space       <- " " / "\t"+^comment    <- "#" char*+^newline    <- "\r\n" / "\r" / "\n"
+ input/peg/tarefa7.peg view
@@ -0,0 +1,60 @@+file <- line+++line      <- statement / comment newline / blank newline+statement <- compound / simple blank comment? newline?++compound <- if_stmt / while_stmt / for_stmt++if_stmt     <- (("if" blank expression blank ":" blank comment?) > line) (elif_stmt / else_stmt)?+elif_stmt   <- (("elif" blank expression blank ":" blank comment?) > line) (elif_stmt / else_stmt)?+else_stmt   <- ("else" blank ":" blank comment?) > line++while_stmt  <- ("while" blank expression blank ":" blank comment?) > line+for_stmt    <- ("for" blank identifier blank "in" blank expression blank ":" blank comment?) > line++simple        <- import_stmt / assignment / expression+import_stmt   <- simple_import / from_import+simple_import <- "import" blank identifier+from_import   <- "from" blank identifier blank "import" blank (id_list / "*")++assignment <- id_list blank attr blank expression+attr       <- "=" / "+=" / "-=" / "*=" / "/="++expression <- or_expr (blank "or" blank or_expr)*+or_expr    <- and_expr (blank "and" blank and_expr)*+and_expr   <- "not" blank comparison / comparison+comparison <- sum (blank op_comp blank sum)*+sum        <- term (blank op_term blank term)* +term       <- factor (blank op_factor blank factor)*+factor     <- power (blank op_power blank power)*+power      <- ("-" / "+") signed / signed+signed     <- primary / "(" blank expression blank ")"++op_comp   <- ("==" / "!=" / "<=" / ">=" / "<" / ">")+op_term   <- ("+" / "-")+op_factor <- ("*" / "//" / "/" / "%")+op_power  <- "**"++primary       <- function_call / atom+function_call <- identifier blank "(" blank expr_list? blank ")"++atom      <- "True" / "False" / "None" / number / strings / identifier+expr_list <- expr1 (blank sep expr1)*+expr1     <- (single_id blank "=" blank)? expression+id_list   <- identifier (blank sep identifier)*++sep <- "," blank++^strings <- fstring / string+fstring  <- "f" string+string   <- ['] (!['] char)* ['] / ["] (!["] char)* ["]+-- TODO: Fazer uma forma mais fácil+char     <- [a-zA-Z0-9 :{}.,;=^~+-*/%$<>()_!?#\t\\áéíóúãõâêôàçÁÉÍÓÚÃÕÂÊÔÀÇ'"ẽĩũîûẼĨŨÎÛ] / "[" / "]"++^identifier <- single_id ("." single_id)*+single_id   <- [a-zA-Z] [a-zA-Z0-9_]*+^number     <- [0-9]+ ("." [0-9]+)?+^blank      <- space*+space       <- " " / "\t"+^comment    <- "#" char*+^newline    <- "\r\n" / "\r" / "\n"
+ input/peg/wiki.peg view
@@ -0,0 +1,3 @@+S <- "x" S "x" / "x"++-- Source: https://en.wikipedia.org/wiki/Parsing_expression_grammar#The_midpoint_problem
+ peg-matching.cabal view
@@ -0,0 +1,118 @@+cabal-version: 2.2++name:           peg-matching+version:        0.1.0.0+synopsis:       Syntax tree matching and rewriting with Parsing Expression Grammars+description:+    @peg-matching@ is a library for parsing, analysing, matching and rewriting+    syntax trees using Parsing Expression Grammars (PEGs) together with a+    dedicated pattern language. It is aimed at research and experimentation+    with syntax-driven transformations over abstract syntax trees.+    .+    The library provides:+    .+    * PEG grammars and their syntax trees ("Syntax.Peg", "Syntax.ParsedTree");+    .+    * parsers for grammars, patterns and inputs ("Parser.Peg", "Parser.Pattern",+      "Parser.ParsedTree");+    .+    * semantic validation, including left-recursion and duplicate-rule detection+      ("Semantic.Peg", "Semantic.Pattern");+    .+    * pattern matching with subtree capture and tree rewriting ("Match.Capture",+      "Match.Rewrite");+    .+    * quasi-quoters for embedding grammars and patterns in Haskell source+      ("Quote.Peg", "Quote.Pattern");+    .+    * a high-level pipeline tying it all together ("Pipeline.MatchPipeline").+    .+    See the README for a worked example.+category:       Language, Parsing+homepage:       https://github.com/lives-group/peg-matching#readme+bug-reports:    https://github.com/lives-group/peg-matching/issues+author:         Guilherme Drummond+maintainer:     Rodrigo Ribeiro <rodrigo.ribeiro@ufop.edu.br>+copyright:      2025 Guilherme Drummond, Rodrigo Ribeiro+license:        BSD-3-Clause+license-file:   LICENSE+build-type:     Simple+tested-with:    GHC == 9.10.3+extra-doc-files:+    README.md+    CHANGELOG.md+extra-source-files:+    input/peg/*.peg+    input/pattern/*.pat+    input/file/*.txt+    input/file/*.py++source-repository head+  type: git+  location: https://github.com/lives-group/peg-matching++library+  exposed-modules:+      -- Syntax+      Syntax.Base+      Syntax.Peg+      Syntax.Pattern+      Syntax.ParsedTree+      -- Parser+      Parser.Base+      Parser.Peg+      Parser.Pattern+      Parser.ParsedTree+      -- Semantic+      Semantic.Peg+      Semantic.Pattern+      -- Match+      Match.Capture+      Match.Rewrite+      -- Pipeline+      Pipeline.MatchPipeline+      -- Quote+      Quote.Base+      Quote.Peg+      Quote.Pattern+  other-modules:+      Paths_peg_matching+  autogen-modules:+      Paths_peg_matching+  hs-source-dirs:+      src+  ghc-options: -Wall -Wcompat -Widentities -Wincomplete-record-updates -Wincomplete-uni-patterns -Wmissing-export-lists -Wmissing-home-modules -Wpartial-fields -Wredundant-constraints+  build-depends:+      base >=4.17 && <5+    , algebraic-graphs >=0.7 && <0.9+    , megaparsec >=9.0 && <10+    , parser-combinators >=1.3 && <1.4+    , pretty >=1.1 && <1.2+    , syb >=0.7 && <0.8+    , template-haskell >=2.19 && <2.24+  default-language: Haskell2010+  default-extensions:+      TupleSections+    , InstanceSigs+    , FlexibleInstances+    , DeriveDataTypeable+    , TemplateHaskell+    , QuasiQuotes++test-suite peg-matching-test+  type: exitcode-stdio-1.0+  main-is: Main.hs+  other-modules:+      Paths_peg_matching+  autogen-modules:+      Paths_peg_matching+  hs-source-dirs:+      test+  ghc-options: -Wall -Wcompat -Widentities -Wincomplete-record-updates -Wincomplete-uni-patterns -Wmissing-export-lists -Wmissing-home-modules -Wpartial-fields -Wredundant-constraints -threaded -rtsopts -with-rtsopts=-N+  build-depends:+      base >=4.17 && <5+    , megaparsec >=9.0 && <10+    , peg-matching+    , tasty >=1.4 && <1.6+    , tasty-hunit >=0.10 && <0.11+  default-language: Haskell2010
+ src/Match/Capture.hs view
@@ -0,0 +1,130 @@+{-# OPTIONS_GHC -Wno-unrecognised-pragmas #-}+{-# HLINT ignore "Use list comprehension" #-}++{-|+Module      : Match.Capture+Description : Functions for matching and capturing patterns in syntax trees.+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module provides functions to check pattern matching ('Pattern') in+AST ('ParsedTree') and capture corresponding subtrees.+-}+module Match.Capture+    ( match+    , match'+    , capture+    ) where++import Syntax.Pattern (Pattern(..))+import Syntax.ParsedTree (ParsedTree(..), ParsedTreeZipper, goDown, goLeft, goRight, goUp, pullFromRight, ofExpression)+import Data.Generics (mkQ, everything)+import Syntax.Peg (Grammar)+import Data.Maybe (isJust)++{-|+Checks if a pattern ('Pattern') matches an AST ('ParsedTree').++The 'match'' function traverses the tree and checks if the structure and values match the given pattern.+Matching is anchored at the focus of the zipper: it does not search the subtrees.+On success it returns the bindings produced by the variables ('PatVar') of the pattern.++The grammar is consulted only to resolve the expression of a 'PatVar', via 'ofExpression'.++=== Usage examples:++>>> let g = ([(NT "S", Sequence (ExprT (T "a")) (ExprT (T "b")))], NT "S")++>>> match' g (PatT (T "a")) (ParsedT (T "a"), [])+Just []++>>> match' g (PatT (T "a")) (ParsedT (T "b"), [])+Nothing++@since 1.0.0+-}+match' :: Grammar -> Pattern -> ParsedTreeZipper -> Maybe [(Pattern, ParsedTree)]+match' g p@(PatVar e _)         z@(t, _) =+    if ofExpression g e t+        then Just [(p, t)]+        else match' g p =<< e2+    where+        up = goUp z+        e1 = (\(expr, z') -> (,z') <$> pullFromRight expr) =<< up+        e2 = goLeft =<< e1+match' _ PatEpsilon           (ParsedEpsilon, _)         = +    Just []+match' _ (PatNot _)           (ParsedNot, _)             = +    Just []+match' g (PatNT nt p)         z@(ParsedNT nt' _, _)      =+    if nt == nt'+        then match' g p =<< goDown z+        else Nothing+match' _ (PatT t)             (ParsedT t', _)          = +    if t == t' then Just [] else Nothing+match' g (PatSeq p1 p2)       z@(ParsedSeq _ _, _)   = +    (++) <$> (match' g p1 =<< goLeft z) <*> (match' g p2 =<< goRight z)+match' g (PatSeq p1 p2)       z@(ParsedIndent _ _, _) = +    (++) <$> (match' g p1 =<< goLeft z) <*> (match' g p2 =<< goRight z) +match' g (PatChoice p1 _)     z@(ParsedChoiceLeft _, _)  = +    match' g p1 =<< goDown z+match' g (PatChoice _ p2)     z@(ParsedChoiceRight _, _) = +    match' g p2 =<< goDown z+match' g (PatStar p)          (ParsedStar ts, _)         = +    foldr (\ x xs -> (++) <$> match' g p (x, []) <*> xs) (Just []) ts+match' g (PatStarSeq ps)      (ParsedStar ts, _)         = +    if length ps == length ts+    then foldr (\ x y -> (++) <$> x <*> y) (Just []) $ zipWith (\ x y -> match' g x (y, [])) ps ts+    else Nothing+match' _ _                    _                          = +    Nothing++{-|+Checks if a pattern ('Pattern') matches any subtree of an AST ('ParsedTree').++Unlike 'match'', which is anchored at the root, this function applies 'match'' to+every subtree and succeeds if any of them matches.++=== Usage examples:++>>> let g = ([(NT "S", Sequence (ExprT (T "a")) (ExprT (T "b")))], NT "S")++>>> match g (PatT (T "a")) (ParsedT (T "a"))+True++The pattern needs to match only a subtree, not the whole tree:++>>> match g (PatT (T "a")) (ParsedSeq (ParsedT (T "a")) (ParsedT (T "b")))+True++@since 1.0.0+-}+match :: Grammar -> Pattern -> ParsedTree -> Bool+match g p = everything (||) (False `mkQ` (isJust . match' g p . (, [])))++{-|+Captures all subtrees of an AST ('ParsedTree') that match a variable ('PatVar').++The 'capture' function applies 'match'' to every subtree and concatenates the+bindings of the matches it finds.++=== Usage examples:++>>> let g = ([(NT "S", Sequence (ExprT (T "a")) (ExprT (T "b")))], NT "S")+>>> let tree = ParsedSeq (ParsedT (T "a")) (ParsedT (T "b"))++>>> capture g (PatSeq (PatT (T "a")) (PatVar (ExprT (T "b")) "B")) tree+[[(PatVar (ExprT (T "b")) "B",ParsedT (T "b"))]]++>>> capture g (PatVar (ExprT (T "a")) "A") tree+[[(PatVar (ExprT (T "a")) "A",ParsedT (T "a"))]]++@since 1.0.0+-}+capture :: Grammar -> Pattern -> ParsedTree -> [[(Pattern, ParsedTree)]]+capture g p = everything (++) ([] `mkQ` (\ x -> case match' g p (x, []) of +                                                Just y -> [y] +                                                Nothing -> []))
+ src/Match/Rewrite.hs view
@@ -0,0 +1,55 @@+{-|+Module      : Match.Rewrite+Description : Functions for rewriting syntax trees based on patterns.+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module provides functions to rewrite ASTs ('ParsedTree')+based on patterns ('Pattern'). It uses pattern matching to replace+subtrees with new structures.+-}+module Match.Rewrite+    ( replace+    , rewrite+    ) where++import Syntax.Pattern (Pattern(..))+import Syntax.ParsedTree (ParsedTree(..))+import Match.Capture (capture)+import Data.Generics (mkT, everywhere)+import Syntax.Peg (Grammar)++{-|+Substitui uma subárvore em uma AST ('ParsedTree') com base em uma variável ('PatVar').++The 'replace' function checks if a subtree matches a variable and, if so,+replaces the corresponding subtree with the provided subtree.++@since 1.0.0+-}+replace :: Pattern -> ParsedTree -> (Pattern, ParsedTree) -> ParsedTree+replace (PatVar _ name)  t (PatVar _ name', t') = if name == name' then t' else t+replace (PatNT nt p)     (ParsedNT nt' t) subst = if nt == nt'+                                                    then ParsedNT nt' (replace p t subst)+                                                    else ParsedNT nt' t+replace (PatSeq p1 p2)   (ParsedSeq t1 t2)     subst = ParsedSeq (replace p1 t1 subst) (replace p2 t2 subst)+-- TODO: The following line was added to try and fix a problem of duplicating the +-- contents of a variable during rewriting. As such, it may not be fully correct+replace (PatSeq p1 p2@(PatVar _ _)) (ParsedIndent t1 t2)  subst = ParsedIndent (replace p1 t1 subst) [replace p2 (ParsedStar t2) subst]+replace (PatSeq p1 p2)   (ParsedIndent t1 t2)  subst = ParsedIndent (replace p1 t1 subst) $ map (\ x -> replace p2 x subst) t2+replace (PatChoice p1 _) (ParsedChoiceLeft t)  subst = ParsedChoiceLeft $ replace p1 t subst+replace (PatChoice _ p2) (ParsedChoiceRight t) subst = ParsedChoiceRight $ replace p2 t subst+replace (PatStar p)      (ParsedStar ts)       subst = ParsedStar $ map (\ x -> replace p x subst) ts+replace _                t                     _     = t++{-|+Rewrites an AST ('ParsedTree') by replacing subtrees that match+a variable ('PatVar') with another pattern.++@since 1.0.0+-}+rewrite :: Grammar -> Pattern -> Pattern -> ParsedTree -> ParsedTree+rewrite g p p' = everywhere $ mkT (\x -> foldr ((flip . replace) p') x (concat (capture g p x)))
+ src/Parser/Base.hs view
@@ -0,0 +1,218 @@+{-|+Module      : Parser.Base+Description : Basic definitions for grammar parsing.+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module provides basic definitions for grammar parsing, including parsers+for non-terminals, terminals, and symbols, as well as utilities for handling+whitespace, comments, and delimiters.+-}+module Parser.Base+    ( Parser+    , ParseError+    , nonTerminal+    , terminal+    , pSymbol+    , parseWith+    , blank+    , sc+    , hsc+    , symbol+    , symbolNL+    , parens+    , brackets+    , curly+    , identifier+    , litTerminal+    ) where++import Syntax.Base (NonTerminal(..), Terminal(..), Symbol)+import Data.Void (Void)+import Text.Megaparsec+    ((<|>), empty, Parsec, between, many, (<?>), parse, someTill, ParseErrorBundle)+import Text.Megaparsec.Char (space1, hspace1, letterChar, alphaNumChar, char, eol)+import qualified Text.Megaparsec.Char.Lexer as Lexer+import Control.Monad (void)++{-|+Type for parsers based on 'Text.Megaparsec'.++@since 1.0.0+-}+type Parser = Parsec Void String++{-|+Type for parsing errors.++@since 1.0.0+-}+type ParseError = ParseErrorBundle String Void++-------------------------------------------------------------------------------+--- Helpers++{-|+Parser that consumes whitespace.++@since 1.0.0+-}+blank :: Parser ()+blank = Lexer.space space1 empty empty++{-|+Parser that consumes whitespace and line comments.++Line comments start with `--`.++@since 1.0.0+-}+sc :: Parser ()+sc = Lexer.space space1 lineComment empty++{-|+Parser that consumes horizontal spaces and line comments.++Line comments start with `--`.++@since 1.0.0+-}+hsc :: Parser ()+hsc = Lexer.space hspace1 lineComment empty++{-|+Parser for line comments.++Line comments start with `--` and end at the end of the line.++@since 1.0.0+-}+lineComment :: Parser ()+lineComment = void (Lexer.skipLineComment "--") <* eol++{-|+Parser that applies a parser and consumes horizontal spaces after it.++@since 1.0.0+-}+lexeme :: Parser a -> Parser a+lexeme = Lexer.lexeme hsc++{-|+Parser for symbols delimited by horizontal spaces.++@since 1.0.0+-}+symbol :: String -> Parser String+symbol = Lexer.symbol hsc++{-|+Parser for symbols delimited by spaces or newlines.++@since 1.0.0+-}+symbolNL :: String -> Parser String+symbolNL = Lexer.symbol sc++{-|+Parser for expressions delimited by parentheses.++@since 1.0.0+-}+parens :: Parser a -> Parser a+parens = between (symbol "(") (symbol ")")++{-|+Parser for expressions delimited by brackets.++@since 1.0.0+-}+brackets :: Parser a -> Parser a+brackets = between (symbol "[") (symbol "]")++{-|+Parser for expressions delimited by curly braces.++@since 1.0.0+-}+curly :: Parser a -> Parser a+curly = between (symbol "{") (symbol "}")++{-|+Parser for identifiers.++An identifier starts with a letter and can contain letters, numbers, or `_`.++@since 1.0.0+-}+identifier :: Parser String+identifier = lexeme ((:) <$> letterChar <*> many (alphaNumChar <|> char '_') <?> "identifier")++{-|+Parser for literals (terminals).++A literal is a non-empty string delimited by double quotes (`"`) or single quotes (`'`).++@since 1.0.0+-}+litTerminal :: Parser String+litTerminal = lexeme (char '"' >> someTill Lexer.charLiteral (char '"') <?> "string")+            -- <|> lexeme (char '\'' >> someTill Lexer.charLiteral (char '\'') <?> "string")++-------------------------------------------------------------------------------+--- Base parser++{-|+Parser for non-terminals.++A non-terminal is represented by an identifier.++@since 1.0.0+-}+nonTerminal :: Parser NonTerminal+nonTerminal =+    NT <$> identifier <?> "nonTerminal"++{-|+Parser for terminals.++A terminal is represented by a literal.++@since 1.0.0+-}+terminal :: Parser Terminal+terminal = T <$> litTerminal <?> "terminal"++{-|+Parser for symbols.++A symbol can be a 'NonTerminal' or a 'Terminal'.++@since 1.0.0+-}+pSymbol :: Parser Symbol+pSymbol = Left <$> nonTerminal <|> Right <$> terminal++{-|+Function to execute a parser on an input string.++Returns an 'Either' containing the parser result or a parsing error.++=== Usage examples:++>>> parseWith nonTerminal "S"+Right (NT "S")++>>> parseWith terminal "\"a\""+Right (T "a")++>>> parseWith terminal "invalid"+Left ...++@since 1.0.0+-}+parseWith :: Parser a -> String -> Either ParseError a+parseWith p = parse p ""
+ src/Parser/ParsedTree.hs view
@@ -0,0 +1,80 @@+{-|+Module      : Parser.ParsedTree+Description : Generation of parsers for syntax trees (Parsed Trees).+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module provides functions to generate parsers based on PEG ('Grammar'),+producing syntax trees ('ParsedTree') as a result.+-}+module Parser.ParsedTree (mkParser) where++import Syntax.Base (Terminal(..), NonTerminal(..))+import Syntax.Peg (Grammar, Expression(..), expression)+import Syntax.ParsedTree (ParsedTree(..), flatten)+import Parser.Base (Parser, blank)+import Text.Megaparsec (notFollowedBy, many, eof, optional, try, (<?>))+import Text.Megaparsec.Char (string)+import Data.Maybe (fromJust)+import Control.Applicative ((<|>))+import qualified Text.Megaparsec.Char.Lexer as Lexer+++{-|+Generates a parser for a PEG.++The 'mkParser' function receives a PEG ('Grammar') and returns a parser that,+when applied to an input string, produces a corresponding AST ('ParsedTree').++The parser is based on the initial non-terminal of the grammar.++=== Usage examples:++>>> let grammar = ([(NT "S", Sequence (ExprT (T "a")) (ExprT (T "b")))], NT "S")+>>> parseWith (mkParser grammar) "ab"+Right (ParsedNT (NT "S") (ParsedSeq (ParsedT (T "a")) (ParsedT (T "b"))))++@since 1.0.0+-}+mkParser :: Grammar -> Parser ParsedTree+mkParser g@(_, nt) = ParsedNT nt <$> mkParser' g (fromJust $ Syntax.Peg.expression g nt)+                        <* optional blank+                        <* eof++{-|+Parser for a terminal.++Receives a terminal ('Terminal') and returns a parser that consumes the string corresponding+to the input terminal.++@since 1.0.0+-}+terminal :: Terminal -> Parser Terminal+terminal (T t) = T <$> string t++{-|+Generates a parser for a PEG expression.++The 'mkParser'' function is used internally by 'mkParser' to process different types+of PEG expressions ('Expression') and produce the corresponding syntax tree.++@since 1.0.0+-}+mkParser' :: Grammar -> Expression -> Parser ParsedTree+mkParser' _ Empty = ParsedEpsilon <$ string ""+mkParser' _ (ExprT t) = ParsedT <$> terminal t+mkParser' g (ExprNT nt@(NT n)) = ParsedNT nt <$> mkParser' g (fromJust $ Syntax.Peg.expression g nt) <?> n+mkParser' g (Choice e1 e2) = try (ParsedChoiceLeft <$> mkParser' g e1)+                             <|> ParsedChoiceRight <$> mkParser' g e2+mkParser' g (Sequence e1 e2) = ParsedSeq <$> mkParser' g e1 <*> mkParser' g e2+mkParser' g (Star e) = ParsedStar <$> many (try $ mkParser' g e)+mkParser' g (Not e) = ParsedNot <$ notFollowedBy (mkParser' g e)+mkParser' g (Flatten e) = ParsedT . T . flatten <$> mkParser' g e+mkParser' g (Indent e b) = Lexer.indentBlock blank p+    where+        p = do+            expr <- mkParser' g e+            return $ Lexer.IndentSome Nothing (return . ParsedIndent expr) (try $ mkParser' g b)
+ src/Parser/Pattern.hs view
@@ -0,0 +1,232 @@+{-|+Module      : Parser.Pattern+Description : Parser for syntactic patterns in grammars.+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module provides parsers for syntactic patterns ('SyntaxPattern') and named patterns+('NamedSynPat') in grammars. It also includes a function to execute the parser on an+input string.+-}+module Parser.Pattern+    ( patterns+    , parsePatterns+    ) where++import Syntax.Pattern (SyntaxPattern(..), NamedSynPat)+import Parser.Base+    (Parser, sc, hsc, symbol, parens, identifier, nonTerminal, terminal, parseWith, ParseError)+import qualified Parser.Peg as Peg+import Text.Megaparsec (eof, (<?>), choice, some, sepBy1, MonadParsec (try))+import Text.Megaparsec.Char (char)+import Control.Monad.Combinators.Expr (Operator(Postfix, Prefix), makeExprParser)++-------------------------------------------------------------------------------+--- SyntaxPattern Parser++{-|+Parser for a list of patterns.++Each pattern is preceded by the keyword @pattern@ and associated with a name.++@since 1.0.0+-}+patterns :: Parser [NamedSynPat]+patterns = id <$ hsc <*> some pat <* eof++{-|+Parser for a pattern.++A pattern is defined in the format:++> pattern <name> : <pattern>++@since 1.0.0+-}+pat :: Parser NamedSynPat+pat =+    f <$> symbol "pattern"+        <*> identifier+        <*> symbol ":"+        <*> patNT+        <* sc+        <?> "pattern"+    where+        f _ name _ p = (name, p)++{-|+Parser for a primary expression.++A primary expression can be:+- An expression enclosed in parentheses.+- A non-terminal associated with a pattern.+- A terminal.+- A pattern variable.+- A reference to a named pattern.+- The empty symbol (@ε@).++@since 1.0.0+-}+primary :: Parser SyntaxPattern+primary = choice+            [ try $ parens patNT+            , parens expression+            , patT+            , patVar+            , reference+            , epsilon+            ]++{-|+Parser for an expression composed of ordered choices.++Choices are separated by the `/` operator.++@since 1.0.0+-}+expression :: Parser SyntaxPattern+expression = foldr1 SynChoice <$> Parser.Pattern.sequence `sepBy1` symbol "/"++{-|+Parser for a sequence of expressions.++Expressions are combined with the 'SynSeq' operator.++@since 1.0.0+-}+sequence :: Parser SyntaxPattern+sequence = foldr1 SynSeq <$> some prefix++{-|+Parser for a non-terminal associated with a pattern.++A non-terminal is followed by the @:=@ operator and an expression.++@since 1.0.0+-}+patNT :: Parser SyntaxPattern+patNT = f <$> nonTerminal <*> symbol ":=" <*> expression+    where f nt _ = SynNT nt++{-|+Parser for a terminal.++A terminal is represented by a literal.++@since 1.0.0+-}+patT :: Parser SyntaxPattern+patT = SynT <$> terminal++{-|+Parser for a pattern variable.++A pattern variable is defined in the format:++> #<name>:<expression>++@since 1.0.0+-}+patVar :: Parser SyntaxPattern+patVar = f <$> char '#' <*> identifier <*> char ':' <*> Peg.primary <?> "pattern variable"+    where+        f _ n _ s = SynVar s n++{-|+Parser for a reference to a named pattern.++A reference is preceded by an at sign (@\@@) and followed by the pattern name.++@since 1.0.0+-}+reference :: Parser SyntaxPattern+reference = f <$> char '@' <*> identifier <?> "pattern name"+    where+        f _ = SynRef++{-|+Parser for the empty symbol (@ε@).++@since 1.0.0+-}+epsilon :: Parser SyntaxPattern+epsilon = SynEpsilon <$ symbol "ε"++{-|+Parser for expressions with prefix and suffix operators.++The available operators are:+- @*@: Repetition zero or more times ('Syntax.Pattern.SynStar', 'Syntax.Pattern.PatStar').+- @+@: Repetition one or more times (@SynSeq e (SynStar e)@, @PatSeq e (PatStar e)@).+- @?@: Optional (@SynChoice e SynEpsilon@, @PatChoice e PatEpsilon@).+- @!@: Negation ('Syntax.Pattern.SynNot', 'Syntax.Pattern.PatNot').+- @&@: And (@SynNot . SynNot@, @PatNot . PatNot@).++@since 1.0.0+-}+prefix :: Parser SyntaxPattern+prefix = makeExprParser primary patOperatorTable++{-|+Operator table for syntactic patterns.++Defines the available prefix and suffix operators.++@since 1.0.0+-}+patOperatorTable :: [[Operator Parser SyntaxPattern]]+patOperatorTable =+    [+        [+            patSuffix "*" SynStar,+            patSuffix "+" plus,+            patSuffix "?" opt+        ],+        [+            patPrefix "!" SynNot,+            patPrefix "&" (SynNot . SynNot)+        ]+    ]+    where+        plus e = SynSeq e (SynStar e)+        opt e = SynChoice e SynEpsilon++{-|+Defines a suffix operator for patterns.++@since 1.0.0+-}+patSuffix :: String -> (SyntaxPattern -> SyntaxPattern) -> Operator Parser SyntaxPattern+patSuffix name f = Postfix (f <$ symbol name)++{-|+Defines a prefix operator for patterns.++@since 1.0.0+-}+patPrefix :: String -> (SyntaxPattern -> SyntaxPattern) -> Operator Parser SyntaxPattern+patPrefix name f = Prefix (f <$ symbol name)++{-|+Executes the pattern parser on an input string.++Returns an 'Either' containing the parser result or a parsing error.++=== Usage examples:++>>> parsePatterns "pattern A : S := \"a\" / \"b\""+Right [("A",SynNT (NT "S") (SynChoice (SynT (T "a")) (SynT (T "b"))))]++>>> parsePatterns "pattern B : S := #x:T"+Right [("B",SynNT (NT "S") (SynVar (ExprNT (NT "T")) "x"))]++>>> parsePatterns "invalid"+Left ...++@since 1.0.0+-}+parsePatterns :: String -> Either ParseError [NamedSynPat]+parsePatterns = parseWith patterns
+ src/Parser/Peg.hs view
@@ -0,0 +1,229 @@+{-|+Module      : Parser.Peg+Description : Parser for PEGs (Parsing Expression Grammars).+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module provides parsers for PEGs (Parsing Expression Grammars),+including definitions, expressions, and PEG operators. It also provides a function+to execute the parser on an input string.+-}+module Parser.Peg+    ( grammar+    , parseGrammar+    , expression+    , primary+    ) where++import Syntax.Base (NonTerminal(NT), Terminal(..))+import Syntax.Peg (Grammar, Definition, Expression(..))+import Parser.Base+    (Parser, sc, symbol, parens, nonTerminal, terminal, hsc, parseWith, ParseError)+import Text.Megaparsec+    (eof, choice, some, sepBy1, someTill, try, optional)+import Text.Megaparsec.Char (alphaNumChar, char, string)+import qualified Text.Megaparsec.Char.Lexer as Lexer+import Control.Monad.Combinators.Expr (Operator(Postfix, Prefix, InfixL), makeExprParser)++-------------------------------------------------------------------------------+--- PEG parser++{-|+Parser for a complete PEG.++A grammar consists of a list of definitions and an initial non-terminal.+The first definition is considered the initial expression of the PEG.++@since 1.0.0+-}+grammar :: Parser Grammar+grammar = f <$> sc <*> some definition <* eof+    where+        f _ d = (d, fst $ head d)++{-|+Parser for a definition in a PEG.++A definition associates a non-terminal with an expression. If the definition is preceded+by a `^`, the expression will be flattened ('Flatten').++@since 1.0.0+-}+definition :: Parser Definition+definition = f <$> optional (string "^") <*> nonTerminal <*> symbol "<-" <*> expression <* sc+    where+        f flat nt _ e = case flat of+                        Nothing -> (nt, e)+                        Just _  -> (nt, Flatten e)++{-|+Parser for an expression in a PEG.++An expression can consist of choices ('Choice') separated by `/`.++@since 1.0.0+-}+expression :: Parser Expression+expression = foldr1 Choice <$> Parser.Peg.sequence `sepBy1` symbol "/"++{-|+Parser for a sequence of expressions.++A sequence consists of multiple expressions combined with the 'Sequence' operator.++@since 1.0.0+-}+sequence :: Parser Expression+sequence = foldr1 Sequence <$> some prefix++{-|+Parser for a primary expression.++A primary expression can be:+- An empty symbol (@ε@).+- A non-terminal.+- A terminal.+- An expression in parentheses.+- A character class.+- A dot (`.`), which represents any terminal in the PEG.++@since 1.0.0+-}+primary :: Parser Expression+primary = choice+            [ epsilon+            , ExprNT <$> nonTerminal+            , parens expression+            , ExprT <$> terminal+            , pClass+            , dot+            ]++{-|+Parser for a character class.++A character class is enclosed in brackets (`[ ]`) and can contain ranges+(e.g., `a-z`) or individual characters.++@since 1.0.0+-}+pClass :: Parser Expression+pClass = foldr1 Choice <$> (char '[' >> someTill range (char ']')) <* hsc++{-|+Parser for a range or individual character in a character class.++A range is defined as `a-z`, while an individual character is a single+literal character.++@since 1.0.0+-}+range :: Parser Expression+range = choice [+            try $ f <$> alphaNumChar <*> char '-' <*> alphaNumChar,+            expr <$> Lexer.charLiteral+        ]+        where+            f a _ b = foldr1 Choice $ map expr [a..b]+            expr = ExprT . T . (:[])++{-|+Parser for the dot (`.`), which represents any character.++@since 1.0.0+-}+dot :: Parser Expression+dot = ExprNT (NT ".") <$ symbol "."++{-|+Parser for the empty symbol (@ε@).++@since 1.0.0+-}+epsilon :: Parser Expression+epsilon = Empty <$ symbol "ε"++{-|+Parser for expressions with prefix and suffix operators.++The available operators are:+- @*@: Zero or more repetitions ('Star').+- @+@: One or more repetitions (@Sequence e (Star e)@).+- @?@: Optional (@Choice e Empty@).+- @!@: Negation ('Not').+- @&@: And (@Not . Not@).++@since 1.0.0+-}+prefix :: Parser Expression+prefix = makeExprParser primary pegOperatorTable++{-|+PEG operator table.++Defines the available prefix and suffix operators.++@since 1.0.0+-}+pegOperatorTable :: [[Operator Parser Expression]]+pegOperatorTable =+    [ [ pegSuffix "*" Star+        , pegSuffix "+" plus+        , pegSuffix "?" opt+        ]+    , [ pegPrefix "!" Not+        , pegPrefix "&" (Not . Not)+        ]+    , [ pegInfix ">" Indent ]+    ]+    where+        plus e = Sequence e (Star e)+        opt e = Choice e Empty++{-|+Defines a suffix operator for PEG expressions.++@since 1.0.0+-}+pegSuffix :: String -> (Expression -> Expression) -> Operator Parser Expression+pegSuffix name f = Postfix (f <$ symbol name)++{-|+Defines a prefix operator for PEG expressions.++@since 1.0.0+-}+pegPrefix :: String -> (Expression -> Expression) -> Operator Parser Expression+pegPrefix name f = Prefix (f <$ symbol name)++{-|+Defines a infix operator for PEG expressions.++@since 1.0.0+-}+pegInfix :: String -> (Expression -> Expression -> Expression) -> Operator Parser Expression+pegInfix name f = InfixL (f <$ symbol name)++{-|+Executes the PEG parser on an input string.++Returns an 'Either' containing the parser result or a parsing error.++=== Usage examples:++>>> parseGrammar "S <- \"a\" / \"b\""+Right ([(NT "S",Choice (ExprT (T "a")) (ExprT (T "b")))],NT "S")++>>> parseGrammar "S <- \"a\" \"b\""+Right ([(NT "S",Sequence (ExprT (T "a")) (ExprT (T "b")))],NT "S")++>>> parseGrammar "invalid"+Left ...++@since 1.0.0+-}+parseGrammar :: String -> Either ParseError Grammar+parseGrammar = parseWith grammar
+ src/Pipeline/MatchPipeline.hs view
@@ -0,0 +1,474 @@+{-|+Module      : Pipeline.MatchPipeline+Description : Functions for processing grammars, patterns, and ASTs.+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module provides functions for processing PEGs, patterns, and ASTs.+It includes grammar and pattern validation, pattern matching, subtree capturing, and AST rewriting.+It also provides auxiliary functions for file input and output.+-}+module Pipeline.MatchPipeline+    ( PrettyError+      -- * Pipelines over strings+    , parseValidGrammar+    , parseValidPatterns+    , parseCorrectPatterns+    , parseFile+    , parseMatch+    , parseMatch1+    , parseCapture+    , parseCapture1+    , parseRewrite+    , parseCallGraph+      -- * Pipelines over files+      --+      -- | These read their inputs from disk and print the result.+    , parseGrammarIO+    , parseValidGrammarIO+    , parsePatternsIO+    , parsePatApply+    , parseValidPatternsIO+    , parseCorrectPatternsIO+    , parseFileIO+    , parseMatchIO+    , parseMatch1IO+    , parseCaptureIO+    , parseCapture1IO+    , parseRewriteIO+    , parseCallGraphIO+    ) where++import Syntax.Base (Pretty(pPrint))+import Syntax.Peg (Grammar)+import Syntax.Pattern (NamedSynPat, NamedPattern, Pattern (PatVar))+import Syntax.ParsedTree (ParsedTree, flatten)+import Parser.Base (parseWith)+import Parser.Peg (parseGrammar)+import Parser.Pattern (parsePatterns)+import Parser.ParsedTree (mkParser)+import Semantic.Peg (processPeg)+import Semantic.Pattern (validPat, correctPat, processPats)+import Match.Capture (match, capture)+import Match.Rewrite (rewrite)+import Text.Megaparsec (errorBundlePretty)+import Data.Bifunctor (Bifunctor(first, bimap, second))+import Data.Foldable (find)+import Data.Maybe (mapMaybe)+import Data.List (nub)++{-|+An error already rendered as human-readable text.++The functions in this module report failures this way so that parse errors and+semantic errors, which have unrelated representations, can share a single return+type.++@since 1.0.0+-}+type PrettyError = String++{-|+Validates a PEG from an input string.++Returns the processed grammar or a formatted error.++@since 1.0.0+-}+parseValidGrammar :: String -> Either PrettyError Grammar+parseValidGrammar contents =+    case parseGrammar contents of+        Left e -> Left $ errorBundlePretty e+        Right g -> first (show . pPrint) (processPeg g)++{-|+Validates syntactic patterns against a PEG.++Receives the grammar and pattern contents as strings and returns the processed patterns+or a formatted error.++@since 1.0.0+-}+parseValidPatterns :: String -> String -> Either PrettyError [NamedPattern]+parseValidPatterns contentsG contentsP =+    case (g, ps) of+        (Left e, _) -> Left e+        (_, Left e) -> Left e+        (Right g', Right ps') -> first (show . pPrint) (processPats g' ps')+    where+        g = parseValidGrammar contentsG+        ps = first errorBundlePretty (parsePatterns contentsP)++{-|+Corrects syntactic patterns against a PEG.++Receives the grammar and pattern contents as strings and returns the corrected patterns+or a formatted error.++@since 1.0.0+-}+parseCorrectPatterns :: String -> String -> Either PrettyError [NamedPattern]+parseCorrectPatterns contentsG contentsP =+    case (g, ps) of+        (Left e, _) -> Left e+        (_, Left e) -> Left e+        (Right g', Right ps') -> bimap (show . pPrint) (correct g') (processPats g' ps')+    where+        g = parseValidGrammar contentsG+        ps = first errorBundlePretty (parsePatterns contentsP)+        mkProof g' (n, p) ps' = maybe ps' ((:ps') . (n,)) (correctPat p =<< validPat g' p)+        correct g' = foldr (mkProof g') []++{-|+Parses an input file based on a PEG.++Receives the grammar and file contents as strings and returns the AST+or a formatted error.++@since 1.0.0+-}+parseFile :: String -> String -> Either PrettyError ParsedTree+parseFile contentsG contentsF =+    case parseValidGrammar contentsG of+        Left e -> Left e+        Right g -> first errorBundlePretty (pFile g)+    where+        pFile g = parseWith (mkParser g) contentsF++{-|+Checks pattern matching in an AST.++Receives the grammar, pattern, and file contents as strings and returns a list+indicating whether each pattern matches the tree.++@since 1.0.0+-}+parseMatch :: String -> String -> String -> Either PrettyError [(String, Bool)]+parseMatch contentsG contentsP contentsF =+    case (g, ps, f) of+        (Left e, _, _) -> Left e+        (_, Left e, _) -> Left e+        (_, _, Left e) -> Left e+        (Right g', Right ps', Right f') -> Right $ map (match' g' f') ps'+    where+        g = parseValidGrammar contentsG+        ps = parseCorrectPatterns contentsG contentsP+        f = parseFile contentsG contentsF+        match' g' f' (n, p) = (n, Match.Capture.match g' p f')++{-|+Checks whether a specific pattern matches an AST.++Receives the grammar, pattern, file contents, and the pattern name as strings.+Returns `True` if the pattern matches the tree, or `False` otherwise.++@since 1.0.0+-}+parseMatch1 :: String -> String -> String -> String -> Either PrettyError Bool+parseMatch1 contentsG contentsP contentsF name =+    case (g, ps, f) of+        (Left e, _, _) -> Left e+        (_, Left e, _) -> Left e+        (_, _, Left e) -> Left e+        (Right g', Right ps', Right f') ->+            case find ((name ==) . fst) ps' of+                Nothing -> Left "Pattern not found in the file"+                Just (_, p) -> Right $ Match.Capture.match g' p f'+    where+        g = parseValidGrammar contentsG+        ps = parseCorrectPatterns contentsG contentsP+        f = parseFile contentsG contentsF++{-|+Captures subtrees matching patterns in an AST.++Receives the grammar, pattern, and file contents as strings and returns a list+of captures for each pattern.++@since 1.0.0+-}+parseCapture :: String -> String -> String -> Either PrettyError [(String, [[(Pattern, ParsedTree)]])]+parseCapture contentsG contentsP contentsF =+    case (g, ps, f) of+        (Left e, _, _) -> Left e+        (_, Left e, _) -> Left e+        (_, _, Left e) -> Left e+        (Right g', Right ps', Right f') -> Right $ map (capture' g' f') ps'+    where+        g = parseValidGrammar contentsG+        ps = parseCorrectPatterns contentsG contentsP+        f = parseFile contentsG contentsF+        capture' g' f' (n, p) = (n, capture g' p f')++{-|+Captures subtrees matching a specific pattern in an AST.++Receives the grammar, pattern, file contents, and the pattern name as strings.+Returns the captures for the specified pattern.++@since 1.0.0+-}+parseCapture1 :: String -> String -> String -> String -> Either PrettyError [[(Pattern, ParsedTree)]]+parseCapture1 contentsG contentsP contentsF name =+    case (g, ps, f) of+        (Left e, _, _) -> Left e+        (_, Left e, _) -> Left e+        (_, _, Left e) -> Left e+        (Right g', Right ps', Right f') ->+            case find ((name ==) . fst) ps' of+                Nothing -> Left "Pattern not found in the file"+                Just (_, p) -> Right $ capture g' p f'+    where+        g = parseValidGrammar contentsG+        ps = parseCorrectPatterns contentsG contentsP+        f = parseFile contentsG contentsF++{-|+Rewrites an AST based on two patterns.++Receives the grammar, pattern, file contents, and the names of the two patterns as strings.+Returns the rewritten tree.++@since 1.0.0+-}+parseRewrite :: String -> String -> String -> String -> String -> Either PrettyError ParsedTree+parseRewrite contentsG contentsP contentsF name1 name2 =+    case (g, ps, f) of+        (Left e, _, _) -> Left e+        (_, Left e, _) -> Left e+        (_, _, Left e) -> Left e+        (Right g', Right ps', Right f') ->+            case (findPat name1 ps', findPat name2 ps') of+                (Nothing, _) -> Left $ "Pattern " ++ name1 ++ " not found in the file"+                (_, Nothing) -> Left $ "Pattern " ++ name2 ++ " not found in the file"+                (Just p1, Just p2) -> Right $ rewrite g' p1 p2 f'+    where+        findPat p = fmap snd . find ((p ==) . fst)+        g = parseValidGrammar contentsG+        ps = parseCorrectPatterns contentsG contentsP+        f = parseFile contentsG contentsF++{-|+Builds a call graph from matches of two named patterns in an AST.++The first pattern is treated as a definition pattern and the second pattern as+a call pattern. The result is a list of definition/call pairs.+@since 1.0.0+-}+parseCallGraph :: String -> String -> String -> String -> String -> Either PrettyError [(ParsedTree, ParsedTree)]+parseCallGraph contentsG contentsP contentsF defPat callPat =+    case (g, ps, f) of+        (Left e, _, _) -> Left e+        (_, Left e, _) -> Left e+        (_, _, Left e) -> Left e+        (Right g', Right ps', Right f') ->+            case (findPat defPat ps', findPat callPat ps') of+                (Nothing, _) -> Left $ "Pattern " ++ defPat ++ " not found in the file"+                (_, Nothing) -> Left $ "Pattern " ++ callPat ++ " not found in the file"+                (Just def, Just call) -> do+                    let definitions = capture g' def f'+                    let pairs = mapMaybe getDef definitions+                    let calls = map (second (mapMaybe getCall . capture g' call)) pairs+                    return $ concatMap (\ (x, y) -> map (x,) y) calls+    where+        findPat p = (snd <$>) . find ((p ==) . fst)+        g = parseValidGrammar contentsG+        ps = parseCorrectPatterns contentsG contentsP+        f = parseFile contentsG contentsF+        findPatTree p = (snd <$>) . find (isVar p)+        isVar p (PatVar _ n, _) = n == p+        isVar _ _ = False+        getCall = findPatTree "name"+        getDef xs = (,) <$> findPatTree "name" xs <*> findPatTree "block" xs+++-------------------------------------------------------------------------------+--- IO++{-|+Parses and prints a PEG from a file.++@since 1.0.0+-}+parseGrammarIO :: FilePath -> IO ()+parseGrammarIO f = do+    contents <- readFile f+    case parseGrammar contents of+        Left e -> putStrLn (errorBundlePretty e)+        Right g -> print $ pPrint g++{-|+Validates and prints a PEG from a file.++@since 1.0.0+-}+parseValidGrammarIO :: FilePath -> IO ()+parseValidGrammarIO f = do+    contents <- readFile f+    let g = parseValidGrammar contents+    case g of+        Left e -> putStrLn e+        Right g' -> print $ pPrint g'+        -- Right g' -> print g'++{-|+Parses and prints syntactic patterns from a file.++@since 1.0.0+-}+parsePatternsIO :: FilePath -> IO ()+parsePatternsIO f = do+    contents <- readFile f+    case parsePatterns contents of+        Left e -> putStrLn (errorBundlePretty e)+        Right g -> print $ pPrint g+        -- Right g -> print g++{-|+Applies a function to syntactic patterns read from a file and prints the result.++@since 1.0.0+-}+parsePatApply :: Show a => ([NamedSynPat] -> a) -> FilePath -> IO ()+parsePatApply g f = do+    contents <- readFile f+    case parsePatterns contents of+        Left bundle -> print (errorBundlePretty bundle)+        Right xs -> print (g xs)++{-|+Validates and prints syntactic patterns against a PEG from files.++@since 1.0.0+-}+parseValidPatternsIO :: FilePath -> FilePath -> IO ()+parseValidPatternsIO pathGrammar pathPattern = do+    contentsG <- readFile pathGrammar+    contentsP <- readFile pathPattern+    case parseValidPatterns contentsG contentsP of+        Left e -> putStrLn e+        Right ps' -> print $ pPrint ps'++{-|+Corrects and prints syntactic patterns against a PEG from files.++@since 1.0.0+-}+parseCorrectPatternsIO :: FilePath -> FilePath -> IO ()+parseCorrectPatternsIO pathGrammar pathPattern = do+    contentsG <- readFile pathGrammar+    contentsP <- readFile pathPattern+    case parseCorrectPatterns contentsG contentsP of+        Left e -> putStrLn e+        Right ps' -> print $ pPrint ps'++{-|+Parses and prints an AST from files.++@since 1.0.0+-}+parseFileIO :: FilePath -> FilePath -> Bool -> IO ()+parseFileIO grammarFile inputFile flat = do+    contentsG <- readFile grammarFile+    contentsF <- readFile inputFile+    case parseFile contentsG contentsF of+        Left e -> putStrLn e+        Right t -> putStrLn $ if flat then flatten t else show (pPrint t)++{-|+Checks pattern matching in an AST and prints the results.++@since 1.0.0+-}+parseMatchIO :: FilePath -> FilePath -> FilePath -> IO ()+parseMatchIO grammarFile patternFile inputFile = do+    contentsG <- readFile grammarFile+    contentsP <- readFile patternFile+    contentsF <- readFile inputFile+    case parseMatch contentsG contentsP contentsF of+        Left e -> putStrLn e+        Right ms -> putStr $ concatMap message ms+    where+        message (n, b) = n ++ (if b then ": match!" else ": not match!") ++ "\n"++{-|+Checks whether a specific pattern matches an AST and prints the result.++@since 1.0.0+-}+parseMatch1IO :: FilePath -> FilePath -> FilePath -> String -> IO ()+parseMatch1IO grammarFile patternFile inputFile pat = do+    contentsG <- readFile grammarFile+    contentsP <- readFile patternFile+    contentsF <- readFile inputFile+    case parseMatch1 contentsG contentsP contentsF pat of+        Left e -> putStrLn e+        Right b -> putStrLn $ pat ++ (if b then ": match!" else ": not match!")++{-|+Captures subtrees matching patterns in an AST and prints the results.++@since 1.0.0+-}+parseCaptureIO :: FilePath -> FilePath -> FilePath -> IO ()+parseCaptureIO grammarFile patternFile inputFile = do+    contentsG <- readFile grammarFile+    contentsP <- readFile patternFile+    contentsF <- readFile inputFile+    case parseCapture contentsG contentsP contentsF of+        Left e -> putStrLn e+        Right ms -> putStr $ concatMap message ms+    where+        message (n, c) = "pattern " ++ n ++ ":\n" ++ concatMap printCaptures c ++ "\n"+        printCaptures xs = concatMap printCapture xs ++ "\n"+        printCapture (p, t) = show (pPrint p) ++ ":\n" ++ flatten t ++ "\n"++{-|+Captures subtrees matching a specific pattern in an AST and prints the results.++@since 1.0.0+-}+parseCapture1IO :: FilePath -> FilePath -> FilePath -> String -> IO ()+parseCapture1IO grammarFile patternFile inputFile pat = do+    contentsG <- readFile grammarFile+    contentsP <- readFile patternFile+    contentsF <- readFile inputFile+    case parseCapture1 contentsG contentsP contentsF pat of+        Left e -> putStrLn e+        Right m -> putStrLn $ concatMap printCaptures m ++ "\n"+    where+        printCaptures xs = concatMap printCapture xs ++ "\n"+        printCapture (p, t) = show (pPrint p) ++ ":\n" ++ flatten t ++ "\n"++{-|+Rewrites an AST based on two patterns and prints the result.++@since 1.0.0+-}+parseRewriteIO :: FilePath -> FilePath -> FilePath -> String -> String -> IO ()+parseRewriteIO grammarFile patternFile inputFile pat1 pat2 = do+    contentsG <- readFile grammarFile+    contentsP <- readFile patternFile+    contentsF <- readFile inputFile+    case parseRewrite contentsG contentsP contentsF pat1 pat2 of+        Left e -> putStrLn e+        Right t -> putStrLn $ flatten t++{-|+Builds and prints a call graph for two named patterns from files.++The first pattern is interpreted as a definition pattern and the second as a+call pattern. Output is printed as `definition -> call` pairs.+@since 1.0.0+-}+parseCallGraphIO :: FilePath -> FilePath -> FilePath -> String -> String -> IO ()+parseCallGraphIO grammarFile patternFile inputFile pat1 pat2 = do+    contentsG <- readFile grammarFile+    contentsP <- readFile patternFile+    contentsF <- readFile inputFile+    case parseCallGraph contentsG contentsP contentsF pat1 pat2 of+        Left e -> putStrLn e+        Right t -> putStrLn $ concat . nub $ map (\ (x, y) -> flatten x ++ " -> " ++ flatten y ++ "\n") t
+ src/Quote/Base.hs view
@@ -0,0 +1,72 @@+{-|+Module      : Quote.Base+Description : Base file for QuasiQuoter.+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module provides basic functions for QuasiQuoters.+-}+module Quote.Base +    ( topLevel+    , parseIO+    , location'+    , setPosition+    ) where++import Parser.Base (Parser, sc)+import Text.Megaparsec+    ( parse+    , MonadParsec(eof, updateParserState)+    , SourcePos(..)+    , mkPos+    , PosState (pstateSourcePos)+    , State (statePosState), errorBundlePretty+    )+import Language.Haskell.TH+    (Q, location, Loc(loc_start, loc_filename))+import Control.Exception (throwIO)++{-|+Parses a parser from the beginning of input and requires that the parser+consumes all remaining whitespace and reaches end of file.+-}+topLevel :: Parser a -> Parser a+topLevel p = sc *> p <* eof++{-|+Parse a string using the provided parser and raise an IO exception on parse+failure.+-}+parseIO :: Parser a -> String -> IO a+parseIO p str =+    case parse p "" str of+        Left err -> throwIO (userError (errorBundlePretty err))+        Right a  -> return a++{-|+Return the current Template Haskell source position as a Megaparsec+position, t'Text.Megaparsec.SourcePos'.+-}+location' :: Q SourcePos+location' = aux <$> location+    where+        aux :: Loc -> SourcePos+        aux loc =+            let (line, col) = loc_start loc+            in SourcePos +            {   sourceName = loc_filename loc+            ,   sourceLine = mkPos line+            ,   sourceColumn = mkPos col +            }++{-|+Set the parser state position to the given t'Text.Megaparsec.SourcePos'.+-}+setPosition :: SourcePos -> Parser ()+setPosition pos = updateParserState $ \state ->+    let pst = statePosState state+        pst' = pst { pstateSourcePos = pos }+    in state { statePosState = pst' }
+ src/Quote/Pattern.hs view
@@ -0,0 +1,37 @@+{-|+Module      : Quote.Pattern+Description : QuasiQuoter for patterns.+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module provides QuasiQuoters for patterns, including definitions, +expressions, and PEG operators.+-}+module Quote.Pattern +    ( patterns+    ) where++import Quote.Base ( topLevel, parseIO, location', setPosition )+import qualified Parser.Pattern as Pattern+import Language.Haskell.TH (runIO)+import Language.Haskell.TH.Quote (dataToExpQ, QuasiQuoter(..))++{-|+QuasiQuoter for pattern syntax.++Parses a pattern string at compile time and converts it into a Template+Haskell expression.+-}+patterns :: QuasiQuoter+patterns = QuasiQuoter {+        quoteExp = \ str -> do+            l <- location'+            c <- runIO $ parseIO (setPosition l *> topLevel Pattern.patterns) str+            dataToExpQ (const Nothing) c+        , quotePat  = undefined+        , quoteType = undefined+        , quoteDec  = undefined+    }
+ src/Quote/Peg.hs view
@@ -0,0 +1,37 @@+{-|+Module      : Quote.Peg+Description : QuasiQuoter for PEGs (Parsing Expression Grammars).+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module provides QuasiQuoters for PEGs (Parsing Expression Grammars),+including definitions, expressions, and PEG operators.+-}+module Quote.Peg +    ( grammar+    ) where++import Quote.Base ( topLevel, parseIO, location', setPosition )+import qualified Parser.Peg as Peg+import Language.Haskell.TH (runIO)+import Language.Haskell.TH.Quote (dataToExpQ, QuasiQuoter(..))++{-|+QuasiQuoter for PEG grammar syntax.++Parses a grammar string at compile time and converts it into a Template+Haskell expression.+-}+grammar :: QuasiQuoter+grammar = QuasiQuoter {+        quoteExp = \ str -> do+            l <- location'+            c <- runIO $ parseIO (setPosition l *> topLevel Peg.grammar) str+            dataToExpQ (const Nothing) c+        , quotePat  = undefined+        , quoteType = undefined+        , quoteDec  = undefined+    }
+ src/Semantic/Pattern.hs view
@@ -0,0 +1,410 @@+{-|+Module      : Semantic.Pattern+Description : Semantic analysis of patterns in PEGs.+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module provides functions for semantic analysis of patterns ('Pattern') in PEGs ('Grammar').+It includes validations, conversions, and error detection, such as invalid patterns, recursions, and duplications.+It also defines specific exceptions for semantic errors related to patterns.+-}+module Semantic.Pattern+    ( PatternException(..)+      -- | Payloads carried by the constructors of 'PatternException'.+    , RefOutOfScopeException(..)+    , InvalidPatternException(..)+    , DuplicatePatternException(..)+    , Proof(..)+    , processPats+    , correctPat+    , validPat+    ) where++import Syntax.Base (toMaybe, duplicatesOfFirst, filterByFirst, Terminal, NonTerminal, Pretty(..))+import Syntax.Peg (Grammar, Expression(..), expression, ExpressionZipper, goLeft, goRight, goDown, goUp, pullFromRight)+import Syntax.Pattern+    ( NamedSynPat+    , NamedPattern+    , SyntaxPattern(..)+    , Pattern(..)+    , references+    , replaceSynPats)+import Data.Foldable (Foldable(toList))+import Data.Maybe (isNothing, fromJust, listToMaybe, mapMaybe, isJust)+import Data.Either (rights, lefts)+import qualified Algebra.Graph.AdjacencyMap as Alga+import qualified Algebra.Graph.AdjacencyMap.Algorithm as Algo+import Data.Bifunctor (Bifunctor(second, first))+import Control.Exception (Exception)+import Control.Applicative ((<|>))+import Data.Data (Typeable, Data)+import Text.PrettyPrint.HughesPJ (Doc, text, (<+>), parens)+import Data.List (intercalate)++-------------------------------------------------------------------------------+--- Types and Exceptions++{-|+Represents a proof of matching a pattern ('Pattern') with a PEG.++@since 1.0.0+-}+data Proof+    = ProofEpsilon+    | ProofT Terminal+    | ProofNT NonTerminal Proof+    | ProofSeq Proof Proof+    | ProofChoice Proof Proof+    | ProofChoiceLeft Proof+    | ProofChoiceRight Proof+    | ProofStar Proof+    | ProofStarSeq [Proof]+    | ProofNot Proof+    | ProofVar Expression String+    deriving (Eq, Show, Ord, Typeable, Data)++{-|+Exception raised when a pattern references non-terminals out of scope.++@since 1.0.0+-}+data RefOutOfScopeException+    = RefOutOfScope NamedSynPat [String]+    deriving (Show, Eq, Ord)++{-|+Exception raised when a pattern is invalid.++@since 1.0.0+-}+data InvalidPatternException+    = InvalidSyntax NamedSynPat+    | InvalidPattern NamedPattern+    deriving (Show, Eq, Ord)++{-|+Exception raised when there are multiple definitions for the same pattern.++@since 1.0.0+-}+data DuplicatePatternException+    = DuplicatePattern String [SyntaxPattern]+    deriving (Show, Eq, Ord)++{-|+Exceptions related to the semantic analysis of patterns.++Possible exceptions include:+- 'PatOutOfScope': References to non-terminals out of scope.+- 'PatRecursive': Recursions between patterns.+- 'PatInvalid': Invalid patterns.+- 'PatDuplicate': Duplicate patterns.++@since 1.0.0+-}+data PatternException+    = PatOutOfScope [RefOutOfScopeException]+    | PatRecursive [NamedSynPat]+    | PatInvalid [InvalidPatternException]+    | PatDuplicate [DuplicatePatternException]+    deriving (Show, Eq, Ord)++instance Exception RefOutOfScopeException+instance Exception InvalidPatternException+instance Exception DuplicatePatternException+instance Exception PatternException++-------------------------------------------------------------------------------+--- Pretty Instances++{-|+Instance of the 'Pretty' class for 'PatternException'.++Prints the exception in a readable format, detailing the type of error and the elements involved.++@since 1.0.0+-}+instance Pretty PatternException where+    pPrint :: PatternException -> Doc+    pPrint (PatOutOfScope refs) = pPrint refs+    pPrint (PatRecursive pats) = text "The following definitions are mutually recursive:"+                                 <+> pPrint pats+    pPrint (PatInvalid invalids) = pPrint invalids+    pPrint (PatDuplicate dups) = pPrint dups++{-|+Instance of the 'Pretty' class for 'RefOutOfScopeException'.++Prints the exception indicating the pattern that references non-terminals out of scope.++@since 1.0.0+-}+instance Pretty RefOutOfScopeException where+    pPrint :: RefOutOfScopeException -> Doc+    pPrint (RefOutOfScope p refs) = text "The pattern" <+> pPrint p+                                    <+> text "depends on undefined rules"+                                    <+> text (intercalate "," refs)++{-|+Instance of the 'Pretty' class for 'InvalidPatternException'.++Prints the exception indicating the invalid pattern or invalid syntax.++@since 1.0.0+-}+instance Pretty InvalidPatternException where+    pPrint :: InvalidPatternException -> Doc+    pPrint (InvalidPattern p) = text "Invalid pattern:" <+> pPrint p+    pPrint (InvalidSyntax p) = text "Invalid syntax:" <+> pPrint p++{-|+Instance of the 'Pretty' class for 'DuplicatePatternException'.++Prints the exception indicating the duplicate pattern.++@since 1.0.0+-}+instance Pretty DuplicatePatternException where+    pPrint :: DuplicatePatternException -> Doc+    pPrint (DuplicatePattern n ps) = text "Multiple definitions for " <+> text n+                                     <+> parens (pPrint ps)++-------------------------------------------------------------------------------+--- Main Functions++{-|+Converts a 'SyntaxPattern' to a 'Pattern', if possible.++@since 1.0.0+-}+synToPat :: SyntaxPattern -> Maybe Pattern+synToPat SynEpsilon        = Just PatEpsilon+synToPat (SynT t)          = Just $ PatT t+synToPat (SynVar s n)      = Just $ PatVar s n+synToPat (SynRef _)        = Nothing+synToPat (SynNot p)        = PatNot <$> synToPat p+synToPat (SynNT nt p)      = PatNT nt <$> synToPat p+synToPat (SynSeq p1 p2)    = PatSeq <$> synToPat p1 <*> synToPat p2+synToPat (SynChoice p1 p2) = PatChoice <$> synToPat p1 <*> synToPat p2+synToPat (SynStar p)       = PatStar <$> synToPat p++{-|+Converts a 'SyntaxPattern' to a 'Pattern', if possible.++If the conversion fails (e.g., due to invalid references), returns an error.++@since 1.0.0+-}+synToPat' :: NamedSynPat -> Either InvalidPatternException NamedPattern+synToPat' p@(n, sn) = maybeToRight (synToPat sn)+    where+        invalid = Left $ InvalidSyntax p+        maybeToRight = maybe invalid (Right . (n,))++{-|+Calculates the dependencies of a syntactic pattern ('NamedSynPat').++Returns a list of edges representing the dependencies between patterns. If there are+references out of scope, returns an exception ('RefOutOfScopeException').++@since 1.0.0+-}+dependencies ::+    NamedSynPat+    -> [NamedSynPat]+    -> Either RefOutOfScopeException [(NamedSynPat, NamedSynPat)] -- List of edges+dependencies p ps =+    case filter (isNothing . snd) depends of+        [] -> Right $ map (\ x -> (second fromJust x, p)) depends+        x -> Left $ RefOutOfScope p (map fst x)+    where+        refs = references $ snd p+        findPats ps' s = (s, lookup s ps')+        depends = map (findPats ps) refs++{-|+Creates the edges of a dependency graph for syntactic patterns ('NamedSynPat').++If there are references out of scope, returns an exception ('PatOutOfScope').++@since 1.0.0+-}+mkEdges :: [NamedSynPat] -> Either PatternException [(NamedSynPat, NamedSynPat)]+mkEdges ps =+    case lefts result of+        [] -> Right . concat . rights $ result+        p -> Left . PatOutOfScope $ p+    where+        result = map (`dependencies` ps) ps++{-|+Checks for duplicate patterns in a list of syntactic patterns ('NamedSynPat').++If there are duplications, returns an exception ('PatDuplicate'). Otherwise, returns+the original list of patterns.++@since 1.0.0+-}+duplicates :: [NamedSynPat] -> Either PatternException [NamedSynPat]+duplicates ps =+    case duplicatesOfFirst ps of+        [] -> Right ps+        ds -> Left . PatDuplicate $ map (\ x -> DuplicatePattern x (filterByFirst ps x)) ds++{-|+Creates a dependency graph for syntactic patterns ('NamedSynPat').++If there are duplicate patterns or references out of scope, returns an exception.++@since 1.0.0+-}+mkGraph :: [NamedSynPat] -> Either PatternException (Alga.AdjacencyMap NamedSynPat)+mkGraph ps =+    case duplicates ps of+        Left e -> Left e+        Right ps' -> second (Alga.overlay (Alga.vertices ps) . Alga.edges) (mkEdges ps')++{-|+Performs topological sorting of a dependency graph of syntactic patterns.++If there are recursions, returns an exception ('PatRecursive'). Otherwise, returns+the sorted list of patterns.++@since 1.0.0+-}+topSort :: Alga.AdjacencyMap NamedSynPat -> Either PatternException [NamedSynPat]+topSort g = first (PatRecursive . toList) (Algo.topSort g)++{-|+Validates a pattern ('Pattern') against a PEG ('Grammar').+Returns a proof if the pattern is valid.++@since 1.0.0+-}+validPat :: Grammar -> Pattern -> Maybe Proof+validPat g (PatNT nt p) = ProofNT nt <$> (checkPat g p . (, []) =<< expr)+    where+        expr = expression g nt+validPat g@(ds, _) p = firstJust (checkPat g p . (, []) . snd) ds+    where+        firstJust f = listToMaybe . mapMaybe f++{-|+Checks if a pattern ('Pattern') matches an expression ('Expression').+Returns a proof if the pattern is valid.++@since 1.0.0+-}+checkPat :: Grammar -> Pattern -> ExpressionZipper -> Maybe Proof+checkPat g (PatVar e n) (e'@(ExprNT nt), _) =+    if e == e'+        then Just $ ProofVar e n+        else (\x -> toMaybe (x == e') (ProofVar x n)) =<< expression g nt+checkPat g (PatVar e@(ExprNT nt) n) (e', _) =+    if e == e'+        then Just $ ProofVar e n+        else (\x -> toMaybe (x == e') (ProofVar x n)) =<< expression g nt+checkPat g (PatVar e n)         z@(e', _)           =+    if e == e'+        then Just $ ProofVar e n+        else checkPat g (PatVar e n) =<< e2+    where+        up = goUp z+        e1 = (\(expr, z') -> (,z') <$> pullFromRight expr) =<< up+        e2 = goLeft =<< e1+checkPat _ PatEpsilon           (Empty, _)          = Just ProofEpsilon+checkPat _ (PatT t)             (ExprT t', _)       = toMaybe (t == t') (ProofT t)+checkPat g p@(PatNT nt _)       (ExprNT nt', _)     = if nt == nt' then validPat g p else Nothing+checkPat g (PatSeq p1 p2)       z@(Sequence _ _, _) = ProofSeq+                                                        <$> (checkPat g p1 =<< goLeft z)+                                                        <*> (checkPat g p2 =<< goRight z)+checkPat g (PatSeq p1 p2)       z@(Indent _ _, _)   = ProofSeq+                                                        <$> (checkPat g p1 =<< goLeft z)+                                                        -- Esse segundo transforma a expressão em uma estrela+                                                        -- por causa do jeito que o Indent funciona+                                                        <*> (checkPat g p2 . first Star =<< goRight z)+checkPat g (PatChoice p1 p2)    z@(Choice _ _, _)   = ProofChoice+                                                        <$> (checkPat g p1 =<< goLeft z)+                                                        <*> (checkPat g p2 =<< goRight z)+checkPat g p                    z@(Choice _ _, _)   = (ProofChoiceLeft <$> (checkPat g p =<< goLeft z))+                                                        <|> (ProofChoiceRight <$> (checkPat g p =<< goRight z))+checkPat _ PatEpsilon           (Star _, _)         = Just $ ProofStarSeq []+checkPat g (PatStar p)          z@(Star _, _)       = ProofStar <$> (checkPat g p =<< goDown z)+checkPat g p                    z@(Star _, _)       = ProofStarSeq <$> (checkPatStar' g p =<< goDown z)+checkPat g (PatNot p)           z@(Not _, _)        = ProofNot <$> (checkPat g p =<< goDown z)+checkPat _ (PatT t)             (Flatten _, _)      = Just $ ProofT t+checkPat g p                    z@(Flatten _, _)    = checkPat g p =<< goDown z+checkPat _ _                    _                   = Nothing++checkPatStar' :: Grammar -> Pattern -> ExpressionZipper -> Maybe [Proof]+checkPatStar' g p@(PatSeq p1 p2) e = if isJust p1' then (:) <$> p1' <*> p2' else (:[]) <$> checkPat g p e+    where+        p1' = checkPat g p1 e+        p2' = checkPatStar' g p2 e+checkPatStar' g p                e = (:[]) <$> checkPat g p e++{-|+Corrects a pattern ('Pattern') based on a proof of matching ('Proof').++@since 1.0.0+-}+correctPat :: Pattern -> Proof -> Maybe Pattern+correctPat PatEpsilon           ProofEpsilon             = Just PatEpsilon+correctPat (PatT t)             (ProofT t')              = toMaybe (t == t') (PatT t)+correctPat (PatNT nt pat)       (ProofNT nt' proof)      = if nt == nt'+                                                            then PatNT nt <$> correctPat pat proof+                                                            else Nothing+-- correctPat (PatVar pat n)       (ProofVar proof n')      = toMaybe (n == n' && pat == proof) (PatVar pat n)+correctPat (PatVar _ n)       (ProofVar proof n')        = toMaybe (n == n') (PatVar proof n)+correctPat (PatSeq p1 p2)       (ProofSeq p1' p2')       = PatSeq <$> correctPat p1 p1' <*> correctPat p2 p2'+correctPat PatEpsilon           (ProofStarSeq _)         = Just $ PatStarSeq []+correctPat p                    (ProofStarSeq xs)        = PatStarSeq <$> correctPatStar p xs+correctPat (PatChoice p1 p2)    (ProofChoice p1' p2')    = PatChoice <$> correctPat p1 p1' <*> correctPat p2 p2'+correctPat pat                  (ProofChoiceLeft proof)  = flip PatChoice (PatNot PatEpsilon) <$> correctPat pat proof+correctPat pat                  (ProofChoiceRight proof) = PatChoice (PatNot PatEpsilon) <$> correctPat pat proof+correctPat (PatStar pat)        (ProofStar proof)        = PatStar <$> correctPat pat proof+correctPat (PatNot pat)         (ProofNot proof)         = PatNot <$> correctPat pat proof+correctPat _                    _                        = Nothing++correctPatStar :: Pattern -> [Proof] -> Maybe [Pattern]+correctPatStar _ [] = Nothing+correctPatStar p [x] = (:[]) <$> correctPat p x+correctPatStar (PatSeq p1 p2) (x:xs) = (:) <$> correctPat p1 x <*> correctPatStar p2 xs+correctPatStar _ (_:_) = Nothing++{-|+Processes a list of syntactic patterns ('NamedSynPat') and validates the patterns.++Returns a list of valid patterns or an exception indicating the errors found.++@since 1.0.0+-}+processSynPats :: Grammar -> [NamedSynPat] -> Either PatternException [NamedPattern]+processSynPats g ps =+    case lefts pats of+        [] -> case filter (isNothing . validPat g . snd) valids of+                [] -> Right valids+                invalids -> Left $ PatInvalid (map InvalidPattern invalids)+        e -> Left $ PatInvalid e+    where+        pats = map synToPat' ps+        valids = rights pats++{-|+Processes a list of syntactic patterns ('NamedSynPat') and validates the patterns.++Returns a list of valid patterns or an exception indicating the errors found.++@since 1.0.0+-}+processPats :: Grammar -> [NamedSynPat] -> Either PatternException [NamedPattern]+processPats g ps =+    case mkGraph ps of+        Left x -> Left x+        Right graph ->+            case topSort graph of+                Left x -> Left x+                Right ps' -> processSynPats g $ replaceSynPats ps'
+ src/Semantic/Peg.hs view
@@ -0,0 +1,328 @@+{-|+Module      : Semantic.Peg+Description : Semantic analysis of PEGs (Parsing Expression Grammars).+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module provides functions for semantic analysis of PEGs ('Grammar'),+including rule validation, left recursion detection, nullable expressions,+and duplicate definitions. It also defines specific exceptions for semantic+errors in PEGs.+-}+module Semantic.Peg+    ( PegException(..)+      -- | Payloads carried by the constructors of 'PegException'.+    , RefOutOfScopeException(..)+    , DuplicateDefinitionException(..)+    , processPeg+    ) where++import Syntax.Base (NonTerminal(..), duplicatesOfFirst, filterByFirst, Pretty(..))+import Syntax.Peg (Expression(..), Definition, Grammar, terminals, expression)+import Data.List (nub)+import Data.Maybe (isNothing, fromJust, fromMaybe)+import Data.Foldable (Foldable (toList))+import Data.Bifunctor (Bifunctor(first, second))+import Control.Exception (Exception)+import Data.Either (lefts, rights)+import qualified Algebra.Graph.AdjacencyMap as Alga+import qualified Algebra.Graph.AdjacencyMap.Algorithm as Algo+import Data.Generics (mkT, everywhere)+import Text.PrettyPrint.HughesPJ (Doc, text, (<+>), parens)++-------------------------------------------------------------------------------+--- Exceptions++{-|+Exception raised when a definition references non-terminals that are not defined.++@since 1.0.0+-}+data RefOutOfScopeException+    = RefOutOfScope Definition [NonTerminal]+    deriving (Show, Eq, Ord)++{-|+Exception raised when there are multiple definitions for the same non-terminal.++@since 1.0.0+-}+data DuplicateDefinitionException+    = DuplicateDefinition NonTerminal [Expression]+    deriving (Show, Eq, Ord)++{-|+Exceptions related to the semantic analysis of PEGs.++Possible exceptions include:+- 'OutOfScope': References to non-terminals out of scope.+- 'LeftRecursive': Left recursion detected.+- 'StarNullable': Nullable expressions inside repetition operators (`*`).+- 'DuplicateRule': Duplicate rules for the same non-terminal.++@since 1.0.0+-}+data PegException+    = OutOfScope [RefOutOfScopeException]+    | LeftRecursive [Definition]+    | StarNullable [Definition]+    | DuplicateRule [DuplicateDefinitionException]+    deriving (Show, Eq, Ord)++instance Exception RefOutOfScopeException+instance Exception DuplicateDefinitionException+instance Exception PegException++-------------------------------------------------------------------------------+--- Pretty Instances++{-|+Instance of the 'Pretty' class for 'PegException'.++Prints the exception in a readable format, detailing the type of error and the elements involved.++@since 1.0.0+-}+instance Pretty PegException where+    pPrint :: PegException -> Doc+    pPrint (OutOfScope refs) = pPrint refs+    pPrint (LeftRecursive defs) = text "The following definitions cause left recursion:"+                                    <+> pPrint defs+    pPrint (StarNullable defs) = text "The following definitions have nullable expressions inside *:"+                                    <+> pPrint defs+    pPrint (DuplicateRule defs) = pPrint defs++{-|+Instance of the 'Pretty' class for 'RefOutOfScopeException'.++Prints the exception indicating the rule that references non-terminals out of scope.++@since 1.0.0+-}+instance Pretty RefOutOfScopeException where+    pPrint :: RefOutOfScopeException -> Doc+    pPrint (RefOutOfScope def nts) = text "The rule" <+> pPrint def+                                     <+> text "depends on undefined rules"+                                     <+> parens (pPrint nts)++{-|+Instance of the 'Pretty' class for 'DuplicateDefinitionException'.++Prints the exception indicating the non-terminal with multiple definitions.++@since 1.0.0+-}+instance Pretty DuplicateDefinitionException where+    pPrint :: DuplicateDefinitionException -> Doc+    pPrint (DuplicateDefinition nt es) = text "Multiple definitions for " <+> pPrint nt+                                         <+> parens (pPrint es)++-------------------------------------------------------------------------------++{-|+Replaces the special symbol `.` in a PEG ('Grammar').++The symbol `.` is replaced by a choice of all terminals present in the grammar.++@since 1.0.0+-}+processDot :: Grammar -> Grammar+processDot g = first (map processDef) g+    where+        t = foldr1 Choice $ map ExprT $ terminals g+        processDef = second (everywhere $ mkT (changeNT t))+        changeNT ts e@(ExprNT (NT nt)) = if nt == "." then ts else e+        changeNT _  e                  = e++{-|+Checks for duplicate definitions in a PEG ('Grammar').++If there are multiple definitions for the same non-terminal, returns an exception+('DuplicateRule'). Otherwise, returns the original PEG.++@since 1.0.0+-}+duplicates :: Grammar -> Either PegException Grammar+duplicates g@(defs, _) =+    case duplicatesOfFirst defs of+        [] -> Right g+        ds -> Left . DuplicateRule $ map (\ x -> DuplicateDefinition x (filterByFirst defs x)) ds++{-|+Determines if a definition in a PEG ('Grammar') is nullable.++A definition is nullable if it can produce the empty string.++@since 1.0.0+-}+nullable :: Grammar -> Definition -> Bool+nullable _ (_, Empty)           = True+nullable _ (_, Star _)          = True+nullable _ (_, Not _)           = True+nullable _ (_, ExprT _)         = False+nullable g (nt, ExprNT nt')     = nt == nt'+                                  || nullable g (nt', fromMaybe (error $ "Error " ++ show nt') (expression g nt'))+nullable g (nt, Sequence e1 e2) = nullable g (nt, e1) && nullable g (nt, e2)+nullable g (nt, Choice e1 e2)   = nullable g (nt, e1) || nullable g (nt, e2)+nullable g (nt, Flatten e)      = nullable g (nt, e)+nullable g (nt, Indent e b)     = nullable g (nt, e) && nullable g (nt, b)++{-|+Identifies nullable expressions inside repetition operators (`*`, 'Star').++Returns a list of definitions that have nullable expressions inside repetition operators.++@since 1.0.0+-}+starNullable :: Grammar -> Definition -> [Definition]+starNullable _ (_, Empty)           = []+starNullable _ (_, ExprT _)         = []+starNullable g (nt, Not e)          = starNullable g (nt, e)+starNullable g (nt, Flatten e)      = starNullable g (nt, e)+starNullable g (nt, Choice e1 e2)   = starNullable g (nt, e1) ++ starNullable g (nt, e2)+starNullable g (nt, ExprNT nt')     = if nt == nt'+                                        then [(nt, ExprNT nt')]+                                        else starNullable g (nt', fromJust $ expression g nt')+starNullable g (nt, Sequence e1 e2) = if nullable g (nt, e1)+                                        then starNullable g (nt, e1) ++ starNullable g (nt, e2)+                                        else starNullable g (nt, e1)+starNullable g (nt, Star e)         = if nullable g (nt, e)+                                        then [(nt, Star e)]+                                        else starNullable g (nt, e)+starNullable g (nt, Indent e1 e2)   = if nullable g (nt, e1)+                                        then starNullable g (nt, e1) ++ starNullable g (nt, e2)+                                        else starNullable g (nt, e1)++{-|+Checks for nullable expressions inside repetition operators in a PEG ('Grammar').++If there are, returns an exception ('StarNullable'). Otherwise, returns `Nothing`.++@since 1.0.0+-}+recursiveLoop :: Grammar -> Maybe PegException+recursiveLoop g@(ds, _) =+    case expr of+        [] -> Nothing+        xs -> Just $ StarNullable xs+    where+        expr = nub $ concatMap (starNullable g) ds++{-|+Returns the non-terminals referenced by a definition in a PEG ('Grammar').++@since 1.0.0+-}+referencesNull :: Grammar -> Definition -> [NonTerminal]+referencesNull _ (_, Empty)           = []+referencesNull _ (_, ExprT _)         = []+referencesNull _ (_, ExprNT nt')      = [nt']+referencesNull g (nt, Sequence e1 e2) = if nullable g (nt, e1)+                                        then referencesNull g (nt, e1) ++ referencesNull g (nt, e2)+                                        else referencesNull g (nt, e1)+referencesNull g (nt, Choice e1 e2)   = referencesNull g (nt, e1) ++ referencesNull g (nt, e2)+referencesNull g (nt, Star e)         = referencesNull g (nt, e)+referencesNull g (nt, Not e)          = referencesNull g (nt, e)+referencesNull g (nt, Flatten e)      = referencesNull g (nt, e)+referencesNull g (nt, Indent e1 e2)   = if nullable g (nt, e1)+                                        then referencesNull g (nt, e1) ++ referencesNull g (nt, e2)+                                        else referencesNull g (nt, e1)++{-|+Calculates the dependencies of a definition in a PEG ('Grammar').++Returns a list of pairs of definitions representing the dependencies. If there are+references to non-terminals out of scope, returns an exception ('RefOutOfScopeException').++@since 1.0.0+-}+dependencies ::+    Grammar+    -> Definition+    -> Either RefOutOfScopeException [(Definition, Definition)] -- List of dependencies+dependencies g@(ds, _) d =+    case filter (isNothing . snd) depends of+        [] -> Right $ map (\ x -> (second fromJust x, d)) depends+        x -> Left $ RefOutOfScope d (map fst x)+    where+        refs = nub $ referencesNull g d+        findNTs ds' s = (s, lookup s ds')+        depends = map (findNTs ds) refs++{-|+Creates the edges of a dependency graph for a PEG ('Grammar').++If there are references out of scope, returns an exception ('OutOfScope').++@since 1.0.0+-}+mkEdges :: Grammar -> Either PegException [(Definition, Definition)]+mkEdges g@(ds, _) =+    case lefts result of+        [] -> Right . concat . rights $ result+        p -> Left . OutOfScope $ p+    where+        result = map (dependencies g) ds++{-|+Creates a dependency graph for a PEG ('Grammar').++If there are duplicate definitions or references out of scope, returns an exception.++@since 1.0.0+-}+mkGraph :: Grammar -> Either PegException (Alga.AdjacencyMap Definition)+mkGraph g@(ds, _) =+    case duplicates g of+        Left e -> Left e+        Right ds' -> second (Alga.overlay (Alga.vertices ds) . Alga.edges) (mkEdges ds')++{-|+Checks for left recursion in a PEG ('Grammar').++If there is, returns an exception ('LeftRecursive'). Otherwise, returns `Nothing`.++@since 1.0.0+-}+leftRecursive :: Alga.AdjacencyMap Definition -> Maybe PegException+leftRecursive g = leftToMaybe (first (LeftRecursive . toList) (Algo.topSort g))+    where+        leftToMaybe = either Just (const Nothing)++{-|+Processes and validates a PEG ('Grammar').++The 'processPeg' function performs the following validations:+1. Replaces the special symbol `.` with a choice of all terminals.+2. Checks for duplicate rules.+3. Detects left recursion.+4. Identifies nullable expressions inside repetition operators (`*`, 'Star').++If the grammar is valid, returns the processed grammar. Otherwise, returns+an exception ('PegException') indicating the error found.++=== Usage examples:++>>> let grammar = ([(NT "S", Sequence (ExprT (T "a")) (ExprT (T "b")))], NT "S")+>>> processPeg grammar+Right ([(NT "S",Sequence (ExprT (T "a")) (ExprT (T "b")))],NT "S")++>>> let invalidGrammar = ([(NT "S", Sequence (ExprNT (NT "S")) (ExprT (T "a")))], NT "S")+>>> processPeg invalidGrammar+Left (LeftRecursive [(NT "S",Sequence (ExprNT (NT "S")) (ExprT (T "a")))])++@since 1.0.0+-}+processPeg :: Grammar -> Either PegException Grammar+processPeg g =+    case mkGraph g' of+        Left x -> Left x+        Right graph ->+            case leftRecursive graph of+                Just x -> Left x+                Nothing -> maybe (Right g') Left (recursiveLoop g')+    where+        g' = processDot g
+ src/Syntax/Base.hs view
@@ -0,0 +1,173 @@+{-# OPTIONS_GHC -Wno-unrecognised-pragmas #-}+{-# HLINT ignore "Use newtype instead of data" #-}++{-|+Module      : Syntax.Base+Description : Basic definitions for symbols and grammar utilities.+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module defines the basic types to represent terminal and non-terminal symbols+in a grammar, as well as utilities for list manipulation and a class for formatted printing.+-}+module Syntax.Base+    ( NonTerminal(..)+    , Terminal(..)+    , Symbol+    , Pretty(..)+    , toMaybe+    , duplicatesOfFirst+    , filterByFirst+    ) where++import Text.PrettyPrint.HughesPJ (text, Doc, hcat)+import Data.Generics (Data, Typeable)++{-|+Represents a non-terminal symbol in a grammar.++A 'NonTerminal' is simply a string that identifies the non-terminal.++@since 1.0.0+-}+data NonTerminal+    = NT String+    deriving (Eq, Show, Ord, Typeable, Data)++{-|+Represents a terminal symbol in a grammar.++A 'Terminal' is a string that identifies the terminal.++@since 1.0.0+-}+data Terminal+    = T String+    deriving (Eq, Show, Ord, Typeable, Data)++{-|+Represents a "symbol," which is either a 'NonTerminal' or a 'Terminal'.++@since 1.0.0+-}+type Symbol = Either NonTerminal Terminal++{-|+Type class for types that can be printed as a text document (PrettyPrint).++The 'Pretty' class defines the 'pPrint' method to generate the representation in 'Doc' format.++@since 1.0.0+-}+class Pretty a where+    {-|+    Generates the formatted representation of a value as a 'Doc'.++    @since 1.0.0+    -}+    pPrint :: a -> Doc++{-|+Instance of the 'Pretty' class for lists.++Prints each element of the list concatenated.++@since 1.0.0+-}+instance Pretty a => Pretty [a] where+    pPrint :: [a] -> Doc+    pPrint l = hcat (map pPrint l)++{-|+Instance of the 'Pretty' class for 'NonTerminal'.++Prints the name of the non-terminal.++@since 1.0.0+-}+instance Pretty NonTerminal where+    pPrint :: NonTerminal -> Doc+    pPrint (NT nt) = text nt++{-|+Instance of the 'Pretty' class for 'Terminal'.++Prints the name of the terminal in quotes.++@since 1.0.0+-}+instance Pretty Terminal where+    pPrint :: Terminal -> Doc+    pPrint (T t) = text (show t)++{-|+Instance of the 'Pretty' class for 'Symbol'.++Prints the symbol, whether it is a 'NonTerminal' or a 'Terminal'.++@since 1.0.0+-}+instance Pretty Symbol where+    pPrint :: Symbol -> Doc+    pPrint (Left nt) = pPrint nt+    pPrint (Right t) = pPrint t++{-|+The 'toMaybe' function takes a boolean value and a generic value.++If the boolean value is 'True', it returns the value wrapped in a 'Just'.+Otherwise, it returns 'Nothing'.++=== Usage examples:++>>> toMaybe True "Hello"+Just "Hello"++>>> toMaybe False "Hello"+Nothing++@since 1.0.0+-}+toMaybe :: Bool -> a -> Maybe a+toMaybe False _ = Nothing+toMaybe True a = Just a++{-|+The 'duplicatesOfFirst' function takes a list of pairs @(a, b)@ and returns a list containing+the elements @a@ that appear more than once in the list. The function compares only the first+elements @(a)@ of the pairs.++=== Usage examples:++>>> duplicatesOfFirst [(1, "a"), (2, "b"), (1, "c"), (3, "d"), (2, "e")]+[2,1]++@since 1.0.0+-}+duplicatesOfFirst :: Eq a => [(a, b)] -> [a]+duplicatesOfFirst ls = duplicates ls [] []+    where+        duplicates []     _       dups = dups+        duplicates (x:xs) checked dups =+            if fst x `elem` checked+                then duplicates xs checked (fst x:dups)+                else duplicates xs (fst x:checked) dups++{-|+The 'filterByFirst' function takes a list of pairs @(a, b)@ and a value of type @a@.++It returns a list containing all the @b@ values that are associated with the given @a@+value. The function filters the pairs by the key @a@ and returns the corresponding values.++=== Usage examples:++>>> filterByFirst [(1, "a"), (2, "b"), (1, "c"), (3, "d")] 1+["a","c"]++@since 1.0.0+-}+filterByFirst :: Eq a => [(a, b)] -> a -> [b]+filterByFirst g' x = map snd $ filter ((x ==) . fst) g'
+ src/Syntax/ParsedTree.hs view
@@ -0,0 +1,271 @@+{-|+Module      : Syntax.ParsedTree+Description : Representation of parsed trees.+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module defines the structure of a parsed tree ('ParsedTree') and+associated functions, such as the 'flatten' function to extract the terminals from a tree.+It also provides an instance of the 'Pretty' class for formatted printing.+-}+module Syntax.ParsedTree+    ( ParsedTree(..)+    , ParsedTreeZipper+    , ParsedTreePath+    , ParsedTreeCrumbs+    , flatten+    , goUp+    , goDown+    , goLeft+    , goRight+    , pullFromRight+    , ofExpression+    ) where++import Syntax.Base (Terminal(..), NonTerminal, Pretty(..))+import Text.PrettyPrint.HughesPJ (text, Doc, (<+>), (<>), empty, lbrack, rbrack, hcat)+import Prelude hiding ((<>))+import Data.Generics (Data, Typeable, mkQ, everything)+import Syntax.Peg (Expression(..), Grammar, expression)++{-|+Represents an abstract syntax tree (AST).++A 'ParsedTree' can be:+- 'ParsedEpsilon': Represents the empty tree (ε).+- 'ParsedT': A terminal symbol.+- 'ParsedNT': A non-terminal symbol associated with a subtree.+- 'ParsedSeq': A sequence of two trees.+- 'ParsedChoiceLeft': Represents the left choice in a choice operation.+- 'ParsedChoiceRight': Represents the right choice in a choice operation.+- 'ParsedStar': Represents a repetition of zero or more times of a tree.+- 'ParsedNot': Represents the negation of a tree.+- 'ParsedIndent': Represents that a list of trees must be indented with respect to another tree.++@since 1.0.0+-}+data ParsedTree+    = ParsedEpsilon+    | ParsedT Terminal+    | ParsedNT NonTerminal ParsedTree+    | ParsedSeq ParsedTree ParsedTree+    | ParsedChoiceLeft ParsedTree+    | ParsedChoiceRight ParsedTree+    | ParsedStar [ParsedTree]+    | ParsedNot+    | ParsedIndent ParsedTree [ParsedTree]+    deriving (Show, Typeable, Data)++{-|+Breadcrumbs used to reconstruct the parent context while navigating a+'ParsedTree' with a zipper.++Each constructor records the information required to rebuild the tree when+moving back up from the current focus.+-}+data ParsedTreeCrumbs+    = ParsedNTCrumb NonTerminal+    | ParsedSeqFirst ParsedTree+    | ParsedSeqSecond ParsedTree+    | ParsedChoiceLeftCrumb+    | ParsedChoiceRightCrumb+    | ParsedStarCrumb [ParsedTree] [ParsedTree] -- primeiro é o que falta, segundo é o que já foi+    | ParsedIndentFirst [ParsedTree]+    | ParsedIndentSecond ParsedTree++{-|+A zipper path is the list of breadcrumbs representing the current position+inside a 'ParsedTree'. The most recent breadcrumb is at the head of the list.+-}+type ParsedTreePath = [ParsedTreeCrumbs]++{-|+A zipper for a parsed tree. The first component is the current focus, and the+second component is the path back to the root.+-}+type ParsedTreeZipper = (ParsedTree, ParsedTreePath)++{-|+Move the focus of a 'ParsedTreeZipper' up to its parent node, if possible.++This reconstructs the parent node from the current focus and the breadcrumb+stored in the zipper path.+-}+goUp :: ParsedTreeZipper -> Maybe ParsedTreeZipper+goUp (t, ParsedNTCrumb nt:z)                 = Just (ParsedNT nt t, z)+goUp (t, ParsedSeqFirst t':z)                = Just (ParsedSeq t t', z)+goUp (t, ParsedSeqSecond t':z)               = Just (ParsedSeq t' t, z)+goUp (t, ParsedChoiceLeftCrumb:z)            = Just (ParsedChoiceLeft t, z)+goUp (t, ParsedChoiceRightCrumb:z)           = Just (ParsedChoiceRight t, z)+-- goUp (t, (ParsedStarCrumb ts []):z)          = Just (ParsedStar (t:ts), z)+-- goUp z@(_, (ParsedStarCrumb _ _):_)          = goUp =<< goLeft z+goUp (t, ParsedStarCrumb ts1 ts2:z)          = Just (ParsedStar (t : reverse ts2 ++ ts1), z)+goUp (t, ParsedIndentFirst ts:z)             = Just (ParsedIndent t ts, z)+goUp (ParsedStar ts, ParsedIndentSecond t:z) = Just (ParsedIndent t ts, z)+goUp (_, ParsedIndentSecond _:_)             = Nothing+goUp (_, [])                                 = Nothing++-- TODO:+-- goLeft, goRight e goDown não dão muito bem quando tentam acessar esquerda e direita+-- de uma árvore que está dentro de uma lista, pois a preferência é por andar na lista.++{-|+Move the focus down into a child subtree, when the current focus is a node+that contains a single child or a non-empty star list.+-}+goDown :: ParsedTreeZipper -> Maybe ParsedTreeZipper+goDown (ParsedNT nt t, z)       = Just (t, ParsedNTCrumb nt:z)+goDown (ParsedChoiceLeft t, z)  = Just (t, ParsedChoiceLeftCrumb:z)+goDown (ParsedChoiceRight t, z) = Just (t, ParsedChoiceRightCrumb:z)+goDown (ParsedStar [], _)       = Nothing+goDown (ParsedStar (t:ts), z)   = Just (t, ParsedStarCrumb ts []:z)+goDown _                        = Nothing++{-|+Move the focus left within the current zipper context.++This is valid for star lists, sequence nodes, and indent nodes where a+left sibling exists.+-}+goLeft :: ParsedTreeZipper -> Maybe ParsedTreeZipper+goLeft (_, (ParsedStarCrumb _ []):_)         = Nothing+goLeft (t, (ParsedStarCrumb ts1 (t':ts2)):z) = Just (t', ParsedStarCrumb (t:ts1) ts2:z)+goLeft (ParsedSeq t1 t2, z)                  = Just (t1, ParsedSeqFirst t2:z)+goLeft (ParsedIndent t ts, z)                = Just (t, ParsedIndentFirst ts:z)+goLeft _                                     = Nothing++{-|+Move the focus right within the current zipper context.++This is valid for star lists, sequence nodes, and indent nodes where a+right sibling exists.+-}+goRight :: ParsedTreeZipper -> Maybe ParsedTreeZipper+goRight (_, (ParsedStarCrumb [] _):_)         = Nothing+goRight (t, (ParsedStarCrumb (t':ts1) ts2):z) = Just (t', ParsedStarCrumb ts1 (t:ts2):z)+goRight (ParsedSeq t1 t2, z)                  = Just (t2, ParsedSeqSecond t1:z)+goRight (ParsedIndent t ts, z)                = Just (ParsedStar ts, ParsedIndentSecond t:z)+goRight _                                     = Nothing++{-|+Pull the first element from the right side of a sequence and append it to+its left side.++If the provided tree is not a sequence, this returns 'Nothing'.+-}+pullFromRight :: ParsedTree -> Maybe ParsedTree+pullFromRight (ParsedSeq t1 t2) = maybe (Just t1') (Just . ParsedSeq t1') tT+    where+        (tH, tT) = getHead t2+        t1' = addAtEnd t1 tH+pullFromRight _ = Nothing++addAtEnd :: ParsedTree -> ParsedTree -> ParsedTree+addAtEnd (ParsedSeq t1 t2) e3 = ParsedSeq t1 $ addAtEnd t2 e3+addAtEnd e e3 = ParsedSeq e e3++getHead :: ParsedTree -> (ParsedTree, Maybe ParsedTree)+getHead (ParsedSeq t1 t2) = (t1, Just t2)+getHead e                = (e, Nothing)++{-|+Instance of the 'Pretty' class for 'ParsedTree'.++Prints the syntax tree in a readable format, with indentation+and visual symbols to represent the tree hierarchy.++@since 1.0.0+-}+instance Pretty ParsedTree where+    pPrint :: ParsedTree -> Doc+    pPrint pt = pPrint' Text.PrettyPrint.HughesPJ.empty pt <> text "\n"++-- Auxiliary functions for tree formatting+nest :: Doc -> Doc+nest i = i <> text "├╴"++nest1 :: Doc -> Doc+nest1 i = i <> text "╰╴"++continue :: Doc -> Doc+continue i = i <> text "| "++continue1 :: Doc -> Doc+continue1 i = i <> text "  "++{-|+Auxiliary function for formatted printing of a 'ParsedTree'.++@since 1.0.0+-}+pPrint' :: Doc -> ParsedTree -> Doc+pPrint' _ ParsedEpsilon = text "ε"+pPrint' _ (ParsedT t) = pPrint t+pPrint' indent (ParsedNT nt tree) =+    text "NT" <+> pPrint nt <> text "\n"+    <> nest1 indent <> pPrint' (continue1 indent) tree+pPrint' indent (ParsedSeq t1 t2) =+    text "Seq" <> text "\n"+    <> nest indent <> pPrint' (continue indent) t1 <> text "\n"+    <> nest1 indent <> pPrint' (continue1 indent) t2+pPrint' indent (ParsedChoiceLeft tree) =+    text "Left" <> text "\n"+    <> nest1 indent <> pPrint' (continue1 indent) tree+pPrint' indent (ParsedChoiceRight tree) =+    text "Right" <> text "\n"+    <> nest1 indent <> pPrint' (continue1 indent) tree+pPrint' indent (ParsedStar ts) =+    text "Star" <+> lbrack <> list' <> rbrack+    where+        listnest = if null ts then Text.PrettyPrint.HughesPJ.empty else text "\n"+        listEnd   = if null ts then Text.PrettyPrint.HughesPJ.empty else nest1 indent+        list      = hcat (map (\ x -> nest indent <> pPrint' (continue indent) x <> text "\n") ts)+        list'     = listnest <> list <> listEnd+pPrint' _ ParsedNot = Text.PrettyPrint.HughesPJ.empty+pPrint' indent (ParsedIndent e b) =+    text "Indent" <> text "\n"+    <> nest indent <> pPrint' (continue indent) e <> text "\n"+    <> nest1 indent <> pPrint' (continue1 indent) (ParsedStar b)++{-|+Extracts all terminal symbols from a 'ParsedTree' as a single string.++=== Usage examples:++>>> flatten (ParsedSeq (ParsedT (T "a")) (ParsedT (T "b")))+"ab"++>>> flatten ParsedEpsilon+""++@since 1.0.0+-}+flatten :: ParsedTree -> String+flatten = everything (++) ("" `mkQ` term)+    where+        term (ParsedT (T t)) = t+        term _ = ""++{-|+Check whether a 'ParsedTree' corresponds to a given grammar expression.++The function follows the structure of the expression and compares it with the+parsed tree, resolving non-terminals using the provided grammar.+-}+ofExpression :: Grammar -> Expression -> ParsedTree -> Bool+ofExpression _ Empty ParsedEpsilon = True+ofExpression _ (ExprT t) (ParsedT t') = t == t'+ofExpression g (ExprNT nt) (ParsedNT nt' t) = nt == nt' && case expression g nt of+                                                Just x -> ofExpression g x t+                                                Nothing -> False+ofExpression g (Sequence e1 e2) (ParsedSeq t1 t2) = ofExpression g e1 t1 && ofExpression g e2 t2+ofExpression g (Choice e1 _) (ParsedChoiceLeft t) = ofExpression g e1 t+ofExpression g (Choice _ e2) (ParsedChoiceRight t)  = ofExpression g e2 t+ofExpression g (Star e) (ParsedStar ts) = all (ofExpression g e) ts+ofExpression _ (Not _) ParsedNot = True+ofExpression _ (Flatten _) (ParsedT _) = True +ofExpression g (Indent e1 e2) (ParsedIndent t ts) = ofExpression g e1 t && all (ofExpression g e2) ts+ofExpression _ _ _ = False
+ src/Syntax/Pattern.hs view
@@ -0,0 +1,205 @@+{-|+Module      : Syntax.Pattern+Description : Definitions of patterns and utilities for grammars.+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module defines structures to represent patterns over grammars,+as well as utility functions for manipulating and replacing named patterns.+It also provides instances of the 'Pretty' class for formatted printing.+-}+module Syntax.Pattern+    ( Pattern(..)+    , SyntaxPattern(..)+    , NamedPattern+    , NamedSynPat+    , references+    , replaceSynPats+    ) where++import Syntax.Base (NonTerminal(..), Terminal(..), Pretty(..))+import Text.PrettyPrint.HughesPJ ((<+>), text, parens, Doc, brackets)+import Data.List (nub)+import Data.Bifunctor (Bifunctor(second))+import Data.Generics (everything, mkQ, Typeable, Data, everywhere, mkT)+import Syntax.Peg (Expression)++{-|+Represents a pattern in a grammar.++A 'Pattern' can be:+- 'PatEpsilon': Represents the empty pattern (ε).+- 'PatT': A terminal symbol.+- 'PatNT': A non-terminal symbol associated with another pattern.+- 'PatSeq': A sequence of two patterns.+- 'PatChoice': A choice between two patterns.+- 'PatStar': A repetition of zero or more times of a pattern.+- 'PatNot': A negation of a pattern.+- 'PatVar': A pattern associated with a variable.++@since 1.0.0+-}+data Pattern+    = PatEpsilon+    | PatT Terminal+    | PatNT NonTerminal Pattern+    | PatSeq Pattern Pattern+    | PatChoice Pattern Pattern+    | PatStar Pattern+    | PatStarSeq [Pattern]+    | PatNot Pattern+    | PatVar Expression String+    deriving (Eq, Show, Ord, Typeable, Data)++{-|+Represents a syntactic pattern in a grammar.++A 'SyntaxPattern' can be:+- 'SynEpsilon': Represents the empty pattern (ε).+- 'SynT': A terminal symbol.+- 'SynNT': A non-terminal symbol associated with another syntactic pattern.+- 'SynSeq': A sequence of two syntactic patterns.+- 'SynChoice': A choice between two syntactic patterns.+- 'SynStar': A repetition of zero or more times of a syntactic pattern.+- 'SynNot': A negation of a syntactic pattern.+- 'SynVar': A syntactic pattern associated with a variable.+- 'SynRef': A reference to a named pattern.++@since 1.0.0+-}+data SyntaxPattern+    = SynEpsilon+    | SynT Terminal+    | SynNT NonTerminal SyntaxPattern+    | SynSeq SyntaxPattern SyntaxPattern+    | SynChoice SyntaxPattern SyntaxPattern+    | SynStar SyntaxPattern+    | SynNot SyntaxPattern+    | SynVar Expression String+    | SynRef String+    deriving (Eq, Show, Ord, Typeable, Data)++{-|+A named pattern, which associates a name ('String') with a 'Pattern'.++@since 1.0.0+-}+type NamedPattern = (String, Pattern)++{-|+A named syntactic pattern, which associates a name ('String') with a 'SyntaxPattern'.++@since 1.0.0+-}+type NamedSynPat = (String, SyntaxPattern)++{-|+Instance of the 'Pretty' class for 'Pattern'.++Prints the pattern in a readable format, with operators like @/@ for choice,+@*@ for repetition, and @!@ for negation.++@since 1.0.0+-}+instance Pretty Pattern where+    pPrint :: Pattern -> Doc+    pPrint (PatNT nt p)      = pPrint nt <+> text ":=" <+> parens (pPrint p)+    pPrint (PatT t)          = pPrint t+    pPrint (PatVar s name)   = text ("#" ++ name) <> text ":" <> parens (pPrint s)+    pPrint PatEpsilon        = text "ε"+    pPrint (PatSeq p1 p2)    = pPrint p1 <+> pPrint p2+    pPrint (PatChoice p1 p2) = parens $ pPrint p1 <+> text "/" <+> pPrint p2+    pPrint (PatStar p)       = parens (pPrint p) <> text "*"+    pPrint (PatStarSeq ps)   = (brackets . pPrint) ps+    pPrint (PatNot p)        = text "!" <> parens (pPrint p)++{-|+Instance of the 'Pretty' class for 'SyntaxPattern'.++Prints the syntactic pattern in a readable format, with operators like @/@ for choice,+@*@ for repetition, and @!@ for negation.++@since 1.0.0+-}+instance Pretty SyntaxPattern where+    pPrint :: SyntaxPattern -> Doc+    pPrint (SynNT nt ps)     = pPrint nt <+> text ":=" <+> parens (pPrint ps)+    pPrint (SynT t)          = pPrint t+    pPrint (SynVar s name)   = text ("#" ++ name) <> text ":" <> parens (pPrint s)+    pPrint SynEpsilon        = text "ε"+    pPrint (SynSeq p1 p2)    = pPrint p1 <+> pPrint p2+    pPrint (SynChoice p1 p2) = parens $ pPrint p1 <+> text "/" <+> pPrint p2+    pPrint (SynStar p)       = parens (pPrint p) <> text "*"+    pPrint (SynNot p)        = text "!" <> parens (pPrint p)+    pPrint (SynRef name)     = text $ "@" ++ name++{-|+Instance of the 'Pretty' class for 'NamedPattern'.++Prints the named pattern in the format @pattern \<name\> : \<pattern\>@.++@since 1.0.0+-}+instance Pretty NamedPattern where+    pPrint :: NamedPattern -> Doc+    pPrint (name, pat) = text ("pattern " ++ name ++ " :") <+> pPrint pat <+> text "\n"++{-|+Instance of the 'Pretty' class for 'NamedSynPat'.++Prints the named syntactic pattern in the format @pattern \<name\> : \<pattern\>@.++@since 1.0.0+-}+instance Pretty NamedSynPat where+    pPrint :: NamedSynPat -> Doc+    pPrint (name, syn) = text ("pattern " ++ name ++ " :") <+> pPrint syn <+> text "\n"++-------------------------------------------------------------------------------++{-|+Replaces all references in a 'SyntaxPattern' with their corresponding patterns,+based on a named pattern.++@since 1.0.0+-}+replaceInPat :: NamedSynPat -> SyntaxPattern -> SyntaxPattern+replaceInPat ref = everywhere $ mkT (replace ref)+    where+        replace (n, p) (SynRef n') = if n == n' then p else SynRef n'+        replace _ p                = p++{-|+Returns a list of pattern names referenced in a 'SyntaxPattern'.++=== Usage examples:++>>> references (SynSeq (SynRef "A") (SynRef "B"))+["A","B"]++@since 1.0.0+-}+references :: SyntaxPattern -> [String]+references = nub <$> everything (++) ([] `mkQ` refs)+    where+        refs (SynRef s) = [s]+        refs _ = []++{-|+Replaces all references in a list of patterns ordered by dependency.++@since 1.0.0+-}+replaceSynPats :: [NamedSynPat] -> [NamedSynPat]+replaceSynPats ps = foldr replaceSynPat ps ps++{-|+Replaces all references in a pattern within a list of patterns.++@since 1.0.0+-}+replaceSynPat :: NamedSynPat -> [NamedSynPat] -> [NamedSynPat]+replaceSynPat p = map (second $ replaceInPat p)
+ src/Syntax/Peg.hs view
@@ -0,0 +1,317 @@+{-|+Module      : Syntax.Peg+Description : Definitions for PEGs (Parsing Expression Grammars).+Copyright   : (c) Guilherme Drummond, Rodrigo Ribeiro, 2025+License     : BSD-3-Clause+Maintainer  : rodrigo.ribeiro@ufop.edu.br+Stability   : experimental+Portability : POSIX++This module defines structures and functions to work with PEGs (Parsing Expression Grammars),+including expressions, definitions, and complete grammars. It also provides instances of the 'Pretty'+class for formatted printing.+-}+module Syntax.Peg+    ( Expression(..)+    , Definition+    , Grammar+    , ExpressionZipper+    , ExpressionPath+    , ExpressionCrumb+    , nonTerminals+    , terminals+    , terminals'+    , expression+    , produces+    , goLeft+    , goRight+    , goUp+    , goDown+    , pullFromRight+    ) where++import Syntax.Base (NonTerminal, Terminal, Pretty(..))+import Text.PrettyPrint.HughesPJ (text, Doc, maybeParens, (<+>), (<>), parens)+import Prelude hiding ((<>))+import Data.List (nub)+import Data.Maybe (isJust)+import Data.Generics (Data, Typeable, mkQ, everything)+import Data.Foldable (find)++{-|+Represents an expression in a PEG.++An expression can be:+- 'Empty': Represents the empty expression (ε).+- 'ExprT': A terminal symbol.+- 'ExprNT': A non-terminal symbol.+- 'Sequence': A sequence of two expressions.+- 'Choice': An ordered choice between two expressions.+- 'Star': A repetition of zero or more times of an expression.+- 'Not': A negation of an expression.+- 'Flatten': An expression that must be "flattened".+- 'Indent': An expression that must be "indented" with respect to the first. Because of the way MegaParsec parses indented blocks, the second expressions turns into a e+.++@since 1.0.0+-}+data Expression+    = Empty+    | ExprT Terminal+    | ExprNT NonTerminal+    | Sequence Expression Expression+    | Choice Expression Expression+    | Star Expression+    | Not Expression+    | Flatten Expression+    | Indent Expression Expression+    deriving (Show, Eq, Ord, Typeable, Data)++{-|+Breadcrumbs used when navigating an 'Expression' tree with a zipper.++Each constructor stores the sibling or parent context needed to reconstruct+the tree when moving back up.+-}+data ExpressionCrumb+    = SequenceFirst Expression+    | SequenceSecond Expression+    | ChoiceFirst Expression+    | ChoiceSecond Expression+    | IndentFirst Expression+    | IndentSecond Expression+    | StarCrumb+    | NotCrumb+    | FlattenCrumb++{-|+A zipper path is the stack of breadcrumbs from the current focus back up to+the root.+-}+type ExpressionPath = [ExpressionCrumb]++{-|+A zipper for an 'Expression'. The first component is the currently focused+expression, and the second is the path back to the root.+-}+type ExpressionZipper = (Expression, ExpressionPath)++{-|+Move the focus of an 'ExpressionZipper' up to its parent expression.+-}+goUp :: ExpressionZipper -> Maybe ExpressionZipper+goUp (e1, SequenceFirst e2:z)  = Just (Sequence e1 e2, z)+goUp (e2, SequenceSecond e1:z) = Just (Sequence e1 e2, z)+goUp (e1, IndentFirst e2:z)    = Just (Indent e1 e2, z)+goUp (e2, IndentSecond e1:z)   = Just (Indent e1 e2, z)+goUp (e1, ChoiceFirst e2:z)    = Just (Choice e1 e2, z)+goUp (e2, ChoiceSecond e1:z)   = Just (Choice e1 e2, z)+goUp (e1, StarCrumb:z)         = Just (Star e1, z)+goUp (e1, NotCrumb:z)          = Just (Not e1, z)+goUp (e1, FlattenCrumb:z)      = Just (Flatten e1, z)+goUp (_, [])                   = Nothing++{-|+Move the focus to the right child of the current expression node, if any.+-}+goRight :: ExpressionZipper -> Maybe ExpressionZipper+goRight (Sequence e1 e2, z) = Just (e2, SequenceSecond e1:z)+goRight (Choice e1 e2, z)   = Just (e2, ChoiceSecond e1:z)+goRight (Indent e1 e2, z)   = Just (e2, IndentSecond e1:z)+goRight _                   = Nothing++{-|+Move the focus to the left child of the current expression node, if any.+-}+goLeft :: ExpressionZipper -> Maybe ExpressionZipper+goLeft (Sequence e1 e2, z) = Just (e1, SequenceFirst e2:z)+goLeft (Choice e1 e2, z)   = Just (e1, ChoiceFirst e2:z)+goLeft (Indent e1 e2, z)   = Just (e1, IndentFirst e2:z)+goLeft _                   = Nothing++{-|+Move the focus down into a nested single-child expression.+-}+goDown :: ExpressionZipper -> Maybe ExpressionZipper+goDown (Star e, z)    = Just (e, StarCrumb:z)+goDown (Not e, z)     = Just (e, NotCrumb:z)+goDown (Flatten e, z) = Just (e, FlattenCrumb:z)+goDown _              = Nothing++{-|+Pull the leftmost element from the right operand of a sequence and append it+onto the left operand.+-}+pullFromRight :: Expression -> Maybe Expression+pullFromRight (Sequence e1 e2) = maybe (Just e1') (Just . Sequence e1') eT+    where+        (eH, eT) = getHead e2+        e1' = addAtEnd e1 eH+pullFromRight _ = Nothing++addAtEnd :: Expression -> Expression -> Expression+addAtEnd (Sequence e1 e2) e3 = Sequence e1 $ addAtEnd e2 e3+addAtEnd e e3 = Sequence e e3++getHead :: Expression -> (Expression, Maybe Expression)+getHead (Sequence e1 e2) = (e1, Just e2)+getHead e                = (e, Nothing)++{-|+Represents a definition in a PEG.++A definition associates a 'NonTerminal' with an 'Expression'.++@since 1.0.0+-}+type Definition = (NonTerminal, Expression)++{-|+Represents a PEG.++A grammar consists of a list of 'Definition' and an initial 'NonTerminal'.++@since 1.0.0+-}+type Grammar = ([Definition], NonTerminal)++-- Auxiliary functions to determine when to use parentheses+parensSeq :: Expression -> Bool+parensSeq (Choice _ _) = True+parensSeq _ = False++parensNot :: Expression -> Bool+parensNot (Choice _ _) = True+parensNot (Sequence _ _) = True+parensNot _ = False++parensStar :: Expression -> Bool+parensStar (Choice _ _) = True+parensStar (Sequence _ _) = True+parensStar (Not _) = True+parensStar _ = False++{-|+Instance of the 'Pretty' class for 'Expression'.++Prints the expression in a readable format, with operators like @/@ for choice,+@*@ for repetition, and @!@ for negation.++@since 1.0.0+-}+instance Pretty Expression where+    pPrint :: Expression -> Doc+    pPrint Empty            = text "ε"+    pPrint (ExprT t)        = pPrint t+    pPrint (ExprNT nt)      = pPrint nt+    pPrint (Sequence e1 e2) = maybeParens (parensSeq e1) (pPrint e1)+                                <+> maybeParens (parensSeq e2) (pPrint e2)+    pPrint (Choice e1 e2)   = pPrint e1 <+> text "/" <+> pPrint e2+    pPrint (Star e)         = maybeParens (parensStar e) (pPrint e) <> text "*"+    pPrint (Not e)          = text "!" <> maybeParens (parensNot e) (pPrint e)+    pPrint (Flatten e)      = text "^" <> parens (pPrint e)+    pPrint (Indent e b)      = parens (pPrint e) <+> text ">" <+> parens (pPrint b)++{-|+Instance of the 'Pretty' class for 'Definition'.++Prints a definition in the format `<non-terminal> <- <expression>`.++@since 1.0.0+-}+instance Pretty Definition where+    pPrint :: Definition -> Doc+    pPrint (nt, e) = pPrint nt <+> text "<-" <+> pPrint e <> text "\n"++{-|+Instance of the 'Pretty' class for 'Grammar'.++Prints all definitions of a grammar.++@since 1.0.0+-}+instance Pretty Grammar where+    pPrint :: Grammar -> Doc+    pPrint (ds, _) = pPrint ds++-------------------------------------------------------------------------------++{-|+Returns the list of non-terminals of a grammar.++=== Usage examples:++>>> nonTerminals ([(NT "S", Empty), (NT "A", ExprT (T "a"))], NT "S")+[NT "S",NT "A"]++@since 1.0.0+-}+nonTerminals :: Grammar -> [NonTerminal]+nonTerminals (ds, _) = map fst ds++{-|+Returns the list of terminals present in an expression.++=== Usage examples:++>>> terminals' (Sequence (ExprT (T "a")) (ExprT (T "b")))+[T "a",T "b"]++@since 1.0.0+-}+terminals' :: Expression -> [Terminal]+terminals' = nub <$> everything (++) ([] `mkQ` terminal)+    where+        terminal (ExprT t) = [t]+        terminal _ = []++{-|+Returns the list of terminals present in a grammar.++=== Usage examples:++>>> terminals ([(NT "S", Sequence (ExprT (T "a")) (ExprT (T "b")))], NT "S")+[T "a",T "b"]++@since 1.0.0+-}+terminals :: Grammar -> [Terminal]+terminals (ds, _) = nub $ concatMap (terminals' . snd) ds++{-|+Returns the expression associated with a non-terminal in a grammar, if it exists.++=== Usage examples:++>>> expression ([(NT "S", Sequence (ExprT (T "a")) (ExprT (T "b")))], NT "S") (NT "S")+Just (Sequence (ExprT (T "a")) (ExprT (T "b")))++>>> expression ([(NT "S", Empty)], NT "S") (NT "A")+Nothing++@since 1.0.0+-}+expression :: Grammar -> NonTerminal -> Maybe Expression+expression (rs, _) nt = snd <$> find (\ x -> fst x == nt) rs++{-|+Checks if a non-terminal produces a terminal in a grammar.++=== Usage examples:++>>> produces ([(NT "S", Sequence (ExprT (T "a")) (ExprT (T "b")))], NT "S") (NT "S") (T "a")+True++>>> produces ([(NT "S", Sequence (ExprT (T "a")) (ExprT (T "b")))], NT "S") (NT "S") (T "b")+True++>>> produces ([(NT "S", Sequence (ExprT (T "a")) (ExprT (T "b")))], NT "S") (NT "S") (T "c")+False++@since 1.0.0+-}+produces :: Grammar -> NonTerminal -> Terminal -> Bool+produces g nt t = isJust produce+    where+        expr = expression g nt+        terms = terminals' <$> expr+        produce = find (== t) =<< terms
+ test/Main.hs view
@@ -0,0 +1,154 @@+{-# LANGUAGE QuasiQuotes #-}++module Main (main) where++import Syntax.Base+import Syntax.Peg+import Syntax.Pattern+import Syntax.ParsedTree+import Parser.Peg+import Match.Capture+import Parser.Pattern (patterns)+import qualified Quote.Peg as QPeg+import qualified Quote.Pattern as QPattern++import Text.Megaparsec (parse, Parsec)++import Test.Tasty+import Test.Tasty.HUnit+++main :: IO ()+main = defaultMain $+        testGroup "Main tests" [testsParserPeg, testsMatch, testsQuote]++parseT :: Parsec e s a -> s -> a+parseT p f = case parse p "" f of+                    Right a -> a+                    Left _ -> error ""++testsParserPeg :: TestTree+testsParserPeg = testGroup "Tests Parser Peg"+    [+        testCase "peg simples, uma única regra" $+            parseT grammar "A <- \"a\"+"+            @?=+            ([(NT "A",Sequence (ExprT (T "a")) (Star (ExprT (T "a"))))],NT "A")++    ,   testCase "peg para expressões, com NT para número" $+            parseT grammar "E <- T (\"\\\"\" T)*\nT <- F (\"*\" F)*\nF <- \"num\" / \"(\" E \")\""+            @?=+            ([(NT "E",Sequence (ExprNT (NT "T")) (Star (Sequence (ExprT (T "\"")) (ExprNT (NT "T"))))),(NT "T",Sequence (ExprNT (NT "F")) (Star (Sequence (ExprT (T "*")) (ExprNT (NT "F"))))),(NT "F",Choice (ExprT (T "num")) (Sequence (ExprT (T "(")) (Sequence (ExprNT (NT "E")) (ExprT (T ")")))))],NT "E")++    ,   testCase "peg para expressões, com range para número" $+            parseT grammar "E <- T (\"+\" T)*\nT <- F (\"*\" F)*\nF <- [0-9]+ / \"(\" E \")\""+            @?=+            ([+                (NT "E",Sequence (ExprNT (NT "T")) (Star (Sequence (ExprT (T "+")) (ExprNT (NT "T"))))),+                (NT "T",Sequence (ExprNT (NT "F")) (Star (Sequence (ExprT (T "*")) (ExprNT (NT "F"))))),+                (NT "F",+                    Choice+                        (Sequence+                            (Choice (ExprT (T "0")) (Choice (ExprT (T "1")) (Choice (ExprT (T "2")) (Choice (ExprT (T "3")) (Choice (ExprT (T "4")) (Choice (ExprT (T "5")) (Choice (ExprT (T "6")) (Choice (ExprT (T "7")) (Choice (ExprT (T "8")) (ExprT (T "9")))))))))))+                            (Star (Choice (ExprT (T "0")) (Choice (ExprT (T "1")) (Choice (ExprT (T "2")) (Choice (ExprT (T "3")) (Choice (ExprT (T "4")) (Choice (ExprT (T "5")) (Choice (ExprT (T "6")) (Choice (ExprT (T "7")) (Choice (ExprT (T "8")) (ExprT (T "9")))))))))))))+                        (Sequence+                            (ExprT (T "("))+                            (Sequence (ExprNT (NT "E")) (ExprT (T ")")))))],NT "E")+    ]++-- | Grammar used by the matching tests.+--+-- The trees in 'testsMatch' are built by hand rather than produced by the+-- parser, so this grammar only needs to justify the subtree bound to a+-- variable: @F@ derives the factor @2 * 3@. 'match' consults the grammar+-- only in the 'PatVar' case, via 'ofExpression'.+matchGrammar :: Grammar+matchGrammar =+    ( [ (NT "F", Sequence (ExprT (T "2")) (Sequence (ExprT (T "*")) (ExprT (T "3")))) ]+    , NT "F"+    )++testsMatch :: TestTree+testsMatch = testGroup "Tests Match"+    [+        testCase "Match Epsilon" $+            match matchGrammar PatEpsilon ParsedEpsilon @? ""++        -- 'match' searches every subtree, so a nested epsilon is a match.+        -- This test used to assert the opposite, back when 'match' was+        -- anchored at the root; see the examples on 'match'.+    ,   testCase "Match Nested Epsilon" $+            match matchGrammar+                PatEpsilon+                (ParsedSeq ParsedEpsilon (ParsedT (T "teste"))) @? ""+    ,   testCase "Match expression tree" $+            match matchGrammar+                (PatSeq    (PatT    (T "1")) (PatSeq    (PatSeq    (PatT    (T "+")) (PatVar (ExprNT (NT "F")) "Teste"))                                                                  (PatSeq    (PatT    (T "+")) (PatT    (T "4")))))+                (ParsedSeq (ParsedT (T "1")) (ParsedSeq (ParsedSeq (ParsedT (T "+")) (ParsedNT (NT "F") (ParsedSeq (ParsedT (T "2")) (ParsedSeq (ParsedT (T "*")) (ParsedT (T "3")))))) (ParsedSeq (ParsedT (T "+")) (ParsedT (T "4")))))+            @? ""+    ,   testCase "Match with itself" $+            match matchGrammar+                (PatSeq    (PatT    (T "1")) (PatSeq    (PatSeq    (PatT    (T "+")) (PatNT    (NT "F") (PatSeq    (PatT    (T "2")) (PatSeq    (PatT    (T "*")) (PatT    (T "3")))))) (PatSeq    (PatT    (T "+")) (PatT    (T "4")))))+                (ParsedSeq (ParsedT (T "1")) (ParsedSeq (ParsedSeq (ParsedT (T "+")) (ParsedNT (NT "F") (ParsedSeq (ParsedT (T "2")) (ParsedSeq (ParsedT (T "*")) (ParsedT (T "3")))))) (ParsedSeq (ParsedT (T "+")) (ParsedT (T "4")))))+            @? ""+    ]++-- The values below used to be exported by Pipeline.MatchPipeline as sample+-- data. They are the only place where the quasi-quoters are exercised, so they+-- live here instead, paired with the equivalent source text: each test asserts+-- that the quasi-quoter and the runtime parser agree on the same input.++expressionSource :: String+expressionSource = unlines+    [ "E <- T (\"+\" T)*"+    , "T <- F (\"*\" F)*"+    , "F <- n / \"(\" E \")\""+    , "^n <- [0-9]+"+    ]++quotedExpressionGrammar :: Grammar+quotedExpressionGrammar = [QPeg.grammar|+E <- T ("+" T)*+T <- F ("*" F)*+F <- n / "(" E ")"+^n <- [0-9]++|]++wikiSource :: String+wikiSource = unlines+    [ "S <- \"x\" S \"x\" / \"x\"" ]++quotedWikiGrammar :: Grammar+quotedWikiGrammar = [QPeg.grammar|+S <- "x" S "x" / "x"+|]++callGraphSource :: String+callGraphSource = unlines+    [ "pattern call : function_call := #name:identifier @space \"(\" @space #v:(expr_list?) \")\" ε"+    , ""+    , "pattern definition : function_def := (\"def\" @space #name:identifier \"(\" @space #p:(id_list?) \")\" @space \":\") #block:(statement*)"+    , ""+    , "pattern space : space := \" \"*"+    ]++quotedCallGraphPatterns :: [NamedSynPat]+quotedCallGraphPatterns = [QPattern.patterns|+pattern call : function_call := #name:identifier @space "(" @space #v:(expr_list?) ")" ε++pattern definition : function_def := ("def" @space #name:identifier "(" @space #p:(id_list?) ")" @space ":") #block:(statement*)++pattern space : space := " "*+|]++testsQuote :: TestTree+testsQuote = testGroup "Tests QuasiQuoters"+    [ testCase "peg quoter agrees with the parser (expressions)" $+        quotedExpressionGrammar @?= parseT grammar expressionSource++    , testCase "peg quoter agrees with the parser (wiki)" $+        quotedWikiGrammar @?= parseT grammar wikiSource++    , testCase "pattern quoter agrees with the parser (call graph)" $+        quotedCallGraphPatterns @?= parseT patterns callGraphSource+    ]