Grammar to parser

1.6.1

The project implements the set of template classes usable for parsing the input (from heap) or from istream. The template class grammar_to_parser::basic_regexp_parser or its specialization for 'char' type , can be used to parse input upon regular expression pattern (simply copy all headers from src directory into your include directory and then include regexp_parser.h):

regexp_parser rxp( "(wee|week)(knights|night)" );

Then use it in following manner:

string input = "weeknights";
rxp.parse( input.c_str, input.length() );
if( rxp.is_parsed() )
{
        cout << "input recognized by (wee|week)(knights|night)" << endl;
}
else
{
        cout << "input not recognized by (wee|week)(knights|night)" << endl;
}

If regexp pattern comes also from user input, it is possible to check the pattern:

if( !rxp.is_pattern_valid() )
{
        cerr << "invalid pattern" << endl;
}

For regexp_parser test results see bottom of this page.
See also src/samples/regexp_parser/regexp_test.cpp, function test_regexp_parser().

Other most usable classes are:

grammar_to_parser::basic_terminal
grammar_to_parser::basic_non_terminal
grammar_to_parser::basic_choice

grammar_to_parser::basic_value_parser
grammar_to_parser::basic_pattern_parser
grammar_to_parser::basic_ascii_range_terminal
grammar_to_parser::basic_regexp_parser

grammar_to_parser::basic_set
grammar_to_parser::basic_subset
grammar_to_parser::basic_list_parser

grammar_to_parser::basic_simple_non_terminal
grammar_to_parser::basic_simple_choice

With use of the classes it is possible to declare parser class (or classes) upon grammar definition. Such parser class can be used for parsing strings of language defined by grammar.

For example, a grammar defined like:

N => 1N | 0N | 1 | 0

defines grammar for generating/accepting binary numbers. In this notation there are non_terminals, which will be defined by template class grammar_to_parser::non_terminal, then there are terminals=grammar_to_parser::terminal, and the choice of rules, defined by grammar_to_parser::choice class. For example, in implementation of previous grammar:

'N' becomes a class c_N,
'1N' becomes a class c_1N,
'0N' becomes a class c_0N

class c_N
{
        class c_1N
        {
                grammar_to_parser::terminal<'1'>        m_1;
                grammar_to_parser::choice<c_N>          m_N;
        };
        class c_0N
        {
                grammar_to_parser::terminal<'0'>        m_0;
                grammar_to_parser::choice<c_N>          m_N;
        };
        grammar_to_parser::non_terminal<c_1N>   m_1N;
        grammar_to_parser::non_terminal<c_0N>   m_0N;
        grammar_to_parser::terminal<'1'>                m_1;
        grammar_to_parser::terminal<'0'>                m_0;
};

For use of members as sub-formula parsers, or nested parser (for example c_1N conains two parser classes - terminal and choice), classes compound from such members must implement a method push_parsers( grammar_to_parser::parsers &l ), which defines of what sub-parsers consists the class. As previous code is not complete because of this, once more declaration of previous class.

class c_N
{
        class c_1N
        {
                grammar_to_parser::terminal<'1'>        m_1;
                grammar_to_parser::choice<c_N>          m_N;
        public:
                void push_parsers( grammar_to_parser::parsers &l )
                {
                        l.push_back(&m_1);
                        l.push_back(&m_N);
                }
        };
        class c_0N
        {
                grammar_to_parser::terminal<'0'>        m_0;
                grammar_to_parser::choice<c_N>          m_N;
        public:
                void push_parsers( grammar_to_parser::parsers &l )
                {
                        l.push_back(&m_0);
                        l.push_back(&m_N);
                }
        };
        grammar_to_parser::non_terminal<c_1N>   m_1N;
        grammar_to_parser::non_terminal<c_0N>   m_0N;
        grammar_to_parser::terminal<'1'>                m_1;
        grammar_to_parser::terminal<'0'>                m_0;
public:
        void push_parsers( grammar_to_parser::parsers &l )
        {
                l.push_back(&m_1N);
                l.push_back(&m_0N);
                l.push_back(&m_1);
                l.push_back(&m_0);
        }
};

The previous declaration is already usable for parsing of any binary number, i.e. recognition of valid binary number. Anyway it is not all. As during parsing the real objects are created dynamically (for example m_1N is also auto_ptr<c_1N>, as indirectly non_terminal inherits from auto_ptr), these can be used in class methods, for example 'evaluate', which converts binary number to decimal. The following code implements the parser usable for converting binary to decimal numbers. Note, that still it is the same class, just extended by new methods.

