Schreiben eines Lexers in C ++

Was sind gute Ressourcen zum Schreiben eines Lexikons in C ++ (Bücher, Tutorials, Dokumente), was sind einige gute Techniken und Vorgehensweisen?

Ich habe im Internet gesucht und jeder sagt, dass er einen Lexer-Generator wie Lex benutzen soll. Das will ich nicht, ich will ein Lexer von Hand schreiben.

Beachten Sie, dass jede Zustandsmaschine einem regulären Ausdruck entspricht, der einem strukturierten Programm mit ifund whileAnweisungen entspricht.

Um zum Beispiel ganze Zahlen zu erkennen, könnte man die Zustandsmaschine haben:

0: digit -> 1
1: digit -> 1

oder der reguläre Ausdruck:

digit digit*

oder der strukturierte Code:

if (isdigit(*pc)){
  while(isdigit(*pc)){
    pc++;
  }
}

Persönlich schreibe ich immer Lexer mit letzterem, weil es meiner Meinung nach nicht weniger klar ist und es nichts schnelleres gibt.

Lexer sind Finite-State-Maschinen. Daher können sie von jeder allgemeinen FSM-Bibliothek erstellt werden. Für meine eigene Ausbildung habe ich jedoch meine eigene mit Ausdrucksvorlagen geschrieben. Hier ist mein Lexer:

static const std::unordered_map<Unicode::String, Wide::Lexer::TokenType> reserved_words(
    []() -> std::unordered_map<Unicode::String, Wide::Lexer::TokenType>
    {
        // Maps reserved words to TokenType enumerated values
        std::unordered_map<Unicode::String, Wide::Lexer::TokenType> result;

        // RESERVED WORD
        result[L"dynamic_cast"] = Wide::Lexer::TokenType::DynamicCast;
        result[L"for"] = Wide::Lexer::TokenType::For;
        result[L"while"] = Wide::Lexer::TokenType::While;
        result[L"do"] = Wide::Lexer::TokenType::Do;
        result[L"continue"] = Wide::Lexer::TokenType::Continue;
        result[L"auto"] = Wide::Lexer::TokenType::Auto;
        result[L"break"] = Wide::Lexer::TokenType::Break;
        result[L"type"] = Wide::Lexer::TokenType::Type;
        result[L"switch"] = Wide::Lexer::TokenType::Switch;
        result[L"case"] = Wide::Lexer::TokenType::Case;
        result[L"default"] = Wide::Lexer::TokenType::Default;
        result[L"try"] = Wide::Lexer::TokenType::Try;
        result[L"catch"] = Wide::Lexer::TokenType::Catch;
        result[L"return"] = Wide::Lexer::TokenType::Return;
        result[L"static"] = Wide::Lexer::TokenType::Static;
        result[L"if"] = Wide::Lexer::TokenType::If;
        result[L"else"] = Wide::Lexer::TokenType::Else;
        result[L"decltype"] = Wide::Lexer::TokenType::Decltype;
        result[L"partial"] = Wide::Lexer::TokenType::Partial;
        result[L"using"] = Wide::Lexer::TokenType::Using;
        result[L"true"] = Wide::Lexer::TokenType::True;
        result[L"false"] = Wide::Lexer::TokenType::False;
        result[L"null"] = Wide::Lexer::TokenType::Null;
        result[L"int"] = Wide::Lexer::TokenType::Int;
        result[L"long"] = Wide::Lexer::TokenType::Long;
        result[L"short"] = Wide::Lexer::TokenType::Short;
        result[L"module"] = Wide::Lexer::TokenType::Module;
        result[L"dynamic"] = Wide::Lexer::TokenType::Dynamic;
        result[L"reinterpret_cast"] = Wide::Lexer::TokenType::ReinterpretCast;
        result[L"static_cast"] = Wide::Lexer::TokenType::StaticCast;
        result[L"enum"] = Wide::Lexer::TokenType::Enum;
        result[L"operator"] = Wide::Lexer::TokenType::Operator;
        result[L"throw"] = Wide::Lexer::TokenType::Throw;
        result[L"public"] = Wide::Lexer::TokenType::Public;
        result[L"private"] = Wide::Lexer::TokenType::Private;
        result[L"protected"] = Wide::Lexer::TokenType::Protected;
        result[L"friend"] = Wide::Lexer::TokenType::Friend;
        result[L"this"] = Wide::Lexer::TokenType::This;

        return result;
    }()
);

