Pisanie leksera w C ++

Jakie są dobre zasoby na temat pisania lekcji w C ++ (książki, samouczki, dokumenty), jakie są dobre techniki i praktyki?

Szukałem w Internecie i wszyscy mówią, aby używać generatora leksykalnego, takiego jak Lex. Nie chcę tego robić, chcę ręcznie napisać leksykon.

Należy pamiętać, że każda skończona maszyna stanu odpowiada wyrażeniu regularnemu, które odpowiada programowi strukturalnemu używającemu ifi whileinstrukcji.

Na przykład, aby rozpoznać liczby całkowite, możesz mieć maszynę stanu:

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

lub wyrażenie regularne:

digit digit*

lub kod strukturalny:

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

Osobiście zawsze piszę leksykon przy użyciu tego drugiego, ponieważ IMHO jest nie mniej jasne i nie ma nic szybszego.

Lexery to skończone maszyny stanowe. Dlatego mogą być konstruowane przez dowolną bibliotekę FSM ogólnego przeznaczenia. Jednak dla własnej edukacji napisałem własną, używając szablonów wyrażeń. Oto mój leksykon:

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;
}

Jest on wspierany przez iteratorową, skończoną bibliotekę maszyn skończonych o śledzeniu wstecznym, która ma długość ~ 400 linii. Jednak, to łatwo zauważyć, że wszystko, co musiałem zrobić, to konstrukt proste operacje logiczne, jak and, ori not, i kilku operatorów regex stylu jak *na zero lub-więcej, epsoznacza „match niczego” i optoznacza „meczu cokolwiek, ale go nie konsumuj ". Biblioteka jest w pełni ogólna i oparta na iteratorach. MakeEquality to prosty test na równość *iti przekazywaną wartość, a MakeRange jest prosty<= >= test.

W końcu planuję przejść od powrotu do przewidywania.

Przede wszystkim dzieją się tutaj różne rzeczy:

• dzielenie listy nagich postaci na tokeny
• rozpoznawanie tych tokenów (identyfikacja słów kluczowych, literałów, nawiasów, ...)
• weryfikacja ogólnej struktury gramatycznej

Ogólnie rzecz biorąc, oczekujemy, że leksykon wykona wszystkie 3 kroki za jednym razem, jednak ten ostatni jest z natury trudniejszy i istnieją pewne problemy z automatyzacją (więcej na ten temat później).

Najbardziej niesamowitym lekserem, jakiego znam, jest Boost.Spirit.Qi . Używa szablonów wyrażeń do generowania wyrażeń leksykalnych, a po przyzwyczajeniu się do składni kod wydaje się naprawdę fajny. Kompiluje się jednak bardzo powoli (ciężkie szablony), dlatego najlepiej jest izolować różne części w dedykowanych plikach, aby uniknąć ich ponownej kompilacji, gdy nie zostały dotknięte.

Występują pewne pułapki w wydajności, a autor kompilatora Epoch wyjaśnia, w jaki sposób uzyskał przyspieszenie 1000x poprzez intensywne profilowanie i badanie działania Qi w artykule .

Na koniec generowany jest również kod przez narzędzia zewnętrzne (Yacc, Bison, ...).

Ale obiecałem napisać o tym, co było nie tak z automatyzacją weryfikacji gramatycznej.

Jeśli na przykład sprawdzisz Clanga, zdasz sobie sprawę, że zamiast używać wygenerowanego parsera i czegoś takiego jak Boost.Spirit, zamiast tego postanowili ręcznie zweryfikować gramatykę za pomocą ogólnej techniki analizy zstępującej. Z pewnością wydaje się to zacofane?

W rzeczywistości istnieje bardzo prosty powód: odzyskiwanie po błędzie .

Typowy przykład w C ++:

struct Immediate { } instanceOfImmediate;

struct Foo {}

void bar() {
}

Zauważ błąd? Brakujący średnik bezpośrednio po deklaracji Foo.