// src/samples/binary_converter/binary_converter.h
class c_N
{
        class c_1N
        {
                grammar_to_parser::terminal<'1'>        m_1;
                grammar_to_parser::choice<c_N>          m_N;
        public:
                void push_parsers( grammar_to_parser::parsers &l )
                {
                        l.push_back(&m_1);
                        l.push_back(&m_N);
                }
                unsigned long evaluate( unsigned long value, unsigned long &exp )
                {
                        value = m_N->evaluate( value, exp );
                        exp = exp * 2;
                        value += exp * 1;
                        return value;
                }
                
        };
        class c_0N
        {
                grammar_to_parser::terminal<'0'>        m_0;
                grammar_to_parser::choice<c_N>          m_N;
        public:
                void push_parsers( grammar_to_parser::parsers &l )
                {
                        l.push_back(&m_0);
                        l.push_back(&m_N);
                }
                unsigned long evaluate( unsigned long value, unsigned long &exp )
                {
                        value = m_N->evaluate( value, exp );
                        exp = exp * 2;
                        value += exp * 0;
                        return value;
                }
        };
        grammar_to_parser::non_terminal<c_1N>   m_1N;
        grammar_to_parser::non_terminal<c_0N>   m_0N;
        grammar_to_parser::terminal<'1'>                m_1;
        grammar_to_parser::terminal<'0'>                m_0;
public:
        void push_parsers( grammar_to_parser::parsers &l )
        {
                l.push_back(&m_1N);
                l.push_back(&m_0N);
                l.push_back(&m_1);
                l.push_back(&m_0);
        }
        unsigned long evaluate( unsigned long value, unsigned long &exp )
        {
                if( m_1N.is_parsed() ) return m_1N->evaluate( value, exp );
                if( m_0N.is_parsed() ) return m_0N->evaluate( value, exp );
                if( m_1.is_parsed() ) return 1;
                if( m_0.is_parsed() ) return 0;
                return 0;
        }
};

Finally the main body:

// src/samples/binary_converter/binary_converter.cpp
#include <iostream>

#include "grammar_to_parser.h"
#include "parser_strategy.h"
#include "binary_converter.h"

using namespace grammar_to_parser;

int main(int argc, char* argv[])
{
        choice<c_N>             the_parser;
        unsigned long   exp = 1;
        
        the_parser.parse("011001", 6 );
        
        if( the_parser.is_parsed() )
                std::cout << the_parser->evaluate(0, exp ) << std::endl;
        else
                std::cout << "invalid binary number" << std::endl;
}

The code can be found on scr/samples/binary_converter directory

Of course, it is posible to write more simple code doing the same. But maybe complexity of his code will arise, when defining the binary calculator, where use of grammar_to_parser classes is much simpler (I hope): see implementation of calculator in calculator subproject (src/samples/calc), where are also used grammar_to_parser helper classes, like
grammar_to_parser::basic_pattern_parser and grammar_to_parser::basic_value_parser

The mentioned helper classes can be used for parsing command line parameters together with grammar_to_parser::set class. Following sample code implements parser, which accepts parameters in undefined order, ignoring letter case in parameter names and ignoring white chars too.

//   src/samples/cmd_line_parser/params.h
class params
{
public:
        class name
        {
        public:
                grammar_to_parser::pattern_parser                               m_param;
                grammar_to_parser::value_parser<std::string>    m_name;
                
                name() : m_param("name:") {};
                void push_parsers( std::list<parser<E>*> &l )
                {
                        l.push_back(&m_param);
                        l.push_back(&m_name);
                }
                operator std::string()
                {
                        return m_name.get_valid();
                }
        };
        class age
        {
        public:
                grammar_to_parser::pattern_parser                               m_param;
                grammar_to_parser::value_parser<unsigned long>  m_age;
                
                age() : m_param("age:") {};
                void push_parsers( std::list<parser<E>*> &l )
                {
                        l.push_back(&m_param);
                        l.push_back(&m_age);
                }
                operator unsigned long()
                {
                        return m_age.get_valid();
                }
        };
        class company
        {
        public:
                grammar_to_parser::pattern_parser                               m_param;
                grammar_to_parser::value_parser<std::string>    m_company;
                
                company() : m_param("company:") {};
                void push_parsers( std::list<parser<E>*> &l )
                {
                        l.push_back(&m_param);
                        l.push_back(&m_company);
                }
                operator std::string()
                {
                        return m_company.get_valid();
                }
        };
        grammar_to_parser::non_terminal<name>           m_name;
        grammar_to_parser::non_terminal<age>            m_age;
        grammar_to_parser::non_terminal<company>        m_company;
        