std::vector<Wide::Lexer::Token*> Lexer::Context::operator()(Unicode::String* filename, Memory::Arena& arena) {

    Wide::IO::TextInputFileOpenArguments args;
    args.encoding = Wide::IO::Encoding::UTF16;
    args.mode = Wide::IO::OpenMode::OpenExisting;
    args.path = *filename;

    auto str = arena.Allocate<Unicode::String>(args().AsString());
    const wchar_t* begin = str->c_str();
    const wchar_t* end = str->c_str() + str->size();

    int line = 1;
    int column = 1;

    std::vector<Token*> tokens;

    // Some variables we'll need for semantic actions
    Wide::Lexer::TokenType type;

    auto multi_line_comment 
        =  MakeEquality(L'/')
        >> MakeEquality(L'*')
        >> *( !(MakeEquality(L'*') >> MakeEquality(L'/')) >> eps)
        >> eps >> eps;

    auto single_line_comment
        =  MakeEquality(L'/')
        >> MakeEquality(L'/')
        >> *( !MakeEquality(L'\n') >> eps);

    auto punctuation
        =  MakeEquality(L',')[[&]{ type = Wide::Lexer::TokenType::Comma; }]
        || MakeEquality(L';')[[&]{ type = Wide::Lexer::TokenType::Semicolon; }]
        || MakeEquality(L'~')[[&]{ type = Wide::Lexer::TokenType::BinaryNOT; }]
        || MakeEquality(L'(')[[&]{ type = Wide::Lexer::TokenType::OpenBracket; }]
        || MakeEquality(L')')[[&]{ type = Wide::Lexer::TokenType::CloseBracket; }]
        || MakeEquality(L'[')[[&]{ type = Wide::Lexer::TokenType::OpenSquareBracket; }]
        || MakeEquality(L']')[[&]{ type = Wide::Lexer::TokenType::CloseSquareBracket; }]
        || MakeEquality(L'{')[[&]{ type = Wide::Lexer::TokenType::OpenCurlyBracket; }]
        || MakeEquality(L'}')[[&]{ type = Wide::Lexer::TokenType::CloseCurlyBracket; }]

        || MakeEquality(L'>') >> (
               MakeEquality(L'>') >> (
                   MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::RightShiftEquals; }]
                || opt[[&]{ type = Wide::Lexer::TokenType::RightShift; }]) 
            || MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::GreaterThanOrEqualTo; }]
            || opt[[&]{ type = Wide::Lexer::TokenType::GreaterThan; }])
        || MakeEquality(L'<') >> (
               MakeEquality(L'<') >> (
                      MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::LeftShiftEquals; }]
                   || opt[[&]{ type = Wide::Lexer::TokenType::LeftShift; }] ) 
            || MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::LessThanOrEqualTo; }] 
            || opt[[&]{ type = Wide::Lexer::TokenType::LessThan; }])

        || MakeEquality(L'-') >> (
               MakeEquality(L'-')[[&]{ type = Wide::Lexer::TokenType::Decrement; }]
            || MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::MinusEquals; }]
            || MakeEquality(L'>')[[&]{ type = Wide::Lexer::TokenType::PointerAccess; }]
            || opt[[&]{ type = Wide::Lexer::TokenType::Minus; }])

        || MakeEquality(L'.')
            >> (MakeEquality(L'.') >> MakeEquality(L'.')[[&]{ type = Wide::Lexer::TokenType::Ellipsis; }] 
            || opt[[&]{ type = Wide::Lexer::TokenType::Dot; }])

        || MakeEquality(L'+') >> (  
               MakeEquality(L'+')[[&]{ type = Wide::Lexer::TokenType::Increment; }] 
            || MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::PlusEquals; }]
            || opt[[&]{ type = Wide::Lexer::TokenType::Plus; }])
        || MakeEquality(L'&') >> (
               MakeEquality(L'&')[[&]{ type = Wide::Lexer::TokenType::LogicalAnd; }]
            || MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::BinaryANDEquals; }] 
            || opt[[&]{ type = Wide::Lexer::TokenType::BinaryAND; }])
        || MakeEquality(L'|') >> (
               MakeEquality(L'|')[[&]{ type = Wide::Lexer::TokenType::LogicalOr; }]
            || MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::BinaryOREquals; }]
            || opt[[&]{ type = Wide::Lexer::TokenType::BinaryOR; }])

        || MakeEquality(L'*') >> (MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::MulEquals; }] 
            || opt[[&]{ type = Wide::Lexer::TokenType::Multiply; }])
        || MakeEquality(L'%') >> (MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::ModulusEquals; }] 
            || opt[[&]{ type = Wide::Lexer::TokenType::Modulus; }])
        || MakeEquality(L'=') >> (MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::EqualTo; }] 
            || opt[[&]{ type = Wide::Lexer::TokenType::Assignment; }])
        || MakeEquality(L'!') >> (MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::NotEquals; }] 
            || opt[[&]{ type = Wide::Lexer::TokenType::LogicalNOT; }])
        || MakeEquality(L'/') >> (MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::DivEquals; }] 
            || opt[[&]{ type = Wide::Lexer::TokenType::Divide; }])
        || MakeEquality(L'^') >> (MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::BinaryXOREquals; }] 
            || opt[[&]{ type = Wide::Lexer::TokenType::BinaryXOR; }])
        || MakeEquality(L':') >> (MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::VarAssign; }] 
            || opt[[&]{ type = Wide::Lexer::TokenType::Colon; }]);

    auto string
        =  L'"' >> *( L'\\' >> MakeEquality(L'"') >> eps || !MakeEquality(L'"') >> eps) >> eps;

    auto character
        =  L'\'' >> *( L'\\' >> MakeEquality(L'\'') >> eps || !MakeEquality(L'\'') >> eps);

    auto digit
        =  MakeRange(L'0', L'9');

    auto letter
        =  MakeRange(L'a', L'z') || MakeRange(L'A', L'Z');

    auto number
        =  +digit >> ((L'.' >> +digit) || opt);

    auto new_line
        = MakeEquality(L'\n')[ [&] { line++; column = 0; } ];

    auto whitespace
        =  MakeEquality(L' ')
        || L'\t'
        || new_line
        || L'\n'
        || L'\r'
        || multi_line_comment
        || single_line_comment;

    auto identifier 
        =  (letter || L'_') >> *(letter || digit || (L'_'));
        //=  *( !(punctuation || string || character || whitespace) >> eps );

    bool skip = false;

    auto lexer 
        =  whitespace[ [&]{ skip = true; } ] // Do not produce a token for whitespace or comments. Just continue on.
        || punctuation[ [&]{ skip = false; } ] // Type set by individual punctuation
        || string[ [&]{ skip = false; type = Wide::Lexer::TokenType::String; } ]
        || character[ [&]{ skip = false; type = Wide::Lexer::TokenType::Character; } ]
        || number[ [&]{ skip = false; type = Wide::Lexer::TokenType::Number; } ]
        || identifier[ [&]{ skip = false; type = Wide::Lexer::TokenType::Identifier; } ];

    auto current = begin;
    while(current != end) {
        if (!lexer(current, end)) {
            throw std::runtime_error("Failed to lex input.");
        }
        column += (current - begin);
        if (skip) {
            begin = current;
            continue;
        }
        Token t(begin, current);
        t.columnbegin = column - (current - begin);
        t.columnend = column;
        t.file = filename;
        t.line = line;
        if (type == Wide::Lexer::TokenType::Identifier) { // check for reserved word
            if (reserved_words.find(t.Codepoints()) != reserved_words.end())
                t.type = reserved_words.find(t.Codepoints())->second;
            else
                t.type = Wide::Lexer::TokenType::Identifier;
        } else {
            t.type = type;
        }
        begin = current;
        tokens.push_back(arena.Allocate<Token>(t));
    }
    return tokens;
}

