3. compiletime string validator generator

compiletime string validator generator

  • G

    Hab nicht viel zu dem Thema im Internet gefunden, also poste ich es mal, vielleicht interessiert es wen.
    Compiled ohne Fehler mit gcc 4.6.

    Das Prinzip ist eigentlich sehr simpel, wenn man es verstanden hat. Jedem Operator aus der EBNF wird ein Typ aus c++ zugeordnet. So wird A = B | C; zu typedef alt< B , C > A; .
    Wenn man Rekursion verwenden will, kann man das so machen: A = B , [ A ] => struct A : concat< B , opt< A > > {}; .
    Terminale werden so definiert: "ABC" => terminal< 'A' , 'B' , 'C' >

    Für den parsing Prozess ist die Funktion

    template< unsigned int N >
constexpr static unsigned int parse( const char (&arr) , unsigned int i );

    zuständig, die in jeder Symbolsklasse definiert wird. Übergeben wird ihr der String in arr und die derzeitige parse-Position im array in i. Die Rückgabe ist entweder das unsigned int maximum, wenn das Symbol nicht erstellt werden konnte, oder eine neue Position im String, wenn das Symbol erstellt werden konnte.

    const unsigned int uimax = 0u - 1;

template< char ... >
struct terminal;
template< char Last >
struct terminal< Last >
{
    template< unsigned int N >
    static constexpr unsigned int parse( const char (&arr)[N] , unsigned int i )
    {
        return
        i < N ?
            arr[i] == Last ?
                i + 1 :
                uimax
            : uimax;
    }
};
template< char First , char ...Tail >
struct terminal< First , Tail... >
{
    template< unsigned int N >
    static constexpr unsigned int parse( const char (&arr)[N] , unsigned int i )
    {
        return
        i < N ?
            arr[i] == First ?
                terminal< Tail... >::parse( arr , i + 1 ) :
                uimax :
            uimax;
    }
};
template< class ... >
struct concat;
template<>
struct concat<>
{
    template< unsigned int N >
    static constexpr unsigned int parse( const char (&arr)[N] , unsigned int i )
    {
        return i;
    }
};
template< class Head , class ...Tail >
struct concat< Head , Tail... >
{
    template< unsigned int N >
    static constexpr unsigned int parse( const char (&arr)[N] , unsigned int i )
    {
        return
        Head::parse( arr , i ) == uimax ?
            uimax :
            concat< Tail... >::parse( arr , Head::parse( arr , i ) );
    }
};
template< class ... >
struct alt;
template< class Last >
struct alt< Last >
{
    template< unsigned int N >
    static constexpr unsigned int parse( const char (&arr)[N] , unsigned int i )
    {
        return
        Last::parse( arr , i ) == uimax ?
            uimax :
            Last::parse( arr , i );
    }
};
template< class Head , class ...Tail >
struct alt< Head , Tail... >
{
    template< unsigned int N >
    static constexpr unsigned int parse( const char (&arr)[N] , unsigned int i )
    {
        return
        Head::parse( arr , i ) == uimax ?
            alt< Tail... >::parse( arr , i ) :
            Head::parse( arr , i );
    }
};
template< class Symbol >
struct opt
{
    template< unsigned int N >
    static constexpr unsigned int parse( const char (&arr)[N] , unsigned int i )
    {
        return
        Symbol::parse( arr , i ) == uimax ?
            i :
            Symbol::parse( arr , i );
    }
};
template< class Symbol >
struct repet
{
    template< unsigned int N >
    static constexpr unsigned int parse( const char (&arr)[N] , unsigned int i )
    {
        return
        Symbol::parse( arr , i ) == uimax ?
            i :
            repet< Symbol >::parse( arr , Symbol::parse( arr , i ) );
    }
};

//Anwendung: parentheses matching
typedef repet
<
    alt
    <
        terminal< ' ' > ,
        terminal< '\n' >
    >
> white;

struct parentheses
    : concat
    <
        white ,
        terminal< '(' > ,
        white ,
        opt< parentheses > ,
        terminal< ')' > ,
        white ,
        opt< parentheses >
    >
{
};

