Escribir un lexer en C ++

¿Cuáles son buenos recursos sobre cómo escribir un lexer en C ++ (libros, tutoriales, documentos), cuáles son algunas buenas técnicas y prácticas?

He buscado en internet y todo el mundo dice que use un generador lexer como lex. No quiero hacer eso, quiero escribir un lexer a mano.

Tenga en cuenta que cada máquina de estados finitos corresponde a una expresión regular, que corresponde a un programa estructurado que usa ify whiledeclaraciones.

Entonces, por ejemplo, para reconocer enteros, podría tener la máquina de estado:

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

o la expresión regular:

digit digit*

o el código estructurado:

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

Personalmente, siempre escribo lexers usando este último, porque en mi humilde opinión, no está menos claro, y no hay nada más rápido.

Los Lexers son máquinas de estados finitos. Por lo tanto, pueden ser construidos por cualquier biblioteca FSM de propósito general. Para los fines de mi propia educación, sin embargo, escribí el mío, usando plantillas de expresión. Aquí está mi 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;
}

Está respaldado por una biblioteca de máquinas de estados finitos basada en iteradores, seguimiento posterior, que tiene ~ 400 líneas de longitud. Sin embargo, es fácil ver que todo lo que tenía que hacer era construir operaciones booleanas simples, como and, ory not, y un par de operadores de estilo regex como *cero o más, epspara significar "coincidir con cualquier cosa" y optsignificar "coincidir cualquier cosa pero no lo consumas ". La biblioteca es totalmente genérica y se basa en iteradores. El material MakeEquality es una prueba simple para la igualdad *ity el valor pasado, y MakeRange es una <= >=prueba simple .

Eventualmente, planeo pasar de retroceder a predictivo.

En primer lugar, hay diferentes cosas pasando aquí:

• dividir la lista de personajes desnudos en tokens
• reconocer esos tokens (identificar palabras clave, literales, corchetes, ...)
• verificar una estructura gramatical general

En general, esperamos que un lexer realice los 3 pasos de una vez, sin embargo, este último es inherentemente más difícil y hay algunos problemas con la automatización (más sobre esto más adelante).

El lexer más sorprendente que conozco es Boost.Spirit.Qi . Utiliza plantillas de expresión para generar sus expresiones léxicas, y una vez acostumbrado a su sintaxis, el código se siente realmente ordenado. Sin embargo, se compila muy lentamente (plantillas pesadas), por lo que es mejor aislar las diversas porciones en archivos dedicados para evitar volver a compilarlas cuando no se han tocado.

Hay algunos inconvenientes en el rendimiento, y el autor del compilador de Epoch explica cómo obtuvo una aceleración de 1000x mediante la creación de perfiles e investigación intensivos sobre cómo funciona Qi en un artículo .

Finalmente, también hay código generado por herramientas externas (Yacc, Bison, ...).

Pero prometí una reseña sobre lo que estaba mal con la automatización de la verificación gramatical.

Si echa un vistazo a Clang, por ejemplo, se dará cuenta de que en lugar de usar un analizador generado y algo como Boost.Spirit, en su lugar, se propusieron validar la gramática manualmente usando una técnica genérica de Descent Parsing. ¿Seguramente esto parece al revés?

De hecho, hay una razón muy simple: recuperación de errores .

El ejemplo típico, en C ++:

struct Immediate { } instanceOfImmediate;

struct Foo {}

void bar() {
}

¿Notaste el error? Falta un punto y coma justo después de la declaración deFoo .

Es un error común, y Clang se recupera perfectamente al darse cuenta de que simplemente falta y voidno es una instancia deFoo sino parte de la próxima declaración. Esto evita los mensajes de error crípticos difíciles de diagnosticar.

La mayoría de las herramientas automatizadas no tienen formas (al menos obvias) de especificar esos posibles errores y cómo recuperarse de ellos. A menudo, la recuperación requiere un pequeño análisis sintáctico, por lo que está lejos de ser evidente.

Por lo tanto, existe una compensación al usar una herramienta automatizada: obtienes tu analizador rápidamente, pero es menos fácil de usar.

Como quiere aprender cómo funcionan los lexers, supongo que realmente quiere saber cómo funcionan los generadores de lexer.

Un generador de lexer toma una especificación léxica, que es una lista de reglas (pares de símbolos de expresión regular) y genera un lexer. Este lexer resultante puede transformar una cadena de entrada (carácter) en una cadena de token de acuerdo con esta lista de reglas.

El método que se usa más comúnmente consiste principalmente en transformar una expresión regular en un autómata finito determinista (DFA) a través de un autómata no determinista (NFA), más algunos detalles.

Una guía detallada de hacer esta transformación se puede encontrar aquí . Tenga en cuenta que no lo he leído yo mismo, pero se ve bastante bien. Además, casi cualquier libro sobre construcción de compiladores presentará esta transformación en los primeros capítulos.

Si está interesado en diapositivas de cursos sobre el tema, no hay duda de que hay una cantidad infinita de cursos sobre la construcción de compiladores. Desde mi universidad, puedes encontrar tales diapositivas aquí y aquí .

Hay algunas cosas más que no se emplean comúnmente en lexers o que se tratan en textos, pero que son bastante útiles:

En primer lugar, manejar Unicode es algo no trivial. El problema es que la entrada ASCII tiene solo 8 bits de ancho, lo que significa que puede tener fácilmente una tabla de transición para cada estado en el DFA, porque solo tienen 256 entradas. Sin embargo, Unicode, que tiene 16 bits de ancho (si usa UTF-16), requiere tablas de 64k para cada entrada en el DFA. Si tiene gramáticas complejas, esto puede comenzar a ocupar bastante espacio. Llenar estas tablas también comienza a tomar bastante tiempo.

Alternativamente, podría generar árboles de intervalos. Un árbol de rango puede contener las tuplas ('a', 'z'), ('A', 'Z'), por ejemplo, que es mucho más eficiente en la memoria que tener la tabla completa. Si mantiene intervalos no superpuestos, puede usar cualquier árbol binario equilibrado para este propósito. El tiempo de ejecución es lineal en la cantidad de bits que necesita para cada carácter, por lo que O (16) en el caso de Unicode. Sin embargo, en el mejor de los casos, generalmente será un poco menos.

Otro problema es que los lexers, como se generan comúnmente, en realidad tienen un rendimiento cuadrático en el peor de los casos. Aunque este comportamiento en el peor de los casos no se ve comúnmente, puede morderte. Si se encuentra con el problema y quiere resolverlo, aquí puede encontrar un documento que describe cómo lograr el tiempo lineal .

Probablemente querrá poder describir expresiones regulares en forma de cadena, como normalmente aparecen. Sin embargo, analizar estas descripciones de expresiones regulares en NFA (o posiblemente una estructura intermedia recursiva primero) es un problema de huevo de gallina. Para analizar descripciones de expresiones regulares, el algoritmo Shunting Yard es muy adecuado. Wikipedia parece tener una página extensa sobre el algoritmo .