Pisanie leksera w C ++

18

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.

po prawej stronie
źródło
Ok, dlaczego lex nie jest dobry dla twojego celu?
CarneyCode
13
Chcę się dowiedzieć, jak działają leksykon. Nie mogę tego zrobić z generatorem leksykalnym.
prawej
11
Lex generuje obrzydliwy kod C. Każdy, kto chce porządnego leksera, nie używa Lexa.
DeadMG
5
@Giorgio: Wygenerowany kod to kod, z którym musisz się komunikować, na przykład z obrzydliwymi zmiennymi globalnymi, które nie są bezpieczne dla wątków, i kod, którego błędy zakończenia NULL wprowadzasz do swojej aplikacji.
DeadMG
1
@Giorgio: Czy kiedykolwiek musiałeś debugować kod wyjściowy Lexa?
mattnz

Odpowiedzi:

7

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.

Mike Dunlavey
źródło
Myślę, że jeśli wyrażenie regularne staje się bardzo złożone, to również odpowiedni kod. Dlatego generator lexerów jest dobry: normalnie sam kodowałbym lexer, jeśli język jest bardzo prosty.
Giorgio
1
@Giorgio: Może to kwestia gustu, ale w ten sposób zbudowałem wiele parserów. Lexer nie musi obsługiwać niczego poza liczbami, interpunkcją, słowami kluczowymi, identyfikatorami, stałymi ciągów, białymi spacjami i komentarzami.
Mike Dunlavey
Nigdy nie napisałem złożonego analizatora składni, a wszystkie leksery i analizatory składni, które napisałem, były również kodowane ręcznie. Zastanawiam się tylko, jak to się skaluje w przypadku bardziej złożonych języków regularnych: nigdy tego nie próbowałem, ale wyobrażam sobie, że użycie generatora (takiego jak lex) byłoby bardziej kompaktowe. Przyznaję, że nie mam doświadczenia z leksykonem lub innymi generatorami poza niektórymi przykładami zabawek.
Giorgio
1
Do łańcucha dołączasz ciąg *pc, prawda? Jak while(isdigit(*pc)) { value += pc; pc++; }. Następnie po }przekształceniu wartości na liczbę i przypisaniu jej do tokena.
prawej
@WTP: Dla liczb po prostu obliczam je w locie, podobnie jak n = n * 10 + (*pc++ - '0');. Robi się nieco bardziej skomplikowany dla zapisu zmiennoprzecinkowego i „e”, ale nie jest źle. Jestem pewien, że mógłbym zapisać trochę kodu, umieszczając znaki w buforze i wywołując atoflub cokolwiek innego. Nie będzie działać szybciej.
Mike Dunlavey
9

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.

DeadMG
źródło
2
Widziałem kilka leksykonów, które po prostu czytają następny token na żądanie parsera, aby to zrobić. Twój wydaje się przeglądać cały plik i tworzyć listę tokenów. Czy ta metoda ma jakąś szczególną zaletę?
user673679,
2
@DeadMG: Chcesz udostępnić MakeEqualityfragment kodu ? W szczególności obiekt zwrócony przez tę funkcję. Wygląda bardzo interesująco.
Deathicon
3

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.

Matthieu M.
źródło
3

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 .

Alex ten Brink
źródło