int main()
{
    constexpr char str_valid[] = "()()( () \n () ( ( ) ) )";
    constexpr char str_invalid[] = "()( ( ( ( ) ) () ) (";
    static_assert( parentheses::parse( str_valid , 0 ) == sizeof( str_valid ) - 1 , "" );
    static_assert( parentheses::parse( str_invalid , 0 ) != sizeof( str_invalid ) - 1 , "" );
}

    Im Moment seh ich noch keinen wirklichen Anwendungszweck, erhoffe mir aber, dass man vielleicht Objekte mit constexpr Konstruktor zurückgeben kann um einen AST aufzubauen.
    Das System, dass man jedes Symbol einfach die parse - Funktion "überschreiben" lässt, kann man übrigens auch hervorragend für einen runtime - Parser (bzw. einen Parser Generator zur compiletime) verwenden.
    Kompletter source wäre zu lang, aber so könnte das dann aussehen:

    template< class Symbol >
class repet
    : public std::vector< Symbol >
{
public:
    template< class IteratorType >
    bool parse( IteratorType &begin , IteratorType end )
    //Diese Funktion wird von jedem Symbol definiert. Sie soll true ergeben, wenn das Symbol erstellt werden konnte und begin erhöhen, falls nötig.
    {
        vec_type::push_back( Symbol() );
        while( vec_type::back().parse( begin , end ) )
        {
            vec_type.push_back( Symbol() );
        }
        vec_type::pop_back();
        return true;
    }
private:
    typedef std::vector< Symbol > vec_type;
};

    So kann man dann sehr leicht einen AST erstellen (leider nur zur runtime).

    0
  • ?

    Cool, danke! 👍

    0
  • K

    Vielleicht kannst du etwas mehr dazu schreiben, bspw. welches Problem geloest werden soll, wie der Ansatz ist, ... und ein paar erklaerende Worte.

    0
  • G

    knivil schrieb:

    Vielleicht kannst du etwas mehr dazu schreiben, bspw. welches Problem geloest werden soll, wie der Ansatz ist, ... und ein paar erklaerende Worte.

    Mach ich jetzt... es war nur so dass die Sonne schon wieder aufging 🙂

    0
  • G

    So, ich jetzt konnte ich auch einen AST generieren und damit einen kleinen Rechner bauen. Er kann im Moment nur + und * und nimmt auch "05" als Zahl an, aber es geht hier ja nur darum, das ganze zu demonstrieren. Auszug aus main.cpp:

    #include "operators.hpp"

#include <string>
#include <iostream>

DEF_TERMINAL( MyTerminal , "asdfasdf" )