Jest to częsty błąd, a Clang odzyskuje sprawnie, uświadamiając sobie, że po prostu go brakuje i voidnie jest przykładem, Fooale częścią kolejnej deklaracji. Pozwala to uniknąć trudnych do zdiagnozowania komunikatów o błędach.

Większość zautomatyzowanych narzędzi nie ma (przynajmniej oczywistych) sposobów określania tych prawdopodobnych błędów i sposobu ich naprawienia. Często odzyskiwanie wymaga niewielkiej analizy składniowej, więc nie jest to oczywiste.

Korzystanie z zautomatyzowanego narzędzia wiąże się z kompromisem: szybko otrzymujesz parser, ale jest on mniej przyjazny dla użytkownika.

Ponieważ chcesz dowiedzieć się, jak działają leksykony, zakładam, że tak naprawdę chcesz wiedzieć, jak działają generatory leksykalne.

Generator leksykalny pobiera specyfikację leksykalną, która jest listą reguł (pary wyrażenia regularnego-token), i generuje leksyk. Ten wynikowy leksyk może następnie przekształcić łańcuch wejściowy (znakowy) w łańcuch tokena zgodnie z tą listą reguł.

Najczęściej stosowana metoda polega głównie na przekształceniu wyrażenia regularnego w deterministyczne automaty skończone (DFA) za pomocą niedeterministycznych automatów (NFA) oraz kilku szczegółów.

Szczegółowy przewodnik wykonywania tej transformacji można znaleźć tutaj . Pamiętaj, że sam tego nie przeczytałem, ale wygląda całkiem dobrze. Ponadto, prawie każda książka o budowie kompilatora będzie zawierała tę transformację w kilku pierwszych rozdziałach.

Jeśli interesują Cię wykłady z wykładów na ten temat, bez wątpienia jest ich nieskończona ilość z kursów na temat budowy kompilatora. Z mojej uczelni możesz znaleźć takie slajdy tutaj i tutaj .

Jest jeszcze kilka rzeczy, które nie są powszechnie używane w leksykach lub traktowane w tekstach, ale mimo to są całkiem przydatne:

Po pierwsze, obsługa Unicode nie jest łatwa. Problem polega na tym, że wejście ASCII ma tylko 8 bitów szerokości, co oznacza, że ​​możesz łatwo mieć tabelę przejścia dla każdego stanu w DFA, ponieważ mają one tylko 256 wpisów. Jednak Unicode, mający szerokość 16 bitów (jeśli używasz UTF-16), wymaga 64k tabel dla każdego wpisu w DFA. Jeśli masz złożoną gramatykę, może to zająć sporo miejsca. Wypełnianie tych tabel również zajmuje sporo czasu.

Alternatywnie możesz wygenerować drzewa interwałów. Drzewo zakresu może zawierać na przykład krotki („a”, „z”), („A”, „Z”), co jest o wiele bardziej wydajne pod względem pamięci niż posiadanie pełnej tabeli. Jeśli zachowasz nie nakładające się interwały, możesz w tym celu użyć dowolnego zbalansowanego drzewa binarnego. Czas działania jest liniowy w liczbie bitów potrzebnej dla każdego znaku, więc O (16) w przypadku Unicode. Jednak w najlepszym przypadku zwykle będzie to nieco mniej.

Kolejną kwestią jest to, że tak często generowane leksykony mają w najgorszym przypadku kwadratową wydajność. Chociaż to najgorsze zachowanie nie jest często spotykane, może cię ugryźć. Jeśli napotkasz problem i chcesz go rozwiązać, możesz znaleźć tutaj artykuł opisujący, jak osiągnąć czas liniowy .

Prawdopodobnie będziesz chciał móc opisywać wyrażenia regularne w postaci ciągów, tak jak zwykle się pojawiają. Jednak parsowanie tych opisów wyrażeń regularnych na NFA (lub prawdopodobnie najpierw rekurencyjną strukturę pośrednią) jest trochę problemem z jajkiem kurzym. Do analizowania opisów wyrażeń regularnych bardzo odpowiedni jest algorytm Shunting Yard. Wydaje się, że Wikipedia ma obszerną stronę dotyczącą algorytmu .