Graph Controlled string Rewriting SIMulator. It simulates the derivation of regulated rewriting systems, in particular insertion-deletion systems with graph control: components (states) hold sets of strings, rules rewrite a string in one component and send the result to another one, and the simulator advances all components synchronously, step by step.
Main features
- Simulation of many variants of regulated rewriting and of insertion-deletion systems. Graph-controlled, matrix, programmed, time-varying, random-context and ordered grammars, Marcus contextual grammars, evolutionary processors, networks of processors and insertion-deletion systems are all written with the same few rule forms (see docs/grammar-types.md).
- Catching wrong derivations and the stage where they happen. Marks flag the strings you care about, for example every terminal string that is not in the language you intended, at the step and component where they appear. The traceback then prints the full derivation, rule by rule from the axiom, of any marked string or of any string you name (see docs/marks-and-derivations.md).
gcrsim is a complete rewrite, in Python, of the earlier Perl simulator of the same name, and its evolution: the model language is
new, the semantics are written down and checked against an independent reference interpreter, and it adds marks, derivation
sequences and resource limits. The Perl version is kept at github.com/sverlan/gcrsim-perl;
models written for it are migrated with gcrsim-convert, see docs/migration.md.
- a small package, standard library only, Python 3.11+;
- rule forms
ins,del,sub, plain rules,send()and regular-expression rules, permitting / forbidding words, multi-character symbols and symbol classes, UTF-8; - for the part of the language without regular expressions, a written specification, an independent reference interpreter,
differential tests and
--cross-check(see docs/checking.md); - for long experiments: declarative component conditions, resource limits, progress reporting,
csvandjsonloutput.
Python 3.11 or later; there are no other dependencies. The package installs three programs: gcrsim (the simulator),
gcrsim-convert (migration of Perl-era models) and gcrsim-retention (look into a retention file).
pip install gcrsim # into the current environment
pipx install gcrsim # as an isolated command-line tool
uv tool install gcrsim # the same, with uv
uvx gcrsim model.txt 10 # run the simulator once, without installing
gcrsim model.txt [steps]
python -m gcrsim model.txt [steps] # the same, from a checkout of the repository without installing
With steps (on the command line or in the configuration) the simulator runs that many steps and exits; with -i it waits for a command after each step (Enter for the next step, q to quit, more commands in docs/interactive.md).
A matrix grammar for aⁿbⁿcⁿ, a language that needs several components. A matrix is a chain of rules applied one after the other, so
each rule gets its own component; the first rules of all the matrices are in component 1, and the last rule of m2 returns to it:
# matrix m1 = (S -> ABC), m2 = (A -> aA, B -> bB, C -> cC), m3 = (A -> a, B -> b, C -> c)
[axioms]
1 = ["S"]
[rules.1]
# m1 (one rule), and the first rules of m2 and m3
S -> A B C, 1
A -> a A, 2
A -> a, 4
# m2: B -> bB in component 2, C -> cC in component 3, then back to component 1
[rules.2]
B -> b B, 3
[rules.3]
C -> c C, 1
# m3: B -> b in component 4, C -> c in component 5, and the word is in component 6
[rules.4]
B -> b, 5
[rules.5]
C -> c, 6
Save the model as matrix.txt and run gcrsim matrix.txt 12; it prints, at every step, the strings of each component; abc, aabbcc, ... appear
in component 6. The same model is in the repository as examples/cookbook/08_matrix_direct.txt.
| Document | Content |
|---|---|
| docs/model-syntax.md | the model language: sections, rule forms, conditions, symbols and classes |
| docs/semantics.md | what a step does, in plain words (exact version: SPEC.md) |
| docs/grammars.md | cookbook: one example for each kind of grammar, in classical notation and as a model |
| docs/grammar-types.md | the types of grammars and systems that are supported, and how each is written |
| docs/configuration.md | settings, configuration files, the filters of the components |
| docs/python.md | the Python interface: the filter file, callbacks, marks from Python, the package API |
| docs/marks-and-derivations.md | marking strings and getting the derivation sequence of a string |
| docs/cli.md | command line options, output, limits, exit statuses |
| docs/interactive.md | the step-by-step mode (-i): looking at the strings, searching, tracing, marking |
| docs/checking.md | how the results are checked, --cross-check |
| docs/migration.md | moving from the Perl simulator, gcrsim-convert |
| examples/ | the cookbook models and the research models |
A summary; the full table, with one sentence on how each grammar is written, is in docs/grammar-types.md, and docs/grammars.md gives an example of each in the classical notation and as a model.
| Grammars and systems | How it is written |
|---|---|
| unrestricted, monotone, context-free and pure grammars; internal Marcus contextual grammars; insertion-deletion systems; evolutionary processors; graph-controlled grammars; random-context and semi-conditional grammars; grammars with derivations of bounded index | directly, with the rule forms |
| external Marcus contextual grammars; networks of evolutionary processors; matrix grammars and matrix insertion-deletion systems; appearance checking (failure fields) in graph-controlled and matrix grammars; programmed grammars; time-varying grammars; regular control; ordered grammars; counter and register machines | with a small encoding (components and send()) |
| scattered-context grammars | in part, with re(...): exact when each symbol occurs once in the word |
| valence grammars | with a Python filter |
| parallel rewriting (L systems, ET0L), splicing and communicating grammar systems, leftmost and rightmost derivations, control by a pushdown automaton or a Petri net | not supported |
The development is AI-assisted, and the work is shared between the human author and the AI. The plan is discussed and validated by the human author. The AI implements the code and writes the tests; the human rereads the code. The examples are written by the AI and the human together, and the results are verified by the human. Independent AI reviews of the plan and of the code were used as an additional check; they do not replace the human steps. What the automatic checks do and do not guarantee is described in docs/checking.md.
uv run pytest # fast tests, plus the Perl comparisons when perl is on PATH
The Perl comparison tests use the original models and configurations in tests/fixtures/perl.