        void push_parsers( std::list<parser<E>*> &l )
        {
                l.push_back(&m_name);
                l.push_back(&m_age);
                l.push_back(&m_company);
        }
        
        
};

//  src/samples/cmd_line_parser/params.cpp
#include <iostream>

#include "grammar_to_parser.h"
#include "parser_strategy.h"
#include "params.h"

using namespace grammar_to_parser;

int main(int argc, char* argv[])
{
        set<params>             the_parser;

        std::string ("Name : Radko   Age : 32   Company :PUB");
        the_parser.parse(input.c_str(), input.length() );
        
        if( the_parser.is_parsed() )
        {
                std::cout << the_parser->m_name << std::endl;
                std::cout << the_parser->m_age << std::endl;
                std::cout << the_parser->m_company << std::endl;
        }
        else
                std::cout << "invalid input" << std::endl;
}

The sample code for parsing command line parameters can be found on src/samples/cmd_line_parser directory.

In version 1.3 was first time introduced a regexp_parser, parser for parsing strings upon regular expression passed as string into the regexp_parser constructor, which feeds the engine used during parsing. For supported features see regexp grammar implemented in regular_expression::regexp.

#include <iostream>
#include "grammar_to_parser.h"
#include "regexp_parser.h"
 
using namespace std;

int main(int argc, char* argv[])
{       
        grammar_to_parser::regexp_parser rxp("[a-z]*?[0-9]");
        string input("thestring1");
        
        rxp.parse( input.c_str(), input.length() );
        if( !rxp.is_parsed() )
        {
                cout << "not recognized" << endl;
        }
        else
        {
                cout << "OK, recognized string:" << rxp << endl;
        }
        return 0;
}

In version 1.4 was added wide char support, where all parsers were rewritten to basic_xxx_parser. It is possible to specify input type in the same manner as it is in basic_string, except usage of allocator and traits is ommited, which can be future job. All parsers accepting wchar_t* input buffer are prefixed with w.

In version 1.4 was also added little support for XML parsing. How the XML parsers can be implemented in future is showed in xml_parser sample code, can be found on src/samples/xml_parser.

In version 1.5 the use of strategies was simplified - support removed from all existing classes and added to new class basic_universal_non_terminal.
New classes for parsing the xml elements were added, in xml_parser sample code is example how to implement complex type classes to be parsed from xml document. Each class, which represents type to be parsed as xml element, must implement methods:

• void push_attributes_parser(parser_list &l) - must give the parser of attributes used in element declaration;
  and the method:
• void push_parsers(parser_list &l) - must give the parser of element value, it can be parser of complex type or parser of simple element types (also regexp_parser - regular expression parser). See following sample code from xml_parser target:

class address
{
protected:
        // attributes of address complex element
        wxml_string_attribute_parser                            m_category;
        wxml_number_attribute_parser<int>                       m_age;
        
        // address sub-elements
        wxml_element_parser<simple_string_element>      m_name;
        wxml_element_parser<simple_string_element>      m_street;
        wxml_element_parser<simple_string_element>      m_city;
        wxml_element_parser<simple_string_element>      m_state;
        wxml_element_parser<simple_int_element>         m_zip;
        
public:
        address() :
                m_category(L"Category"),
                m_age(L"Age",wxml_attribute_parser::OPTIONAL),
                m_name(L"Name"),
                m_street(L"Street"),
                m_city(L"City"),
                m_state(L"State"),
                m_zip(L"Zip") {};
        

        // methods which must be implemented - begin
        void push_attributes_parsers( wattributes_parsers_list &l )
        {
                l.push_back(&m_category);
                l.push_back(&m_age);
        }
        
        void push_parsers( wparsers &l )
        {
                l.push_back(&m_name);
                l.push_back(&m_street);
                l.push_back(&m_city);
                l.push_back(&m_state);
                l.push_back(&m_zip);
        }
}

The wxml_element_parser<address>("address") can be used to parse following xml element from document:

           <address category="friend">
                   <name>Ivan Sabata</name>
                   <street>Nogradyho 11</street>
                   <city>Zvolen</city>
                   <state>Sk</state>
                   <zip>96212</zip>
           </address>   

See xml parser classes in xml_parsers namespace, e.g.:
xml_parser::basic_xml_element_parser
xml_parser::basic_xml_number_attribute_parser
xml_parser::basic_xml_string_attribute_parser

