Die großen Dinge parsen

Hallo Community!

Kennt sich hier wer mit Parsen aus? Ich wollte mal im Allgemeinen Fragen, wie man "größere" Dinge parst. Ich habe bisher immer nur std::string und die iostreams im imperativen Stil verwendet um Dinge zu parsen. Aber was, wenn es mal was größeres ist? Sagen wir zum Beispiel einen IMAP-Mail-Parser oder gar ne ganze Sprache! Da ist mir aufgefallen, dass das eine ziemlich heikele Sache ist, wenn man imperativ und mit Streams arbeitet. Gibt es hier vielleicht nennenswerte Idiome, oder gar ganze Parsing-Libraries, die einem das Parsen vereinfachen können?

Ich habe auch ein Beispiel. Teil einer Mail:

Received: from (domain [IP])
        by mx.google.com with ESMTP id u6si2825139wia.7.2015.09.12.06.35.39;
        Sat, 12 Sep 2015 06:35:39 -0700 (PDT)

Dazu habe ich eine normale Struktur gebaut, die ganz simpel wie folgt aussieht:

struct value_pair{
    std::string name, value;

    void parse(std::istream& stream){
        ...
    }
};

Nur, wie kann ein Parser erkennen, ob die nächste Zeile noch zum gleichen value_pair gehört oder nicht? Nicht jede Zeile endet mit ';' oder ',' wie man oben an meinem Beispiel erkennen kann.

Die einzige Möglichkeit, die mir einfällt ist es, eine Helper-Funktion zu bauen, die einem die nächste Zeile eines Streams zurückgibt, ohne jedoch die Position des Streams selbst zu verändern. Dann schau ich nach, ob in der besagten nächsten Zeile ein ':' vorkommt, wenn nicht, gehört die nächste Zeile zum selben value_pair, andernfalls ist es ein anderes value_pair. Und nun stellt euch vor, die nächste Zeile gehört tatsächlich noch zum selben value_pair, nur dass in diesem Wert tatsächlich ein Doppelpunkt vorkommt. Und schon macht meine Methode keinen Sinn mehr.

Kann mir jemand bei dem Parsen der Mails auf die Sprünge helfen?
Kennt wer irgendwelche guten Parsing-Techniken (Idiome, Libraries)?

Würde mich auf Antworten freuen.

Liebe Grüße,
Farmer123

Besorg dir z.B. folgendes Buch (auch als pdf im www findbar).

Parr - Language Implementation Patterns

Parsen ist durchaus ein komplexes Thema,
aber bereits gut erforscht. D.h du wirst zu deinem Problem bereits Pattern finden, welche dieses lösen, ein bisschen Theorie brauchst du aber trotzdem. In obigem Buch findest du beides (Theorie+Praxis).

Th69

Schau dir mal Boost Spirit an.

Für das Parsen von IMAP schau einfach in die Spec: INTERNET MESSAGE ACCESS PROTOCOL - VERSION 4rev1 (unter Kapitel 9 ist dann die Beschreibung als ABNF, welche man dann (fast) 1:1 mittels Boost.Spirit umsetzen kann).

Danke, ich werde mich etwas näher mit all dem beschäftigen.
Boost.Spirit sieht interessant aus.

Ich hab mich etwas in Boost.Spirit reingelesen und habe es geschafft einen kleinen Mathe-Parser zu machen. Nun verstehe ich noch nicht, wie man die Werte vernünftig ansprechen kann. Folgender Code:

#include <boost/spirit/include/qi.hpp>
#include <iostream>

using namespace boost::spirit::qi;

void add(double x){
    std::cout << x << '\n';
}

int main(){
    rule<std::string::iterator, ascii::space_type> add_expr, sub_expr, mult_expr, div_expr, math_expr, term, fact, group;

    term = double_;
    fact = term | group;
    group = char_('(') >> math_expr >> char_(')');

    add_expr = +(char_('+') >> fact)[add];
    sub_expr = +(char_('-') >> fact);
    mult_expr = +(char_('*') >> fact);
    div_expr = +(char_('/') >> fact);
    math_expr = fact >> *(add_expr | sub_expr | mult_expr | div_expr);

    std::string str = "1+1+(1+1)";
    std::string::iterator it = str.begin();

    phrase_parse(it, str.end(), math_expr, ascii::space);
    std::cout << &*it << '\n';
}

In Zeile 19 versuche ich über eine Funktion an den Wert zu kommen, doch dieser lautet genau dreimal 43. Woher kommt diese 43? Und wie spreche ich die 1 an?

Th69

