Quick Start
Algorithms Library Toolkit is a set of C++ libraries that allows you to manipulate the data structures.
It comes with an builtin aql2 executable which is an aql (algorithm query language) shell.
aql2
Aql is not vim, it can be exited…
quit
The syntax of aql is similar to bash. The outputs of algorithms can be passed as inputs to other algorithms using pipes. See full specification of the query language for complete reference.
Aql is implemented using the readline library and aql implements the features like multiline strings, shell history using arrows and CTRL+R. You can also benefit from an autocompletion using TAB key.
Basics
The aql shell allows you to input (or load from a file) an automaton, grammar, regexp, string or even a tree. You can parse the representation and use it as an input for an operation.
For example, let us input a regular expression a + (a b)*, parse it, convert to a finite automaton and display the automaton.
First of all we should refer to the text inputs syntax page. After we learn the syntax of regular expressions, we can execute the first command which loads the string into aql.
> execute "a + (a b)*"
We can see that result of this operation is processed but discarted.
> print "a + (a b)*"
Now the string is printed back.
We have to parse it as a regular expression.
In order to do that we pass the output to the string::Parse algorithm.
The first argument of that algorithms is an data structure we want to parse and the second is the input.
If dash (-) is specified as an input the result of previous command is used.
> print "a + (a b)*" | string::Parse @regexp::RegExp -
(FormalRegExp (FormalRegExpAlternation (FormalRegExpSymbol a) (RegExpFormalRegExpIteration (FormalRegExpConcatenation (FormalRegExpSymbol a) (FormalRegExpSymbol b)))))
Now we can see that we parsed the regular expression.
We can also pass the string directly into the Parse algorithm.
The result is the same and we save a small amount of electricity.
> print string::Parse @regexp::RegExp "a + (a b)*"
(FormalRegExp (FormalRegExpAlternation (FormalRegExpSymbol a) (RegExpFormalRegExpIteration (FormalRegExpConcatenation (FormalRegExpSymbol a) (FormalRegExpSymbol b)))))
The next step is logically a conversion to an automaton. The algorithm we want to use is regexp::convert::ToAutomaton.
> print string::Parse @regexp::RegExp "a + (a b)*" | regexp::convert::ToAutomaton -
(NFA states = {((InitialStateLabel), 0), (a, 2), (a, 3), (b, 1)}inputAlphabet = {a, b}initialState = ((InitialStateLabel), 0)finalStates = {((InitialStateLabel), 0), (a, 3), (b, 1)}transitions = {((((InitialStateLabel), 0), a), (a, 2)), ((((InitialStateLabel), 0), a), (a, 3)), (((a, 2), b), (b, 1)), (((b, 1), a), (a, 2))})
This is actually human readable but we can do better. Let the aql provide us with the same notation as for finite automaton input syntax.
> print string::Parse @regexp::RegExp "a + (a b)*" | regexp::convert::ToAutomaton - | string::Compose -
NFA a b
><(initial, 0) (a, 2)|(a, 3) -
(a, 2) - (b, 1)
<(a, 3) - -
<(b, 1) (a, 2) -
That is actually better. How about a visualisation of such automaton?
In case the dot executable is found on your system, you can use the following command.
> execute string::Parse @regexp::RegExp "a + (a b)*" | regexp::convert::ToAutomaton - | convert::DotConverter - | Dot -
The print command is not used because the result of Dot statement is void and there is nothing to print at all.
Comments
Aql supports C++-like comments: single-line comment // and (possibly multiline) /* ... */.
Listing the available algorithms
We can list all the algorithms and list of algorithms in the regexp namespace, respectively, using the following commands.
> introspect algorithms
> introspect algorithms regexp::
Each of the algorithms has the documentation and a list of overloads available.
Let us print all the variants of the Determinize algorithm.
> introspect overloads automaton::determinize::Determinize
Loading from files
If you want to load the text representation from the file, use the cli::builtin::ReadFile command.
> print cli::builtin::ReadFile "regexp" | string::Parse @regexp::RegExp -
a + (a b)*
Saving and using intermediate results
You can redirect the output of and algorithm into a variable and use it later.
Just use the > notation like in shell.
> execute string::Parse @regexp::RegExp "a + (a b)*" > $regexp1
> print $regexp1
(FormalRegExp (FormalRegExpAlternation (FormalRegExpSymbol a) (RegExpFormalRegExpIteration (FormalRegExpConcatenation (FormalRegExpSymbol a) (FormalRegExpSymbol b)))))
> print ToAutomatonThompson $regexp1 | string::Compose -
ENFA a b #E
>1 - - 3|5
<2 - - -
3 4 - -
4 - - 2
5 - - 6|7
6 - - 2
7 8 - -
8 - - 9
9 - 10 -
10 - - 6|7
Printing though print command can be used even with variable redirection.
Named pipes
Basic examples
To specify finite automaton, its string representation should be used with string parser. The automaton can later be converted to dot and displayed.
print string::Parse @Automaton "NFA a b
>1 1|2 1
2 - 3
3 4 -
4 - 5
5 - 6
<6 - -" | convert::DotConverter - | Dot -
Note, the automata string representation is line oriented.
Commands of the language accept parameters, dash - represents result of the previous command.
To make the automaton deterministic call Determinize command
print string::Parse @Automaton "NFA a b
>1 1|2 1
2 - 3
3 4 -
4 - 5
5 - 6
<6 - -" | Determinize - | convert::DotConverter - | Dot -
Other operations available with automata can be listed by
introspect algorithms automaton::
Overloads of any algorithm (like an algorithm to make an automaton total) can be listed by
introspect overloads automaton::simplify::Total