it-swarm-eu.dev

Schreiben eines Lexers in C ++

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

Ich habe im Internet nachgesehen und jeder sagt, er solle einen Lexer-Generator wie Lex verwenden. Ich möchte das nicht tun, ich möchte einen Lexer von Hand schreiben.

19
rightfold

Beachten Sie, dass jede endliche Zustandsmaschine einem regulären Ausdruck entspricht, der einem strukturierten Programm mit den Anweisungen if und while entspricht.

Um beispielsweise Ganzzahlen zu erkennen, können Sie die Zustandsmaschine verwenden:

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.

7
Mike Dunlavey

Lexer sind endliche Zustandsmaschinen. Daher können sie von jeder Allzweck-FSM-Bibliothek erstellt werden. Für meine eigene Ausbildung habe ich jedoch meine eigenen 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 von einer iteratorbasierten, rückverfolgbaren Finite-State-Machine-Bibliothek mit einer Länge von ca. 400 Zeilen unterstützt. Es ist jedoch leicht zu erkennen, dass ich nur einfache boolesche Operationen wie and, or und not sowie einige Operatoren im Regex-Stil erstellen musste * für null oder mehr bedeutet eps "alles abgleichen" und opt "alles abgleichen, aber nicht verbrauchen". Die Bibliothek ist vollständig generisch und basiert auf Iteratoren. Das MakeEquality-Zeug ist ein einfacher Test für die Gleichheit zwischen *it und der übergebene Wert, und MakeRange ist ein einfaches <= >= Prüfung.

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

9
DeadMG

Zunächst einmal gibt es hier verschiedene Dinge:

  • aufteilen der Liste der bloßen Zeichen in Token
  • erkennen dieser Token (Identifizieren von Schlüsselwörtern, Literalen, Klammern, ...)
  • ü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).

Der erstaunlichste Lexer, den 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 (schwere Vorlagen), daher ist es am besten, die verschiedenen Teile in dedizierten Dateien zu isolieren, um zu vermeiden, dass sie neu kompiliert werden, wenn sie nicht berührt wurden.

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

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


Aber ich versprach einen Bericht darüber, was mit der Automatisierung der Grammatikverifizierung nicht stimmte.

Wenn Sie beispielsweise Clang auschecken, werden Sie feststellen, dass anstelle eines generierten Parsers und so etwas wie Boost.Spirit die Grammatik manuell mithilfe einer generischen Descent Parsing-Technik überprüft werden soll. Sicher scheint das rückwärts 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 void keine Instanz von Foo ist, sondern Teil der nächsten Deklaration. Dies vermeidet schwer zu diagnostizierende kryptische Fehlermeldungen.

Die meisten automatisierten Tools haben keine (zumindest offensichtlichen) Möglichkeiten, diese wahrscheinlichen Fehler anzugeben und wie sie behoben werden können. Oft erfordert die Wiederherstellung eine kleine syntaktische Analyse, so dass dies alles andere als offensichtlich ist.


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

3
Matthieu M.

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 handelt (Token-Paare mit regulären Ausdrücken), und generiert einen Lexer. Dieser resultierende Lexer kann dann eine Eingabezeichenfolge (Zeichenfolge) gemäß dieser Liste von Regeln in eine Tokenzeichenfolge umwandeln.

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

Eine ausführliche Anleitung zur Durchführung dieser Transformation finden Sie hier . Beachten Sie, dass ich es selbst nicht gelesen habe, aber es sieht ziemlich gut aus. In nahezu jedem Buch zur Compilerkonstruktion wird diese Transformation in den ersten Kapiteln vorgestellt.

Wenn Sie an Vorlesungsfolien von Kursen zu diesem Thema interessiert sind, gibt es zweifellos unendlich viele davon aus Kursen über Compilerkonstruktion. An meiner Universität finden Sie solche Folien hier und hier .

Es gibt nur noch wenige Dinge, die in Lexern nicht häufig verwendet oder in Texten behandelt werden, aber dennoch sehr nützlich sind:

Erstens ist der Umgang mit Unicode nicht trivial. Das Problem ist, dass ASCII Eingabe nur 8 Bit breit ist, was bedeutet, dass Sie leicht eine Übergangstabelle für jeden Zustand im DFA haben können, da sie nur 256 Einträge haben. Allerdings ist Unicode 16 Bit breit (wenn Sie UTF-16 verwenden), erfordert 64.000 Tabellen für jeden Eintrag im DFA. Wenn Sie komplexe Grammatiken haben, nimmt dies möglicherweise viel Platz in Anspruch. Das Ausfüllen dieser Tabellen nimmt auch einige Zeit in Anspruch.

Alternativ können Sie Intervallbäume generieren. Ein Bereichsbaum kann beispielsweise die Tupel ('a', 'z'), ('A', 'Z') enthalten, was viel speichereffizienter ist als die vollständige Tabelle. Wenn Sie nicht überlappende Intervalle beibehalten, können Sie zu diesem 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 ist sie jedoch normalerweise etwas geringer .

Ein weiteres Problem ist, dass die üblicherweise erzeugten Lexer tatsächlich eine quadratische Leistung im ungünstigsten Fall aufweisen. Obwohl dieses Worst-Case-Verhalten nicht häufig auftritt, kann es Sie beißen. Wenn Sie auf das Problem stoßen und es lösen möchten, finden Sie ein Dokument, in dem beschrieben wird, wie eine lineare Zeit erreicht wird hier .

Möglicherweise möchten Sie reguläre Ausdrücke in Zeichenfolgenform 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 bisschen ein Hühnerei-Problem. Zum Analysieren von Beschreibungen regulärer Ausdrücke ist der Shunting Yard-Algorithmus sehr gut geeignet. Wikipedia scheint eine umfangreiche Seite über den Algorithmus zu haben.

3
Alex ten Brink