int main()
{
    //compile time parsing
    constexpr const_string< char > cstr = "2  + 54 * 2 + 83";
    constexpr addition a( cstr );
    static_assert( a.eval() == 193 , "");
    constexpr const_string< char > cstr2 = "asd fasdf";
    constexpr MyTerminal t( cstr2 );
    static_assert( !t.valid() , "" );

    //run time parsing, but I guess this is very inefficient
    std::string str;
    std::cin >> str;
    const_string< char > cstr3( &*str.begin() , &*str.end() );
    addition a_run_time( cstr3 );
    if( a_run_time.end() == str.size() )
        std::cout << a_run_time.eval() << std::endl;
    else
        std::cout << "parse error" << std::endl;
}

    Den kompletten source kann man sich hier runterladen:
    http://www.file-upload.net/download-4010616/compile-time-parser.zip.html

    Das hat jetzt vielleicht so langsam einen Sinn... vielleicht wird man irgendwann z.B. SQL in c++ compilen können (inklusive Syntaxchecks und c++ performance).

    0
  • E

    Find ich persönlich richtig genial.

    Das hat jetzt vielleicht so langsam einen Sinn... vielleicht wird man irgendwann z.B. SQL in c++ compilen können (inklusive Syntaxchecks und c++ performance).

    Wäre es denn theoretisch möglich? Wenn ja, lust eine minimale Scriptsprache mit einem "print xyz" Befehl zu bauen? Würde das gerne sehen.

    0
  • P

    Ethon schrieb:

    Find ich persönlich richtig genial.

    Das hat jetzt vielleicht so langsam einen Sinn... vielleicht wird man irgendwann z.B. SQL in c++ compilen können (inklusive Syntaxchecks und c++ performance).

    Wäre es denn theoretisch möglich? Wenn ja, lust eine minimale Scriptsprache mit einem "print xyz" Befehl zu bauen? Würde das gerne sehen.

    Oder ein "in c++ c++ compiler xD" Lol könnte der sich dann nicht selbst kompiliern? oO Kann mir das gerade nicht so richtig vorstellen ... ein Compiler der sich während des Erstellens selbst compiled?!

    0
  • G

    Ethon schrieb:

    Find ich persönlich richtig genial.

    Das hat jetzt vielleicht so langsam einen Sinn... vielleicht wird man irgendwann z.B. SQL in c++ compilen können (inklusive Syntaxchecks und c++ performance).

    Wäre es denn theoretisch möglich?

    Ich wüsste nicht, warum es nicht möglich sein sollte. Den query könnte man natürlich nicht zur Compilezeit ausführen (macht ja auch wenig Sinn), aber man kann schonmal den Befehl in c++ (und dann in Maschinencode) übersetzen.

    Wenn ja, lust eine minimale Scriptsprache mit einem "print xyz" Befehl zu bauen? Würde das gerne sehen.

    Wie meinst du das? Eine Sprache die nur "print string" kann, beim compilen übersetzt wird und den string dann über ein code.exec() zur Laufzeit ausgibt? Es gäbe vielleicht die Möglichkeit, über ein static_assert eine Ausgabe beim compilen zu erzeugen... aber ich wüsste jetzt so spontan nicht, wie ich einen constexpr char substr[] aus einem anderen constexpr string generieren könnte...

    pyhax schrieb:

    Oder ein "in c++ c++ compiler xD" Lol könnte der sich dann nicht selbst kompiliern? oO Kann mir das gerade nicht so richtig vorstellen ... ein Compiler der sich während des Erstellens selbst compiled?!

    Er könnte seinen eigenen Quellcode übersetzen, ja. Aber so ungewöhnlich ist das nicht, der gcc oder javac können das auch.

    0
  • C
    Mod

    GorbGorb schrieb:

    Es gäbe vielleicht die Möglichkeit, über ein static_assert eine Ausgabe beim compilen zu erzeugen... aber ich wüsste jetzt so spontan nicht, wie ich einen constexpr char substr[] aus einem anderen constexpr string generieren könnte...

    Eine Möglichkeit:

    #include <cstddef>
#include <iostream>

template <typename T> struct identity
{
    using type = T;
};
template <std::ptrdiff_t... i> struct index_list
    : identity<index_list<i...>> {};

template <typename... T> struct concat_index_lists
    : concat_index_lists<typename T::type...> {};
template <std::ptrdiff_t... i, std::ptrdiff_t... j, typename... T> struct concat_index_lists<index_list<i...>, index_list<j...>, T...>
    : concat_index_lists<index_list<i..., j...>, T...> {};
template <std::ptrdiff_t... i> struct concat_index_lists<index_list<i...>>
    : identity<index_list<i...>> {};

template <typename T, std::ptrdiff_t shift> struct shift_index_list
    : shift_index_list<typename T::type, shift> {};
template <std::ptrdiff_t... i, std::ptrdiff_t shift> struct shift_index_list<index_list<i...>, shift>
    : identity<index_list<(i + shift)...>> {};

template <std::size_t N> struct make_index_list
    : concat_index_lists<make_index_list<N / 2>, shift_index_list<make_index_list<N / 2>, N / 2>, shift_index_list<make_index_list<N % 2>, N - 1>> {};
template <> struct make_index_list<1>
    : identity<index_list<0>> {};
template <> struct make_index_list<0>
    : identity<index_list<>> {};

template <const char* str, std::ptrdiff_t begin, std::ptrdiff_t end, typename = typename make_index_list<end - begin>::type> struct substr;
template <const char* str, std::ptrdiff_t begin, std::ptrdiff_t end, std::ptrdiff_t... i> struct substr<str, begin, end, index_list<i...>>
{
    static constexpr char value[] = { str[ i + begin ]..., '\0' };
};
template <const char* str, std::ptrdiff_t begin, std::ptrdiff_t end, std::ptrdiff_t... i>
constexpr char substr<str, begin, end, index_list<i...>>::value[];

extern constexpr char test[] = "substr123";