NOTE - Xml parser classes don't implement parse for istream input, this is the future task.

In version 1.6 is again change concerning strategies. The context_free_grammar_strategy had too complex algorithm and for recognition of more complex grammars it took too much time. This strategy was removed from the version and all context_free_grammars (like in calc subproject) were redefined into grammars, which are not left recursive. In version 1.6 I left the backdoor for implementing the own strategy : the parser has two parse methods - one with parameter pointer to strategy, where the strategy must be inherited from basic_parser_strategy, the second one original parse method, usable for parsing non-left recursive context-free grammars.

In version 1.6. is also implemented new regular expression parser, where the regular expression is defined using The Open Group specification Issue 6, IEEE Std 1003.1, 2004 Edition, Copyright 2001-2004 The IEEE and The Open Group. The parser was also extended to return matches of the regexp and to address all subexpressions matches. With use of matches it is possible to manipulate the input string. See also src/samples/regexp_parser

The test results from regexp_parser tests:

[--8z--] parsed succesfully input = - recognized succesfully
[[.-.]] parsed succesfully input = - recognized succesfully
[a-bc] parsed succesfully input = ch recognized succesfully
[[:print:]] parsed succesfully input = 1 recognized succesfully
[8--] parsed succesfully input = - recognized succesfully
[a-c] parsed succesfully input = a recognized succesfully
[^a-f] parsed succesfully input = g recognized succesfully
[^a-f] parsed succesfully input = c not recognized succesfully
[[:alnum:]] parsed succesfully input = a recognized succesfully
[--z] parsed succesfully input = - recognized succesfully
[aa-b] parsed succesfully input = b recognized succesfully
[a-bc-h] parsed succesfully input = g recognized succesfully
[a-bc-de-f] parsed succesfully input = a recognized succesfully
[[.a.]] parsed succesfully input = a recognized succesfully
[[=a=]] parsed succesfully input = a recognized succesfully
[[.ch.]] parsed succesfully input = ch not recognized wrongly
  "abc "def" "ghi" jkl" succesfully recognized by "".*"" ,size=11 position=4
    match (subexpr) key = 1  position=4 size=11;

  "abc "def" "ghi" jkl" succesfully recognized by "".*?"" ,size=5 position=4
    match (subexpr) key = 1  position=4 size=5;

  "aaabbbb" succesfully recognized by "a(a(b){1,3})" ,size=6 position=0
    match (subexpr) key = 1  position=0 size=6;
    match (subexpr) key = 1.1  position=1 size=5;
    match (subexpr) key = 1.1.1  position=3 size=1;
    match (subexpr) key = 1.1.2  position=4 size=1;
    match (subexpr) key = 1.1.3  position=5 size=1;

  "abab" succesfully recognized by "(ab){2,5}" ,size=4 position=0
    match (subexpr) key = 1  position=0 size=4;
    match (subexpr) key = 1.1  position=0 size=2;
    match (subexpr) key = 1.2  position=2 size=2;

  "ab" succesfully not recognized by "(ab){2,5}"
  "aa" succesfully recognized by "(a){2}" ,size=2 position=0
    match (subexpr) key = 1  position=0 size=2;
    match (subexpr) key = 1.1  position=0 size=1;
    match (subexpr) key = 1.2  position=1 size=1;

  "a" succesfully recognized by "(a){1}" ,size=1 position=0
    match (subexpr) key = 1  position=0 size=1;
    match (subexpr) key = 1.1  position=0 size=1;

  "aa" succesfully recognized by "((a){1,2}){2}" ,size=2 position=0
    match (subexpr) key = 1  position=0 size=2;
    match (subexpr) key = 1.1  position=0 size=1;
    match (subexpr) key = 1.1.1  position=0 size=1;
    match (subexpr) key = 1.2  position=1 size=1;
    match (subexpr) key = 1.2.1  position=1 size=1;

  "abcabcabc" succesfully recognized by "((abc){1,3}){2,5}" ,size=9 position=0
    match (subexpr) key = 1  position=0 size=9;
    match (subexpr) key = 1.1  position=0 size=6;
    match (subexpr) key = 1.1.1  position=0 size=3;
    match (subexpr) key = 1.1.2  position=3 size=3;
    match (subexpr) key = 1.2  position=6 size=3;
    match (subexpr) key = 1.2.1  position=6 size=3;

  "abcabcabcabcabcabcabcabc" succesfully recognized by "(((abc){2,5}){2,5}){2,5}" ,size=24 position=0
    match (subexpr) key = 1  position=0 size=24;
    match (subexpr) key = 1.1  position=0 size=12;
    match (subexpr) key = 1.1.1  position=0 size=6;
    match (subexpr) key = 1.1.1.1  position=0 size=3;
    match (subexpr) key = 1.1.1.2  position=3 size=3;
    match (subexpr) key = 1.1.2  position=6 size=6;
    match (subexpr) key = 1.1.2.1  position=6 size=3;
    match (subexpr) key = 1.1.2.2  position=9 size=3;
    match (subexpr) key = 1.2  position=12 size=12;
    match (subexpr) key = 1.2.1  position=12 size=6;
    match (subexpr) key = 1.2.1.1  position=12 size=3;
    match (subexpr) key = 1.2.1.2  position=15 size=3;
    match (subexpr) key = 1.2.2  position=18 size=6;
    match (subexpr) key = 1.2.2.1  position=18 size=3;
    match (subexpr) key = 1.2.2.2  position=21 size=3;

  "abcabcabcabcabcabcabc" succesfully not recognized by "(((abc){2,5}){2,5}){2,5}"
  "aaaa" succesfully recognized by "(a)*" ,size=4 position=0
    match (subexpr) key = 1  position=0 size=4;
    match (subexpr) key = 1.1  position=0 size=1;
    match (subexpr) key = 1.2  position=1 size=1;
    match (subexpr) key = 1.3  position=2 size=1;
    match (subexpr) key = 1.4  position=3 size=1;

  "abbbc" succesfully recognized by "bb*" ,size=3 position=1
    match (subexpr) key = 1  position=1 size=3;

  "cdabababb" succesfully recognized by "[ab]*" ,size=7 position=2
    match (subexpr) key = 1  position=2 size=7;

  "abcabcabc" succesfully recognized by "(abc){1,3}" ,size=9 position=0
    match (subexpr) key = 1  position=0 size=9;
    match (subexpr) key = 1.1  position=0 size=3;
    match (subexpr) key = 1.2  position=3 size=3;
    match (subexpr) key = 1.3  position=6 size=3;

  "cabc" succesfully recognized by "(abc){1,3}" ,size=4 position=0
    match (subexpr) key = 1  position=0 size=4;
    match (subexpr) key = 1.1  position=1 size=3;

  "cabcddcabd" succesfully recognized by "(abc)(cab)d{1,3}" ,size=10 position=0
    match (subexpr) key = 1  position=0 size=10;
    match (subexpr) key = 1.1  position=1 size=3;
    match (subexpr) key = 1.2  position=6 size=3;

  "cabcddcabddddd" succesfully recognized by "(abc)(cab)d{1,3}" ,size=12 position=0
    match (subexpr) key = 1  position=0 size=12;
    match (subexpr) key = 1.1  position=1 size=3;
    match (subexpr) key = 1.2  position=6 size=3;

  "ddddd" succesfully recognized by "d{1,3}d{2,5}" ,size=5 position=0
    match (subexpr) key = 1  position=0 size=5;

  "ddddd" succesfully recognized by "d{1,3}" ,size=3 position=0
    match (subexpr) key = 1  position=0 size=3;

  "abcabcabcabc" succesfully recognized by "((abc){1,2}){2,5}" ,size=12 position=0
    match (subexpr) key = 1  position=0 size=12;
    match (subexpr) key = 1.1  position=0 size=6;
    match (subexpr) key = 1.1.1  position=0 size=3;
    match (subexpr) key = 1.1.2  position=3 size=3;
    match (subexpr) key = 1.2  position=6 size=6;
    match (subexpr) key = 1.2.1  position=6 size=3;
    match (subexpr) key = 1.2.2  position=9 size=3;

  "abcabcabcabc" succesfully recognized by "(abc){1,2}{2}" ,size=12 position=0
    match (subexpr) key = 1  position=0 size=12;
    match (subexpr) key = 1.1  position=0 size=3;
    match (subexpr) key = 1.2  position=3 size=3;
    match (subexpr) key = 1.3  position=6 size=3;
    match (subexpr) key = 1.4  position=9 size=3;

  "caabcbdcb" succesfully recognized by "a(a(b){3})" ,size=8 position=1
    match (subexpr) key = 1  position=1 size=8;
    match (subexpr) key = 1.1  position=2 size=7;
    match (subexpr) key = 1.1.1  position=3 size=1;
    match (subexpr) key = 1.1.2  position=5 size=1;
    match (subexpr) key = 1.1.3  position=8 size=1;

  "ba" succesfully not recognized by "^a$"
  "a" succesfully recognized by "^a$" ,size=1 position=0
    match (subexpr) key = 1  position=0 size=1;

  "bac" succesfully not recognized by "^a$"
  "abc" succesfully not recognized by "^a$"
  "aaa" succesfully recognized by "^aaa$" ,size=3 position=0
    match (subexpr) key = 1  position=0 size=3;

  "aba" succesfully recognized by "^a(a)$" ,size=3 position=0
    match (subexpr) key = 1  position=0 size=3;
    match (subexpr) key = 1.1  position=2 size=1;

  "abbbaa" succesfully recognized by "^a(a)a$" ,size=6 position=0
    match (subexpr) key = 1  position=0 size=6;
    match (subexpr) key = 1.1  position=4 size=1;

  "abbaccb" succesfully recognized by "^a(a(b))$" ,size=7 position=0
    match (subexpr) key = 1  position=0 size=7;
    match (subexpr) key = 1.1  position=3 size=4;
    match (subexpr) key = 1.1.1  position=6 size=1;

  "b" succesfully recognized by "a|b" ,size=1 position=0
    match (subexpr) key = 1  position=0 size=1;

  "ab" succesfully recognized by "(a)(b)" ,size=2 position=0
    match (subexpr) key = 1  position=0 size=2;
    match (subexpr) key = 1.1  position=0 size=1;
    match (subexpr) key = 1.2  position=1 size=1;

  "a" succesfully recognized by "(a)|(b)" ,size=1 position=0
    match (subexpr) key = 1  position=0 size=1;
    match (subexpr) key = 1.1  position=0 size=1;

  "add" succesfully recognized by "(a)|(b)|c|dd" ,size=2 position=1
    match (subexpr) key = 1  position=1 size=2;

  "ac" succesfully recognized by "(a)(b|c)" ,size=2 position=0
    match (subexpr) key = 1  position=0 size=2;
    match (subexpr) key = 1.1  position=0 size=1;
    match (subexpr) key = 1.2  position=1 size=1;

  "ac" succesfully recognized by "(a|b)(c|d)" ,size=2 position=0
    match (subexpr) key = 1  position=0 size=2;
    match (subexpr) key = 1.1  position=0 size=1;
    match (subexpr) key = 1.2  position=1 size=1;

  "aic" succesfully recognized by "(ai|b)(c|d)" ,size=3 position=0
    match (subexpr) key = 1  position=0 size=3;
    match (subexpr) key = 1.1  position=0 size=2;
    match (subexpr) key = 1.2  position=2 size=1;

  "abbaba" succesfully recognized by "^a(a(^b)a$)" ,size=6 position=0
    match (subexpr) key = 1  position=0 size=6;
    match (subexpr) key = 1.1  position=3 size=3;
    match (subexpr) key = 1.1.1  position=4 size=1;

  "weeknights" succesfully recognized by "(wee|week)(knights|night)" ,size=10 position=0
    match (subexpr) key = 1  position=0 size=10;
    match (subexpr) key = 1.1  position=0 size=3;
    match (subexpr) key = 1.2  position=3 size=7;

  "aabcbdcb" succesfully recognized by "^a(a(b){3})$" ,size=8 position=0
    match (subexpr) key = 1  position=0 size=8;
    match (subexpr) key = 1.1  position=1 size=7;
    match (subexpr) key = 1.1.1  position=2 size=1;
    match (subexpr) key = 1.1.2  position=4 size=1;
    match (subexpr) key = 1.1.3  position=7 size=1;

  "abab" succesfully recognized by "(ab){2,5}" ,size=4 position=0
    match (subexpr) key = 1  position=0 size=4;
    match (subexpr) key = 1.1  position=0 size=2;
    match (subexpr) key = 1.2  position=2 size=2;

  "ab" succesfully not recognized by "(ab){2,5}"
  "aa" succesfully recognized by "(a){2}" ,size=2 position=0
    match (subexpr) key = 1  position=0 size=2;
    match (subexpr) key = 1.1  position=0 size=1;
    match (subexpr) key = 1.2  position=1 size=1;

  "a" succesfully recognized by "(a){1}" ,size=1 position=0
    match (subexpr) key = 1  position=0 size=1;
    match (subexpr) key = 1.1  position=0 size=1;

  "aa" succesfully recognized by "((a){1,2}){2}" ,size=2 position=0
    match (subexpr) key = 1  position=0 size=2;
    match (subexpr) key = 1.1  position=0 size=1;
    match (subexpr) key = 1.1.1  position=0 size=1;
    match (subexpr) key = 1.2  position=1 size=1;
    match (subexpr) key = 1.2.1  position=1 size=1;

  "abcabcabc" succesfully recognized by "((abc){1,3}){2,5}" ,size=9 position=0
    match (subexpr) key = 1  position=0 size=9;
    match (subexpr) key = 1.1  position=0 size=6;
    match (subexpr) key = 1.1.1  position=0 size=3;
    match (subexpr) key = 1.1.2  position=3 size=3;
    match (subexpr) key = 1.2  position=6 size=3;
    match (subexpr) key = 1.2.1  position=6 size=3;

  "abcabcabcabcabcabcabcabc" succesfully recognized by "(((abc){2,5}){2,5}){2,5}" ,size=24 position=0
    match (subexpr) key = 1  position=0 size=24;
    match (subexpr) key = 1.1  position=0 size=12;
    match (subexpr) key = 1.1.1  position=0 size=6;
    match (subexpr) key = 1.1.1.1  position=0 size=3;
    match (subexpr) key = 1.1.1.2  position=3 size=3;
    match (subexpr) key = 1.1.2  position=6 size=6;
    match (subexpr) key = 1.1.2.1  position=6 size=3;
    match (subexpr) key = 1.1.2.2  position=9 size=3;
    match (subexpr) key = 1.2  position=12 size=12;
    match (subexpr) key = 1.2.1  position=12 size=6;
    match (subexpr) key = 1.2.1.1  position=12 size=3;
    match (subexpr) key = 1.2.1.2  position=15 size=3;
    match (subexpr) key = 1.2.2  position=18 size=6;
    match (subexpr) key = 1.2.2.1  position=18 size=3;
    match (subexpr) key = 1.2.2.2  position=21 size=3;

  "abcabcabcabcabcabcabc" succesfully not recognized by "(((abc){2,5}){2,5}){2,5}"
  "aaaa" succesfully recognized by "(a)*" ,size=4 position=0
    match (subexpr) key = 1  position=0 size=4;
    match (subexpr) key = 1.1  position=0 size=1;
    match (subexpr) key = 1.2  position=1 size=1;
    match (subexpr) key = 1.3  position=2 size=1;
    match (subexpr) key = 1.4  position=3 size=1;

  "abbbc" succesfully recognized by "bb*" ,size=3 position=1
    match (subexpr) key = 1  position=1 size=3;

  "cdabababb" succesfully recognized by "[ab]*" ,size=7 position=2
    match (subexpr) key = 1  position=2 size=7;

  "abcabcabc" succesfully recognized by "(abc){1,3}" ,size=9 position=0
    match (subexpr) key = 1  position=0 size=9;
    match (subexpr) key = 1.1  position=0 size=3;
    match (subexpr) key = 1.2  position=3 size=3;
    match (subexpr) key = 1.3  position=6 size=3;

  "cabc" succesfully recognized by "(abc){1,3}" ,size=4 position=0
    match (subexpr) key = 1  position=0 size=4;
    match (subexpr) key = 1.1  position=1 size=3;

  "cabcddcabd" succesfully recognized by "(abc)(cab)d{1,3}" ,size=10 position=0
    match (subexpr) key = 1  position=0 size=10;
    match (subexpr) key = 1.1  position=1 size=3;
    match (subexpr) key = 1.2  position=6 size=3;

  "cabcddcabddddd" succesfully recognized by "(abc)(cab)d{1,3}" ,size=12 position=0
    match (subexpr) key = 1  position=0 size=12;
    match (subexpr) key = 1.1  position=1 size=3;
    match (subexpr) key = 1.2  position=6 size=3;

  "ddddd" succesfully recognized by "d{1,3}d{2,5}" ,size=5 position=0
    match (subexpr) key = 1  position=0 size=5;

  "ddddd" succesfully recognized by "d{1,3}" ,size=3 position=0
    match (subexpr) key = 1  position=0 size=3;

  "abcabcabcabc" succesfully recognized by "((abc){1,2}){2,5}" ,size=12 position=0
    match (subexpr) key = 1  position=0 size=12;
    match (subexpr) key = 1.1  position=0 size=6;
    match (subexpr) key = 1.1.1  position=0 size=3;
    match (subexpr) key = 1.1.2  position=3 size=3;
    match (subexpr) key = 1.2  position=6 size=6;
    match (subexpr) key = 1.2.1  position=6 size=3;
    match (subexpr) key = 1.2.2  position=9 size=3;

  "abcabcabcabc" succesfully recognized by "(abc){1,2}{2}" ,size=12 position=0
    match (subexpr) key = 1  position=0 size=12;
    match (subexpr) key = 1.1  position=0 size=3;
    match (subexpr) key = 1.2  position=3 size=3;
    match (subexpr) key = 1.3  position=6 size=3;
    match (subexpr) key = 1.4  position=9 size=3;

  "caabcbdcb" succesfully recognized by "a(a(b){3})" ,size=8 position=1
    match (subexpr) key = 1  position=1 size=8;
    match (subexpr) key = 1.1  position=2 size=7;
    match (subexpr) key = 1.1.1  position=3 size=1;
    match (subexpr) key = 1.1.2  position=5 size=1;
    match (subexpr) key = 1.1.3  position=8 size=1;

  "ba" succesfully not recognized by "^a$"
  "a" succesfully recognized by "^a$" ,size=1 position=0
    match (subexpr) key = 1  position=0 size=1;

  "bac" succesfully not recognized by "^a$"
  "abc" succesfully not recognized by "^a$"
  "aaa" succesfully recognized by "^aaa$" ,size=3 position=0
    match (subexpr) key = 1  position=0 size=3;

  "aba" succesfully recognized by "^a(a)$" ,size=3 position=0
    match (subexpr) key = 1  position=0 size=3;
    match (subexpr) key = 1.1  position=2 size=1;

  "abbbaa" succesfully recognized by "^a(a)a$" ,size=6 position=0
    match (subexpr) key = 1  position=0 size=6;
    match (subexpr) key = 1.1  position=4 size=1;

  "abbaccb" succesfully recognized by "^a(a(b))$" ,size=7 position=0
    match (subexpr) key = 1  position=0 size=7;
    match (subexpr) key = 1.1  position=3 size=4;
    match (subexpr) key = 1.1.1  position=6 size=1;

  "b" succesfully recognized by "a|b" ,size=1 position=0
    match (subexpr) key = 1  position=0 size=1;

  "ab" succesfully recognized by "(a)(b)" ,size=2 position=0
    match (subexpr) key = 1  position=0 size=2;
    match (subexpr) key = 1.1  position=0 size=1;
    match (subexpr) key = 1.2  position=1 size=1;

  "a" succesfully recognized by "(a)|(b)" ,size=1 position=0
    match (subexpr) key = 1  position=0 size=1;
    match (subexpr) key = 1.1  position=0 size=1;

  "add" succesfully recognized by "(a)|(b)|c|dd" ,size=2 position=1
    match (subexpr) key = 1  position=1 size=2;

  "ac" succesfully recognized by "(a)(b|c)" ,size=2 position=0
    match (subexpr) key = 1  position=0 size=2;
    match (subexpr) key = 1.1  position=0 size=1;
    match (subexpr) key = 1.2  position=1 size=1;

  "ac" succesfully recognized by "(a|b)(c|d)" ,size=2 position=0
    match (subexpr) key = 1  position=0 size=2;
    match (subexpr) key = 1.1  position=0 size=1;
    match (subexpr) key = 1.2  position=1 size=1;

  "aic" succesfully recognized by "(ai|b)(c|d)" ,size=3 position=0
    match (subexpr) key = 1  position=0 size=3;
    match (subexpr) key = 1.1  position=0 size=2;
    match (subexpr) key = 1.2  position=2 size=1;

  "abbaba" succesfully recognized by "^a(a(^b)a$)" ,size=6 position=0
    match (subexpr) key = 1  position=0 size=6;
    match (subexpr) key = 1.1  position=3 size=3;
    match (subexpr) key = 1.1.1  position=4 size=1;

  "weeknights" succesfully recognized by "(wee|week)(knights|night)" ,size=10 position=0
    match (subexpr) key = 1  position=0 size=10;
    match (subexpr) key = 1.1  position=0 size=3;
    match (subexpr) key = 1.2  position=3 size=7;

  "aabcbdcb" succesfully recognized by "^a(a(b){3})$" ,size=8 position=0
    match (subexpr) key = 1  position=0 size=8;
    match (subexpr) key = 1.1  position=1 size=7;
    match (subexpr) key = 1.1.1  position=2 size=1;
    match (subexpr) key = 1.1.2  position=4 size=1;
    match (subexpr) key = 1.1.3  position=7 size=1;

---