Es wird durch eine iteratorbasierte Back-Tracking-Bibliothek für endliche Zustandsmaschinen mit einer Länge von ca. 400 Zeilen unterstützt. Es ist jedoch leicht einzusehen, dass ich nur einfache boolesche Operationen wie and, orund notund ein paar regex-artige Operatoren wie *für null oder mehr erstellen musste , epsum "irgendetwas stimmen" und "stimmen" optzu bedeuten alles andere als nicht verbrauchen ". Die Bibliothek ist vollständig generisch und basiert auf Iteratoren. Das MakeEquality-Zeug ist ein einfacher Test für die Gleichheit zwischen *itund dem übergebenen Wert, und MakeRange ist ein einfacher <= >=Test.

Schließlich plane ich, vom Backtracking zum Predictive überzugehen.

Zunächst einmal geht es hier um verschiedene Dinge:

• Aufteilen der Liste der bloßen Zeichen in Token
• Erkennen dieser Token (Identifizieren von Schlüsselwörtern, Literalen, Klammern usw.)
• Überprüfung einer allgemeinen Grammatikstruktur

Im Allgemeinen erwarten wir, dass ein Lexer alle drei Schritte auf einmal ausführt. Letzteres ist jedoch von Natur aus schwieriger und es gibt einige Probleme mit der Automatisierung (dazu später mehr).