Ist schon ein bißchen her, seitdem ich mit Spirit gearbeitet habe, aber 43 (hex: 2B) ist der ASCII-Code für '+'
Die Zahlen (Terminalzeichen) definiserst du ja mittels

term = double_;

Schau mal, ob du mittels

void number(double x)
{
    std::cout << x << '\n';
}

term = double_[number];

an die Zahlen kommst.

Ja, damit komm ich zwar an die Zahlen, das Problem dabei ist jedoch, dass ich so nicht weiß wie ich addieren, subtrahieren, etc. soll. Ich habe mir das so vorgestellt, dass ich vorerst mal ne globale "double result = 0;" mache und bei den entsprechenden Parsern dann die Operation mache. Im Sinne von:

double res = 0;

void add(double x){
    res += x;
}

add_expr = +(char_('+') >> fact)[add];

Ist mein Vorhaben realisierbar?

Ich habe auch schon folgendes versucht:

#include <boost/spirit/include/qi.hpp>

using namespace boost::spirit::qi;

void add(boost::fusion::vector<char, double> x){
    std::cout << boost::fusion::at_c<1>(x) << '\n';
}

int main(){
    rule<std::string::iterator, ascii::space_type> add_expr, sub_expr, mult_expr, div_expr, math_expr, term, group;
    rule<std::string::iterator, double, ascii::space_type> fact = term | group;

    term = double_;
    group = char_('(') >> math_expr >> char_(')');

    add_expr = +(char_('+') >> fact)[add];
    sub_expr = +(char_('-') >> fact);
    mult_expr = +(char_('*') >> fact);
    div_expr = +(char_('/') >> fact);
    math_expr = fact >> *(add_expr | sub_expr | mult_expr | div_expr);

    std::string str = "1+1";
    std::string::iterator it = str.begin();

    phrase_parse(it, str.end(), math_expr, ascii::space);
    std::cout << &*it << '\n';
}

Das kompiliert, aber damit wird mir nur einmal 0 ausgegeben und verstehe nicht woher diese Null auf einmal herkommt.

Und so hätte ich es mir am schönsten vorgestellt, kompiliert nur leider nicht:

void dowork(boost::fusion::vector<double, boost::fusion::vector<char, double>> x){}
 math_expr = (fact >> *((char_('+')|char_('-')|char_('*')|char_('/')) >> fact))[dowork];

PS: Ja, das mit dem '+' war ein char, stimmt!

Ich habs nun irgendwie geschafft.

#include <boost/spirit/include/qi.hpp>

namespace qi = boost::spirit::qi;

template<typename Iterator>
class math_parser : public qi::grammar<Iterator, qi::ascii::space_type>{
    qi::rule<Iterator, qi::ascii::space_type> start;
    qi::rule<Iterator, double, qi::ascii::space_type> term, fact, group;
    qi::rule<Iterator> identifier;

    void work(boost::fusion::vector<double, std::vector<boost::fusion::vector<char, double>>>& values){
        result = boost::fusion::at_c<0>(values);
        auto vec = boost::fusion::at_c<1>(values);

        double value;
        char op;

        for(auto&& v : std::move(vec)){
            op = boost::fusion::at_c<0>(v);
            value = boost::fusion::at_c<1>(v);

            switch(op){
                case '+':
                    result += value;
                    break;

                case '-':
                    result -= value;
                    break;

                case '*':
                    result *= value;
                    break;

                case '/':
                    result /= value;
            }
        }
    }

public:
    double result;

    math_parser() : qi::grammar<Iterator, qi::ascii::space_type>(start){
        identifier = qi::alpha >> *(qi::alnum);

        term = qi::double_ | identifier;

        fact = term | group;

        group = qi::char_('(') >> start >> qi::char_(')');

        start = (fact >> *((qi::char_('+') | qi::char_('-') | qi::char_('*') | qi::char_('/')) >> fact))
        [std::bind(&math_parser::work, this, std::placeholders::_1)];
    }
};

#include <iostream>

int main(){
    std::string str = "(1)+2+3";
    std::string::iterator it = str.begin();
    math_parser<decltype(it)> parser;

    qi::phrase_parse(it, str.end(), parser, qi::ascii::space);
    std::cout << parser.result << '\n';
}

Da gibt es nur ein winziges Problem. Bei Expressions wie "1+2+3" klappt alles wundersam, jedoch, sobald ich die Klammern setze, werden diese Klammern mitberechnet. Was ich also suche, ist es, dem Parser "group" irgendwie mitzuteilen, was genau er zurückgeben soll. Wie mach ich das? Oder denke ich schon wieder in die falsche Richtung?