Tree @master (Download .tar.gz)
relwrite
relwrite
relates strings to strings via a grammar in the Chomsky hierarchy.
What does "relate" mean in this context?
- Given a grammar and a string of terminals, it can parse that string, and report if is in the language of the grammar or not.
- Given a grammar and a nonterminal, it can generate a string of terminals from them.
The relational engine in relwrite
is a very general one, based on string rewriting.
There are therefore no restrictions on the input grammar -- it may be regular,
context-free, context-sensitive, or unrestricted. If the grammar is
ambiguous, then all possible parses (or generations) can be returned.
It should be understood that relwrite
trades off performance and small
memory footprint in favour of generality, so in general usage, it works
best on small inputs.
There are, however, features intended to improve performance in the case of very long derivations. Search strategies can be used to enable a beam search algorithm which aggressively focuses on derivations with a desired propery, e.g. a particular minimum length. This does sacrifice completeness however -- only a handful of all the possible results will be returned.
The grammar must be provided in the form of a JSON file. There are example
grammar files in the eg/
directory of this repo.
Example usage
Generate a string from a starting non-terminal in a grammar:
./bin/relwrite complete eg/recursive-grammar.json \
--start "<Sentence>" --max-derivations=1
Parse a string w.r.t. a grammar:
./bin/relwrite complete eg/recursive-grammar.json \
--parse --start "a penguin sees a penguin then sees a dog" \
--goal "<Sentence>"
Use the complete
strategy to generate all possible strings from a
starting non-terminal in a grammar. NOTE that this can use unreasonable
amounts of resources, with possibly adverse effects on your system.
./bin/relwrite complete eg/sample-grammar.json --start "<Sentence>"
Use the expand
strategy to generate a really long string from a non-terminal
in a grammar, without running out of memory and only taking a few hours of
processor time:
./bin/relwrite expand eg/recursive-grammar.json \
--start "<Sentence>" --max-derivations=1 --expand-until=3000 \
--output-file=out.json
Use the contract
strategy to parse a really long string from a non-terminal
in a grammar, without running out of memory and only taking a few hours of
processor time. This assumes the string to be parsed is in JSON format in
the file out.json
-- the generation example above would produce this.
./bin/relwrite contract eg/recursive-grammar.json \
--parse --start-set-file=out.json
Detailed usage
Run relwrite --help
for a description of all the possible command-line options. Note that
these are somewhat provisional and subject to change.
Notes
relwrite
uses the term "derivation" as a generic term meaning "a parse or a generated utterance".
It also uses the term "utterance" to mean "any string of terminals and non-terminals".
TODO
Analyze the input grammar and classify it in the Chomsky hierarchy.
If the input grammar is context-free, use a chart parsing algorithm to efficiently parse it, or an incremental algorithm to generate from it.
Allow strategies to be defined richly, perhaps in JSON files, and let them configure parameters like beam width, max rewrites per utterance, etc.
For max rewrites per utterance, allow them to be taken from random points (or at least from a randomly-chosen start point) in the utterace.
Support random search. For contract
strategy, it should be sufficient to
identify the subset of the next states that is sufficiently contracting
(this is not a "beam width" so much as a "pre-filter"),
then select a single instance from it at random (beam width of 1).
Commit History
@master
git clone https://git.catseye.tc/relwrite/
- Turn `complete` into a strategy that must be explicitly selected. Chris Pressey 1 year, 9 months ago
- Implement `--goal` option to assert what final utterance is reached. Chris Pressey 1 year, 9 months ago
- If `--output-file` not given, dump result to stdout. Chris Pressey 1 year, 9 months ago
- Add `--output-file` option for specifying the output filename. Chris Pressey 1 year, 9 months ago
- Some aspirational TODO notes. Chris Pressey 1 year, 10 months ago
- Add --save-snapshots-every command-line option. Chris Pressey 1 year, 10 months ago
- Introduce new strategy. Name strategies consistently. Chris Pressey 1 year, 10 months ago
- Add an example of a noncontracting (context-sensitive) grammar. Chris Pressey 1 year, 10 months ago
- Add MIT license. Chris Pressey 1 year, 10 months ago
- Initial import of files for relwrite. Chris Pressey 1 year, 10 months ago