int main()
{
    std::cout << substr<test, 4, 8>::value << '\n';
}

    (gcc-4.7 erforderlich, Anpassung in 4.6 ist möglich).
    Hier hatte ich auch ein paar Techniken verwendet, die nützlich sein könnten.

    0
  • E

    Ich wüsste nicht, warum es nicht möglich sein sollte. Den query könnte man natürlich nicht zur Compilezeit ausführen (macht ja auch wenig Sinn), aber man kann schonmal den Befehl in c++ (und dann in Maschinencode) übersetzen.
    Zitat:

    ...

    Wie meinst du das? Eine Sprache die nur "print string" kann, beim compilen übersetzt wird und den string dann über ein code.exec() zur Laufzeit ausgibt? Es gäbe vielleicht die Möglichkeit, über ein static_assert eine Ausgabe beim compilen zu erzeugen... aber ich wüsste jetzt so spontan nicht, wie ich einen constexpr char substr[] aus einem anderen constexpr string generieren könnte...

    Na das meinte ich ja ungefähr.
    Mich hat interessiert wie es aussehen würde aus einem

    constexpr const_string< char > cmd = "print Hallo";

    ein

    std::cout << "Hallo";

    zu bauen (und logischerweise zu kompilieren), da du ja meintest dass soetwas möglich ist.

    Für mich ist die ganze Meta-Templatespielerei noch recht schwarze Magie.

    0
  • G

    Wie immer sehr kompetenter Beitrag, hab ne Weile gebraucht bis ich alles verstanden hatte (vor allem, um zu begreifen was make_index tun soll... ist es so deutlich schneller als mit der naiven Variante?).

    camper schrieb:

    extern constexpr char test[] = "substr123";

    Kannst du das extern bisschen erklären? Warum kann man test nur damit als template Parameter verwenden?

    @Ethon:

    #include <iostream>

#include "terminal.hpp"
#include "concat.hpp"
#include "repet.hpp"

DEF_TERMINAL( Tprint , "print" )

struct anything
    : symbol
{
    constexpr anything( const_string< char > str , unsigned int begin = 0 )
        : symbol( str.size() ) ,
          m_str( str ) ,
          m_begin( begin )
    {
    }
    void print() const
    {
        std::cout << m_str.m_begin + m_begin;
    }
    const_string< char > m_str;
    unsigned int m_begin;
};

struct statement
    : concat
    <
        Tprint ,
        concat< terminal< ' ' > , repet< terminal< ' ' > > > ,
        anything
    >
{
    template< class ...ArgTypes >
    constexpr statement( ArgTypes ...args )
        : concat
        <
            Tprint ,
            concat< terminal< ' ' > , repet< terminal< ' ' > > > ,
            anything
        >( args... )
    {
    }
    void exec() const
    {
        get< 2 >().print();
    }
};

int main()
{
    constexpr statement s( const_string< char >( "print hello world" ) );
    static_assert( s.valid() , "" );
    s.exec();
}

    Braucht die files von dem mathparser. Außerdem wirst du erst eine Fehlermeldung bekommen, dass m_begin in const_string private ist, mach es einfach public.
    Diese Variante kommt natürlich nur mit einem "print" klar und gibt dann den Rest aus.

    0
  • C
    Mod

    GorbGorb schrieb:

    Wie immer sehr kompetenter Beitrag, hab ne Weile gebraucht bis ich alles verstanden hatte (vor allem, um zu begreifen was make_index tun soll... ist es so deutlich schneller als mit der naiven Variante?).

    camper schrieb:

    extern constexpr char test[] = "substr123";

    Kannst du das extern bisschen erklären? Warum kann man test nur damit als template Parameter verwenden?

    Schnelligkeit ist nicht so sehr das Problem, Speicherverbrauch dagegen schon, und der nimmt bei linearer Implementierung ziemlich schnell zu.

    Das extern gehört dahin, weil nur Zeiger auf Objekte mit externer Bindung Templateargumente sein können, deshalb können auch Stringliterale nicht direkt als Templateargumente verwendet werden.

    Man könnte auch eine einfache Funktion schreiben

    template <std::ptrdiff_t... i>
constexpr std::array<char, sizeof...(i)+1> substr_impl(const char* str, index_list<i...>)
{
    return std::array<char, sizeof...(i)+1>{ { str[i]..., 0 } };
}