Das erstaunlichste Lexer, das ich kenne, ist Boost.Spirit.Qi . Es verwendet Ausdrucksvorlagen, um Ihre Lexer-Ausdrücke zu generieren, und sobald es an seine Syntax gewöhnt ist, fühlt sich der Code wirklich ordentlich an. Es wird jedoch sehr langsam kompiliert (umfangreiche Vorlagen). Es ist daher am besten, die verschiedenen Teile in dedizierten Dateien zu isolieren, um zu vermeiden, dass sie erneut kompiliert werden, wenn sie nicht berührt wurden.

Es gibt einige Fallstricke bei der Leistung, und der Autor des Epochen-Compilers erklärt, wie er durch intensive Profilerstellung und Untersuchung der Funktionsweise von Qi in einem Artikel eine 1000-fache Geschwindigkeit erzielt hat .

Schließlich wird auch Code von externen Tools (Yacc, Bison, ...) generiert.

Aber ich versprach eine Zusammenfassung dessen, was mit der Automatisierung der Grammatiküberprüfung nicht stimmte.

Wenn Sie beispielsweise Clang auschecken, werden Sie feststellen, dass anstelle eines generierten Parsers und so etwas wie Boost.Spirit die Grammatik manuell mit einer generischen Descent Parsing-Technik validiert werden soll. Das scheint doch rückständig zu sein?

In der Tat gibt es einen sehr einfachen Grund: Fehlerbehebung .

Das typische Beispiel in C ++:

struct Immediate { } instanceOfImmediate;

struct Foo {}

void bar() {
}

Beachten Sie den Fehler? Ein fehlendes Semikolon direkt nach der Deklaration von Foo.

Es ist ein häufiger Fehler, und Clang erholt sich ordentlich, indem er erkennt, dass er einfach fehlt und voidnicht nur ein Beispiel, Foosondern ein Teil der nächsten Deklaration ist. Dies vermeidet schwer zu diagnostizierende kryptische Fehlermeldungen.

Die meisten automatisierten Tools haben keine (zumindest offensichtlichen) Möglichkeiten, diese wahrscheinlichen Fehler zu spezifizieren und zu beheben. Oft erfordert die Wiederherstellung ein wenig syntaktische Analyse, so dass dies alles andere als offensichtlich ist.