template <ptrdiff_t begin, ptrdiff_t end>
constexpr std::array<char,end-begin+1> substr(const char* str)
{
    return substr_impl(str, typename shift_index_list<make_index_list<end - begin>, begin>::type());
}
    0
  • G

    Ich seh grade dass man in static_assert einen string literal braucht... hatte erwartet dass es nur ein konstanter Ausdruck sein muss. Dann hat sich die Sache mit der Ausgabe über static_assert natürlich eh erledigt. (schade, das wäre witzig gewesen die Ausgabe eines Programms über die Fehlermeldungen des compilers laufen zu lassen)

    0
  • 3

    Wo wir gerade bei TMP-Magie sind, ich habe vorgestern eine kleine Compiletime-Bigint Lib geschrieben. Im Moment ist nur Addition, Shifts, Vergleichsoperatoren und ein min/max implementiert, aber das kann man ja relativ einfach erweitern...
    http://ideone.com/U7OzC
    to_string gibt derzeit nur Binärstrings zurück und wahrscheinlich kann man am Code vieles vereinfachen. Ich hab das um 3 Uhr morgens gemacht. 😉

    0
  • C
    Mod

    314159265358979 schrieb:

    Wo wir gerade bei TMP-Magie sind, ich habe vorgestern eine kleine Compiletime-Bigint Lib geschrieben. Im Moment ist nur Addition, Shifts, Vergleichsoperatoren und ein min/max implementiert, aber das kann man ja relativ einfach erweitern...
    http://ideone.com/U7OzC
    to_string gibt derzeit nur Binärstrings zurück und wahrscheinlich kann man am Code vieles vereinfachen. Ich hab das um 3 Uhr morgens gemacht. 😉

    Gegeben sei

    #include <cstddef>

template <typename T> struct identity
{
    typedef T type;
};

template <std::size_t... i> struct index_list
    : identity<index_list<i...>> {};

template <typename T>       struct append_index_list
    : append_index_list<typename T::type> {};
template <std::size_t... i> struct append_index_list<index_list<i...>>
    : identity<index_list<0, ( i + 1 )...>> {};

template <std::size_t N> struct make_index_list
    : append_index_list<make_index_list<N - 1>> {};
template <>              struct make_index_list<0>
    : identity<index_list<>> {};

template <char... c> struct string
    : identity<string<c...>>
{
    static constexpr char value[] = { c..., '\0' };
};
template <char... c>
constexpr char string<c...>::value[];

template <typename str, typename indexes> struct substr
    : substr<typename str::type, typename indexes::type> {};
template <typename str, std::size_t... i> struct substr<str, index_list<i...>>
    : identity<string<str::value[i]...>> {};

#define C( s, x )        (x<sizeof(s)?s[x]:'\0')
#define STR4( s, x )     C( s, x), C(s, x+1), C(s, x+2), C(s, x+3)
#define STR16( s, x )    STR4(   s, x), STR4(   s, x+4),    STR4(  s, x+8),     STR4(   s, x+12)
#define STR64( s, x )    STR16(  s, x), STR16(  s, x+16),   STR16( s, x+32),    STR16(  s, x+48)
#define STR256( s, x )   STR64(  s, x), STR64(  s, x+64),   STR64( s, x+128),   STR64(  s, x+192)
#define STR1024( s, x )  STR256( s, x), STR256( s, x+256),  STR256(s, x+512),   STR256( s, x+768)
#define STR4096( s, x )  STR1024(s, x), STR1024(s, x+1024), STR1024(s, x+2048), STR1024(s, x+3072)
#define STRING( x )      substr<string<STR4096(x,0), '\0'>,make_index_list<sizeof(x)>>::type

#include <iostream>
int main()
{
    std::cout << STRING("12345")::value << '\n';
}

    Jetzt möchte ich eine Template-Metafunktion haben, die Strings direkt parst und ggf. Berechnungen anstellt, also z.B.

    std::cout << compute<STRING("10+20+30")::value

    sollte dann 60 ausgeben.

    0
  • 3

    So blöd es klingt, aber einen Mathe-Parser kriege ich nicht mal mit "normalen" Funktionen ordentlich hin. Da kann ich einen über TMP erst recht nicht.

    0
Anmelden zum Antworten