Daher ist die Verwendung eines automatisierten Tools mit einem Kompromiss verbunden: Sie erhalten Ihren Parser schnell, aber er ist weniger benutzerfreundlich.

Da Sie lernen möchten, wie Lexer funktionieren, möchten Sie vermutlich wissen, wie Lexer-Generatoren funktionieren.

Ein Lexer-Generator verwendet eine lexikalische Spezifikation, bei der es sich um eine Liste von Regeln (Token-Paare aus regulären Ausdrücken) handelt, und generiert einen Lexer. Dieser resultierende Lexer kann dann eine Eingabe- (Zeichen-) Zeichenfolge gemäß dieser Liste von Regeln in eine Token-Zeichenfolge umwandeln.

Die am häufigsten verwendete Methode besteht hauptsächlich darin, einen regulären Ausdruck über einen nicht deterministischen Automaten (NFA) und einige Details in einen deterministischen endlichen Automaten (DFA) umzuwandeln.

Eine ausführliche Anleitung zur Durchführung dieser Transformation finden Sie hier . Beachten Sie, dass ich es nicht selbst gelesen habe, aber es sieht ganz gut aus. Außerdem wird in den ersten Kapiteln so gut wie jedes Buch zum Thema Compilerkonstruktion diese Transformation enthalten.

Wenn Sie sich für Vorlesungsfolien von Lehrveranstaltungen zum Thema interessieren, gibt es zweifellos unendlich viele von ihnen aus Lehrveranstaltungen zur Compilerkonstruktion. An meiner Universität finden Sie solche Folien hier und hier .

Es gibt noch einige Dinge, die normalerweise nicht in Lexern verwendet oder in Texten behandelt werden, die aber dennoch sehr nützlich sind:

Erstens ist der Umgang mit Unicode nicht ganz einfach. Das Problem ist, dass die ASCII-Eingabe nur 8 Bit breit ist. Dies bedeutet, dass Sie problemlos eine Übergangstabelle für jeden Status im DFA erstellen können, da sie nur 256 Einträge enthält. Da Unicode jedoch 16 Bit breit ist (wenn Sie UTF-16 verwenden), sind für jeden Eintrag im DFA 64-KB-Tabellen erforderlich. Wenn Sie komplexe Grammatiken haben, kann dies sehr viel Platz in Anspruch nehmen. Das Befüllen dieser Tische nimmt ebenfalls viel Zeit in Anspruch.

Alternativ können Sie Intervallbäume generieren. Ein Bereichsbaum kann beispielsweise die Tupel ('a', 'z'), ('A', 'Z') enthalten. Dies ist viel speichereffizienter als die vollständige Tabelle. Wenn Sie nicht überlappende Intervalle beibehalten, können Sie für diesen Zweck einen beliebigen ausgeglichenen Binärbaum verwenden. Die Laufzeit ist linear in der Anzahl der Bits, die Sie für jedes Zeichen benötigen, also O (16) im Unicode-Fall. Im besten Fall wird es jedoch in der Regel einiges weniger sein.

Ein weiteres Problem ist, dass die Lexer, wie sie üblicherweise erzeugt werden, tatsächlich eine quadratische Leistung im ungünstigsten Fall haben. Obwohl dieses Verhalten im schlimmsten Fall nicht häufig vorkommt, kann es Sie beißen. Wenn Sie in das Problem laufen und es lösen wollen, ein Papier beschreibt , wie die lineare Zeit zu erreichen , kann gefunden werden hier .

Möglicherweise möchten Sie reguläre Ausdrücke so beschreiben können, wie sie normalerweise angezeigt werden. Das Parsen dieser Beschreibungen regulärer Ausdrücke in NFAs (oder möglicherweise zuerst in eine rekursive Zwischenstruktur) ist jedoch ein kleines Henne-Ei-Problem. Zum Parsen von Beschreibungen regulärer Ausdrücke ist der Shunting Yard-Algorithmus sehr gut geeignet. Wikipedia scheint eine umfangreiche Seite über den Algorithmus zu haben .